面试速答（先看这里）

**一句话结论：**在红黑树中，每个节点是红色或黑色。

60秒标准回答：

红黑树是一种自平衡的二叉查找树

在红黑树中，每个节点是红色或黑色。通过一些规则和颜色的约束，红黑树确保了从根节点到叶子节点的最长路径不会超过最短路径的两倍，因此近似于平衡。这种近似平衡保证了红黑树操作的时间复杂度在最坏情况下仍为对数级别（O(log n)），使得红黑树在各种场景中，如关联数组、优先队列等数据结构中非常有用

红黑树有以下优点

**答题顺序：**结论 → 原理/机制 → 关键流程 → 场景与取舍 → 易错点

回答主线：

**要点1：**红黑树在插入和删除操作中通过旋转和重新着色来保持上述性质，以维护树的平衡。
**要点2：**红黑树的插入操作首先按照二叉查找树的规则插入新节点，然后为了维护红黑树的性质，新插入的节点被着色为红色。
**要点3：**如此变化之后，需要将祖父节点设置为当前节点，继续插入动作，做自平衡处理。
**要点4：**如我们的例子，新节点是根节点了，那么就按照情况1，直接把他染色成黑色即可：
**要点5：**上面五种情况中，情况一和情况二比较简单，情况三、四、五看上去比较复杂。

**记忆锚点：**红黑树 → log → NIL → （O(log n)） → 旋转和重新着色的方法 → 自平衡的二叉查找树

关键取舍：

红黑树有以下优点：保证最坏情况下的性能：红黑树通过维持树的大致平衡，而不是完美平衡。
但如果细心观察，会发现这三种情况的区别在于叔叔节点的颜色：如果叔叔节点为红色，直接变色如果叔叔节点为黑色，且新节点在内测，则需要进行旋转。

易错提醒：

红色节点规则：红色节点的子节点必须是黑色的（即红色节点不能相邻）。
这条规则也被称为"红色节点不能有红色的孩子"或"红色节点必须有黑色的父节点和黑色的孩子"。

加分表达：

这种近似平衡保证了红黑树操作的时间复杂度在最坏情况下仍为对数级别（O(log n)），使得红黑树在各种场景中，如关联数组、优先队列等数据结构中非常有用。
如果新插入的节点是根节点，直接将其重新着色为黑色即可。

追问准备：

围绕「红黑树」：底层原理是什么？使用时有哪些边界和常见坑？
围绕「log」：底层原理是什么？使用时有哪些边界和常见坑？
围绕「NIL」：底层原理是什么？使用时有哪些边界和常见坑？
如果线上出现异常，你会如何定位、验证并规避？

典型回答

红黑树是一种自平衡的二叉查找树。

在红黑树中，每个节点是红色或黑色。通过一些规则和颜色的约束，红黑树确保了从根节点到叶子节点的最长路径不会超过最短路径的两倍，因此近似于平衡。这种近似平衡保证了红黑树操作的时间复杂度在最坏情况下仍为对数级别**（O(log n)），**使得红黑树在各种场景中，如关联数组、优先队列等数据结构中非常有用。

节点颜色：每个节点要么是红的，要么是黑的。
根节点：根节点总是黑色的。
红色节点规则：红色节点的子节点必须是黑色的（即红色节点不能相邻）。这条规则也被称为"红色节点不能有红色的孩子"或"红色节点必须有黑色的父节点和黑色的孩子"。
每个叶子节点（NIL节点，空节点）是黑色的：这里的叶子节点是指树末端的NIL指针，而不是树中的实际叶子节点。它们通常表示为空（null）。
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点：这个性质保证了没有任何路径能够有两倍于其他路径的长度，从而保持了树的大致平衡。

红黑树有以下优点：

保证最坏情况下的性能：红黑树通过维持树的大致平衡，而不是完美平衡。这样确保了在插入、删除和查找操作中最坏情况下的时间复杂度均为 O(log n)。这比普通的二叉搜索树（在最坏情况下可能退化为链表，时间复杂度为 O(n)）要好得多。
自平衡：每次插入或删除操作后，红黑树通过旋转和重新着色的方法自动维持平衡，无需额外的操作或维护。
数据结构简洁：节点只需要额外存储一个颜色位，因此相比于其他平衡树（如AVL树）来说，内存的额外开销较小。