树系列第 12 篇：红黑树的插入与删除——修复全流程

欢迎来到“树系列”第 12 篇。上一篇我们认识了红黑树的五条性质，弄懂了“红色节点是借来的层”“黑色骨架决定树高”这些直觉。但性质只是静止的规则，本篇要回答的问题才真正劝退过无数人：插入一个节点、删除一个节点之后，到底怎么把树修回合法状态？ 我们会把插入的三种修复情况、删除的“双黑”问题与四种修复情况全部拆开，配图逐步走完，最后给出完整的 TypeScript 实现。准备好了吗？先把五条性质搬出来，然后开始动手。

0 本篇路线图

红黑树的插入和删除，本质上都是同一套套路：先当普通二叉搜索树（BST）操作，把节点物理地放进去或摘下来；再检查五条性质有没有被破坏；最后用“变色”和“旋转”两种工具把破坏的性质修好。插入只会破坏性质四（红节点不能有红孩子），因为新节点被染成红色；删除则可能破坏性质五（黑高一致），因为被摘走的节点可能是个黑节点。两种破坏的“症状”不同，修复的方法也不同，但底层工具完全相同。

为了让你不迷路，先给本篇画一张地图。第 1 节回顾五条性质与黑高，并给出“先 BST、后修复”的总体策略；第 2 节是插入修复的专场，依次讲新节点为什么默认红色、叔叔为红时怎么变色上溯、叔叔为黑时怎么旋转，最后用一个十二键的序列从头走到尾；第 3 节进入公认最难的删除修复，先讲清“双黑”替身是怎么产生的，再逐个拆解四种情况，并完整走两三个删除案例；第 4 节给出可运行的完整代码与逐行讲解；第 5 节总结复杂度，推导“插入最多两次旋转、删除最多三次旋转”这两个工程上极其重要的结论，并和 AVL 做最终对比；第 6 节用 2-3-4 树的视角重新解释所有修复动作，让“背案例”变成“讲道理”；结尾是速查表、自测题和下一篇预告。

1 回顾：五条性质与黑高

1.1 五条性质，一条都不能少

红黑树是每个节点多带一个颜色属性的二叉搜索树，颜色只有红、黑两种。它满足以下五条性质：

1. 每个节点非红即黑：颜色是节点的固有属性，不存在“无色”节点；
2. 根是黑色：整棵树的顶端必须是黑色；
3. 每个叶子（NIL）是黑色：这里的叶子指的不是带键的内部节点，而是所有空子树位置的哨兵 NIL；
4. 红色节点的两个孩子都是黑色：任何一条父子边上，不能出现“红-红”相连；
5. 从任一节点出发，到它所有后代 NIL 叶子的路径上，黑色节点的数量相同。

性质一、二是定义性约束，性质三是计数基准，性质四和性质五才是红黑树的“发动机”：性质四限制红色节点不能连续出现，性质五要求黑色骨架严格均衡。两者合在一起，就能推出“任何一条根到叶子的路径，长度不超过最短路径的两倍”，进而推出树高 O(log n)。第 11 篇已经证明过，这里不再重复推导，只把它们当作本篇所有修复动作的“验收标准”——每做完一步修复，都要问自己：五条性质现在都成立吗？

上面这棵树就满足全部五条性质。请你随手验一遍：根 7 是黑色；NIL 全是黑色；红色节点 1 和 15 的孩子都不是红色；从根到每个 NIL 的路径上黑节点数都是 3（例如 7、3、1、NIL 或 7、15、11、NIL）。这里 NIL 的作用就体现出来了：如果没有 NIL 作为统一的终点，性质五根本没法严谨计数。

1.2 黑高：修复工作最重要的计量单位

黑高（black-height） 是理解插入、删除修复的核心概念。定义如下：从某个节点 x 出发，向下走到任一 NIL 叶子，路径上遇到的黑色节点个数（不包括 x 自己），称为 x 的黑高，记作 bh(x)。根据性质五，从 x 出发的所有路径黑节点数相同，所以这个定义没有歧义。

举几个例子。上图中，节点 5 的黑高是 1（它下面只有一个 NIL，NIL 算一个黑色节点，路径上黑节点只有 NIL 自己）；节点 3 的黑高是 1（到 NIL 的路径上有 5 黑和 NIL 黑？不对——路径从 3 到 NIL 经过 5 和 NIL，黑节点是 5 和 NIL，共 2 个）。等等，这里要小心：从 3 出发到 5 的左 NIL，路径是 3 → 5 → NIL，不算 3 自己，黑节点有 5 和 NIL，共 2 个；从 3 出发到 1 的左 NIL，路径是 3 → 1 → NIL，黑节点有 1 和 NIL，共 2 个。所以 bh(3) = 2。而根 7 的黑高 bh(7) = 3，因为任何一条路径从 7 走到 NIL，都要经过 7 下面的两个黑节点再加上 NIL 本身。你可能会发现规律：红色节点不贡献黑高，黑色节点和 NIL 各贡献 1。

黑高的价值在于：一次插入或删除，往往只改变局部路径的黑节点分布，用黑高可以精确描述“哪里缺了黑、哪里多了黑”。比如删除一个黑色节点，会让它所在路径的每条“经过它的根到叶路径”少一个黑节点，也就是这些路径的黑高集体减 1；插入一个红色节点则完全不影响黑高——这正是新节点默认染红的第一个理由。

1.3 总体策略：先当 BST，再修颜色

红黑树的插入和删除都分两步走，这两步的“分工”极其清晰：

第一步，BST 操作。 插入时按 BST 规则找到空位，把新节点挂上去；删除时按 BST 规则找到真正被摘除的节点，用它的孩子或后继把它替换下来。这一步完全不看颜色，保证的是“中序遍历仍然有序”这一基本盘。

第二步，红黑修复。 用变色和旋转把五条性质修好。变色只改颜色位、不动指针；旋转会改变局部子树的结构，但不会改变中序遍历顺序。红黑树的所有修复工作，都是这两个动作的组合。

这个“两步走”的框架看起来简单，但真正的难度全在第二步：插入时冲突可能向上传播，删除时“欠下的黑”也可能向上传递。接下来两节，我们把每一步都走一遍。

2 插入修复：把一个红色节点“扶正”

2.1 新节点为什么默认是红色

插入一个节点时，我们面临一个选择：把它染成红色，还是染成黑色？教科书直接告诉你“染红”，但背后的理由值得拆开讲，因为它决定了后续所有修复动作的形状。

如果把新节点染成黑色，会发生什么？新节点挂在哪条路径上，那条路径就凭空多了一个黑节点。性质五要求“从任一节点到后代 NIL 的所有路径黑节点数相同”，现在新节点所在的所有根到叶路径，黑高都比别的路径多了 1——性质五立刻被破坏。而且这种破坏是“结构性”的：多出来的黑节点固定在某个位置，你很难通过局部变色把它消掉，因为变色只是把“黑的标记”从一个节点移到另一个节点，路径上的黑节点总数并不变。要修复“多了一个黑”，往往需要旋转把整个子树重新配平，代价很大。

如果把新节点染成红色呢？红色节点不参与黑高计数，所有路径的黑节点数原封不动，性质五自动保持。唯一可能被破坏的是性质四：如果新节点的父节点恰好也是红色，就会出现“红-红”相连。而性质四的破坏有一个绝妙的特点——它是“局部可传播”的：我们可以通过变色把红色标记向上推，或者通过旋转把结构重新摆平，修复手段非常明确。更妙的是，如果父节点是黑色，插入之后五条性质全部成立，连修复都省了。这就是“新节点默认红色”的全部逻辑：染红把可能违规的范围从“黑高问题”压缩成“红红问题”，而红红问题恰好是变色和旋转最擅长解决的。

从 2-3-4 树的视角看，这个选择也顺理成章：插入一个新键相当于往某个 2-3-4 节点里“塞”一个键，红色节点是“借来的层”，它和父节点同属一个逻辑节点；只有当父节点也已经有“夹层”时，才需要把夹层摊开或拆开。这个视角第 6 节还会展开，现在先记住结论：新节点一律染红，除非它的父节点是黑，否则启动修复流程。

2.2 三种情况的判定顺序

设新插入的节点为 z。只要 z 的父节点是红色，我们就进入修复循环；每轮先看 z 的祖父节点（必然存在，因为根是黑色的，而 z 的父节点是红色，说明 z 至少有两层祖先），祖父必然是黑色。接下来，判定顺序的关键一步：看叔叔的颜色。

叔叔（uncle）就是祖父的另一个孩子：如果 z 的父节点是祖父的左孩子，叔叔就是祖父的右孩子；反之亦然。叔叔有两种颜色，正好把修复分成两大类：

• 叔叔是红色：这是“情况一”。父亲和叔叔都是红的，说明祖父这一层有两个“红色夹层”要摊平。做法是变色——把父亲和叔叔染黑、祖父染红，把矛盾上移到祖父，然后让 z 指向祖父，继续循环。
• 叔叔是黑色（包括叔叔是 NIL 的情况）：这时不能只靠变色，需要旋转。旋转之前还要看 z 相对祖父的“位置形态”，细分为两种情况二和三：如果 z、父、祖父三点在一条直线上（左-左或右-右），做一次旋转就能解决；如果三点构成折线（左-右或右-左），要先做一次旋转把它掰直，再做一次旋转解决。

