CLRS 红黑树删除详解：RB-DELETE 与 RB-DELETE-FIXUP 全案例解析（《算法导论》第 3 版 13.4 节习题全解）-平芜编程栈

文档
教程
教育

【免费下载链接】CLRS

📚 Solutions to Introduction to Algorithms Third Edition

项目地址：https://gitcode.com/gh_mirrors/clr/CLRS

本文围绕《算法导论》第 3 版（Introduction to Algorithms, Third Edition）第 13.4 节“Deletion（删除）”展开，完整梳理红黑树删除的两阶段流程——RB-DELETE结构性删除与RB-DELETE-FIXUP四案例修复——并逐题剖析本仓库 docs/Chap13/13.4.md 收录的 13.4-1 ~ 13.4-7 全部七道习题。读者将掌握：为什么删除修复后根节点必为黑色、双红节点冲突如何被一次着色消除、哨兵T.nil在哪些行被读写、Figure 13.7 各案例变换前后的黑高守恒验证，以及“先插入再删除同一节点”为何不一定还原原树。所有结论均可在仓库的配套图示（docs/img）与相关章节习题（如 docs/Chap17/Problems/17-4.md）中交叉印证。

红黑树是 CLRS（Cormen、Leiserson、Rivest、Stein）《算法导论》第 3 版第 13 章的核心主题，其删除操作远比插入复杂：先通过RB-DELETE完成二叉搜索树的嫁接（RB-TRANSPLANT），再通过RB-DELETE-FIXUP处理可能被破坏的红黑性质。本仓库的 docs/Chap13/13.4.md 以习题解答形式给出了七个关键论断，本文按“流程回顾 → 七题精解 → 案例黑高守恒 → 实战反例”的组织方式展开，并将每道题的结论映射回教材中的行号、案例编号与图号，方便对照原书同步阅读。

一、删除流程回顾：RB-DELETE 与 RB-DELETE-FIXUP 的分工

在深入七道习题之前，先厘清教材中红黑树删除的完整结构。红黑树删除分两个阶段：

RB-DELETE(T, z)：先按普通二叉搜索树的逻辑删除节点z，用RB-TRANSPLANT完成子树嫁接。若被删节点y为黑色，则记下替代者x（y的右孩子，可能为哨兵T.nil），并将额外的一重“黑色”转移到x上，随后调用RB-DELETE-FIXUP(T, x)进行修复。
RB-DELETE-FIXUP(T, x)：通过一个while循环配合四种案例（case 1 ~ case 4，对应教材 Figure 13.7）旋转、变色，把x代表的额外黑色沿树向上传递或消除，最终恢复红黑树五条性质。其中case 2 是非终止案例，可能沿树向上反复执行；case 1、case 3 是终止案例，执行一次旋转/变色后循环即结束。

这一“删除黑色节点 → 用额外黑色修复”的机制，与第 13.3 节RB-INSERT的“插入红色节点 → 用双红冲突修复”形成对称。仓库 docs/Chap13/13.3.md 中 13.3-5 的解答表明，插入修复后树中至少保留一个红色节点；而删除修复则恰好相反，其目标之一是把可能变成红色的根重新涂黑（见下文 13.4-1）。两套修复过程可结合 docs/Chap17/Problems/17-4.md（红黑树重构的摊还分析）进一步理解：该题 b 问明确列出“对于RB-DELETE，case 1 与 case 3 是终止的”，与本节各案例的终止性判断完全一致。

二、13.4-1：为什么执行 RB-DELETE-FIXUP 之后根节点必为黑色？

原题：证明执行RB-DELETE-FIXUP之后，树的根节点一定是黑色。

这实际上是性质 2（根为黑色）的恢复保证。解答按四种案例逐一说明：

Case 1：案例 1 通过旋转变色转化为案例 2、3、4 之一，若循环在此终止，则必然落到后续案例，而最终案例都会把根（新的x）涂黑。
Case 2：若案例 2 使循环终止，则此时的新x（子树根）被设置为黑色。
Case 3：案例 3 通过旋转变色转化为案例 4，由案例 4 收尾。
Case 4：案例 4 是终止案例，循环结束时把新的x设置为黑色。

