★ FEATURED ARTICLE 红黑树删除是《算法导论》第十三章里最劝退的一个点没有之一。插入的红红冲突好歹只要盯着叔叔节点转圈删除直接引入双黑节点——八种分支互为镜像旋转方向写反一次整棵树的黑高就崩给你看。可删除偏偏是工程里躲不开的定时器到期要摘链、有序集合要删元素、事件循环里要取消任务底层都绕不开红黑树的删除。这篇就把第十三章的删除部分拆成三件事来谈先弄清楚删除为什么欠一笔黑债再逐分支拆解修复动作最后给一套能跑的实现和随机测试思路。适合正在啃教材的读者也适合写基础设施代码时被删除修复折磨过的同学。1. 删除的整体思路先按二叉搜索树删再还黑债1.1 普通二叉搜索树的删除三态红黑树本质上是二叉搜索树加上颜色约束所以删除的第一步完全照搬二叉搜索树的删除分三种情况。第一种待删节点没有孩子直接摘掉。第二种待删节点只有一个孩子让孩子顶上来。第三种待删节点有两个孩子这是最麻烦的常规做法是找它的中序后继——也就是右子树里最小的那个节点——用后继的值覆盖待删节点然后转头去删除后继节点。关键点是后继节点一定没有左孩子所以双子删除最终会被化简成删一个至多只有一个右孩子的节点。这里有个很多人会困惑的点用值覆盖而不是真的把后继节点搬过来是不是改变了树结构没错树结构确实没变变的只是某个节点的值。红黑树的平衡性和颜色属性都建立在节点位置上和节点的具体值无关。所以只要待删节点和后继交换了值问题就转化成删除后继节点而后继节点至多有一个孩子删除难度瞬间降维。1.2 黑债从哪来黑高才是红黑树的命根红黑树的五条性质里最核心的是第5条从任意节点到它每个叶子节点的路径包含相同数目的黑色节点。这个相同数目就是黑高。插入时我们保证它删除时破坏的也是它。如果被删节点是红色事情很简单——红色节点不贡献黑高删掉它之后每条路径的黑色节点数量不变直接结束。如果被删节点是黑色麻烦就来了所有经过被删节点的路径都会少一个黑色黑高不再一致。这时候替代被删节点位置的那个孩子就要承担一笔债务。想象一下替补节点本来有自己的颜色现在它还要继承被删节点的黑色。如果替补节点原本是红色红加黑等于一个黑色债务被吸收问题解决。如果替补节点原本就是黑色黑加黑就成了双黑——这是红黑树删除修复里最核心的概念后面所有分支都是围绕怎么还掉这层双黑展开的。1.3 修复的本质让双黑往上跑直到被吸收双黑节点不是一个真实存在的颜色而是对欠债状态的描述。修复过程做的工作本质上就一件事把双黑状态往祖先方向移动直到移动到一个红色节点上把它吸收或者一路推到根节点直接抹掉。用生活里的场景类比公司里一个部门被裁掉但部门欠的预算额度还在于是这笔账要并到上级部门上级部门如果本来有盈余红色节点就能把这笔债平掉如果上级部门也在亏损黑色节点账还得继续往上并并到整个公司层面根节点时直接一笔勾销。这个类比能解释后面几乎所有修复动作的动机旋转、变色不是为了让局部变好看是为了让债务安全上移或者一次还清。2. 删除修复的八种情况把双黑还给祖先2.1 先看兄弟再看侄子当双黑节点x不是根时修复动作围绕四个角色展开x、x的父节点p、x的兄弟节点w、以及w的两个孩子可以叫近侄子和远侄子。这里规定如果x是p的左孩子那么w就是p的右孩子此时w的左孩子是近侄子w的右孩子是远侄子如果x是p的右孩子全部镜像对称。为什么只看兄弟不看别的亲戚因为双黑节点所在的路径少了一个黑色要和同层另一条路径对齐只能从兄弟那边借黑色过来。兄弟是红是黑、侄子有没有红决定了能不能借、怎么借。这个向兄弟借黑的思路是整段删除修复的地基。2.2 情况1兄弟是红色先来一次大旋转如果兄弟w是红色直接借不了黑色——红节点不贡献黑高借了也白借。这时候的处理是w染黑、p染红然后对p做一次旋转让w升到p的位置。旋转之后新的兄弟变成了原来w的孩子而这个孩子必定是黑色红节点的孩子必须是黑。这一套动作的意义是换一个兄弟把红色的麻烦兄弟换成黑色兄弟问题本身没有消失但转换成了后面几类可以处理的情况。记住这个分支不会终结修复流程它只是把局面从兄弟红改写成兄弟黑。2.3 情况2兄弟黑色两个侄子全黑把债上移当w是黑色且w的两个孩子也都是黑色时没法从侄子那边借红色就得走债务上移路线w染红、x上移到p。为什么敢把w染红w变红后以w为根的子树黑高减少1恰好和双黑x所在分支减少一个黑后的黑高对齐。此时局部齐了但p之上还有问题没解决p这颗子树整体相比以前少了一个黑。于是x变成p如果p原本是红色循环退出后会把p染黑债务被红色父节点吸收如果p也是黑色p就变成了新的双黑节点继续向上循环。情况2是唯一可能导致修复一直往上跑的分支但它不产生旋转。2.4 情况3兄弟黑色近侄子红、远侄子黑先调个方向如果w是黑色但两侄子一红一黑情况就分成两种。先看在x是左孩子的设定下近侄子红、远侄子黑的情况。此时直接旋转p解决不了问题因为远侄子这个方向是黑的旋转后黑高还是对不上。处理方式是近侄子染黑、w染红对w做一次右旋让近侄子升到w的位置成为新的兄弟。新兄弟现在是黑色的而它的右孩子是原来的w红色。换句话说情况3通过一次小旋转把近侄子红改造成了远侄子红从而进入情况4。这里可以记一句口诀近红变远红旋转才有用。红黑树修复里最终那一锤子旋转永远需要远侄子是红的因为只有远处有一个红色节点才能通过旋转把它甩到目标路径上补偿黑高。2.5 情况4兄弟黑色远侄子红一次结清终于到了终态。此时w是黑色、远侄子红色。执行w继承p原来的颜色、p染黑、远侄子染黑、对p做一次旋转然后把x置为根结束。这步为什么能一次解决旋转后w升到了子树根的位置p带着x沉到左边远侄子作为w的右子树留在右边。p染黑相当于给双黑x所在的新路径补了一个黑色债务直接还清远侄子染黑是补偿w原本路径被借走的黑色保证右边的黑高不减。子树根继承原p的颜色则是为了不向上层破坏红黑性质。整个过程一层补偿、一层还债两边的黑高全部对齐而且颜色约束也没被破坏。2.6 删除修复至多三次旋转把上面的分支串起来看删除修复的旋转次数有上界。情况1消耗一次旋转把局面转成情况2或情况3或情况4情况3消耗一次旋转转入情况4情况4消耗最后一次旋转终结。最坏路径是情况1接情况3再接情况4总共三次旋转。情况2本身不旋转只是把双黑往上传可能反复出现但全程没有旋转成本。这是红黑树有别于许多平衡树的重要优势。AVL树删除时可能需要沿着路径做O(log n)次旋转红黑树把这个成本压到了常数级。很多真实系统在一些删除高频场景下选择红黑树而不是AVL树这是一个重要理由。3. 从伪代码到实现一套能上手的删除方案3.1 节点结构和哨兵节点看教材伪代码时一切都很完美真动手写代码才发现处处是坑。最大的坑是叶子的表示伪代码里每个叶子是一个独立节点有自己的parent指针但真实实现如果给每个叶子分配一个节点内存浪费太大。常见的做法是共用一个sentinel节点通常叫NIL所有空指针都指向它。#define RED 0 #define BLACK 1 struct rb_node { unsigned long key; void *payload; int color; struct rb_node *left; struct rb_node *right; struct rb_node *parent; }; static struct rb_node *nil; static struct rb_node *root;NIL节点初始化为黑色左右子都指向自己。这样做的好处是旋转、删除时不需要对空指针做大量特判代码会简洁很多。但共享NIL的坑立刻出现所有叶子共享同一个节点NIL的parent字段只能存一个值不可能同时表示我是这棵树的叶子也是那棵树的叶子。删除修复中经常需要知道x的父节点是谁如果x本身就是NIL从x-parent取父节点就是错的。这也是很多照着CLRS伪代码抄实现的人翻车的地方。3.2 删除主流程选好替补记录孤儿方向解决共享NIL问题的方法是删除时不去依赖x-parent而是额外记录x的父节点parent和方向dir。dir为0表示x在parent左侧dir为1表示在右侧。修复函数全程用这两个参数定位。先看删除主体的框架void rb_erase(struct rb_node *z) { struct rb_node *y z; struct rb_node *x; struct rb_node *parent; int dir; int y_color y-color; if (z root z-left nil z-right nil) { root nil; free(z); return; } if (z-left nil || z-right nil) { x (z-left nil) ? z-right : z-left; parent z-parent; dir (z parent-left) ? 0 : 1; rb_transplant(z, x); } else { y tree_minimum(z-right); x y-right; y_color y-color; if (y-parent z) { parent y; dir 1; } else { parent y-parent; dir (y parent-left) ? 0 : 1; rb_transplant(y, y-right); y-right z-right; z-right-parent y; } rb_transplant(z, y); y-left z-left; z-left-parent y; y-color z-color; } if (y_color BLACK) { rb_delete_fixup(x, parent, dir); } free(z); }有两个细节必须说明。第一删除根节点且根没有孩子的情况要单独处理否则parent为NILdir都没法算。第二双子删除里y是z的中序后继它一定没有左孩子所以x就是y-right。当y不是z的直接右孩子时需要先把x放到y原来的位置再把y搬去顶替z这个顺序不能反。顺序一错y的右子树就丢了。3.3 修复函数用方向参数避开NIL陷阱修复函数的核心循环如下dir参数替代了伪代码里x parent-left这种比较static void rb_delete_fixup(struct rb_node *x, struct rb_node *parent, int dir) { while (x ! root (x nil || x-color BLACK)) { struct rb_node *w dir ? parent-left : parent-right; if (w-color RED) { w-color BLACK; parent-color RED; if (dir 0) left_rotate(parent); else right_rotate(parent); w dir ? parent-left : parent-right; } if (w-left-color BLACK w-right-color BLACK) { w-color RED; x parent; parent x-parent; if (parent ! nil) dir (x parent-left) ? 0 : 1; } else { if (dir 0) { if (w-right-color BLACK) { w-left-color BLACK; w-color RED; right_rotate(w); w parent-right; } w-color parent-color; parent-color BLACK; w-right-color BLACK; left_rotate(parent); } else { if (w-left-color BLACK) { w-right-color BLACK; w-color RED; left_rotate(w); w parent-left; } w-color parent-color; parent-color BLACK; w-left-color BLACK; right_rotate(parent); } x root; } } if (x ! nil) x-color BLACK; }几个值得强调的点。循环条件里的x nil判断不能省因为共享NIL颜色固定是黑去掉这个判断会漏掉NIL也是双黑的情况。每次旋转后必须重新取w兄弟节点在旋转后已经换了人继续用之前的w指针必然出错。情况2把x上移后如果parent是NIL说明x已经到根了下一轮循环条件x ! root会拦住它所以dir更新可以跳过。旋转函数的实现也要小心NIL尤其旋转节点的孩子解引用前要确认不是NILstatic void left_rotate(struct rb_node *x) { struct rb_node *y x-right; x-right y-left; if (y-left ! nil) y-left-parent x; y-parent x-parent; if (x-parent nil) { root y; } else if (x x-parent-left) { x-parent-left y; } else { x-parent-right y; } y-left x; x-parent y; }右旋是镜像代码把所有的left和right互换即可。实际的rb_transplant里如果v是NIL不需要更新v-parent因为共享NIL没有独立的parent语义反正修复函数也不靠这个字段。3.4 值拷贝还是节点搬移双子删除时代码里用的是节点搬移方案把y真正搬到z的位置而不是拷贝z的值。这套方案来自CLRS伪代码优点是不拷贝payload。如果节点里挂的是大型业务数据或嵌套指针值拷贝很容易引入浅拷贝问题。另一种常见做法是只拷贝key和payload然后删除后继y。代码更简单删除后不必关心颜色继承和指针重建的细节。缺点是大对象拷贝开销明显。方案优点缺点适用场景值拷贝逻辑简单不易出错大payload拷贝开销高教学、小对象、原型验证节点搬移无拷贝开销贴近教材指针重连细节多生产环境、大规模数据如果只是验证红黑树删除的性质用值拷贝就够了。如果是写基建设施比如定时器管理里的节点同时还挂着回调堆栈推荐节点搬移减少无谓的内存操作。4. 随机压力测试与黑高校验怎样证明删除没写错4.1 一个常见的应用场景定时器管理说一个我实际做过的场景。某项目里写用户态事件循环定时器需要按到期时间有序排列支持高频插入、到期摘除、任意取消。一开始用的是最小堆到期摘除很痛快但任意取消一个还没有到期的定时器成了麻烦——堆里删除任意元素是O(n)事件量一上来就顶不住。换成红黑树之后按时到期时间戳作为key插入删除都是O(log n)。这个模块里删除操作和插入操作大概各占一半红黑树的常数极低最坏情况下三次旋转的上界对实时性也有好处。那段时间我对红黑树删除的实战观感就是从这套代码里来的。4.2 自校验器每次操作后检查五条性质写了删除修复光靠眼睛看不出对错。我的做法是写一个自校验函数每次插入或删除后调用违反任何一条性质立刻中止程序。红黑树五条性质里黑高一致性是最好抓bug的int verify(struct rb_node *n) { int l, r; if (n nil) return 1; if (n-color RED) { if (n-left-color ! BLACK || n-right-color ! BLACK) { fprintf(stderr, red node has red child: %lu\n, n-key); abort(); } } l verify(n-left); r verify(n-right); if (l ! r) { fprintf(stderr, black height mismatch: %lu (%d vs %d)\n, n-key, l, r); abort(); } return l (n-color BLACK); }这个函数递归遍历整棵树红色节点的孩子必须是黑色左右子树的黑高必须相等最后加上自己如果是黑色就多计一个。配合一个中序遍历检查有序性五条性质基本都覆盖了。4.3 随机增删的测试流程测试主循环设计成随机序列先随机插入大量节点再随机删除其中一部分每次操作后跑一遍verify和有序性检查。多换几个随机种子跑小规模数据跑几千轮大规模数据跑几十万轮。我当时的测试输出长这样seed42: inserted3000 deleted1800 height21 black_height9 ok seed7: inserted5000 deleted4300 height22 black_height10 ok seed99: inserted10000 deleted9700 height24 black_height11 ok树高维持在log级别附近黑高始终一致这才敢把代码合进去。如果你刚自己实现完删除强烈建议跑一轮随机测试比任何肉眼review都有说服力。4.4 测试抓到的真实bug这套测试帮我抓到过至少两类印象深刻的问题。第一类修复函数里旋转方向写反。当时情况4的远侄子染色写对了但左旋和右旋弄反了结果随机测试跑到某个操作时checker报出黑高不一致。视野缩到旋转函数后才发现镜像分支里我把左旋写成了右旋。这类错误靠代码审查很难发现因为树的结构在旋转后依然是有序的只有黑高会悄悄出错。第二类双子删除时x的父节点记录错误。在y不是z的直接右孩子分支里我在rb_transplant之前没有正确记录parent导致修复函数拿着错误的父节点去取兄弟树直接崩掉。这个问题到最后是在调试器里定位的但事后想想如果一开始就在删除主流程里把parent和dir的赋值点写清楚是可以提前避免的。5. 删除与插入的对称之美一张表看懂两项操作的本质5.1 冲突的根源不同插入的冲突是红红相邻发生在向下生长的过程中修复时看叔叔节点的颜色红叔叔就染色上移黑叔叔就旋转。删除的冲突是黑高欠账发生在向上修复的过程中修复时看兄弟节点的颜色红兄弟先旋转换人黑兄弟再按侄子颜色细分成情况2、3、4。一个是违规一个是欠债。违规可以局部纠正欠债可能需要一路追到根。这就是为什么删除的代码总是比插入长一截。5.2 旋转次数上界不同操作最多旋转次数最坏变色次数修复趋势插入2O(log n)向上但通常局部结束删除3O(log n)双黑可能上移到根插入最多两次旋转就能收尾删除最多三次。这个常数差别在实际系统里体现得非常明显删除操作不会因为树的高度增加而变慢很多这是红黑树能被用在定时器、内存分配器这类删除高频场景的重要原因。5.3 为什么删除看起来更复杂本质上插入只需要保证新路径和周围路径颜色不冲突修复动作是我给我这层擦屁股。删除需要同时平衡两条路径的黑高差——被删路径少了黑兄弟路径没少得把黑色从一边匀到另一边还要保证匀的过程中整棵树的红黑性质不被破坏。多一个跨路径调配的维度复杂程度自然上了一个台阶。但换个角度看删除的八种情况其实非常有逻辑红兄弟先换成黑兄弟黑兄弟配上全黑侄子就上移债务配上近红侄子就先调方向配上远红侄子就一次结清。一条线串下来比死记硬背强得多。6. 高频踩坑与排查速查6.1 根节点被删后变成红色删除的是黑色根节点且修复过程中双黑一路推到根最后一步的x-color BLACK会把根重新染黑。这个兜底赋值是必须的漏掉之后红黑树的第一条性质直接失效。校验器记得检查root-color BLACK这个最简单也最容易漏。6.2 共享NIL导致方向判断错误用共享NIL时不能在修复函数里用x parent-left来判断方向因为两个空位置都指向同一个NIL无法区分。这属于实现层特有的坑教材伪代码不会告诉你。解决办法就是前面写的在删除主流程里显式记录dir修复函数靠dir定位。这是整段代码里最值得提前规划的地方。6.3 双子删除时顺序颠倒当后继y不是z的直接右孩子时必须先rb_transplant(y, y-right)再把y-right改成z-right。如果先改y-right原来的右子树指针就被覆盖了x还没顶到y的位置树直接从中间断开。这类错误的发生往往只差一行代码但查起来要命。写完主流程后建议在每个分支都画一下指针状态比debug省时间。6.4 黑高校验失败时先查哪几个点如果checker报黑高不一致按我的经验优先级是先看情况4里远侄子染黑有没有执行再看情况3之后w有没有重新取最后查情况2中w染红后是否漏了把x上移。三个点覆盖了大部分删除修复的初学者错误。6.5 两个定位问题的土办法没用可视化工具的时候我靠两个土办法定位红黑树bug。第一打印中序遍历序列同时输出每个节点的颜色能快速判断有序性和红黑约束。第二随机测试一旦崩了用二分法收缩导致崩溃的序列长度先试前一半操作如果崩了就再对半砍很快就能定位到第一个触发问题的操作。这比盯着屏幕干猜高效得多。最后说一点个人体会红黑树的删除只看不写等于没看。我第一次照着教材敲代码时光是共享NIL的坑就折腾了一个晚上等到随机测试全绿的那一刻整棵树的删除逻辑才算真正长在脑子里。如果你也在写自己的实现建议别急着抄代码先把双黑的含义和情况之间转换的方向在草稿纸上画明白动手写的时候会轻松很多。
阅读完成 · 觉得有帮助？