所以严格来说，插入修复一共有三种情况，其中情况三常常被进一步拆成“先转成情况二再处理”，于是也有人称它为四种情形。为了和教材对齐，本篇统一用三情况表述：情况一（叔叔红）、情况二（叔叔黑 + 直线形态）、情况三（叔叔黑 + 折线形态）。

判定顺序有个容易踩的坑：一定要先看叔叔的颜色，再看 z 的位置。很多初学者一上来就盯住 z 是父节点的左孩子还是右孩子，忘了叔叔是红的时根本不需要关心位置。叔叔的颜色才是“变色还是旋转”的总开关。

2.3 情况一：叔叔是红色的，变色上溯

先看情况一。假设 z 是红色，父 p 是红色，祖父 g 是黑色，叔叔 u 是红色。此时 g 的两个孩子 p 和 u 都是红色，也就是说 g 带着两个“红色夹层”，而 z 又要挤在 p 下面，红-红冲突发生在 z 与 p 之间。下图左边是修复前的状态（为了画图清楚，只画关键路径，省略其他子树）：

修复动作只有三步，全部是变色：

1. 把父节点 p 染成黑色；
2. 把叔叔 u 染成黑色；
3. 把祖父 g 染成红色，然后把 z 上移到 g，继续下一轮循环。

做完之后，树变成下图：

为什么这样改是安全的？我们来验证性质五：修复前，g 是黑色，p 和 u 是红色；修复后，p 和 u 变成黑色，g 变成红色。站在任意一条穿过 g 的根到叶路径上看，黑节点数量完全没变——路径上原本有 g 一个黑，现在变成 p 或 u 各一个黑，总数还是 1。换句话说，变色上溯是一笔“等价交换”：用祖父的红，换来父和叔的黑，黑高守恒，性质五不会破坏。

性质四呢？修复后 p 和 u 都是黑的了，它们的红孩子（包括 z）不会和它们形成红-红；唯一可能出问题的是 g 和 g 的父节点——如果 g 的父节点恰好是红色，就出现了新的红-红。这正是我们把 z 指向 g、继续循环的原因：冲突没有消失，只是从“z 与 p”上移到了“g 与 g 的父”。如果 g 是根，循环下一轮会因为“父节点是 NIL（黑色）”直接退出，最后由“根强制染黑”收尾。

情况一还有一个重要特点：它只变色、不旋转。变色不改变任何父子关系，所以整棵树的形状完全不变，只是颜色标记变了。这正是红黑树“插入平均修复成本低”的底气——大多数插入冲突都能用情况一向上推走，旋转只留给真正需要动结构的情况二、三。

2.4 情况二与情况三：叔叔是黑的，旋转加变色

情况二、情况三的共同前提是：z 是红色、父 p 是红色、祖父 g 是黑色，而叔叔 u 是黑色（注意 NIL 也是黑色，所以叔叔为空也算“黑叔叔”）。此时 p 和 u 一红一黑，无法像情况一那样“父叔同时染黑”做等价交换——把 p 单独染黑会破坏黑高，因为 p 所在路径会多一个黑节点，而 u 那边没有相应的黑补上。所以必须动用第二种工具：旋转。

情况二：直线形态（LL 或 RR）

如果 z、p、g 三点在一条直线上，事情最简单。以“左-左”为例：p 是 g 的左孩子，z 是 p 的左孩子，整条路径一路向左，像一条直杆。修复动作只有三步：

1. 把 p 染成黑色；
2. 把 g 染成红色；
3. 以 g 为轴做一次右旋，让 p 升上来当子树的新根。

右旋之后，p 的左孩子是 z，右孩子是 g，g 的右孩子保持原样（下图里用“g 的右子树”表示）。修复前后对比：

注意修复后 z 和 g 都是红色，它们分别在 p 的左右两侧，p 是黑色，所以不再有红-红相连；性质四恢复。黑高呢？右旋只是把 p 和 g 的位置互换，变色把 p 染黑、g 染红，穿过这棵子树的每条根到叶路径上，黑节点仍然是“一个黑 + 原有黑色”，总数不变，性质五保持。最妙的是，这棵子树的根从红色变成了黑色，它和外面（g 原来的父节点）不可能产生新的红-红冲突，所以修复到此结束，循环退出。

“右-右”是它的镜像：p 是 g 的右孩子、z 是 p 的右孩子时，把 p 染黑、g 染红，然后以 g 为轴左旋，效果完全对称。你可以把 LL 和 RR 记成一句话：谁在最上层的直杆中间，谁就升上去当黑根，原来的根降下来当红孩子。

情况三：折线形态（LR 或 RL）

如果三点不在一条直线上，比如 p 是 g 的左孩子、z 是 p 的右孩子，路径先向左再向右，像一根折弯的杆。直接对 g 旋转没有意义——旋转只会把“弯”挪个位置。正确的做法分两步：

1. 先“掰直”：以 p 为轴左旋，让 z 升上来当 p 的父节点，p 变成 z 的左孩子。这一步过后，z、p（此时 z 是父、p 是子）、g 三点变成直线形态，而且 z 变成了“外层孩子”的位置；
2. 再按情况二处理：此时把 z 当成新的“父角色”，把 g 当成祖父，做一次右旋，并配上和情况二完全相同的变色——把新的子树根（也就是原来的 z）染黑，把 g 染红。

最终形态很有规律：原来的 z 变成黑色的子树根，p 和 g 变成它的两个红色孩子。对于镜像的 RL（p 是 g 的右孩子、z 是 p 的左孩子），先以 p 为轴右旋掰直，再以 g 为轴左旋，变色规则完全相同。

这里特别提醒一个初学者常绕晕的点：情况三里的“父/祖角色”在两次旋转之间会互换。第一次旋转后，z 变成了 p 的父节点，原来的“父”变成了“子”；第二次旋转时，我们处理的是“z 与 g”这一对，而不是最初的“p 与 g”。只要记住“先掰直、后旋转、中键染黑、两端染红”这十六个字，就能从任何折线形态一步推到位，不用背四个方向的变体。

2.5 循环何时结束：根强制染黑

插入修复是一个 while 循环：while (z.parent 是红色)。每一轮根据叔叔的颜色走情况一、二或三。三种情况对“循环是否继续”的影响完全不同：

• 情况一只变色不旋转，冲突上移到祖父，循环继续。它可能一连发生很多轮，一路把红色标记推到根附近；
• 情况二做一次旋转加变色，冲突就地解决，循环立刻退出；
• 情况三做两次旋转加变色，同样就地解决，循环立刻退出。

所以插入修复的循环次数在理论上有 O(log n) 轮（全是情况一），但旋转最多只有两次：要么一次（情况二），要么两次（情况三），要么零次（纯情况一）。这个“旋转次数”的结论是红黑树工程价值的重要来源，第 5 节会细算。

循环退出后，还有最后一道保险：无条件把根染成黑色。为什么需要这一手？因为情况一可能一路把 z 推到根，此时根是红色的，违反性质二；而根的父节点是 NIL（黑色），循环条件已经不成立了，所以循环自己永远不会处理“根是红”这个局面。把根直接染黑，会不会破坏性质五？不会——根是所有根到叶路径的公共起点，把它从红变黑，等于每条路径都同步多了一个黑节点，路径之间的黑高关系不变，性质五依然成立。这条保险还有一个隐藏福利：哪怕插入后根本来就是黑的，再染一次也毫无副作用。因此“循环 + 根染黑”两步合起来，保证五条性质全部恢复。

顺便记住一个调试技巧：红黑树实现里如果出现“根是红的”的 bug，多半是忘了最后这行根染黑；如果出现“连续红节点”，多半是情况二、三的旋转方向写反了。后面第 4 节写代码时，我们会用这几条经验做自检。

2.6 完整走查：把序列 [10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70] 插进去

理论讲得再清楚，不如亲手走一遍。我们选用一个有代表性的序列：[10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70]。它里面既有“叔叔是红”的变色上溯，也有“叔叔是黑”的直线旋转和折线双旋，还有一路推到根附近才收尾的情况一连锁反应。走完之后，你会对“判定顺序”产生肌肉记忆。下文每张图只画带键的内部节点，NIL 一律省略，但判定叔叔颜色时，请记住“空位 = 黑叔叔”。

第 1 步：插入 10。 树为空，10 直接成为根。它是红色，但父节点是 NIL（黑色），循环不进入，最后“根强制染黑”，10 变成黑色。这是整棵树的第一块黑色基石。

第 2 步：插入 18。 18 比 10 大，成为 10 的右孩子，染红。父节点 10 是黑色，五条性质全部成立，无需修复。此时树是“黑根 + 红右孩子”。

第 3 步：插入 7。 7 比 10 小，成为 10 的左孩子，染红。父节点 10 仍是黑色，无需修复。此时 10 的左右各挂一个红孩子，三个节点形成“黑父、双红子”的形态——这在红黑树里完全合法，两个红色节点并没有父子关系。

第 4 步：插入 15。 15 比 10 大、比 18 小，成为 18 的左孩子，染红。这次父节点 18 是红色，触发修复。看祖父：祖父是 10；叔叔是祖父的左孩子 7，它是红色，所以走情况一：把父 18 和叔叔 7 染黑，把祖父 10 染红，然后把 z 上移到 10。此时 z=10 的父节点是 NIL，循环退出，最后根强制染黑，10 恢复黑色。整个第 4 步一次旋转都没用，纯变色：