归纳可见，RB-DELETE-FIXUP的四条出口路径（无论经由哪个案例、经历多少次循环）最终都会走到“把x染黑”这一步。而x沿着x.p指针逐层上移，一旦x成为根，染黑x即染黑根；即便x未成为根，根也可能因 case 1 的祖父变色而短暂变红，但案例链的终点必然再次将其置黑。因此删除修复结束后，树根一定是黑色，性质 2 得以保持。

三、13.4-2：x 与 x.p 同时为红时，一次调用如何恢复性质 4？

原题：证明若在RB-DELETE中x与x.p都是红色，则调用RB-DELETE-FIXUP(T, x)会恢复性质 4（红节点的孩子必为黑色）。

解答的关键在于指出“双红”出现的唯一位置与唯一处理方式：

唯一性：x与x.p同时为红，只可能发生在RB-DELETE第 9 行的else分支中（即y有两个孩子、x取y.right的情形）。
兄弟必黑：因为删除发生在红黑树中，y.p的另一个孩子（经第 14 行RB-TRANSPLANT后成为x的兄弟）必然是黑色——否则性质 4 早已被破坏。因此x是x.p下唯一的红色孩子。
循环立即退出：RB-DELETE-FIXUP的while循环条件是“x非根且x为黑色”（教材伪代码中x != T.root与x.color == BLACK）。由于x此时是红色，循环条件立即被违反，直接执行循环体之外的着色语句x.color = BLACK，一次赋值即消除双红、恢复性质 4。

这一论证非常简洁：双红情况下修复函数根本不需要进入任何案例分支，只需一行“把x染黑”即可。它也从侧面说明，删除修复的核心工作集中在“x为黑色而路径黑高失衡”的场景，而“红色x”反而是最容易被治愈的情况。

四、13.4-3：依次插入 41, 38, 31, 12, 19, 8 后，再依次删除 8, 12, 19, 31, 38, 41

原题：习题 13.3-2 中你得到了把键41, 38, 31, 12, 19, 8依次插入空树所得的红黑树。现在请给出按顺序8, 12, 19, 31, 38, 41依次删除这些键所得的红黑树。

本题是删除操作最直观的“纸上演练”，与 13.3-2 的插入演练首尾呼应（插入过程图示见 docs/img 下的13.3-2-1.png~13.3-2-6.png，删除过程图示见13.4-3-1.png~13.4-3-7.png）。逐步结果如下：

初始树（13.3-2 插入六键后的最终形态）：

删除 8 后：8 是叶节点，且其兄弟与父节点颜色满足可直接删除条件，树形收缩，红黑性质保持：

删除 12 后：

删除 19 后：19 有一个孩子，删除时需将其子树嫁接上来，可能触发一次旋转变色：

删除 31 后：

删除 38 后：此时树已收缩至两节点，删除后仅剩根：

删除 41 后：删除最后一个键，树变为空：

值得注意：删除顺序刻意采用了与插入相反的次序。虽然最终树被清空，但每一步中间形态并不只是插入过程的简单“逆放”——因为RB-DELETE修复案例与RB-INSERT修复案例并不一一对偶（插入是 case 1 上移、case 2/3 旋转终止；删除是 case 2 上移、case 1/3/4 旋转终止）。读者可对照 docs/Chap13/13.3.md 中 13.3-2 的插入序列，逐一核对两张图示序列中黑高与红节点分布的变化，体会删除修复独有的“兄弟节点分支”逻辑。

五、13.4-4：RB-DELETE-FIXUP 在哪些行会读写哨兵 T.nil？

原题：RB-DELETE-FIXUP的代码中，可能在哪些行检查或修改哨兵T.nil？

哨兵T.nil是红黑树中所有空指针统一指向的黑色外部节点。删除场景下它可能成为x本身，解答给出两处关键位置：

