基本信息

---

下载

文档摘要

---

红黑树面试题及答案

1.请简述红黑树的核心性质，这些性质为什么能保证树的近似平衡？

答案：

红黑树有5个核心性质，缺一不可：

每个节点要么是红色，要么是黑色；

根节点必须是黑色；

所有叶子节点（NIL节点，即空节点）都是黑色；

若一个节点是红色，则它的两个子节点必须是黑色（即“红父必带黑孩”，不存在连续的红色节点）；

从任意节点到其所有叶子节点的路径中，黑色节点的数量都相同（这个数量称为“黑高”）。

平衡保证逻辑：

假设某棵红黑树的黑高为h（根到叶子的黑色节点数），根据性质4，红色节点不能连续，所以最长路径（红黑交替）的长度不会超过2h-1（比如h=3时，最长路径是“黑