第 5 步：插入 16。 16 比 15 大，成为 15 的右孩子，染红。父节点 15 是红色，需要修复。祖父是 18，叔叔是 18 的右孩子——空位，也就是 NIL，黑色。于是进入“叔叔是黑”的分支：z=16 是父 15 的右孩子，而父 15 是祖父 18 的左孩子，构成左-右折线（LR），走情况三：

1. 以 15 为轴左旋，16 升上来，15 变成 16 的左孩子；
2. 现在三点成直线，按情况二处理：把新的“父”16 染黑，把 18 染红，再以 18 为轴右旋；
3. 旋转后 16 成为这棵子树的根，15 和 18 成为它的两个红孩子。

把局部放回整棵树，第 5 步结束时：10（黑）的左孩子是 7（黑），右孩子变成 16（黑）；16 的左孩子是 15（红）、右孩子是 18（红）。这棵树依然合法：根 10 黑、无红-红、每条路径黑节点数一致。

第 6 步：插入 30。 30 一路向右，成为 18 的右孩子，染红。父 18 是红色，需要修复。祖父是 16，叔叔是 16 的左孩子 15，红色——情况一：18 和 15 染黑，16 染红，z 上移到 16。此时 z=16 的父节点是 10，黑色，循环退出；根 10 本来就是黑的，最后一道“根染黑”只是例行公事。第 6 步同样是纯变色：

到这里，序列已经走完一半，出现了两次“情况一”和一次“情况三”。注意观察一个规律：情况一出现时树形完全不变，只是颜色标记在换位置；情况三出现时才真正动了两次旋转。这就是红黑树“大部分时候很便宜”的直观证据。

第 7 步：插入 25。 25 比 16 大、比 18 大、比 30 小，成为 30 的左孩子，染红。父 30 是红色，需要修复。祖父是 18，叔叔是 18 的右孩子——空位 NIL，黑色。z=25 是父 30 的左孩子，而父 30 是祖父 18 的右孩子，构成右-左折线（RL），走情况三的镜像：

1. 以 30 为轴右旋，25 升上来，30 变成 25 的右孩子；
2. 按情况二处理：把新的“父”25 染黑，把 18 染红，再以 18 为轴左旋；
3. 旋转后 25 成为子树根，18 和 30 成为它的两个红孩子。

第 7 步结束时，树是：10（黑）的右孩子是 16（红）；16 的左孩子 15（黑）、右孩子 25（黑）；25 的左孩子 18（红）、右孩子 30（红）。红色 16 的两个孩子都是黑色，红色 18、30 没有红孩子，合法。

第 8 步：插入 40。 40 一路向右，成为 30 的右孩子，染红。父 30 是红色，需要修复。祖父是 25，叔叔是 25 的左孩子 18，红色——情况一：30 和 18 染黑，25 染红，z 上移到 25。注意，情况一没有让问题消失：现在 z=25 是红色，而它的父节点 16 也是红色，新的红-红冲突出现了。继续循环：z=25 的祖父是 10，叔叔是 10 的左孩子 7，黑色；z=25 是父 16 的右孩子，父 16 是祖父 10 的右孩子，构成右-右直线（RR），走情况二：把 16 染黑、10 染红，以 10 为轴左旋。

这一步特别值得停下来体会：情况一只是把冲突向上推了一层，真正解决问题的是随后的情况二旋转。这也解释了为什么“叔叔的颜色”是每轮循环都要重新判断的——颜色变了，分支就可能变。左旋之后，16 成为新的根，10 变成 16 的左孩子：

第 9 步：插入 60。 60 比 40 大，成为 40 的右孩子，染红。父 40 是红色，需要修复。祖父是 30，叔叔是 30 的左孩子——空位 NIL，黑色。z=60 是父 40 的右孩子，父 40 是祖父 30 的右孩子，右-右直线（RR），走情况二：40 染黑、30 染红，以 30 为轴左旋。修复后 40 成为子树根，左孩子 30（红）、右孩子 60（红）：

第 10 步：插入 2。 2 比 16 小、比 10 小、比 7 小，成为 7 的左孩子，染红。父节点 7 是黑色，无需修复。树里只是安静地多了一个红叶子。

第 11 步：插入 1。 1 比 2 小，成为 2 的左孩子，染红。父 2 是红色，需要修复。祖父是 7，叔叔是 7 的右孩子——空位 NIL，黑色。z=1 是父 2 的左孩子，父 2 是祖父 7 的左孩子，左-左直线（LL），走情况二：2 染黑、7 染红，以 7 为轴右旋。修复后 2 成为子树根，左孩子 1（红）、右孩子 7（红）：

第 12 步：插入 70。 70 比 60 大，成为 60 的右孩子，染红。父 60 是红色，需要修复。祖父是 40，叔叔是 40 的左孩子 30，红色——情况一：60 和 30 染黑，40 染红，z 上移到 40。新的冲突出现：z=40 是红色，父 25 是红色。继续循环：祖父是 16，叔叔是 16 的左孩子 10，也是红色——情况一再次生效：25 和 10 染黑，16 染红，z 上移到 16。现在 z=16 的父节点是 NIL，循环退出，最后一道“根强制染黑”把 16 变回黑色。两次情况一，一次旋转都没有，全部靠变色把红色标记一路推到根，再被根染黑吸收掉：

十二个键全部插入完毕，最终的红黑树长这样：

请验收一下这棵树的五条性质：根 16 是黑的；红色节点 1、7、40、70 的孩子都非红（空位视为黑 NIL）；从根出发的所有路径黑节点数都是 4（比如 16→10→2→1→NIL 和 16→25→40→60→70→NIL）。如果用一个最简单的搜索来验证，你会发现这棵树的查找路径长度最多 4 层，而 12 个节点如果退化成链会有 12 层——平衡的价值一目了然。

把整个过程整理成一张表，方便你对照复习：

步骤	新键	父颜色	叔叔颜色	走哪个分支	动作
1	10	NIL	-	无需修复	染黑成为根
2	18	黑	-	无需修复	直接挂上
3	7	黑	-	无需修复	直接挂上
4	15	红	红（7）	情况一	变色上溯，根染黑
5	16	红	黑（NIL）	情况三 LR	左旋 15，右旋 18
6	30	红	红（15）	情况一	变色上溯
7	25	红	黑（NIL）	情况三 RL	右旋 30，左旋 18
8	40	红	红（18）→黑（7）	情况一 + 情况二 RR	变色上溯，左旋 10
9	60	红	黑（NIL）	情况二 RR	左旋 30
10	2	黑	-	无需修复	直接挂上
11	1	红	黑（NIL）	情况二 LL	右旋 7
12	70	红	红（30）→红（10）	情况一 × 2	变色上溯两次，根染黑

整段走查里一共出现了 5 次情况一、2 次情况三、2 次情况二。旋转总数只有 6 次，其余 6 次插入要么无需修复，要么纯变色。这就是红黑树插入的真实节奏：旋转是稀缺资源，变色才是常态。

2.7 插入修复的不变式：为什么循环不会“越修越坏”

走完整个序列之后，值得停下来提炼一个贯穿全程的概念：不变式。插入修复循环每执行一轮，都维持着这样一个承诺——除了“当前 z 的父节点是红色”和“根可能是红色”这两个已知问题之外，其余四条性质全部成立。听起来像废话，但它是理解修复安全性的关键：

性质五（黑高一致）永远不会被插入修复破坏。 情况一的变色是“父、叔染黑，祖父染红”的等价交换，穿过祖父的每条路径黑节点数不变；情况二、三的旋转加变色，同样是“黑、红互换 + 位置互换”，任何路径上的黑节点总数不变。所以不管循环跑多少轮，黑高账本始终是平的——修复只需要盯着性质四，不会按下葫芦浮起瓢。

性质四的冲突只存在于“z 与 z 的父”这一处。 每轮循环开始时，z 是红色，z 的父是红色，冲突在此；其他红色节点的孩子都必须是黑色。情况一执行后，父、叔变黑，冲突点变成“祖父（红）与祖父的父”，于是 z 上移到祖父，冲突点依然只有一处；情况二、三执行后，新的子树根是黑色的，冲突点彻底消失，循环终止。这个“只允许存在一个冲突点”的约束，让修复永远不需要回头处理已经修好的地方。

循环必然终止。 情况二、三直接结束；情况一每次把 z 向上移动两层（z 指向祖父），而树高有限，z 最多到根。到了根，循环条件 z.parent 是红色 不再成立，退出后由“根强制染黑”解决最后的颜色问题。三条性质合起来，就构成了插入修复的完备性论证：每轮保持其余性质不变、冲突点唯一、且必然向根推进。

这个“不变式”思维在第 3 节删除修复里会更加重要——双黑循环承诺的是“除当前双黑外，其余性质不变”。读删除代码时，建议时刻用这个框架问自己：这一步保持黑高了吗？冲突点还在原处吗？循环在向根推进吗？三个答案都是“是”，修复就是安全的。

3 删除修复：双黑问题的四种解法

如果说插入是“有点绕”，删除就是“公认最难”。难在哪里？插入破坏的是性质四——红-红相连，这是看得见的违规：扫描树的时候一眼就能指出来“这两个红节点是父子”。删除破坏的却是性质五——黑高一致，这是看不见的违规：删掉一个黑节点之后，某条路径上少了一个黑，但树里没有任何一个节点会“变色报错”，只有当你数每条路径的黑节点数时才会发现失衡。所以删除修复的第一步，是先给这场“看不见的失衡”一个看得见的载体，这就是双黑。在介绍双黑之前，先把删除的 BST 部分复习一遍。