当被删节点y没有孩子时，x = T.nil，此时会检查RB-DELETE-FIXUP的第 2 行（教材伪代码中while x != T.root and x.color == BLACK之后的w = x.p.right等取兄弟操作）。由于x是T.nil，x.p仍指向其父，取兄弟、比较颜色等读写操作都会触及哨兵。
当删除的恰是根节点时，x = T.nil且此时x即新的根，则第 23 行会把x染黑——也就是把哨兵染黑。这既保证了空树的根（哨兵）为黑色，也呼应 13.4-1 的结论：修复结束时根必黑。

这一问提醒我们：哨兵不是“不参与逻辑的占位符”，在删除黑色叶子节点或删除根节点这两条边界路径上，RB-DELETE-FIXUP会直接以T.nil为对象进行读（取兄弟、比较颜色）与写（染黑）操作。它与 13.3-4 的结论（RB-INSERT-FIXUP永不把T.nil染红，见 docs/Chap13/13.3.md）形成互补：插入侧保证哨兵不“变红”，删除侧则允许哨兵被“染黑”且这正是保持性质 2/5 所必需的。

六、13.4-5：Figure 13.7 各案例变换前后的黑高计数验证

原题：对 Figure 13.7 的每个案例，给出从所示子树根到各子树 $\alpha, \beta, \ldots, \zeta$ 的黑节点计数，并验证变换前后每个计数保持不变。当节点颜色属性为 $c$ 或 $c'$ 时，用记号 $\text{count}(c)$、$\text{count}(c')$ 符号化计数。

黑高守恒是红黑树旋转/变色操作合法性的核心判据——任何案例只有在不改变任意根到叶子路径的黑节点数时，才能保证性质 5。解答约定“计数包含根（若根为黑色）”，四案例结果如下：

案例	子树	变换前计数	变换后计数	结论
Case 1	$\alpha, \beta, \ldots, \zeta$ 全部子树	2	2	不变（纯变色，无旋转）
Case 2	$\alpha, \beta$	$1 + \text{count}(c)$	$1 + \text{count}(c)$	不变
Case 2	其余子树（$\gamma$ 及以下）	$2 + \text{count}(c)$	$1 + \text{count}(c)$	减少 1，由`x`代表额外一重黑色来弥补
Case 3	$\epsilon, \zeta$	$2 + \text{count}(c)$	$2 + \text{count}(c)$	不变
Case 3	其余子树	$1 + \text{count}(c)$	$1 + \text{count}(c)$	不变
Case 4	$\alpha, \beta$	$1 + \text{count}(c)$	$2 + \text{count}(c)$	增加 1（此前`x`携带额外黑色）
Case 4	$\gamma, \delta$	$1 + \text{count}(c) + \text{count}(c')$	$1 + \text{count}(c) + \text{count}(c')$	不变
Case 4	$\epsilon, \zeta$	$1 + \text{count}(c)$	$1 + \text{count}(c)$	不变

对表中两处“非守恒”需要特别理解：

Case 2 的减少由x补足：案例 2 把x的兄弟染红、x.p染黑并把x上移到父位置，导致除 $\alpha, \beta$ 外的子树黑计数减少 1。这一缺口由“x继续代表一重额外黑色”来承载——这正是删除修复中“额外黑色沿树向上传递”的机制，与 17.4 题 g 问（RB-DELETE-FIXUP每次调用的摊还结构修改次数为 $O(1)$，见 docs/Chap17/Problems/17-4.md）使用的正是 case 2 这种非终止上移。
Case 4 的增加吸收x的额外黑色：案例 4 是终止案例，通过旋转变色把根染黑，使 $\alpha, \beta$ 的黑计数增加 1，恰好吸收掉此前x携带的额外黑色，于是整棵树的黑高完全恢复，修复过程结束。

这两处一“减”一“增”的对称，是理解RB-DELETE-FIXUP正确性证明（即“循环不变式：以x为根的子树多一重额外黑色”）的关键。

七、13.4-6：Skelon 与 Baron 教授的担忧为何不成立？

原题：Skelton 和 Baron 两位教授担心，在RB-DELETE-FIXUP的案例 1 开始时，x.p可能不是黑色。如果教授们是对的，那么第 5–6 行（x.p变黑、w变黑、祖父变红的操作）就是错误的。请证明案例 1 开始时x.p必为黑色。

