红黑树：性质、旋转与插入删除修复 | 自在学

红黑树：用局部修复守住对数高度

把订单编号 10, 20, 30, 40, 50 依次插入普通二叉搜索树，得到的不是枝叶舒展的树，而是一条不断向右延伸的链。此时查找 50 要比较 5 次；数据再多一些，搜索、插入和删除都会从期待中的 $O(\log n)$ 滑向 $O(n)$ 。

红黑树解决的正是这种不确定性。它仍按二叉搜索树的规则存放键，只给每个节点增加红或黑这一位状态，再在更新后做少量重着色和旋转。我们关心的不是让每个节点左右一样高，而是让所有根到空叶路径的长度保持在可控比例内。

本节会沿着一条主线展开：先确定必须一直成立的不变量，再看插入或删除破坏了哪一条，最后用局部操作恢复它。这样学习红黑树，不需要把修复分支当成孤立口诀。

从退化搜索树到颜色约束

红黑树首先是一棵二叉搜索树。对任意节点 x，左子树中的键小于 x.key，右子树中的键大于 x.key；重复键如何处理由具体接口约定。颜色不参与键的比较，只约束树形。

为了让边界也能参与统一推理，我们把每个空孩子视为黑色的 NIL 叶子。实现时通常让整棵树共享一个哨兵对象，而不是为每个空位置分配节点。这样旋转和删除修复可以读取 NIL.color，不用在每个分支里先判断空指针。

一棵红黑树满足以下五条性质：

每个节点非红即黑。
根节点是黑色。
每个 NIL 叶子是黑色。
红节点的两个孩子都是黑色，因而不会出现相邻的两个红节点。
从任意节点出发，到它的任一后代 NIL 叶子的简单路径都包含相同数量的黑节点。

第五条中的数量叫黑高。记 bh(x) 为从 x 出发但不计 x 本身、到任一后代 NIL 的路径上的黑节点数。由于所有这类路径黑节点数相同，bh(x) 才是确定的。

红黑树五条性质与黑高示意图：黑色根节点、互不相邻的红节点、黑色 NIL 叶子，以及两条黑节点计数相同的高亮路径

颜色约束让根到各个 NIL 叶子的黑节点数量保持一致，从而把搜索树的高度限制在对数级别。

观察这些约束的分工：二叉搜索树性质负责有序，统一黑高限制不同分支不能相差任意多，红节点不相邻又限制一条路径不能靠连续红节点无限拉长。根黑本身不会改变渐进高度，但让定义和修复出口更统一。

真实数据节点的“叶节点”和表示空孩子的 NIL 不是同一个概念。性质中的叶子指 NIL。一个没有真实孩子的数据节点，仍有两个黑色 NIL 孩子。

检查一棵红黑树是否合法时，哪些现象一定构成违例？

黑高怎样推出高度上界

颜色约束有用，必须能把它转成高度的数学上界。关键中间结论是：以任意节点 x 为根的子树至少有

2^{bh(x)}-1

个内部节点。

对子树规模做归纳

当 x 是 NIL 时，bh(x)=0，内部节点数为 0，恰好等于 $2^0-1$ 。

再看一个真实节点 x。它的每个孩子的黑高至少是 $bh(x)-1$ ：如果孩子是黑色，向下时已经消耗一个黑节点；如果孩子是红色，黑高不减，规模只会更大。按归纳假设，每棵孩子子树至少包含

2^{bh(x)-1}-1

个内部节点。把左右子树和 x 本身相加：

\begin{aligned} n_x &\ge 2\left(2^{bh(x)-1}-1\right)+1 \\ &=2^{bh(x)}-1 \end{aligned}

结论成立。

从黑高走到树高

设整棵树有 $n$ 个内部节点，高度为 $h$ 。由于红节点不能相邻，任意根到 NIL 的路径上，至少一半节点是黑色，所以根的黑高满足

bh(\text{root}) \ge \frac{h}{2}

代入刚才的规模下界：