3.1 删除的 BST 部分：用后继替换

红黑树的删除完全复用 BST 的删除逻辑，分三种情况：

1. 被删节点 z 没有左孩子：直接用 z 的右孩子顶替 z 的位置；
2. 被删节点 z 没有右孩子：直接用 z 的左孩子顶替 z 的位置；
3. z 有两个孩子：找到 z 的中序后继 y（z 右子树里的最小节点），把 y 的键复制给 z，然后把 y 从它原来的位置上摘除。由于 y 是右子树的最小值，它必然没有左孩子，所以摘除 y 又回到了情况一或二。

第三种情况需要特别理解：我们“物理删除”的其实不是 z 本身，而是 z 的中序后继 y。z 这个节点只是被换上了 y 的键，它作为节点仍然留在树里，只是内容变了；真正从树上消失的是 y。因此，红黑树删除修复关心的是 y 的颜色，而不是 z 的颜色——y 是红色，摘掉它不伤黑高；y 是黑色，就欠下了一笔黑债。

在具体实现里，我们通常不是“复制键”，而是用指针移植（transplant）：把 y 的右孩子 x 移到 y 的位置，再把 y 整个节点搬到 z 的位置，并继承 z 的颜色。两种写法等价，第 4 节代码会采用指针移植版，因为实现“继承颜色”更直接。无论哪种写法，都要记住一句话：删除的物理动作只发生在“至多一个孩子的节点”身上，被摘下来的节点要么是叶子、要么只有右孩子。

3.2 双黑：删除黑节点留下的债

现在把颜色加回来。假设被真正摘除的节点是 y，它原来的颜色是黑色。y 消失后，原来穿过 y 的所有根到叶路径，都少了一个黑节点——性质五被破坏。受影响的路径不是一条，而是 y 的子树里所有根到叶路径，因为它们都经过 y。换句话说，y 原来所在的那一整“束”路径，黑高集体减了 1。

修复的经典技巧是：让顶替 y 的那个节点 x（可能是 y 的孩子，也可能是 NIL）承担“双份黑色”，变成一个双黑（doubly black）节点。这个名字很形象：x 本来可能是黑色或红色，现在它身上除了自己的颜色，还背着 y 欠下的那一个黑。于是，性质五的账先被“赊”下来：路径上的黑节点数暂时视为“x 算两个黑”，所有路径重新“看起来”一致了。真正的修复，就是想办法把这笔债还掉——把多出来的一个黑转移走，直到某个节点能“吸收”它，或者把它推到根上消掉。

双黑修复是一个循环：while (x 不是根 && x 是黑色)。每一轮根据 x 的兄弟 w 的颜色、以及 w 的两个孩子（侄子）的颜色，走四种情况之一：

• 情况一：兄弟 w 是红色。这时 w 的两个孩子必是黑色。做法：w 染黑、父染红，以父为轴旋转，把 w 的位置让给一个黑兄弟，问题转化为情况二、三或四；
• 情况二：兄弟 w 是黑色，且 w 的两个孩子都是黑色。做法：把 w 染红，把 x 身上的“双黑”削减为单黑，把多出来的黑上推给父节点，x 指向父，继续循环；
• 情况三：兄弟 w 是黑色，近侄是红色、远侄是黑色。做法：近侄染黑、w 染红，以 w 为轴旋转，把“红侄子”转到远侄位置，问题转化为情况四；
• 情况四：兄弟 w 是黑色，远侄是红色。做法：w 继承父的颜色，父染黑，远侄染黑，以父为轴旋转，然后 x 直接指向根结束。

看到这里你可能会问：为什么删除要比插入多一种情况？因为插入只有“红-红”一种违规，且新节点位置已知；删除的“双黑”要同时处理“兄弟是红”和“兄弟是黑”两大类，而黑兄弟又按侄子的颜色细分成三种。好消息是，四种情况的判定顺序是固定的，而且每种情况的动作都有明确的“为什么”。接下来逐个拆解。

3.3 情况一：兄弟是红色的，先旋转换成黑兄弟

先交代本节的统一假设：x 是双黑节点，w 是 x 的兄弟。为了叙述方便，我们假定 x 是父节点 p 的左孩子（右孩子的情况完全镜像，代码里用对称分支处理）。情况一的判定条件是：w 是红色。由于红节点的两个孩子必须是黑色，w 的两个侄子必是黑色；又因为 w 是红色、不能有红父，所以父节点 p 也必是黑色。

情况一的动作分三步：

1. 把 w 染成黑色；
2. 把 p 染成红色；
3. 以 p 为轴左旋，让 w 升到 p 的位置，p 变成 w 的左孩子。

为什么要做这笔“换血”？因为 w 是红色时，它的子树里黑色信息很少，直接对它做“借黑”或“染红”都会破坏黑高；而旋转之后，x 的新兄弟变成了原来 w 的左孩子——它是一个黑色节点，于是问题就落回了“黑兄弟”的领地，也就是情况二、三、四。换句话说，情况一的本质是转化：把一个没法直接处理的局面，变成一个能处理的局面。做完这一步，x 仍然是双黑，循环继续，但下一轮一定会走到情况二、三或四。

一个常见的困惑是：情况一做完，p 变成红色，会不会产生新的红-红违规？不会。旋转前 w 的两个孩子都是黑色；旋转后 p 是红色，它的两个孩子是 x（双黑）和原来的 w 左孩子（黑），都不是红，所以性质四安全。而黑高方面，旋转本身不改变任何路径上的黑节点数（w 黑、p 红互换，位置变化但颜色随之迁移），所以只需继续处理 x 的双黑即可。

3.4 情况二：兄弟黑且两个侄子都黑，把黑上推

情况二的前提是：w 是黑色，并且 w 的两个孩子（近侄和远侄）都是黑色。注意 NIL 是黑色，所以 w 没有孩子也算“两个侄子都黑”。此时 x 的子树“欠一个黑”，而 w 的子树“完全正常”，两边黑高差 1。怎么补？把 w 染成红色，让 w 的子树也“少一个黑”，两边就重新平了。具体动作：

1. 把 w 染成红色；
2. 把 x 身上的双黑削减为单黑（也就是把“欠账”还掉一半）；
3. 把 x 指向父节点 p，继续循环。

用“欠账”的语言说：x 这边欠了一个黑，w 那边主动贡献一个黑（w 由黑变红，w 的子树黑高减 1），两边账目平了；但 p 的整棵子树现在比外面少了一个黑，所以这笔债并没有消失，而是上推到了 p。如果 p 原来是红色，那就太好了——把 p 染成黑色，债就还清了（这也是为什么循环退出后有一句无条件 x.color = BLACK）；如果 p 原来是黑色，p 就变成新的“双黑”，继续向上走。

情况二可能是四种情况里唯一会“循环多轮”的：如果 p 是黑的，它变成双黑后，下一轮又要看 p 的兄弟……如此一路向上。最坏情况下，情况二能把双黑一路推到根；一旦 x 成为根，循环退出，最后把根染黑，双黑就地消失——因为“根的额外一黑”不违反任何性质五约束（所有路径都从根出发，多一黑也是大家一起多）。和插入的情况一类似，情况二也是纯变色、零旋转，这正是删除修复“平均便宜”的又一个来源。

3.5 情况三：近侄红、远侄黑，先旋转再转化

情况三的前提是：w 是黑色，近侄（离 x 近的那一侧孩子）是红色，远侄是黑色。沿用“x 是左孩子”的假设，近侄就是 w 的左孩子，远侄就是 w 的右孩子。为什么这种情况不能直接处理？因为 w 这边有一个红孩子，直接像情况二那样把 w 染红，会制造新的红-红（w 红 + 近侄红）；而 w 的右孩子是黑的，又没法像情况四那样直接用远侄的红来“买单”。于是教科书给出的动作是：把近侄的红色转移到远侄那边，把局面变成情况四。

具体三步：

1. 把近侄染成黑色；
2. 把 w 染成红色；
3. 以 w 为轴右旋，让近侄升到 w 的位置。

旋转之后，原来的近侄变成了 x 的新兄弟 w’，它是黑色；w 变成 w’ 的右孩子，是红色；远侄还是黑色，待在 w 的右孩子位置。现在再看局面：w’ 是黑色，w’ 的右孩子（远侄）是红色——这正是情况四的形态。所以情况三从来不是终点，它的全部意义就是“制造情况四”。这个思路和插入时“情况三先掰直、再按情况二处理”如出一辙：红黑树修复大量使用“化归”，把陌生形态转成已知形态。

3.6 情况四：远侄是红的，一次旋转彻底收尾

情况四的前提是：w 是黑色，远侄是红色（近侄颜色不限）。此时 w 的子树“有余粮”——远侄这个红节点可以染黑来补黑高。动作分四步：

1. 把 w 染成 p 原来的颜色（w 继承父色，保证上层不受影响）；
2. 把 p 染成黑色；
3. 把远侄染成黑色；
4. 以 p 为轴左旋（x 是左孩子时），然后把 x 指向根，循环结束。

为什么这样能一次解决？我们来数黑高。旋转前，穿过 x 的路径少一个黑（x 双黑）；旋转后，p 变成 w 的左孩子，而 p 被染成黑色，它正好挡在 x 的上面，把“少掉的那个黑”补了回来；远侄被染黑，则补偿了 w 侧因为旋转而变化的黑节点分布；w 继承 p 的原色，保证 w 的上层看到的颜色和旋转前一模一样。三条黑高账全部结清，双黑解除，性质五恢复。同时 p 是黑的，x 无论原来是红是黑都不会再有红-红问题，性质四也安全。

