(xa4)红黑树：删除
拆解删除后的4种修复情形，掌握双黑、颜色翻转与旋转的完整逻辑
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
(xa4)红黑树：删除
拆解删除后的4种修复情形，掌握双黑、颜色翻转与旋转的完整逻辑
以曲为直
删除有两个孩子的节点很棘手——直接抽走,左右两棵子树就成了无主的孤儿。红黑树的诀窍是'绕一下':用中序后继的值顶替目标节点,转而删除那个后继——它最多只有一个孩子,问题就变简单了。
先把上面碍事的挪开,搬走底箱;上面不必原样放回——绕了一圈,直路反而走得通
算法框架
BST 删除我们已熟：找节点、替换、断开。但红黑树多了一道锁——删完必须保住五条性质。一旦删的是黑节点，这条路径就'欠了一个黑'，得靠兄弟子树来偿还。
兄弟替还或侄子顶债，层层上传至父亲，直至账平或归零
双黑缺陷
前页框架把删点后的修正交给接替结点 x；删去黑结点后，相关路径会少 1 个黑高单位。这个缺口若用“额外黑”记录，就形成双黑缺陷。
被删黑位像多记的一笔；x 是欠款位置，兄弟、父亲与根构成补款链路。
BB-1
前面看到了删除黑色节点会冒出「双黑」缺陷，也知道修复要绕到兄弟子树。现在我们退一步，把红黑树删除这件事正式定义一下：它做什么、难点在哪、用在哪里。
拆掉一根柱子后，顶部重量要分给相邻柱子（兄弟子树）重新平衡
反观回味
走完 BB-1 回头看，删除的真相没那么神秘——核心就一句'黑高不能乱'，而修复的关键不在'补'而在'借'。
有人离队时不能直接补，要靠调队形（旋转）和换肩章（变色）让各排依然平衡
BB-2R
BB-1 我们已经会了——远侄红，一旋就完。但天不遂人愿：远侄偏偏是黑的、近侄才是红的，套 BB-1 走不通。这就是 BB-2R 出场的时刻。
当前局面不能直接赢，先把子挪到能赢的形态，再一击制胜
BB-2B
BB-2R 运气好——有个红侄子帮忙，旋转一下就搞定。可如果兄弟俩都是黑孩子，没人能帮忙扛这个'多出来的黑'，怎么办？
当前层没人能解决，把多出来的黑责任推给上层
BB-3
BB-2R 和 BB-2B 都能靠旋转一锤定音。可若双黑的兄弟是黑的、左右侄儿也都黑——没有红孩子可借色，旋转也无处着力。BB-3 的出路只有一条：把兄弟染红，让双黑顺着父节点继续往上推。
兄弟无力解决，把双黑甩给上一级；上一级若也无力再上甩，直到根或可解决的位置
: 归纳体味
BB-1 旋转、BB-2R 终结、BB-2B 上推、BB-3 变形——四个分支各不相同，但拆开看，它们都在回答同一道题：删除黑节点留下的那层'黑色'该往哪去。
BB-2R 直接平账；BB-2B 推上级；BB-1/BB-3 调整票据再走流程
本节要点
- ✓红黑树删除 = BST 删除 + 修补双黑缺陷
- ✓双黑沿父链上移，遇红兄弟或根即停
- ✓BB-1/2/3 穷尽修补情形，BB-2 按侄子细分
- ✓单次修补常数次旋转/染色，整体 O(log n) 不破
课后思考
先合上书想五分钟，再翻看参考答案——这三问没有标准答案，思路比结论更重要。
参考答案插入只增加红色节点、不改变黑高；删除会真实减少某条路径上的黑节点数。'双黑'是'欠一格黑色'的占位标记，让修复规则能统一处理所有路径——这是红黑树不变量设计的精髓。
参考答案BB-2R 时兄弟为红，意味着父和侄子必黑，可借一格黑色补上当前缺口，多余的红色上推后黑高立即平衡。BB-2B 时兄弟为黑，能借的不够，只能染红兄弟、把'债'转嫁给父节点继续修。
参考答案分支数会显著增多（AVL 失衡类型更多），最坏旋转次数也可能上升。约束越严，失衡可能性越高、修复代价越大——红黑树用'宽松黑高'换'低廉修复代价'，是工程取舍的典范。