n \ge 2^{h/2}-1

移项并取以 2 为底的对数，得到

h \le 2\log_2(n+1)

这不是平均情况结论。只要五条性质成立，无论键以什么顺序到达，沿根到叶路径运行的搜索、极值、前驱和后继都不会超过 $O(\log n)$ 。

“最长路径至多是最短路径的两倍”是直观图景； $h\le 2\log_2(n+1)$ 才把路径比例变成了关于节点数的高度保证。

高度为 h 的红黑树中，根的黑高至少是 h/2，直接原因是什么？

旋转：改变形状但不改变次序

修复颜色有时只需重着色，有时必须改变局部结构。旋转就是那把只动常数个指针的工具。

设 x 的右孩子是 y，三棵挂接子树分别为 $\alpha$ 、 $\beta$ 、 $\gamma$ 。旋转前的中序关系是

\alpha < x < \beta < y < \gamma

对 x 左旋时，y 上升为局部根，x 成为 y 的左孩子，原来 y 的左子树 $\beta$ 改接为 x 的右子树。旋转后中序关系仍是同一行不等式。

左旋前后局部二叉搜索树结构对照图，展示 α、x、β、y、γ 的中序次序保持不变

左旋只改变局部树的形状：旋转前后均满足 $\alpha < x < \beta < y < \gamma$ ，因此中序次序不变。

左旋可以写成以下指针步骤。右旋把“左”和“右”镜像交换即可。

text

LEFT-ROTATE(T, x)
    y = x.right
    x.right = y.left
    if y.left != T.nil
        y.left.parent = x
    y.parent = x.parent
    让 x 原来的父节点改为指向 y
    y.left = x
    x.parent = y

旋转不自动保证红黑性质，它只保证二叉搜索树的次序不变。节点颜色是否要变、从哪一侧旋转，都由当前违例决定。因为只修改固定数量的指针，一次旋转是 $O(1)$ 。

容易漏掉的父指针

手写实现时，最常见的错误不是方向记反，而是漏掉以下连接之一： $\beta$ 的父指针、局部根与原父节点的连接、整棵树根指针。安全做法是把旋转看成“六个连接点的重接”，每次都覆盖根、父、孩子和中间子树。

对 x 左旋后，原来 y 的左子树 β 应该成为谁的哪棵子树？

插入修复：把红红冲突留在局部

插入分成两段：先按普通二叉搜索树找到位置，再把新节点 z 染红并修复。

为什么不先染黑？插入黑节点会让所有经过新节点的路径多一个黑节点，立刻破坏统一黑高；插入红节点不改变任何路径的黑节点数，只可能产生两种局部问题：新节点是红色根，或者它的父节点也是红色。

修复循环始终盯住四个角色：问题节点 z、父节点 p、祖父节点 g 和叔叔节点 u。只要父节点是黑色，红红冲突就不存在；循环结束后再把根染黑。

以下假设 p 是 g 的左孩子。若 p 在右侧，所有方向镜像交换。

红黑树插入修复三种局部情形：叔叔为红时重新着色并上移冲突，内侧折线先对父左旋，外侧直线染色后对祖父右旋恢复

插入修复把红红冲突限制在局部：先判断叔叔颜色，再通过重新着色或至多两次局部旋转恢复红黑性质。

叔叔为红：重着色并上移

此时 p 与 u 都是红色，g 必为黑色。把 p、u 染黑，把 g 染红。局部每条路径仍经过同样数量的黑节点，但 g 可能与它的父节点形成新的红红冲突，因此令 z=g，继续向上检查。

这一步不会旋转，是唯一可能让循环重复的情况。问题节点一次上移两层，所以最多重复 $O(\log n)$ 次。

叔叔为黑且呈内侧折线：先拉直

若 z 是 p 的右孩子，g-p-z 呈左后右的折线。先对 p 左旋，交换 z 与 p 在局部中的角色，把折线变成外侧直线。这个情形只是过渡，随后一定进入下一步。