四种情况全部登场完毕。最后用一句口诀帮你记忆：“红兄弟先旋转，黑兄弟看侄子：侄子全黑向上推，近红远黑先转化，远侄一红就收尾。”接下来，我们用三个真实案例把口诀跑一遍。

3.7 完整删除案例一：情况二的单轮修复

先建立一棵“实验树”，它和插入走查用的树不同，专门挑形状简单、便于验证黑高的结构：

请先确认这棵树合法：根 7 是黑的；红色 2、11、15 的孩子都不是红的；从根出发的所有路径黑节点数都是 3。现在执行删除 1。

1 是黑色叶子，没有左孩子，所以被真正摘除的 y 就是 1 自己，颜色黑色。顶替它的是 x = 1 的右孩子 NIL。黑债产生：x 变成双黑。此时 x 的父节点 p = 2（红色），兄弟 w = 5（黑色），w 的两个孩子都是 NIL（黑色）——完全符合情况二。执行：w 染红，x 上移到 p。因为 p = 2 原来是红色，循环条件 x 是黑色 不再满足，循环退出；最后一句“x 染黑”把 2 从红色变成黑色。整个修复只有两次变色，零旋转：

验证结果：2 由红变黑、5 由黑变红，穿过 2 的所有路径黑节点数不变（黑少了一个，但双黑也消掉了）；11 侧完全没动。最后数一遍：7→2→NIL 有 7、2、NIL 三个黑；7→11→14→15→NIL 有 7、11、14、NIL 四个黑——等等，这里似乎多了？别急，14 的右孩子 15 是红色，所以路径 7、11（红）、14（黑）、15（红）、NIL（黑）的黑节点是 7、14、NIL，共 3 个。全部路径都是 3，合法。

3.8 完整删除案例二：情况一旋转 + 情况二收尾

案例一留下的树是：7（黑）、2（黑）、5（红）、11（红）、8（黑）、14（黑）、15（红）。我们想制造“兄弟是红色”的局面。先删除 5：它是红色叶子，摘掉它不影响任何黑高，连修复循环都不用进，树变成：7（黑）、2（黑）、11（红）、8（黑）、14（黑）、15（红），2 的右孩子变成 NIL。

接着删除 2。2 现在是黑色叶子，x = NIL 变成双黑。看它的兄弟：w = 11，红色——情况一登场！父 p = 7 是黑色。执行：w 染黑、p 染红，以 p 为轴左旋。左旋后 11 升到根的 7 的位置，7 变成 11 的左孩子，7 的右孩子变成原来 11 的左孩子 8：

情况一并没有消除双黑，它只是把局面换成了“更好处理”的样子：现在 x 的新兄弟 w’ = 8 是黑色，w’ 的两个孩子都是 NIL（黑色）——情况二。执行：8 染红，x 上移到 7。7 是红色，循环退出，最后把 7 染黑。整个删除 2 的过程用了一次旋转（左旋 7）和三轮变色，最终树：

验证：根 11 黑；红 8、15 的孩子都是空位（黑）；黑高——11→7→NIL 是 11、7、NIL 三个黑；11→7→8→NIL 是 11、7、NIL 三个黑（8 是红的）；11→14→15→NIL 是 11、14、NIL 三个黑。五条性质全部成立。这个案例的精华在于：情况一本身不还债，它把“红兄弟”转化成“黑兄弟”，真正的还债动作发生在随后的情况二。这和插入里“情况三先掰直、再套情况二”是同一个化归思想。

3.9 完整删除案例三：情况四的一次旋转收尾

回到 3.7 的实验树：7（黑）、2（红）、11（红）、1（黑）、5（黑）、8（黑）、14（黑）、15（红）。这次执行删除 8。8 是黑色叶子，x = NIL 变成双黑；它的父 p = 11（红色），兄弟 w = 14（黑色）。看 w 的两个孩子：左孩子是空位 NIL（黑），右孩子 15 是红色——远侄是红的，直接命中情况四：

1. w（14）继承 p 的颜色，也就是红色；
2. p（11）染成黑色；
3. 远侄（15）染成黑色；
4. 以 p 为轴左旋，然后 x 指向根，循环结束。

旋转后 14 升到 11 原来的位置，11 变成 14 的左孩子，11 的右孩子接住原来 14 的左子树（这里是 NIL），15 留在 14 的右孩子位置。逐条验证：根 7 黑；红 2 的孩子 1、5 都是黑；红 14 的孩子 11、15 都是黑；黑高——7→2→1→NIL 是 7、2、1、NIL 四个黑？数一下：7 黑、2 红、1 黑、NIL 黑，共 3 个黑；7→14→11→NIL 是 7、14、11、NIL 共 3 个；7→14→15→NIL 是 7、14、15、NIL 共 3 个。全部一致，删除完成。注意情况四之所以能“一次解决”，关键在第 3 步：远侄由红变黑，等于在 w 这一侧补回了一个黑，正好抵消 x 那边缺的黑，两边黑高同时归位。

三个删除案例走下来，正好覆盖了四种情况里的三类：案例一走情况二，案例二走情况一接情况二，案例三走情况四；情况三的局部转化在 3.5 节已经配图拆过。你可以发现一个隐藏规律：情况一、三都不是终点，它们把问题“翻译”成情况二或四；真正结束战斗的只有情况二（把债向上推，直到被红父吸收）和情况四（旋转后原地还债）。

最后把删除修复的完整决策流程画成一张图，贴在脑子里：

这张图从左到右只有四层判断，但每一层都要同时留意“x 是左孩子还是右孩子”的镜像问题——代码里通常用两个对称分支处理，图形上则只要记住“旋转方向始终把兄弟转到 x 的对侧”即可。

4 完整代码：从结构到修复

前面所有配图，最终都要落成代码。这一节给出一个可以复制运行的 TypeScript/JavaScript 实现，采用教科书式的哨兵（NIL）写法，把“空指针”统一成一个黑色节点，代码会非常整洁。为了讲解方便，我们把代码拆成三块：第一块是节点结构与旋转，第二块是插入，第三块是删除。每一块后面紧跟逐行解读。

4.1 节点结构与旋转原语

先看节点与哨兵。颜色用布尔值表示：true 是红色，false 是黑色。每个节点除了键和颜色，还维护左孩子、右孩子、父节点三个指针：

const RED = true;
const BLACK = false;

class RBNode {
  constructor(key, color = RED) {
    this.key = key;        // 键
    this.color = color;    // 颜色：true 红 / false 黑
    this.left = null;      // 左孩子
    this.right = null;     // 右孩子
    this.parent = null;    // 父节点
  }
}

// 哨兵 NIL：所有空位共用同一个黑色节点
const NIL = new RBNode(null, BLACK);
NIL.left = NIL;
NIL.right = NIL;
NIL.parent = NIL;

// 创建节点并让它的三个指针都指向 NIL
function newNode(key, color = RED) {
  const n = new RBNode(key, color);
  n.left = n.right = n.parent = NIL;
  return n;
}

逐行看几个容易写错的地方。第一，颜色用布尔值而不是字符串，是因为修复代码里到处是“取反”和“比较”，布尔值写起来最省；第二，NIL 在类定义之后创建，创建完立刻把它的 left、right、parent 都指向自己，否则遍历到空位时会解引用空指针；第三，newNode 是唯一的新节点工厂，保证所有新节点的三个指针统一指向 NIL——如果忘记这一步，插入后的树会带着 null 指针到处跑，修复代码里的 x.parent.color 之类访问就会崩。

旋转是红黑树唯一的“结构手术”，左旋和右旋互为镜像。以左旋为例，它的输入是 x，要求 x 的右孩子 y 不是 NIL；旋转后 y 升到 x 的位置，x 变成 y 的左孩子，y 原来的左子树过继给 x 当右子树：

function rotateLeft(tree, x) {
  const y = x.right;              // y 是 x 的右孩子，旋转后成为新根
  x.right = y.left;               // y 的左子树过继给 x 当右子树
  if (y.left !== NIL) {
    y.left.parent = x;            // 同步更新过继子树的父指针
  }
  y.parent = x.parent;            // y 接管 x 原来的父节点
  if (x.parent === NIL) {
    tree.root = y;                // x 是根：y 成为新的根
  } else if (x === x.parent.left) {
    x.parent.left = y;            // x 是左孩子：父节点的左指针指向 y
  } else {
    x.parent.right = y;           // x 是右孩子：父节点的右指针指向 y
  }
  y.left = x;                     // x 降为 y 的左孩子
  x.parent = y;                   // x 的父指针指向 y
}

function rotateRight(tree, x) {
  const y = x.left;               // 镜像：y 是 x 的左孩子
  x.left = y.right;
  if (y.right !== NIL) {
    y.right.parent = x;
  }
  y.parent = x.parent;
  if (x.parent === NIL) {
    tree.root = y;
  } else if (x === x.parent.left) {
    x.parent.left = y;
  } else {
    x.parent.right = y;
  }
  y.right = x;
  x.parent = y;
}

旋转代码最容易写错的是“重新挂回父节点”那三行：旋转改变了子树的根，如果原根 x 不是整棵树的根，就必须把 x 的父节点对 x 的引用改成 y。很多实现 bug 都是只改了 x、y 和中间子树，忘了改 x.parent 的孩子指针。另一个高频错误是父指针没同步：改完孩子指针后，y.parent = x.parent 和 x.parent = y 必须成对出现，否则后续沿父链上溯时指针会断。