解答的逻辑非常直接：

案例 1 开始时，算法已把w设置为x的兄弟节点。
第 4 行检查w.color == RED（案例 1 的进入条件）成立。
若x.p（x与w的共同父节点）也是红色，则父节点与红色兄弟节点相邻——这直接违反性质 4（红节点的两个子节点必须为黑色）。

因此，只要进入案例 1，x.p必然为黑色，否则树在删除之前就已不合法。教授们的担忧不成立，第 5–6 行的变色操作（把w染黑、x.p染红）建立在x.p为黑的前提上，是安全且正确的。这道题本质上是性质 4 的一个“反证法”应用：案例 1 的进入条件本身就排除了父红兄弟红的情形。

八、13.4-7：插入一个节点后立即删除，树还和原来一样吗？

原题：假设节点x先被RB-INSERT插入红黑树，随后立即被RB-DELETE删除。所得红黑树与初始红黑树相同吗？说明理由。

答案：不一定相同。这是因为RB-INSERT与RB-DELETE的修复过程都可能触发旋转（rotation），而旋转会改变树的拓扑结构。插入时为了消除双红冲突进行的旋转，并不会在删除该节点时被“逆转”回来——RB-DELETE删除节点后，修复流程是根据新树的结构选择案例，与当初插入时的旋转路径毫无关联。因此，即使键的集合与最终黑高不变，树的形状（父子关系、子树归属）也可能与初始形态不同。

仓库图示给出了两个具体反例：

示例 1：初始为某种形态的树，插入键1后触发修复，删除1后树形与初始不同：

示例 2：另一初始形态，同样插入并删除1，最终树形与初始不同：

两个示例的共同点：插入1时由于叔叔节点为红色，RB-INSERT-FIXUP的 case 1 会把祖父染红、父与叔染黑，并让z上移两代继续检查，随后可能触发旋转使树形改变；而删除1时节点已因旋转改变位置，删除修复依据的是新结构，不会“撤销”插入时的旋转。结论：插入再删除同一键，键集合虽然还原，但树的结构不保证还原。这一特性与二叉搜索树不同（普通 BST 删除叶子通常可精确还原），也是红黑树这类自平衡树在工程实现（如 C++std::map、Linux 内核、JavaTreeMap）中值得注意的行为。

九、总结：删除修复的正确性骨架与仓库延伸阅读

把七道习题串起来，可以得到RB-DELETE-FIXUP正确性的完整骨架：

终止与根黑（13.4-1）：四条案例出口最终都把根染黑，性质 2 恒成立。
双红快速治愈（13.4-2）：红色x直接染黑即可恢复性质 4，无需进入案例分支。
全流程演练（13.4-3）：六键依次删除的逐步树形，验证删除修复各案例的真实触发路径。
哨兵边界（13.4-4）：x = T.nil的两条边界路径（删叶子、删根）分别在修复的第 2 行与第 23 行读写哨兵。
黑高守恒（13.4-5）：四案例的旋转/变色均保持各根到叶子路径的黑计数不变（case 2 的缺口由额外黑色承载、case 4 的增量吸收额外黑色）。
案例 1 前提自洽（13.4-6）：w.color == RED本身排除了x.p为红，性质 4 保证变色操作安全。
非对称不可逆（13.4-7）：旋转导致“插入+删除同一键”不保证还原树形。

若希望进一步研究删除修复的复杂度与摊还行为，可延伸阅读仓库中的 docs/Chap17/Problems/17-4.md（红黑树重构的摊还分析，含 case 终止性分类与势函数证明）；若关注删除后维护附加属性，可参考 docs/Chap13/Problems/13-2.md（如何在RB-DELETE中维护T.bh黑高属性）与 docs/Chap14/14.3.md（区间树对删除操作的增强）。整个第 13 章的插入、旋转、删除三节解答分别位于 docs/Chap13/13.1.md、docs/Chap13/13.2.md、docs/Chap13/13.3.md，配合本文所在的 docs/Chap13/13.4.md，可构成红黑树完整的学习闭环。