红黑树：规则、旋转与染色

这部分知识我前后看过不止一次。刚接触“红黑树：规则、旋转与染色”时，红黑树是我曾经最想跳过的一篇：规则很多、旋转和染色交织，源码里还有大量分支，看一遍几乎留不下东西。等我回头从问题本身出发，而不是从模板出发，很多原来零散的规则才慢慢连在一起。下面按我自己的理解过程展开。

红黑树是一种近似平衡的二叉搜索树。它不要求左右高度差始终不超过 1，而是用颜色规则约束任意根到叶路径，使最长路径不超过最短路径的两倍，因此查询、插入和删除保持 O(log n)。

它从哪里来

红黑树并不是先从五条颜色规则开始。Rudolf Bayer 在 1972 年研究对称二叉 B 树，Leonidas Guibas 与 Robert Sedgewick 在 1978 年用红、黑颜色描述这种平衡关系。颜色是编码工具，真正目标是在二叉表示中维持多路树的近似平衡。

五条规则

不同资料对空叶节点的表述略有差异，常见规则是：

每个节点是红色或黑色。
根节点是黑色。
所有空叶节点视为黑色。
红色节点不能有红色孩子。
从任一节点到其后代空叶节点的每条路径，黑色节点数相同。

第 4 条阻止连续红节点形成过长链，第 5 条维持“黑高”一致，两者共同给出高度上界。

设根到空叶路径上的黑节点数量为 bh。因为红节点不能连续出现，最长路径最多在每两个黑节点之间插入一个红节点，所以高度不超过 2 × bh；同时包含 bh 个黑节点的子树至少拥有指数级数量的内部节点。最终可以得到高度至多约为 2log₂(n+1)，这就是最坏操作仍为 O(log n) 的原因。

插入为什么先染红

把新节点染黑会让经过它的路径黑高立即增加，破坏第 5 条；先染红通常不改变黑高，只可能造成“红父红子”冲突，因此修复范围更局部。

插入修复主要看父节点、叔叔节点和祖父节点：

父节点黑色：无需修复。
父和叔叔都红：父、叔染黑，祖父染红，并把问题向上移动。
父红、叔黑：根据内外侧关系先旋转成直线，再旋转祖父并重新染色。

红黑树颜色规则和插入修复决策图

图：红黑规则约束树高，插入冲突通过变色和旋转局部修复

不要死背左右方向。先判断“新节点、父、祖父”是直线还是折线，再做对称操作更可靠。

插入修复分解

可以把所有情况压缩为三个问题：

父节点是否为黑？是则结束。
叔叔是否为红？是则颜色上移，把祖父当成新的待修复节点。
叔叔为黑时，当前节点与父、祖父是折线还是直线？折线先旋父变直线，直线再旋祖父并交换父祖颜色。

最后强制根为黑。左右情况完全对称，实现时可统一用 parentOf、colorOf、leftOf 和 rightOf 辅助函数处理空节点，减少 null 分支。

红黑树插入的叔红、直线和折线三类情况图

图：先判断父叔颜色，再判断新节点、父节点和祖父节点的形状

旋转前后必须保持中序顺序；染色负责恢复黑高和红色相邻限制。

旋转不是交换两个节点

左旋和右旋本质上是在保持中序顺序的前提下改变局部父子关系。以 x 左旋为例，需要依次处理：

让 y = x.right。
把 y.left 接到 x.right，并修正其父指针。
让 y 接替 x 原来在父节点或根的位置。
把 x 设置为 y.left，并令 x.parent = y。

private void rotateLeft(Node x) {
    Node y = x.right;
    x.right = y.left;
    if (y.left != nil) y.left.parent = x;

    y.parent = x.parent;
    if (x.parent == nil) root = y;
    else if (x == x.parent.left) x.parent.left = y;
    else x.parent.right = y;

    y.left = x;
    x.parent = y;
}

这里用统一的黑色哨兵 nil 代替 null，能减少修复代码中的空判断。真实实现还需维护 size、值和可能存在的增强字段。最常见错误是漏改转移子树的父指针，或旋转根时忘记更新 root。

红黑树与 2-3-4 树

可以把红色连接理解为把多个二叉节点粘合成一个多键节点，黑色连接则跨越树层。这个视角能解释染色为什么相当于多路节点的分裂或合并，也能减少对大量 case 的机械记忆。

黑节点独立对应 2-节点。
黑节点与一个红孩子可编码 3-节点。
黑节点与两个红孩子可编码 4-节点。