4.2 insert 与 insertFixup 逐行解读

插入分两段：insert 负责纯 BST 的定位与挂接，insertFixup 负责颜色修复，两个函数的分界非常干净。

function insert(tree, key) {
  const z = newNode(key, RED);       // 新节点染红：不破坏黑高
  let y = NIL;                       // y 将记录 z 的父节点
  let x = tree.root;                 // 从根出发找插入位置

  while (x !== NIL) {                // 标准 BST 查找
    y = x;
    x = key < x.key ? x.left : x.right;
  }

  z.parent = y;                      // 挂上父节点
  if (y === NIL) {
    tree.root = z;                   // 空树：z 直接成为根
  } else if (key < y.key) {
    y.left = z;                      // 挂在左孩子
  } else {
    y.right = z;                     // 挂在右孩子
  }

  insertFixup(tree, z);              // 修复可能出现的红-红冲突
}

insert 里没有任何颜色判断，它只回答“新键应该放在哪里”。注意 newNode 已经把 z 的 left、right、parent 都指向 NIL，所以循环结束后只需要设置 z.parent，孩子指针不用再动。这段代码还隐含了一个约定：重复键插入右侧，实现简单，且不影响正确性。

真正的重头戏是 insertFixup：

function insertFixup(tree, z) {
  // 只要父节点是红色，就存在红-红冲突
  while (z.parent !== NIL && z.parent.color === RED) {
    if (z.parent === z.parent.parent.left) {
      // 父节点是祖父的左孩子
      const uncle = z.parent.parent.right;

      if (uncle !== NIL && uncle.color === RED) {
        // 情况一：叔叔红 → 变色上溯
        z.parent.color = BLACK;        // 父染黑
        uncle.color = BLACK;           // 叔染黑
        z.parent.parent.color = RED;   // 祖父染红
        z = z.parent.parent;           // 冲突上移到祖父
      } else {
        // 叔叔黑（或 NIL）→ 看 z 的位置
        if (z === z.parent.right) {
          // 情况三（LR）：先左旋父，把折线掰直
          z = z.parent;
          rotateLeft(tree, z);
        }
        // 情况二（LL）：变色 + 右旋祖父
        z.parent.color = BLACK;
        z.parent.parent.color = RED;
        rotateRight(tree, z.parent.parent);
      }
    } else {
      // 镜像：父节点是祖父的右孩子
      const uncle = z.parent.parent.left;

      if (uncle !== NIL && uncle.color === RED) {
        // 情况一：同样变色上溯
        z.parent.color = BLACK;
        uncle.color = BLACK;
        z.parent.parent.color = RED;
        z = z.parent.parent;
      } else {
        if (z === z.parent.left) {
          // 情况三（RL）：先右旋父，再按情况二处理
          z = z.parent;
          rotateRight(tree, z);
        }
        // 情况二（RR）：变色 + 左旋祖父
        z.parent.color = BLACK;
        z.parent.parent.color = RED;
        rotateLeft(tree, z.parent.parent);
      }
    }
  }
  tree.root.color = BLACK;   // 根强制染黑，性质二收尾
}

逐行过一遍逻辑骨架。循环条件 z.parent.color === RED 就是“还有红-红冲突”的信号：父是红，z 自己也是红（新节点从红开始，且变色上溯时 z 指向被染红的祖父），冲突成立。进入循环后，第一个 if 判断父节点在祖父的哪一侧，这个判断本身没有算法含义，纯粹是为了找叔叔——父在左，叔叔就是祖父的右孩子；父在右，叔叔就是祖父的左孩子。找到叔叔后，一切分叉都由叔叔的颜色决定：

• 叔叔红 → 情况一：父、叔染黑，祖父染红，z = z.parent.parent 把冲突上移。注意这里没有旋转，树形不变；
• 叔叔黑 → 看 z 的位置：如果 z 是内侧孩子（LR/RL），先旋转父节点“掰直”，同时 z = z.parent 让 z 指向新的“父角色”；无论是否经过这次预旋转，最后都统一走情况二——把 z 的父染黑、祖父染红，旋转祖父。

情况三里 z = z.parent; rotateLeft(tree, z) 这两行是最容易看晕的地方：旋转前把 z 更新为旧父节点，旋转后旧父节点降为原 z 的左孩子，此时 z.parent 恰好是原 z——也就是旋转后的新父。于是后面 z.parent.color = BLACK 染的正是“新父”，z.parent.parent 就是祖父，旋转方向也是对的。这个“先更新 z 再旋转”的写法，本质是把 LR 问题的焦点从“冲突节点”转移到“将来要染黑的新根”上。

最后一行 tree.root.color = BLACK 无条件执行，对应 2.5 节的结论：情况一可能把红色一路推到根，根的父是 NIL（黑），循环不会自己处理，必须由这行强制收尾。由于根是所有路径的公共起点，把它染黑不会破坏黑高，永远安全。

4.3 deleteNode 与 deleteFixup 逐行解读

删除实现分三个层次：transplant 负责指针移植，deleteNode 负责 BST 删除并决定“要不要修”，deleteFixup 负责还清双黑。先看前两层：

function search(x, key) {
  while (x !== NIL && x.key !== key) {
    x = key < x.key ? x.left : x.right;
  }
  return x;
}

function transplant(tree, u, v) {
  // 用 v 顶替 u 的位置，v 可以是 NIL
  if (u.parent === NIL) {
    tree.root = v;              // u 是根：v 成为新根
  } else if (u === u.parent.left) {
    u.parent.left = v;
  } else {
    u.parent.right = v;
  }
  v.parent = u.parent;          // 同步父指针
}

function minimum(x) {
  while (x.left !== NIL) x = x.left;
  return x;
}

function deleteNode(tree, key) {
  const z = search(tree.root, key);
  if (z === NIL) return false;  // 键不存在

  let y = z;                    // y：真正被摘除的节点
  let yOriginalColor = y.color; // 记住原始颜色
  let x;                        // x：顶替 y 的节点，可能是 NIL

  if (z.left === NIL) {
    x = z.right;                // 情况一：右孩子顶替
    transplant(tree, z, z.right);
  } else if (z.right === NIL) {
    x = z.left;                 // 情况二：左孩子顶替
    transplant(tree, z, z.left);
  } else {
    y = minimum(z.right);       // 情况三：找后继
    yOriginalColor = y.color;
    x = y.right;
    if (y.parent === z) {
      x.parent = y;             // 后继是 z 的直接右孩子
    } else {
      transplant(tree, y, y.right); // 先把后继摘下来
      y.right = z.right;
      y.right.parent = y;
    }
    transplant(tree, z, y);     // 后继顶替 z 的位置
    y.left = z.left;
    y.left.parent = y;
    y.color = z.color;          // 继承 z 的颜色
  }

  if (yOriginalColor === BLACK) {
    deleteFixup(tree, x);       // 摘除的是黑节点才需要修复
  }
  return true;
}

这里有三个必须讲透的点。第一，为什么修复看 yOriginalColor 而不是 z 的颜色？ 当 z 有两个孩子时，物理摘除的是后继 y，z 只是换了个键、换了颜色；真正从树里消失、可能引发黑高缺口的只有 y。所以颜色判定必须在“摘除 y 之前”快照下来。第二，为什么 y.parent === z 分支要单独处理？ 因为如果后继就是 z 的右孩子，transplant(z, y) 之后 y.right 还指着旧 z.right（也就是 y 自己），必须提前把 x（y 的右孩子）的父指针指向 y，并跳过“先摘 y、再嫁接 z.right”的步骤，否则会出现自环。第三，为什么删除时 x 可能是 NIL 还能继续修复？ 因为 NIL 是全局哨兵，它有 parent 指针，x.parent 仍然可用，双黑 NIL 照常参与循环。

修复主函数 deleteFixup 和插入修复一样是 while 循环，只是分支更细：

function deleteFixup(tree, x) {
  // x 不是根且是黑色，说明它还背着双黑
  while (x !== tree.root && x.color === BLACK) {
    if (x === x.parent.left) {
      // x 是左孩子，兄弟在右侧
      let w = x.parent.right;

      if (w.color === RED) {
        // 情况一：兄弟红 → 先转化为黑兄弟
        w.color = BLACK;
        x.parent.color = RED;
        rotateLeft(tree, x.parent);
        w = x.parent.right;      // 新兄弟必为黑色
      }

      if (w.left.color === BLACK && w.right.color === BLACK) {
        // 情况二：侄子全黑 → 把债上推
        w.color = RED;
        x = x.parent;
      } else {
        if (w.right.color === BLACK) {
          // 情况三：近侄红、远侄黑 → 转情况四
          w.left.color = BLACK;
          w.color = RED;
          rotateRight(tree, w);
          w = x.parent.right;
        }
        // 情况四：远侄红 → 旋转收尾
        w.color = x.parent.color;  // 兄弟继承父色
        x.parent.color = BLACK;    // 父染黑
        w.right.color = BLACK;     // 远侄染黑
        rotateLeft(tree, x.parent);
        x = tree.root;             // 直接结束循环
      }
    } else {
      // 镜像：x 是右孩子，兄弟在左侧
      let w = x.parent.left;

      if (w.color === RED) {
        w.color = BLACK;
        x.parent.color = RED;
        rotateRight(tree, x.parent);
        w = x.parent.left;
      }

      if (w.right.color === BLACK && w.left.color === BLACK) {
        w.color = RED;
        x = x.parent;
      } else {
        if (w.left.color === BLACK) {
          w.right.color = BLACK;
          w.color = RED;
          rotateLeft(tree, w);
          w = x.parent.left;
        }
        w.color = x.parent.color;
        x.parent.color = BLACK;
        w.left.color = BLACK;
        rotateRight(tree, x.parent);
        x = tree.root;
      }
    }
  }
  x.color = BLACK;   // 吸收残余双黑，包括“双黑上推到根”的情况
}

