文档教程教育【免费下载链接】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中交叉印证。红黑树是 CLRSCormen、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为黑色则记下替代者xy的右孩子可能为哨兵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-DELETEcase 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-2x 与 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-4RB-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.nilx.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-5Figure 13.7 各案例变换前后的黑高计数验证原题对 Figure 13.7 的每个案例给出从所示子树根到各子树 $\alpha, \beta, \ldots, \zeta$ 的黑节点计数并验证变换前后每个计数保持不变。当节点颜色属性为 $c$ 或 $c$ 时用记号 $\text{count}(c)$、$\text{count}(c)$ 符号化计数。黑高守恒是红黑树旋转/变色操作合法性的核心判据——任何案例只有在不改变任意根到叶子路径的黑节点数时才能保证性质 5。解答约定“计数包含根若根为黑色”四案例结果如下案例子树变换前计数变换后计数结论Case 1$\alpha, \beta, \ldots, \zeta$ 全部子树22不变纯变色无旋转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-6Skelon 与 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.px与w的共同父节点也是红色则父节点与红色兄弟节点相邻——这直接违反性质 4红节点的两个子节点必须为黑色。因此只要进入案例 1x.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 删除叶子通常可精确还原也是红黑树这类自平衡树在工程实现如 Cstd::map、Linux 内核、JavaTreeMap中值得注意的行为。九、总结删除修复的正确性骨架与仓库延伸阅读把七道习题串起来可以得到RB-DELETE-FIXUP正确性的完整骨架终止与根黑13.4-1四条案例出口最终都把根染黑性质 2 恒成立。双红快速治愈13.4-2红色x直接染黑即可恢复性质 4无需进入案例分支。全流程演练13.4-3六键依次删除的逐步树形验证删除修复各案例的真实触发路径。哨兵边界13.4-4x T.nil的两条边界路径删叶子、删根分别在修复的第 2 行与第 23 行读写哨兵。黑高守恒13.4-5四案例的旋转/变色均保持各根到叶子路径的黑计数不变case 2 的缺口由额外黑色承载、case 4 的增量吸收额外黑色。案例 1 前提自洽13.4-6w.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可构成红黑树完整的学习闭环。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 红黑树删除专题RB-DELETE 与 RB-DELETE-FIXUP 的习题推演与源码对照CLRS 红黑树删除专题RB DELETE 与 RB DELETE FIXUP 的习题推演与源码对照 红黑树的删除RB DELETE是《算法导论》第 13文档教程示例工程红黑树插入算法 RB-INSERT 与 RB-INSERT-FIXUP 全解析CLRS 13.3 习题详解与 C/C 源码验证红黑树插入算法 RB INSERT 与 RB INSERT FIXUP 全解析CLRS 13.3 习题详解与 C/C 源码验证 本文以《算法导论》CLR文档教程示例工程CLRS 第 12.3 节题解精讲二叉搜索树的插入与删除TREE-INSERT 与 TREE-DELETECLRS 第 12.3 节题解精讲二叉搜索树的插入与删除TREE INSERT 与 TREE DELETE 本文围绕《算法导论》Introduction文档教程教育创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考