红连接必须朝哪一侧，在不同红黑树变体中可能有额外约束。左倾红黑树把红连接统一倾向左侧，代码更对称，但不是所有标准库实现的唯一方式。

删除为何更难

删除黑节点可能减少一条路径的黑高，需要通过兄弟节点的颜色、兄弟孩子颜色、旋转与重新染色逐级修复。生产实现必须经过大量随机序列和不变量测试，不能只覆盖几张手画示意图。

推荐验证器同时检查：

中序遍历严格有序。
根为黑色。
不存在红父红子。
每个节点到空叶的黑高一致。
节点数与容器 size 一致。

删除红节点通常不会改变黑高；删除黑节点则可能形成“额外黑色”缺口。修复会检查兄弟：红兄弟先旋转转化为黑兄弟；黑兄弟的孩子都黑时通过染色把缺口上移；若兄弟有红孩子，则根据近侄和远侄方向旋转并染色，消除缺口。

理解目标比背四个对称分支重要：始终让经过替代节点的路径补回一个黑色，同时不制造红父红子。

删除拥有两个孩子的节点时，通常先找到中序后继，把待删除位置转化为“删除至多有一个非空孩子的节点”。真正决定是否修复的是物理移除节点的原颜色，而不是用户最初指定节点的颜色。

修复黑缺口时可以围绕兄弟分成三类目标：

红兄弟：旋转和换色，把问题转换成黑兄弟情形。
黑兄弟且两个侄子都黑：兄弟染红，黑缺口向父级传播。
黑兄弟且至少一个方向合适的红侄子：一到两次旋转和换色后直接消除缺口。

实现中所有左右分支都应保持镜像关系。修改一侧逻辑后若忘记同步另一侧，是红黑树删除最隐蔽的缺陷之一。

用程序验证不变量

下面的思路返回每棵子树的黑高；发现红色相邻或左右黑高不等时立即失败：

private int verify(Node node, K min, K max) {
    if (node == nil) return 1;
    if (min != null && node.key.compareTo(min) <= 0) fail("BST 下界错误");
    if (max != null && node.key.compareTo(max) >= 0) fail("BST 上界错误");
    if (node.red && (node.left.red || node.right.red)) fail("出现连续红节点");

    int leftBlackHeight = verify(node.left, min, node.key);
    int rightBlackHeight = verify(node.right, node.key, max);
    if (leftBlackHeight != rightBlackHeight) fail("黑高不一致");
    return leftBlackHeight + (node.red ? 0 : 1);
}

验证前还要确认根为黑，验证后核对节点总数。随机测试应同时与 TreeMap 比较插入覆盖、删除返回值、查找结果和有序迭代结果；只跑几组手工 case 很难覆盖删除修复的对称组合。

工程选择

TreeMap、TreeSet 需要有序遍历、范围查询和稳定 O(log n) 时很合适。只做精确键查找时 HashMap 平均更快；只取极值时堆更直接。红黑树是有序字典的通用折中，不是所有查找问题的默认答案。

TreeMap 的键比较结果为 0 时会被视为同一个键，即使 equals 返回 false。比较器必须稳定且尽量与 equals 一致，否则 contains、覆盖和集合语义会令人困惑。键对象入树后也不应修改排序字段。

红黑树节点通常包含键、值、颜色、左右孩子和父指针，内存开销高于紧凑数组。大量小对象还会影响缓存局部性，因此在数据可批量构建且很少修改时，有序数组加二分查找可能更快。

普通红黑树也不是线程安全容器。并发写入若没有同步，旋转期间其他线程可能看到断裂的父子关系。工程上应使用已有并发容器、外部锁或不可变快照，不要因为单次操作是 O(log n) 就忽略并发语义。

常见理解误区

红黑树不是完全平衡树，也不保证任意节点左右高度只差 1。
旋转本身不会自动恢复颜色规则，必须与染色配合。
O(log n) 是增长上界，不代表红黑树在所有规模上都比 HashMap 快。
TreeMap 的顺序由比较器决定，不是由 hashCode 或插入顺序决定。
红色和黑色是维护不变量的元数据，不对应业务中的优先级或状态。

测试清单

根插入、叔叔红的颜色翻转。
LL、RR、LR、RL 插入修复。
删除红叶、黑叶、单孩子和双孩子节点。
每次操作检查 BST 顺序、根色、红邻接和黑高。
统计树高，验证不超过理论上界。
随机序列与 TreeMap 的键集合和顺序对照。