对照 3.3 到 3.6 的四张图读这段代码：情况一旋转后 w = x.parent.right 刷新兄弟指针，这是新手最容易漏的一行——旋转改变了兄弟的位置，不刷新就会把旧兄弟当成新兄弟继续判断；情况二把 x = x.parent，对应“债上推”；情况三旋转后同样刷新 w；情况四做完旋转后直接把 x 指向根，强制退出，因为双黑已经原地还清。循环外的 x.color = BLACK 负责两个收尾场景：循环因为 x 变成根而退出时，把根上的残余双黑吸收；循环因为 x 变成红色而退出时，把红节点染黑还债。

4.4 用验证函数兜底

红黑树代码的正确性光靠肉眼不够，最好写一个“裁判”函数，在每次插入、删除后检查五条性质：

function check(tree) {
  let problems = [];
  let refBlack = -1;

  function walk(n, blackCount) {
    if (n === NIL) {
      // 叶子：黑高必须和第一条路径一致
      if (refBlack === -1) refBlack = blackCount + 1;
      else if (blackCount + 1 !== refBlack) problems.push("黑高不一致");
      return;
    }
    if (n.color === RED) {
      if (n.left.color === RED || n.right.color === RED) {
        problems.push("红-红相连：" + n.key);
      }
    }
    const next = blackCount + (n.color === BLACK ? 1 : 0);
    walk(n.left, next);
    walk(n.right, next);
  }

  if (tree.root.color !== BLACK) problems.push("根不是黑色");
  walk(tree.root, 0);
  return problems;
}

const tree = { root: NIL };
for (const key of [10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70]) {
  insert(tree, key);
}
console.log(check(tree));            // 期望输出 []

for (const key of [15, 2, 40]) {
  deleteNode(tree, key);
}
console.log(check(tree));            // 期望输出 []

这个验证函数递归遍历整棵树：每到红色节点检查孩子不是红；每到 NIL 检查累计黑节点数（加上 NIL 自己）与第一条路径一致；最后单独检查根。把 2.6 节的插入序列跑进去，check 返回空数组，说明我们手绘的最终树和代码实现完全一致。删除三个键后再跑一次，同样为空。“配图推演 + 代码验证”双轨对照，是学习红黑树最不容易走偏的方式：图负责给直觉，代码负责给确定性。

4.5 常见 bug 清单与调试顺序

红黑树实现是“看着简单、写错一片”的典型。把最常见的错误集中列出来，写代码时逐条自查，能省下大量调试时间。

第一类：指针类错误。 旋转之后父指针没有成对更新；transplant 忘了处理“u 是根”的分支；deleteNode 里 y.parent === z 的分支漏掉 x.parent = y，导致自环。这类错误的表现非常隐蔽——树看起来还在，但沿父链上溯时会走进死循环或访问到错误节点。调试办法是写一个“父指针一致性”检查：递归遍历全树，验证每个非根节点的父节点确实指向它。

第二类：颜色类错误。 最常见的三个：忘了最后把根染黑（根变成红色）；情况一漏判“叔叔是 NIL 也属于黑叔叔”；删除循环条件写成 while (x.color === BLACK) 而忘了 x !== tree.root，导致 x 变成根后还继续访问 x.parent，解引用 NIL 崩溃。颜色错误的好处是容易被 check 函数抓住：根红、红-红、黑高不一致，三个症状对应三类错误。

第三类：分支顺序错误。 插入修复必须先判叔叔颜色再判 z 的位置；删除修复必须先判兄弟颜色，再判侄子颜色，最后区分近侄和远侄。把顺序写反（比如先看 z 是左孩子还是右孩子）不会立刻报错，但会在某些输入下漏走正确的修复路径，留下一个“偶尔才坏”的树——这种 bug 最难抓。

第四类：旋转方向错误。 LL 对应右旋祖父，RR 对应左旋祖父；LR 先左旋父再右旋祖父，RL 先右旋父再左旋祖父。镜像写反会让树形越修越歪。建议在实现里保留 2.6 节的序列作为回归测试，每次插入后调用 check，任何旋转方向错误都会在几步之内被黑高不一致暴露出来。

最后给一个推荐的调试顺序：先跑插入序列并 check，再跑删除序列并 check，最后用随机键做上千次随机插入、删除混合操作，每步都 check。如果随机测试全绿，你的实现基本可以放心了。红黑树的正确性不是“看着对”，而是“验证过”。

5 复杂度与工程对比：红黑树凭什么“又稳又便宜”

代码写完，回到一个贯穿全系列的问题：红黑树的插入、删除到底有多贵？答案藏在两个数字里：插入最多 2 次旋转，删除最多 3 次旋转。这两个数字是红黑树工程价值的根基，也是面试最爱问的结论，值得把推导过程讲透。

5.1 旋转次数：为什么是“最多 2 次”和“最多 3 次”

先算插入。插入修复的每一轮循环只可能做三件事之一：

• 情况一：纯变色，零旋转，冲突上移，循环继续；
• 情况二：一次旋转加变色，冲突就地解决，循环终止；
• 情况三：先转一次掰直、再按情况二转一次，共两次旋转，循环终止。

情况一可以连续发生很多轮（最坏 O(log n) 轮），但每一轮都不旋转；而情况二、三一旦出现，本轮必定终止。因此整次插入的旋转次数只可能来自“最后一轮”：情况二贡献 1 次，情况三贡献 2 次，纯情况一贡献 0 次。结论：插入旋转次数 ≤ 2。

再看删除。删除修复的轮次构成要复杂一点，但可以逐类计数：

• 情况二：纯变色，零旋转，把双黑上推，循环继续。它可以连续发生很多轮；
• 情况一：一次旋转，把红兄弟变成黑兄弟。关键性质是：情况一同时把 x 的父节点染成红色，所以紧接着无论走情况二（x 上移到红父后循环立即退出）还是情况三、四，都不会再产生第二次“红兄弟”局面——情况一在一整次删除中至多出现一次；
• 情况三：一次旋转，把局面转化为情况四；
• 情况四：一次旋转，原地还债，循环终止。

把最坏组合排一下：情况一（1 次旋转）→ 情况二（0 次）→ 再次碰到情况一？不可能，理由如上；情况一 → 情况三（1 次）→ 情况四（1 次），共 3 次；或者纯情况二链条后接情况四（1 次）。所以删除旋转次数 ≤ 3。更精确地说，删除修复里“连续变色的轮次”可以多达 O(log n)，但旋转永远被限制在常数 3 以内——这正是红黑树与 AVL 最本质的差异。

作为对照，第 10 篇讲过：AVL 删除一次可能让多个祖先接连失衡，最坏需要 O(log n) 次旋转。红黑树把“最坏旋转次数”压缩成常数，代价是树高上界从 AVL 的约 1.44·log₂n 放宽到 2·log₂(n+1)。用一点点树高，换来写入路径上几乎恒定的结构修复成本，这就是红黑树的设计哲学。

5.2 为什么总体仍是 O(log n)

把两个结论合起来：红黑树的高度 ≤ 2·log₂(n+1)（第 11 篇已证）；查找、插入、删除的 BST 阶段都是沿高度行走，O(h) = O(log n)；修复阶段，插入最多 O(log n) 轮变色加常数次旋转，删除最多 O(log n) 轮变色加常数次旋转，每轮都是 O(1) 的指针或颜色操作。于是三个操作的最坏时间复杂度全部是 O(log n)。

这里要提醒一个常被误解的点：说“插入最多 2 次旋转”，不等于“插入只需要常数时间”。情况一的变色上溯最多可以走 O(log n) 层，所以插入的最坏时间仍然是 O(log n)，只是其中昂贵的旋转被压到了常数次。变色本身极其便宜——只改一个颜色位，不改任何指针——所以实际常数很小。这也是为什么“红黑树比 AVL 更适合写入”这句话的底气不是“次数少”，而是“贵的动作少”。

5.3 与 AVL 的终极对比（第 10 篇的延续）

第 10 篇我们详细对比过 AVL 的插入与删除，这里把红黑树加入，做一个最终的横向对比：

对比维度	AVL 树	红黑树
平衡标准	任意节点左右子树高度差 ≤ 1	最长路径 ≤ 2 × 最短路径
树高上界	约 1.44·log₂(n+2)	2·log₂(n+1)
查找性能	略快：树更矮，比较更少	略慢：树可能高约 1.4 倍
插入旋转	至多 2 次，但每轮都查高度	至多 2 次，变色为主
删除旋转	最坏 O(log n) 次	至多 3 次
修复成本	写入后沿祖先重算平衡因子	变色上溯/下推，旋转稀缺
额外存储	高度或平衡因子（通常一个整数）	颜色（1 位即可）
适用负载	读多写少、构建后几乎只查	通用场景、写多或读写均衡
典型出场	内存索引、只读字典	Java TreeMap、C++ std::map、Linux 内核