叔叔为黑且呈外侧直线：重着色后旋转

若 z 是 p 的左孩子，把 p 染黑、g 染红，再对 g 右旋。旋转后的局部根是黑色，原来的红红冲突消失，而且各挂接子树的黑高不变。

在交互中逐个插入 41, 38, 31, 12, 19, 8。不要只记录“情况几”，还要说出判断链：父是否红、叔叔是什么颜色、节点位于内侧还是外侧、操作后违例去了哪里。

正确性与旋转次数

插入前原树合法；加入一个红节点后，统一黑高未变，违例最多出现在 z 与父节点之间。叔叔红时，局部黑高保持且问题严格上移；叔叔黑时，一至两次旋转消除冲突。最后把根染黑只会让所有根到叶路径同时多一个黑节点。因此所有性质都恢复。

一次插入的搜索和上移总共走 $O(\log n)$ 层，时间为 $O(\log n)$ ；无论重着色向上传播多少层，旋转最多两次。

新节点默认染红的首要理由是什么？

删除修复：追踪真正移走的黑色

删除比插入难，不是因为二叉搜索树删除本身变了，而是因为“用户要删的节点”和“真正从原位置移走的节点”可能不同。

设用户请求删除 z。若 z 至多有一个真实孩子，它自己从树中移走；若 z 有两个孩子，通常找右子树最小节点 y 作为后继，让 y 移到 z 的位置。此时影响原路径黑高的是 y 移走前的颜色，而不是 z 的颜色。

算法因此保存 yOriginalColor，并用 x 指向补到 y 原位置的节点：

text

RB-DELETE(T, z)
    y = z
    yOriginalColor = y.color
    按 z 的孩子数量执行移植；若 z 有两个孩子，让 y = successor(z)
    x = 补到 y 原位置的孩子，可能是 T.nil
    if yOriginalColor == BLACK
        RB-DELETE-FIXUP(T, x)

移走红节点不会改变黑高，通常无需修复。移走黑节点则让经过该位置的路径少一个黑节点。我们把这份缺失记作附着在指针 x 上的“额外黑”：x 的颜色字段仍只有红或黑，双重黑只是推理状态。

删除修复围绕 x 的兄弟 w、近侄和远侄判断。下面假设 x 是父节点的左孩子，远侄就是 w.right；另一侧完全镜像。

红黑树删除修复四种情况，展示兄弟红、两个侄子黑、近侄红和远侄红时的变色、额外黑上移与旋转过程

额外黑节点位于父节点左侧时，根据兄弟、近侄和远侄的颜色选择对应的删除修复操作；位于右侧时将所有方向镜像。

兄弟红：先变成黑兄弟问题

兄弟红意味着父节点和兄弟的孩子都为黑。把兄弟染黑、父染红，再对父左旋。额外黑尚未消失，但 x 的新兄弟一定是黑色，问题被规约为后面三类。

兄弟黑、两个侄子都黑：把额外黑上移

把兄弟染红，相当于从 x 一侧和兄弟一侧各拿掉一个黑，再把缺失合并到父节点。令 x=x.parent 继续循环。只有这一类会让问题向上重复。

兄弟黑、近侄红、远侄黑：先把远侄转红

把近侄染黑、兄弟染红，对兄弟右旋。此时新兄弟为黑，新远侄为红，结构转入最后一类。它与插入的“内侧折线先拉直”有相似的规约作用。

兄弟黑、远侄红：一次消解

让兄弟继承父节点颜色，把父和远侄染黑，再对父左旋。旋转后，原来 x 一侧补回一个黑，另一侧的黑节点数不变，额外黑被消解，循环结束。

用黑节点计数验证每个分支

不要凭图形“看起来更平衡”判断正确性。把 x 的额外黑也计入，分别计算变换前后从局部根到每棵挂接子树的黑节点数；四类操作都保持这些计数。循环最终有三个出口：x 到达根、x 是红黑叠加状态，或最后一类已经消解额外黑。统一把 x 染黑即可恢复全部性质。

