什么是红黑树？它有哪五条性质？

简化版

红黑树是一种弱平衡的自平衡二叉搜索树，每个节点被染成红色或黑色，通过五条颜色规则约束，保证从根到叶子的最长路径不超过最短路径的两倍，从而把树高控制在 O(log n)。它不像 AVL 那样严格平衡，但插入删除时的旋转调整更少，综合性能好，被 Java TreeMap、C++ map、Linux 内核等广泛使用。

详细版

红黑树的五条性质（不变式）：

每个节点非红即黑。
根节点是黑色。
每个叶子节点（NIL 空节点）是黑色。（红黑树把 null 视为黑色的哨兵叶子）
红色节点的孩子必须是黑色（即不能有两个连续的红色节点；红节点的父和子不能同时为红）。
从任一节点出发，到它下面所有叶子节点的路径，包含的黑色节点数目相同（称为「黑高」相同）。

这五条一起，保证了红黑树的「大致平衡」。其中性质 4（红不相邻）和性质 5（黑高相同） 是限制树高的关键。

完整版教学

一、红黑树的定位：平衡与效率的折中

红黑树的设计哲学是「不追求完美平衡，只要足够平衡就行」。AVL 树要求每个节点左右高度差 ≤ 1，非常严格，维护成本高；红黑树放宽了要求，只保证「最长路径 ≤ 2 倍最短路径」，用更少的旋转换取更低的维护成本。这个折中让它在「插入删除频繁」的通用场景里比 AVL 更实用。

二、逐条理解五条性质

性质 1（非红即黑）：给每个节点一个颜色属性，只占 1 bit。
性质 2（根黑）：根永远是黑色（若插入后根变红，就直接染回黑）。
性质 3（叶子 NIL 黑）：红黑树把所有 null 指针看成统一的黑色空叶子（哨兵）。这让「路径到叶子」有明确终点，方便定义黑高。真正存数据的节点都是「内部节点」。
性质 4（红节点的孩子全黑）：等价于「不能出现父子都是红」，即红色节点不能相邻。这限制了红色节点的密度。
性质 5（黑高相同）：从任意节点到其所有后代叶子的路径，黑色节点数量必须一样。这保证了各条路径长度不会差太多。

三、这些性质如何限制树高（核心）

关键推理链：

由性质 5，从根到任意叶子的每条路径黑色节点数相同，设为黑高 bh。所以每条路径至少有 bh 个节点（最短路径就是「全黑」的那条）。
由性质 4，红节点不能相邻，所以任意一条路径上红节点数不会超过黑节点数。因此最长路径（红黑交替）最多是 2·bh。
于是最长路径 ≤ 2 × 最短路径，树高 h ≤ 2·log₂(n+1)，即 O(log n)。

这就是红黑树保证 O(log n) 操作的数学基础——性质 4 和性质 5 联手锁死了「最长/最短路径比 ≤ 2」。

四、红黑树 vs 完美平衡

红黑树不是完美平衡的（左右子树高度可以相差较多），但它的高度仍是 O(log n)，只是常数比 AVL 大一点（AVL 高度 ≤ 1.44 log n，红黑树 ≤ 2 log n）。所以红黑树查找略慢于 AVL，但插入删除的调整代价更低。

五、如何维持这些性质

插入和删除会破坏某些性质（比如插入红节点可能违反性质 4，删除黑节点可能违反性质 5）。红黑树通过两种手段修复：

变色（recoloring）：改变节点颜色。
旋转（rotation）：和 AVL 一样的左旋/右旋，调整结构。

修复的目标就是「在保持 BST 有序性的前提下，恢复被破坏的红黑性质」（详见插入/删除专题）。

六、常见误区与追问

考点	正确口径
颜色	节点红或黑
根	根节点为黑
叶子 NIL	空叶子视为黑
红约束	红节点不能有红孩子
黑高	任一节点到后代 NIL 的黑节点数相同

red node -> children must be black
blackHeight(left) == blackHeight(right)
root.color = BLACK

红黑树五条性质共同服务于一个目标：用较少旋转换取 O(log n) 高度上界。

误区：NIL 叶子可以忽略不算。 红黑树性质里的叶子通常指黑色 NIL 节点，黑高计算离不开它。
误区：红黑树是严格平衡树。 它不是 AVL 那种高度差严格平衡，而是通过颜色约束保持近似平衡。
误区：红节点越少越好。 红节点允许树更灵活，减少更新时的旋转；关键是不能连续红。
追问：哪两条性质限制高度？ 红节点不能连续和黑高一致共同推出最长路径不超过最短路径两倍。
追问：为什么根要黑？ 根为黑是规范化要求，也简化插入删除后的修复收尾。
追问：红黑树和 2-3-4 树有什么关系？ 红黑树可看作 2-3-4 树的二叉表示，红链接表达多节点合并关系。

七、加强记忆

红黑树是弱平衡自平衡 BST，五条性质：①非红即黑 ②根黑 ③叶子 NIL 黑 ④红节点的孩子全黑（红不相邻） ⑤从任一节点到各叶子路径黑节点数相同（黑高相同）。性质 ④⑤ 联手保证最长路径 ≤ 2 倍最短路径、树高 O(log n)。靠变色 + 旋转维持。比 AVL 平衡更松、查找略慢，但调整更少、通用性更强。

简化版

详细版