这张表的读法不是“谁赢谁输”，而是“谁更适合什么”：如果你的数据构建一次、之后十万次查找，AVL 的矮树身能让每次查找快那么一点点；如果你的系统每秒几十万次插入删除、查找只占一半，红黑树把旋转成本锁死在常数次，整体吞吐往往更高。标准库面对的是未知负载，于是普遍选择了红黑树这个“均衡型选手”。第 10 篇说过 AVL 不是输给红黑树，而是输给了“通用”二字，到这里结论闭环了。

6 红黑树与 2-3-4 树的对应关系：修复动作的“后台真相”

如果把红黑树的所有修复动作都背下来，你会发现它们像一套没有剧本的舞台戏：变色、旋转、上溯、下推，各演各的，很难记住。但一旦把红黑树“翻译”成 2-3-4 树，整套剧本立刻有了主线——红黑树是 2-3-4 树的二叉树编码，插入、删除的每一个修复动作，都是 2-3-4 树里“节点分裂”“节点合并”“键的借用”的投影。

2-3-4 树是多叉搜索树：每个节点可以装 1 到 3 个键，相应地有 2 到 4 个孩子；所有叶子在同一层，所以它天生完美平衡。红黑树用“黑色 + 红色”把它编码成二叉树：黑色节点是 2-3-4 树的“正式节点”，红色节点是“同一个逻辑节点里多出来的键”。一个装了 3 个键的 4-节点，在红黑树里就是“一个黑节点 + 两个红孩子”：

这个对应关系像一把万能钥匙，能解释红黑树几乎所有“为什么”：

• 为什么新节点默认红色？ 往 2-3-4 树里插键，是先塞进现有节点，不新建层；对应到红黑树，新键就是现有黑节点旁边的一个红“邻居”。只有当节点已经满员（3 个键）时，才需要分裂；
• 为什么“叔叔是红”就变色？ 叔叔红意味着祖父是一个满员 4-节点（黑 + 两个红）。再塞一个键就超过 4 个了，必须分裂：中间键上移、左右键各成新节点。对应到红黑树，就是父、叔染黑（各自成独立黑节点），祖父染红（中间键上移一层）；
• 为什么“叔叔是黑”就旋转？ 叔叔黑意味着祖父只是 2-节点或 3-节点，还有空位，根本不需要分裂；但二叉编码的形态可能“歪了”，旋转只是把二叉树的形状摆正，让编码保持“黑 + 红”的规范形态；
• 为什么红节点不能有红孩子？ 因为 2-3-4 节点最多 3 个键，对应黑 + 最多 2 个红；连续两个红连接意味着“黑 + 红 + 红 + 红”共 4 个键，超过 4 阶容量；
• 为什么每条路径黑高相同？ 因为 2-3-4 树所有叶子同层，而黑色节点代表真正的“层”，红节点是层内的夹层，所以黑高天然一致。

删除修复同样能翻译。双黑节点在 2-3-4 树里对应一个“缺了一个键、需要合并或借键”的节点：情况二“兄弟黑且侄子全黑”对应兄弟节点合并（把欠的键向上传递）；情况三、四对应向兄弟借键（把兄弟的键旋转过来，颜色随之调整）。特别是情况四“远侄红”，在 2-3-4 树里就是“兄弟有富余的键可以借”，借完之后节点恢复满员，红黑树也随之恢复平衡：

有了 2-3-4 树这层“后台真相”，前面所有的案例都不再是孤立的背题素材，而是一个连续故事：插入是“往节点里塞键，满了就分裂”，删除是“节点缺键，先合并、再借键”。红黑树的颜色只是这个故事在二叉树上的投影。这个视角也为下一篇埋下伏笔：2-3-4 树本身就是 B 树家族的一员（4 阶 B 树），把“一个节点装多个键”推广到磁盘页，就得到了数据库索引的基石——B 树。树的进化，从来不是凭空发明，而是一步步把平衡的思想搬到更大的舞台上。

6.1 左倾红黑树：把编码规则收紧的变体

通用红黑树允许红色节点既当左孩子又当右孩子，所以同一个 2-3-4 树可以对应多种红黑树编码。Robert Sedgewick 提出的左倾红黑树（Left-Leaning Red-Black Tree，LLRB） 做了一件事：额外规定“红色节点只能作为左孩子”，把编码规则锁死成一对一。这个约束的代价是插入、删除时情况一和情况二可以合并简化，代码更短；代价是树形被强制左倾，某些操作的旋转次数会比通用红黑树略多一点。它特别适合教学——很多教材用 LLRB 讲红黑树与 2-3-4 树的对应，就是因为“红孩子只能向左”让 3-节点只有一种画法，不容易产生歧义。

理解 LLRB 还有一层实用价值：面试时如果被问到“红黑树和 2-3-4 树为什么不是完全等价”，答案就在这里——等价关系成立的前提是约定“红色孩子只能在哪一侧”。通用红黑树里红色孩子两侧都可出现，对应 2-3-4 树时一个 3-节点既可以画成“黑左红”，也可以画成“黑右红”，所以是“多对一”；LLRB 加上方向约定后才变成“一一对应”。本篇所有配图都采用通用红黑树，但你完全可以用 LLRB 的视角重新读一遍：凡是“红孩子在右侧”的形态，在 LLRB 里会先被旋转成左侧再处理，逻辑主线不变。

顺便说一句，红黑树家族并不止这两种：还有为并发场景设计的变体、与跳表竞争的随机化结构等。但万变不离其宗——颜色标记的本质，是把“多键节点”编码进二叉树的额外维度。掌握了这条主线，任何变体都能在半小时内看懂。

7 动手体验：在可视化实验室里亲手修复

配图看懂、代码跑通之后，还差最后一步：亲手“摸”一遍修复过程。本系列的搜索算法可视化实验室支持插入、删除与多种树形切换——如果实验室已经支持红黑树，请把本篇的序列 [10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70] 原样插进去，对照 2.6 节每一步的树形和颜色，你会看到每一个“情况一”的变色上溯、每一次“情况三”的双旋，都和纸面推演完全吻合。然后试着从实验树里删除 1、5、2，观察“兄弟是红”时的旋转和“黑兄弟”时的变色上推。手眼并用，是记住这七种修复情形最有效的办法。

建议在实验室里做两个对照实验。第一个是“升序灾难实验”：连续插入 1 到 30，观察红黑树如何抵抗有序输入的退化——如果实验室提供“裸 BST”对照模式，你会看到同样的输入在裸 BST 里长成一根 30 层的链，在红黑树里却始终维持在 8 层左右。第二个是“修复动作统计实验”：连续插入 50 个随机键，一边操作一边数变色和旋转的次数，你会发现旋转通常只有个位数，而变色动辄几十次——这就是第 5 节“旋转是稀缺资源”的现场版。做完这两个实验，红黑树的“近似平衡 + 低维护成本”就不再是抽象结论，而是你亲眼看到的数字。

如果没有可视化工具，也可以用一个“穷举法”做心理验证：随机挑一棵合法的红黑树，手动删除一个黑节点，然后反复问自己三个问题——兄弟是什么颜色？侄子们是什么颜色？这一步是变色还是旋转？把三个问题的答案对着速查表查一遍，修复动作自然就出来了。

8 插入/删除情况速查表

插入修复速查表（前提：新节点 z 为红，父 p 为红，祖父 g 为黑）：

情况	判定条件	修复动作	旋转次数
情况一	叔叔 u 为红	p、u 染黑，g 染红，z 上移到 g	0
情况二	u 为黑，z 与 p、g 成直线（LL/RR）	p 染黑，g 染红，旋转 g	1
情况三	u 为黑，z 与 p、g 成折线（LR/RL）	先旋转 p 掰直，再按情况二处理	2

删除修复速查表（前提：x 为双黑，w 为 x 的兄弟）：

情况	判定条件	修复动作	旋转次数
情况一	w 为红	w 染黑，父染红，旋转父，刷新 w	1
情况二	w 为黑，两个侄子都黑	w 染红，x 上移到父	0
情况三	w 为黑，近侄红、远侄黑	近侄染黑，w 染红，旋转 w，刷新 w	1
情况四	w 为黑，远侄红	w 继承父色，父染黑，远侄染黑，旋转父	1

两张表加起来正好七种情形。记住两个总开关：插入看叔叔，删除看兄弟；再记住两个“必然”：情况一和情况三都不会直接结束，前者把冲突上移，后者把问题转给情况四。

9 自测题

10 下一篇预告

红黑树把平衡的成本压到了极致，但它依然是一棵“活在内存里的树”：每个节点都靠指针相连，读一个键要沿指针跳很多次，而指针的“跳转成本”在磁盘面前微不足道——磁盘真正怕的是随机读。当数据量大到必须放在磁盘上时，红黑树的高度虽然只有 log₂n 量级，却可能对应几十次随机磁盘 I/O，而一次随机 I/O 的成本是内存访问的十万倍以上。怎么办？答案是让一个“节点”多装一些键、多带一些孩子，把树的高度从 log₂n 压到 log_m n——这就是 B 树。

下一篇，《树系列第 13 篇：从内存到磁盘——为什么需要 B 树》，我们会看到 2-3-4 树如何升级成通用 B 树，理解“磁盘页 = 树的节点”这个核心等式，并亲手搭建一棵支持分裂与合并的 B 树。红黑树的旅程在这里画上句号，但树的进化还在继续。第 13 篇见！