情况 2 每次让 x 上移一层，最多经过树高；其他情况只做常数次变换后结束。删除总时间为 $O(\log n)$ ，一次修复最多三次旋转。

删除修复不能只看“被请求删除的节点是什么颜色”。当目标有两个孩子时，真正离开原位置的是后继；应检查后继移走前的颜色，并让 x 记录它原位置的黑高缺失。

删除一个有两个孩子的节点 z 后，是否调用删除修复主要取决于什么？

把正确性和复杂度放在一起看

红黑树的每个修改都可以按“保留什么、修复什么、问题是否严格推进”来检查。

操作	始终保留	可能破坏	推进方式	最坏时间
搜索	BST 次序、全部颜色性质	无	沿一条根到叶路径	$O(\log n)$
旋转	BST 中序次序	单独使用时不承诺颜色性质	常数个指针重接	$O(1)$
插入	BST 次序、原路径黑高	红色根或红红相邻	冲突上移两层，或旋转终止	$O(\log n)$
删除	BST 次序	统一黑高，也可能影响根黑或红红相邻	额外黑上移一层，或旋转终止	$O(\log n)$

对插入，循环重复只发生在叔叔为红时，问题节点严格上移；对删除，循环重复只发生在黑兄弟且两个侄子都黑时，额外黑严格上移。树高已经被证明是 $O(\log n)$ ，所以两个循环都会终止，并得到对数最坏界。

旋转次数比重着色次数更紧：插入最多两次，删除最多三次。这里不能误读成整个操作是 $O(1)$ ，因为寻找位置以及冲突向上传播仍可能走过 $O(\log n)$ 层。

红黑树插入最多做两次旋转，因此一次插入的最坏时间是 O(1)。

工程选择：红黑树适合什么接口

选择数据结构要先看调用方需要什么，不要只比较一个复杂度符号。

红黑树适合动态有序集合：既要频繁插入和删除，又要最坏情况稳定的查找，还需要有序遍历、范围查询、最小最大、前驱后继。颜色通常只增加很小的节点元数据；相较要求更严格的高度平衡，红黑树允许局部稍高，换取更新时有限的旋转次数。

需求	更常见的候选	原因
只做等值查找，不要求有序	哈希表	平均查找直接，接口更简单
需要内存中的动态有序映射	红黑树	更新、范围和前驱后继都具备最坏对数界
查找远多于更新，希望路径更短	更严格平衡树或排序数组	可以用更紧树高或批量重建换查询效率
面向磁盘页或数据库索引	B 树、B+ 树	高分支数能减少块访问次数
可以接受随机化的期望保证	treap、跳表	实现策略和并发特性可能更合适

实现层面还有三个容易被忽略的选择：重复键是计数还是独立节点；迭代器在旋转和删除后的失效规则；父指针、哨兵和颜色位如何布局。它们不改变红黑树证明，却会直接影响接口语义、内存占用和维护难度。

一个内存索引需要频繁增删，并持续支持区间 [a,b] 的有序扫描，哪种候选最贴近需求？

综合练习与解析

练习一：黑高与规模

某节点 x 的黑高为 4。以 x 为根的子树至少有多少个内部节点？

练习二：插入情形判断

新节点 z 为父节点 p 的右孩子，p 为祖父 g 的左孩子，叔叔 u 为黑色。应先做什么，随后怎样结束修复？

练习三：删除情形判断

x 携带额外黑且是左孩子。它的兄弟 w 为黑，w.left 为红，w.right 为黑。说明修复动作和额外黑的去向。

练习四：反例辨析

一棵树满足 BST 次序，根为黑，红节点没有红孩子，而且树高看起来接近 $\log n$ 。能否据此断定它是红黑树？

练习五：完整审查清单

实现一个红黑树验证器时，至少应检查哪些条件？

关于红黑树修复，下列哪些说法正确？