红黑树这三个字几乎是每个写算法的人绕不开的一道坎。我最早认真啃它是因为翻 JDK 的 TreeMap 源码看到满屏的 rotateLeft、rotateRight 和颜色翻转一脸懵后来做 Linux 后台开发发现内核的 CFS 调度器、epoll、Nginx 的定时器里全是红黑树的影子这才下定决心彻底搞懂它。如果你也准备手写一棵红黑树或者想在面试前把插入、删除的来龙去脉捋清楚这篇文章就是按我当年踩坑总结出来的思路写的不讲废话直接讲原理配上能跑的代码。1. 红黑树到底解决了什么问题1.1 从二叉搜索树的退化说起普通二叉搜索树BST的规则很简单左子树小、右子树大。这个结构本身没毛病问题出在它不限制树的形状。如果你按 1、2、3、4、5……的顺序插入BST 会直接退化成一条链表查找时间复杂度从期望的 O(log n) 变成 O(n)。我在实际项目里就遇到过这种情况一张加了索引的表达式中代码不小心用有序数据反复触发最坏情况查询直接崩到秒级排查很久才意识到是树形索引退化了。红黑树本质上也是一种 BST但它通过额外约束让整棵树保持“近似平衡”保证树高始终在一个可控范围内。所谓近似平衡不是说左右子树高度严格相等而是最长的路径不会超过最短路径的两倍。这个性质对工程来说非常关键无论你按什么顺序插入、删除红黑树都能把查找、插入、删除的整体复杂度稳定压在 O(log n)。1.2 平衡的代价与收益平衡二叉树这个家族里AVL 树是另一个代表。AVL 要求任意节点的左右子树高度差不超过 1这个约束非常严格树确实更矮查找常数也更小但代价是插入和删除时为了维持“高度差不超过 1”需要频繁旋转甚至可能一路旋转到根。红黑树选择了“松绑”它不关心子树具体差几层只要求从根到叶子的所有路径上黑色节点数量相等且红色节点不能连续出现。这个看似奇怪的规则换来的是插入时最多两次旋转、删除时最多三次旋转而且调整操作通常是局部变色成本大幅下降。所以选平衡树时并没有谁绝对碾压谁而是看场景。查找居多、插入删除极少AVL 更合适插入删除频繁、还需要稳定 O(log n) 保证红黑树更合适。我自己的经验是做通用集合类、内核模块、缓存管理这类写多读也多的组件红黑树几乎是默认答案。2. 红黑树的五条性质规则与背后的意图2.1 逐条拆解五条性质红黑树的全部规则就是下面这五条任何一棵合法的红黑树必须同时满足编号性质大白话解释1每个节点非红即黑颜色是节点的额外标记字段2根节点是黑色树的根基必须稳定3所有叶子节点NIL是黑色这里的叶子指的是空节点不是我们平时说的数据叶子4红色节点的两个子节点必须是黑色不能出现连续两个红节点5从任意节点到其每个叶子节点的路径上黑色节点数量相同这个数量就叫“黑高”很多人背性质背得很熟但不理解为什么是这五条。其实核心就是第 4 条加第 5 条。第 5 条保证了所有路径的黑高一致第 4 条限制了红色节点的串联于是任何路径上红色节点数量不可能超过黑色节点数量最长路径顶多是一半黑一半红交替而最短路径可以全是黑。两者一比最长路径最多是最短路径的两倍这就保证了树不会过度倾斜。2.2 黑高与树高的数学推导我们把从某个节点出发到叶子节点路径上黑色节点的个数包含该节点自身不包含 NIL 叶子称为该节点的黑高记作 bh。一棵包含 n 个内部节点的红黑树它的高度 h 最多是 2 * log2(n 1)。这个上界怎么来的我当年第一次看到推导时觉得绕后来用反证思路理解就顺了。假设一棵黑高为 bh 的树它至少要有多少节点如果一棵全是黑节点那它最紧凑满二叉树的节点数是 2^bh - 1。如果允许红节点节点数只会更多不会更少。又因为第 4 条限制了红黑交替所以整棵树的高度 h 最多是黑高的两倍即 bh h / 2。把这个带进 n 2^bh - 1就得到 n 2^(h/2) - 1也就是 h 2log2(n 1)。虽然这个上界比 AVL 的 1.44log2(n1) 宽松但从工程角度看2 倍也是常数级别O(log n) 的承诺依然成立而实现和旋转成本却低了不少。3. 旋转红黑树的原子操作3.1 旋转的本质红黑树的调整不管是插入还是删除最终都会落到两类操作上变色和旋转。旋转分左旋和右旋它们的作用是在不破坏 BST 中序顺序的前提下把一个节点往下“沉”把它的子节点往上“提”。左旋的场景如果你有一个节点 x它的右孩子 y 不想当孩子了想当爹那就围绕 x 做一次左旋。左旋完成后y 变成子树的新根x 变成 y 的左孩子而 y 原来的左孩子会过继给 x变成 x 的右孩子。仔细看这个过继操作保证了 BST 的顺序性不变y 的左孩子原本大于 x、小于 y左旋后它成为 x 的右孩子依然大于 x、小于 y非常自然。右旋就是镜像对称操作把左孩子提上来自己沉下去。旋转操作的时间复杂度是 O(1)因为它只改动常数个指针。这是红黑树所有调整操作的“地基”插入删除那些令人头大的 case本质上都是在安排旋转和变色的顺序。3.2 左旋与右旋的代码实现旋转代码看起来简单但写起来最容易出错的地方往往不是旋转本身而是父指针的维护。我贴一段自己项目里用过的 C 风格实现假设节点结构里带 parent 指针。typedef struct rb_node { int key; int color; // 0 黑1 红 struct rb_node *left, *right, *parent; } rb_node; void rotate_left(rb_node **root, rb_node *x) { rb_node *y x-right; x-right y-left; if (y-left ! NULL) { y-left-parent x; } y-parent x-parent; if (x-parent NULL) { *root y; } else if (x x-parent-left) { x-parent-left y; } else { x-parent-right y; } y-left x; x-parent y; } void rotate_right(rb_node **root, rb_node *y) { rb_node *x y-left; y-left x-right; if (x-right ! NULL) { x-right-parent y; } x-parent y-parent; if (y-parent NULL) { *root x; } else if (y y-parent-left) { y-parent-left x; } else { y-parent-right x; } x-right y; y-parent x; }这段代码里有几个地方值得你多看两眼。第一所有子节点指针更新后都要同步更新子节点的 parent。第二如果 x 是根旋转后必须更新树的 root 指针否则后续操作会从旧根出发导致完全错乱。第三判断 x 是父节点的左孩子还是右孩子时必须用原本的父子关系不能在更新 parent 之后再判断。4. 插入实操从变色到再平衡4.1 插入流程总览插入操作的思路分三步。第一步按普通 BST 的规则找到插入位置把新节点挂到树上。第二步把新节点涂成红色。第三步从新节点开始向上修复让整棵树重新满足五条性质。很多初学者会问为什么新节点一定要是红色道理很简单如果你涂黑色那么从根到新节点这条路径上的黑高立刻比别的路径多 1直接违反第 5 条而这个性质是最难修复的。涂红色则不会破坏黑高最多只会出现连续红节点也就是可能违反第 4 条但第 4 条是局部约束修复起来代价小得多。这个选择背后就是典型的“把问题限制在容易处理的场景”。修复过程关注三个节点当前节点 z、它的父节点 p、它的叔节点 u即 p 的兄弟。当 z 的父节点是黑色时直接结束因为这棵树依然合法。需要处理的就是父节点为红色的情况它按叔叔节点的颜色和位置分裂成三种 case。4.2 三种情况的处理策略第一种叔叔节点是红色。这种情况最温柔不需要旋转只需要变色把父节点和叔叔节点都变成黑色把祖父节点变成红色。这样做的效果是原来从祖父到两个子路径上的黑高保持不变但“红色往上移动”到了祖父。接下来把 z 指向祖父继续向上检查。注意如果祖父正好是根最后一步要把根强制涂黑。第二种叔叔节点是黑色且 z 是父节点的“内侧”孩子。所谓内侧是指父节点是左孩子而 z 是右孩子或者父节点是右孩子而 z 是左孩子也就是形成了 LR 或 RL 的形状。这时候直接对祖父旋转没法一步到位需要先对父节点做一次旋转把它转化成第三种情况。比如父是左孩子、z 是右孩子就先对父节点左旋然后 z 和父的角色互换变成“父是左孩子且 z 也是左孩子”的形状。第三种叔叔节点是黑色且 z 是父节点的“外侧”孩子也就是 LL 或 RR 形状。这时对祖父节点做一次旋转让父节点顶替祖父的位置然后交换父和祖父的颜色父变黑祖父变红。这样整棵子树的黑高恢复原状连续红节点也消除了调整可以直接结束。这三种情况的判断顺序不是随意定的。变色的 case 会把问题抛给上一层靠循环解决而旋转的 case 一旦执行整棵子树立刻合法循环就终止了。所以说红黑树插入最坏情况下只需两次旋转但变色操作的次数可以沿着路径累积到 O(log n)。4.3 插入代码实现下面是我整理好的插入修复函数代码里我故意保留了“插入后统一修复”的结构方便你对照上面的 case 理解。void rb_insert_fixup(rb_node **root, rb_node *z) { while (z-parent ! NULL z-parent-color 1) { rb_node *p z-parent; rb_node *g p-parent; rb_node *u (p g-left) ? g-right : g-left; if (u ! NULL u-color 1) { // case 1: 叔红变色后上移 u-color 0; p-color 0; g-color 1; z g; } else { if (p g-left) { if (z p-right) { // case 2 的内侧情况先左旋父节点 z p; rotate_left(root, z); p z-parent; } // case 3: 外侧情况右旋祖父并变色 rotate_right(root, g); p-color 0; g-color 1; break; } else { if (z p-left) { z p; rotate_right(root, z); p z-parent; } rotate_left(root, g); p-color 0; g-color 1; break; } } } (*root)-color 0; }这里要注意case 2 我直接沿用了“z p 再重新取 p”的写法这样代码结构上和教科书版一致逻辑更清晰。实际生产代码里有人会写得更高压缩但可读性差很多我建议先按这个清晰版本理解再慢慢优化。5. 删除实操最麻烦的双黑问题5.1 删除流程与替换删除法删除比插入复杂核心难点在于如果删掉一个黑色节点那么从根到它叶子路径上的黑高就少 1这会破坏第 5 条“所有路径黑高相同”的性质而且不像插入那样有个“红色往上提”的简单策略删除修复的这个黑色缺失会一直存在直到我们通过旋转和变色把它补回来。先说删除节点的基本策略。如果待删节点 z 最多只有一个非空子节点那就直接用子节点顶替它这种最简单。如果 z 有两个非空子节点标准做法是“替换删除”找到 z 的中序后继 y把 y 的 key 值拷贝到 z然后删除 y。因为 y 是右子树的最左节点它最多只有一个非空右孩子这样问题又退化到单子节点场景。这个技巧很巧妙地避免了直接删除有两个孩子的节点时复杂的子链接操作。真正需要修复的是实际被删除的节点 y 为黑色的情况。我们把顶替 y 位置的那个节点记为 x如果 x 是红色直接把它涂黑就能补回黑高万事大吉如果 x 也是黑色那么这棵子树相对于外界“少了一个黑”我们把这种情况称为 x 带有“双黑”修复的目标就是消除这个双黑。5.2 兄弟节点的四种情况删除修复是在循环中处理的每次处理时双黑节点 x 处于某个父节点 p 之下我们关注 x 的兄弟节点 w。为便于描述假设 x 是 p 的左孩子右边情况对称。第一种情况w 是红色。这说明父节点 p 一定是黑色且 w 的两个孩子都是黑色。处理方式是左旋 p把 w 提上来然后染色w 变黑p 变红。经过这次操作x 的兄弟变成原来 w 的左孩子一个黑色节点问题转化到后面的 case 2、3、4。第二种情况w 是黑色且 w 的两个孩子都是黑色。这是最“温和”的向上抛问题把 w 变成红色这样 x 和 w 两侧的黑高各少 1双黑被吸收到 p 身上x 指向 p循环继续。注意如果 p 是红色循环结束后把它涂黑即可。第三种情况w 是黑色w 的左孩子是红色右孩子是黑色。个案型处理对 w 右旋把 w 的左孩子提上来染黑顶替的节点w 变红。这样处理之后新兄弟节点变成了此前 w 的左孩子它有一个红色右孩子正好满足第四种情况的前提。第四种情况w 是黑色w 的右孩子是红色。这是唯一能结束循环的旋转 case对 p 左旋w 继承 p 的颜色p 变成黑色w 的右孩子变成黑色。这一步把黑高缺口完美补上x 直接指向根节点循环终止。综合来看删除修复最多三次旋转但变色和向上传播可以一路走到根所以时间复杂度是 O(log n)。我当年写删除时最常犯的错误就是漏掉“x 可能是 NIL 节点”的情况——实际被删的是黑色叶节点顶替它的就是空节点 NIL代码里必须允许 x 本身为 NULL但不能对 NULL 解引用。5.3 删除修复代码实现为了方便理解我把删除修复也按“x 是左孩子”和“x 是右孩子”两个分支来写镜像逻辑直接复制后左右互换虽然代码长了点但比用 helper 隐藏对称性更容易读。void rb_delete_fixup(rb_node **root, rb_node *x, rb_node *parent) { while (x ! *root (x NULL || x-color 0)) { if (x parent-left) { rb_node *w parent-right; if (w-color 1) { // case 1: 兄弟红 w-color 0; parent-color 1; rotate_left(root, parent); w parent-right; } if ((w-left NULL || w-left-color 0) (w-right NULL || w-right-color 0)) { // case 2: 兄弟黑且兄弟的孩子全黑 w-color 1; x parent; parent x-parent; } else { if (w-right NULL || w-right-color 0) { // case 3: 兄弟的右孩子黑左孩子红 if (w-left ! NULL) { w-left-color 0; } w-color 1; rotate_right(root, w); w parent-right; } // case 4: 兄弟的右孩子红 w-color parent-color; parent-color 0; if (w-right ! NULL) { w-right-color 0; } rotate_left(root, parent); x *root; break; } } else { // 镜像逻辑不再逐行解释 rb_node *w parent-left; if (w-color 1) { w-color 0; parent-color 1; rotate_right(root, parent); w parent-left; } if ((w-left NULL || w-left-color 0) (w-right NULL || w-right-color 0)) { w-color 1; x parent; parent x-parent; } else { if (w-left NULL || w-left-color 0) { if (w-right ! NULL) { w-right-color 0; } w-color 1; rotate_left(root, w); w parent-left; } w-color parent-color; parent-color 0; if (w-left ! NULL) { w-left-color 0; } rotate_right(root, parent); x *root; break; } } } if (x ! NULL) { x-color 0; } }呼这段代码我每个分支都测试过随机插入删除但这属于“需要仔细对待”的代码你抄进自己的工程后一定要跑随机验证不要看一遍就认为没问题。6. 常见问题与排查技巧实录6.1 调试红黑树的心法手写红黑树的调试期是最痛苦的很容易出现“看起来对但随机操作几万次后某个性质被破坏”的幽灵问题。我的经验是不要用人眼盯着树看也不要只靠单测用例而是写一个校验器每次插入删除后都自动验证五条性质是否成立。一个合格的校验器要检查四件事根是否是黑、红节点的孩子是否是黑、所有路径黑高是否一致、树的中序序列是否有序。为了让校验器能找到问题节点我习惯在递归函数里返回“以当前节点为根的子树黑高”一旦发现某条路径黑高不一致立刻打印出该节点的 key 和左右子树的黑高这样能快速定位到失衡的局部。下面是我常用的递归校验代码基于 Python 写方便测试时快速验证。def check_rb(node, is_rootFalse): # 返回黑高非法返回 -1 if node is None: return 1 # NIL 叶子算一个黑高 if is_root and node.color ! black: print(root is not black) return -1 if node.color red: if node.left and node.left.color red: print(red-red at, node.key) return -1 if node.right and node.right.color red: print(red-red at, node.key) return -1 lh check_rb(node.left) if lh 0: return -1 rh check_rb(node.right) if rh 0: return -1 if lh ! rh: print(black height mismatch at, node.key, lh, rh) return -1 return lh (1 if node.color black else 0)这个校验器虽然简单但非常管用。我每次写完插入或删除会随机生成几十万条操作序列穿插插入和删除每步结束后都跑一遍校验一旦报错就二分定位到具体操作极大缩短了排查时间。6.2 最容易踩的三个坑第一个坑是 NIL 节点处理。很多教材画树时黑高是从“真正的叶子节点”算的但代码里叶子其实就是空指针。如果你在递归里没有把空节点当作黑色叶子处理插入删除的黑高逻辑很容易写错。我建议统一约定NULL 就是黑色 NIL 叶子这样代码条件判断里到处都要写“ NULL || color 0”看着烦但对。第二个坑是 parent 指针不同步。旋转代码里容易漏掉更新孩子节点的 parent或者漏掉判断“当前节点是不是根”结果 list 遍历时出现环形指针程序直接死循环。排查这种问题很折磨所以我建议旋转函数里先更新所有孩子 parent再更新父 parent再更新 root每一步都按顺序来。第三个坑是删除修复的循环条件。修复循环必须在 x 成为根节点或 x 为红色时终止。如果你把“x NULL”漏在循环条件外就会在删除黑色叶节点时对空指针解引用。我吃过的亏是循环写成 while(x ! root x-color 0)结果 x 为 NULL 时直接崩溃改成允许 NULL 的版本后才稳定。7. 红黑树的工程应用与选型建议7.1 你身边那些看不见的红黑树红黑树并不只是面试题它是很多基础组件的核心结构。我最早从 Java 的 TreeMap 和 TreeSet 开始认识它这两个类底层就是红黑树要求 key 可排序且支持范围查询。C 的 std::map 和 std::set 也是红黑树标准库对它迭代器的稳定性保证正是来自红黑树插入删除对结构局部性的控制。Linux 内核里红黑树用得更多CFS 调度器用它管理进程调度实体保证每次都能以 O(log n) 找到最小虚拟运行时间的进程epoll 用它管理被监听的文件描述符。Nginx 的定时器也是经典的红黑树应用通过 key 是超时时间快速找到最快到期的定时器。你会发现凡是需要“动态插入、删除、频繁查找最值”的场景红黑树都是高频选择。7.2 红黑树、AVL 与跳表的取舍选型时我经常要比较红黑树、AVL 和跳表。AVL 的树更矮查找性能理论更好但删除旋转次数比红黑树多对写多场景不友好。跳表实现异常简单区间查询和并发改造都容易Redis 的有序集合就用的跳表但它需要额外的层指针内存占用偏高而且最坏情况下没有严格的平衡保证。红黑树的优势是内存紧凑、插入删除旋转次数有硬上限、树高稳定劣势是实现复杂、对并发场景需要额外加锁。如果是写一个通用有序集合红黑树基本可以无脑选如果需求特别看重实现简单和并发读多写多跳表值得考虑如果场景几乎是静态数据、只做高频查找AVL 依然能打。没有“最强的数据结构”只有“最匹配当前场景的结构”这句话我是在调了无数次优之后才真正认同的。7.3 我的建议路线最后给你一条我自己验证过的学习路径。第一步别急着背 case先把五条性质写在一张纸上。第二步实现二叉搜索树的查找、插入、删除至少搞清楚中序后继。第三步实现旋转。第四步加校验器。第五步写插入修复跑随机测试。第六步写删除修复继续跑随机测试。每一步都让前面的代码可运行、可验证再进入下一步。从看着 TreeMap 源码头晕到自己把红黑树完整跑通我最大的体会是红黑树学习的真正门槛不在那六个 case而在你能不能把“为什么新节点是红色”“为什么删除会产生双黑”“为什么旋转不破坏有序性”这几个为什么想透。想透之后case 只是若干种形状的组合你完全可以现场推导出来。如果你也想彻底告别对红黑树的恐惧我建议今天就写个校验器再开始写插入多跑几轮随机测试那比看十遍教程都管用。
红黑树原理详解：从旋转到插入删除的完整实现
红黑树这三个字几乎是每个写算法的人绕不开的一道坎。我最早认真啃它是因为翻 JDK 的 TreeMap 源码看到满屏的 rotateLeft、rotateRight 和颜色翻转一脸懵后来做 Linux 后台开发发现内核的 CFS 调度器、epoll、Nginx 的定时器里全是红黑树的影子这才下定决心彻底搞懂它。如果你也准备手写一棵红黑树或者想在面试前把插入、删除的来龙去脉捋清楚这篇文章就是按我当年踩坑总结出来的思路写的不讲废话直接讲原理配上能跑的代码。1. 红黑树到底解决了什么问题1.1 从二叉搜索树的退化说起普通二叉搜索树BST的规则很简单左子树小、右子树大。这个结构本身没毛病问题出在它不限制树的形状。如果你按 1、2、3、4、5……的顺序插入BST 会直接退化成一条链表查找时间复杂度从期望的 O(log n) 变成 O(n)。我在实际项目里就遇到过这种情况一张加了索引的表达式中代码不小心用有序数据反复触发最坏情况查询直接崩到秒级排查很久才意识到是树形索引退化了。红黑树本质上也是一种 BST但它通过额外约束让整棵树保持“近似平衡”保证树高始终在一个可控范围内。所谓近似平衡不是说左右子树高度严格相等而是最长的路径不会超过最短路径的两倍。这个性质对工程来说非常关键无论你按什么顺序插入、删除红黑树都能把查找、插入、删除的整体复杂度稳定压在 O(log n)。1.2 平衡的代价与收益平衡二叉树这个家族里AVL 树是另一个代表。AVL 要求任意节点的左右子树高度差不超过 1这个约束非常严格树确实更矮查找常数也更小但代价是插入和删除时为了维持“高度差不超过 1”需要频繁旋转甚至可能一路旋转到根。红黑树选择了“松绑”它不关心子树具体差几层只要求从根到叶子的所有路径上黑色节点数量相等且红色节点不能连续出现。这个看似奇怪的规则换来的是插入时最多两次旋转、删除时最多三次旋转而且调整操作通常是局部变色成本大幅下降。所以选平衡树时并没有谁绝对碾压谁而是看场景。查找居多、插入删除极少AVL 更合适插入删除频繁、还需要稳定 O(log n) 保证红黑树更合适。我自己的经验是做通用集合类、内核模块、缓存管理这类写多读也多的组件红黑树几乎是默认答案。2. 红黑树的五条性质规则与背后的意图2.1 逐条拆解五条性质红黑树的全部规则就是下面这五条任何一棵合法的红黑树必须同时满足编号性质大白话解释1每个节点非红即黑颜色是节点的额外标记字段2根节点是黑色树的根基必须稳定3所有叶子节点NIL是黑色这里的叶子指的是空节点不是我们平时说的数据叶子4红色节点的两个子节点必须是黑色不能出现连续两个红节点5从任意节点到其每个叶子节点的路径上黑色节点数量相同这个数量就叫“黑高”很多人背性质背得很熟但不理解为什么是这五条。其实核心就是第 4 条加第 5 条。第 5 条保证了所有路径的黑高一致第 4 条限制了红色节点的串联于是任何路径上红色节点数量不可能超过黑色节点数量最长路径顶多是一半黑一半红交替而最短路径可以全是黑。两者一比最长路径最多是最短路径的两倍这就保证了树不会过度倾斜。2.2 黑高与树高的数学推导我们把从某个节点出发到叶子节点路径上黑色节点的个数包含该节点自身不包含 NIL 叶子称为该节点的黑高记作 bh。一棵包含 n 个内部节点的红黑树它的高度 h 最多是 2 * log2(n 1)。这个上界怎么来的我当年第一次看到推导时觉得绕后来用反证思路理解就顺了。假设一棵黑高为 bh 的树它至少要有多少节点如果一棵全是黑节点那它最紧凑满二叉树的节点数是 2^bh - 1。如果允许红节点节点数只会更多不会更少。又因为第 4 条限制了红黑交替所以整棵树的高度 h 最多是黑高的两倍即 bh h / 2。把这个带进 n 2^bh - 1就得到 n 2^(h/2) - 1也就是 h 2log2(n 1)。虽然这个上界比 AVL 的 1.44log2(n1) 宽松但从工程角度看2 倍也是常数级别O(log n) 的承诺依然成立而实现和旋转成本却低了不少。3. 旋转红黑树的原子操作3.1 旋转的本质红黑树的调整不管是插入还是删除最终都会落到两类操作上变色和旋转。旋转分左旋和右旋它们的作用是在不破坏 BST 中序顺序的前提下把一个节点往下“沉”把它的子节点往上“提”。左旋的场景如果你有一个节点 x它的右孩子 y 不想当孩子了想当爹那就围绕 x 做一次左旋。左旋完成后y 变成子树的新根x 变成 y 的左孩子而 y 原来的左孩子会过继给 x变成 x 的右孩子。仔细看这个过继操作保证了 BST 的顺序性不变y 的左孩子原本大于 x、小于 y左旋后它成为 x 的右孩子依然大于 x、小于 y非常自然。右旋就是镜像对称操作把左孩子提上来自己沉下去。旋转操作的时间复杂度是 O(1)因为它只改动常数个指针。这是红黑树所有调整操作的“地基”插入删除那些令人头大的 case本质上都是在安排旋转和变色的顺序。3.2 左旋与右旋的代码实现旋转代码看起来简单但写起来最容易出错的地方往往不是旋转本身而是父指针的维护。我贴一段自己项目里用过的 C 风格实现假设节点结构里带 parent 指针。typedef struct rb_node { int key; int color; // 0 黑1 红 struct rb_node *left, *right, *parent; } rb_node; void rotate_left(rb_node **root, rb_node *x) { rb_node *y x-right; x-right y-left; if (y-left ! NULL) { y-left-parent x; } y-parent x-parent; if (x-parent NULL) { *root y; } else if (x x-parent-left) { x-parent-left y; } else { x-parent-right y; } y-left x; x-parent y; } void rotate_right(rb_node **root, rb_node *y) { rb_node *x y-left; y-left x-right; if (x-right ! NULL) { x-right-parent y; } x-parent y-parent; if (y-parent NULL) { *root x; } else if (y y-parent-left) { y-parent-left x; } else { y-parent-right x; } x-right y; y-parent x; }这段代码里有几个地方值得你多看两眼。第一所有子节点指针更新后都要同步更新子节点的 parent。第二如果 x 是根旋转后必须更新树的 root 指针否则后续操作会从旧根出发导致完全错乱。第三判断 x 是父节点的左孩子还是右孩子时必须用原本的父子关系不能在更新 parent 之后再判断。4. 插入实操从变色到再平衡4.1 插入流程总览插入操作的思路分三步。第一步按普通 BST 的规则找到插入位置把新节点挂到树上。第二步把新节点涂成红色。第三步从新节点开始向上修复让整棵树重新满足五条性质。很多初学者会问为什么新节点一定要是红色道理很简单如果你涂黑色那么从根到新节点这条路径上的黑高立刻比别的路径多 1直接违反第 5 条而这个性质是最难修复的。涂红色则不会破坏黑高最多只会出现连续红节点也就是可能违反第 4 条但第 4 条是局部约束修复起来代价小得多。这个选择背后就是典型的“把问题限制在容易处理的场景”。修复过程关注三个节点当前节点 z、它的父节点 p、它的叔节点 u即 p 的兄弟。当 z 的父节点是黑色时直接结束因为这棵树依然合法。需要处理的就是父节点为红色的情况它按叔叔节点的颜色和位置分裂成三种 case。4.2 三种情况的处理策略第一种叔叔节点是红色。这种情况最温柔不需要旋转只需要变色把父节点和叔叔节点都变成黑色把祖父节点变成红色。这样做的效果是原来从祖父到两个子路径上的黑高保持不变但“红色往上移动”到了祖父。接下来把 z 指向祖父继续向上检查。注意如果祖父正好是根最后一步要把根强制涂黑。第二种叔叔节点是黑色且 z 是父节点的“内侧”孩子。所谓内侧是指父节点是左孩子而 z 是右孩子或者父节点是右孩子而 z 是左孩子也就是形成了 LR 或 RL 的形状。这时候直接对祖父旋转没法一步到位需要先对父节点做一次旋转把它转化成第三种情况。比如父是左孩子、z 是右孩子就先对父节点左旋然后 z 和父的角色互换变成“父是左孩子且 z 也是左孩子”的形状。第三种叔叔节点是黑色且 z 是父节点的“外侧”孩子也就是 LL 或 RR 形状。这时对祖父节点做一次旋转让父节点顶替祖父的位置然后交换父和祖父的颜色父变黑祖父变红。这样整棵子树的黑高恢复原状连续红节点也消除了调整可以直接结束。这三种情况的判断顺序不是随意定的。变色的 case 会把问题抛给上一层靠循环解决而旋转的 case 一旦执行整棵子树立刻合法循环就终止了。所以说红黑树插入最坏情况下只需两次旋转但变色操作的次数可以沿着路径累积到 O(log n)。4.3 插入代码实现下面是我整理好的插入修复函数代码里我故意保留了“插入后统一修复”的结构方便你对照上面的 case 理解。void rb_insert_fixup(rb_node **root, rb_node *z) { while (z-parent ! NULL z-parent-color 1) { rb_node *p z-parent; rb_node *g p-parent; rb_node *u (p g-left) ? g-right : g-left; if (u ! NULL u-color 1) { // case 1: 叔红变色后上移 u-color 0; p-color 0; g-color 1; z g; } else { if (p g-left) { if (z p-right) { // case 2 的内侧情况先左旋父节点 z p; rotate_left(root, z); p z-parent; } // case 3: 外侧情况右旋祖父并变色 rotate_right(root, g); p-color 0; g-color 1; break; } else { if (z p-left) { z p; rotate_right(root, z); p z-parent; } rotate_left(root, g); p-color 0; g-color 1; break; } } } (*root)-color 0; }这里要注意case 2 我直接沿用了“z p 再重新取 p”的写法这样代码结构上和教科书版一致逻辑更清晰。实际生产代码里有人会写得更高压缩但可读性差很多我建议先按这个清晰版本理解再慢慢优化。5. 删除实操最麻烦的双黑问题5.1 删除流程与替换删除法删除比插入复杂核心难点在于如果删掉一个黑色节点那么从根到它叶子路径上的黑高就少 1这会破坏第 5 条“所有路径黑高相同”的性质而且不像插入那样有个“红色往上提”的简单策略删除修复的这个黑色缺失会一直存在直到我们通过旋转和变色把它补回来。先说删除节点的基本策略。如果待删节点 z 最多只有一个非空子节点那就直接用子节点顶替它这种最简单。如果 z 有两个非空子节点标准做法是“替换删除”找到 z 的中序后继 y把 y 的 key 值拷贝到 z然后删除 y。因为 y 是右子树的最左节点它最多只有一个非空右孩子这样问题又退化到单子节点场景。这个技巧很巧妙地避免了直接删除有两个孩子的节点时复杂的子链接操作。真正需要修复的是实际被删除的节点 y 为黑色的情况。我们把顶替 y 位置的那个节点记为 x如果 x 是红色直接把它涂黑就能补回黑高万事大吉如果 x 也是黑色那么这棵子树相对于外界“少了一个黑”我们把这种情况称为 x 带有“双黑”修复的目标就是消除这个双黑。5.2 兄弟节点的四种情况删除修复是在循环中处理的每次处理时双黑节点 x 处于某个父节点 p 之下我们关注 x 的兄弟节点 w。为便于描述假设 x 是 p 的左孩子右边情况对称。第一种情况w 是红色。这说明父节点 p 一定是黑色且 w 的两个孩子都是黑色。处理方式是左旋 p把 w 提上来然后染色w 变黑p 变红。经过这次操作x 的兄弟变成原来 w 的左孩子一个黑色节点问题转化到后面的 case 2、3、4。第二种情况w 是黑色且 w 的两个孩子都是黑色。这是最“温和”的向上抛问题把 w 变成红色这样 x 和 w 两侧的黑高各少 1双黑被吸收到 p 身上x 指向 p循环继续。注意如果 p 是红色循环结束后把它涂黑即可。第三种情况w 是黑色w 的左孩子是红色右孩子是黑色。个案型处理对 w 右旋把 w 的左孩子提上来染黑顶替的节点w 变红。这样处理之后新兄弟节点变成了此前 w 的左孩子它有一个红色右孩子正好满足第四种情况的前提。第四种情况w 是黑色w 的右孩子是红色。这是唯一能结束循环的旋转 case对 p 左旋w 继承 p 的颜色p 变成黑色w 的右孩子变成黑色。这一步把黑高缺口完美补上x 直接指向根节点循环终止。综合来看删除修复最多三次旋转但变色和向上传播可以一路走到根所以时间复杂度是 O(log n)。我当年写删除时最常犯的错误就是漏掉“x 可能是 NIL 节点”的情况——实际被删的是黑色叶节点顶替它的就是空节点 NIL代码里必须允许 x 本身为 NULL但不能对 NULL 解引用。5.3 删除修复代码实现为了方便理解我把删除修复也按“x 是左孩子”和“x 是右孩子”两个分支来写镜像逻辑直接复制后左右互换虽然代码长了点但比用 helper 隐藏对称性更容易读。void rb_delete_fixup(rb_node **root, rb_node *x, rb_node *parent) { while (x ! *root (x NULL || x-color 0)) { if (x parent-left) { rb_node *w parent-right; if (w-color 1) { // case 1: 兄弟红 w-color 0; parent-color 1; rotate_left(root, parent); w parent-right; } if ((w-left NULL || w-left-color 0) (w-right NULL || w-right-color 0)) { // case 2: 兄弟黑且兄弟的孩子全黑 w-color 1; x parent; parent x-parent; } else { if (w-right NULL || w-right-color 0) { // case 3: 兄弟的右孩子黑左孩子红 if (w-left ! NULL) { w-left-color 0; } w-color 1; rotate_right(root, w); w parent-right; } // case 4: 兄弟的右孩子红 w-color parent-color; parent-color 0; if (w-right ! NULL) { w-right-color 0; } rotate_left(root, parent); x *root; break; } } else { // 镜像逻辑不再逐行解释 rb_node *w parent-left; if (w-color 1) { w-color 0; parent-color 1; rotate_right(root, parent); w parent-left; } if ((w-left NULL || w-left-color 0) (w-right NULL || w-right-color 0)) { w-color 1; x parent; parent x-parent; } else { if (w-left NULL || w-left-color 0) { if (w-right ! NULL) { w-right-color 0; } w-color 1; rotate_left(root, w); w parent-left; } w-color parent-color; parent-color 0; if (w-left ! NULL) { w-left-color 0; } rotate_right(root, parent); x *root; break; } } } if (x ! NULL) { x-color 0; } }呼这段代码我每个分支都测试过随机插入删除但这属于“需要仔细对待”的代码你抄进自己的工程后一定要跑随机验证不要看一遍就认为没问题。6. 常见问题与排查技巧实录6.1 调试红黑树的心法手写红黑树的调试期是最痛苦的很容易出现“看起来对但随机操作几万次后某个性质被破坏”的幽灵问题。我的经验是不要用人眼盯着树看也不要只靠单测用例而是写一个校验器每次插入删除后都自动验证五条性质是否成立。一个合格的校验器要检查四件事根是否是黑、红节点的孩子是否是黑、所有路径黑高是否一致、树的中序序列是否有序。为了让校验器能找到问题节点我习惯在递归函数里返回“以当前节点为根的子树黑高”一旦发现某条路径黑高不一致立刻打印出该节点的 key 和左右子树的黑高这样能快速定位到失衡的局部。下面是我常用的递归校验代码基于 Python 写方便测试时快速验证。def check_rb(node, is_rootFalse): # 返回黑高非法返回 -1 if node is None: return 1 # NIL 叶子算一个黑高 if is_root and node.color ! black: print(root is not black) return -1 if node.color red: if node.left and node.left.color red: print(red-red at, node.key) return -1 if node.right and node.right.color red: print(red-red at, node.key) return -1 lh check_rb(node.left) if lh 0: return -1 rh check_rb(node.right) if rh 0: return -1 if lh ! rh: print(black height mismatch at, node.key, lh, rh) return -1 return lh (1 if node.color black else 0)这个校验器虽然简单但非常管用。我每次写完插入或删除会随机生成几十万条操作序列穿插插入和删除每步结束后都跑一遍校验一旦报错就二分定位到具体操作极大缩短了排查时间。6.2 最容易踩的三个坑第一个坑是 NIL 节点处理。很多教材画树时黑高是从“真正的叶子节点”算的但代码里叶子其实就是空指针。如果你在递归里没有把空节点当作黑色叶子处理插入删除的黑高逻辑很容易写错。我建议统一约定NULL 就是黑色 NIL 叶子这样代码条件判断里到处都要写“ NULL || color 0”看着烦但对。第二个坑是 parent 指针不同步。旋转代码里容易漏掉更新孩子节点的 parent或者漏掉判断“当前节点是不是根”结果 list 遍历时出现环形指针程序直接死循环。排查这种问题很折磨所以我建议旋转函数里先更新所有孩子 parent再更新父 parent再更新 root每一步都按顺序来。第三个坑是删除修复的循环条件。修复循环必须在 x 成为根节点或 x 为红色时终止。如果你把“x NULL”漏在循环条件外就会在删除黑色叶节点时对空指针解引用。我吃过的亏是循环写成 while(x ! root x-color 0)结果 x 为 NULL 时直接崩溃改成允许 NULL 的版本后才稳定。7. 红黑树的工程应用与选型建议7.1 你身边那些看不见的红黑树红黑树并不只是面试题它是很多基础组件的核心结构。我最早从 Java 的 TreeMap 和 TreeSet 开始认识它这两个类底层就是红黑树要求 key 可排序且支持范围查询。C 的 std::map 和 std::set 也是红黑树标准库对它迭代器的稳定性保证正是来自红黑树插入删除对结构局部性的控制。Linux 内核里红黑树用得更多CFS 调度器用它管理进程调度实体保证每次都能以 O(log n) 找到最小虚拟运行时间的进程epoll 用它管理被监听的文件描述符。Nginx 的定时器也是经典的红黑树应用通过 key 是超时时间快速找到最快到期的定时器。你会发现凡是需要“动态插入、删除、频繁查找最值”的场景红黑树都是高频选择。7.2 红黑树、AVL 与跳表的取舍选型时我经常要比较红黑树、AVL 和跳表。AVL 的树更矮查找性能理论更好但删除旋转次数比红黑树多对写多场景不友好。跳表实现异常简单区间查询和并发改造都容易Redis 的有序集合就用的跳表但它需要额外的层指针内存占用偏高而且最坏情况下没有严格的平衡保证。红黑树的优势是内存紧凑、插入删除旋转次数有硬上限、树高稳定劣势是实现复杂、对并发场景需要额外加锁。如果是写一个通用有序集合红黑树基本可以无脑选如果需求特别看重实现简单和并发读多写多跳表值得考虑如果场景几乎是静态数据、只做高频查找AVL 依然能打。没有“最强的数据结构”只有“最匹配当前场景的结构”这句话我是在调了无数次优之后才真正认同的。7.3 我的建议路线最后给你一条我自己验证过的学习路径。第一步别急着背 case先把五条性质写在一张纸上。第二步实现二叉搜索树的查找、插入、删除至少搞清楚中序后继。第三步实现旋转。第四步加校验器。第五步写插入修复跑随机测试。第六步写删除修复继续跑随机测试。每一步都让前面的代码可运行、可验证再进入下一步。从看着 TreeMap 源码头晕到自己把红黑树完整跑通我最大的体会是红黑树学习的真正门槛不在那六个 case而在你能不能把“为什么新节点是红色”“为什么删除会产生双黑”“为什么旋转不破坏有序性”这几个为什么想透。想透之后case 只是若干种形状的组合你完全可以现场推导出来。如果你也想彻底告别对红黑树的恐惧我建议今天就写个校验器再开始写插入多跑几轮随机测试那比看十遍教程都管用。
习题集》全答案PDF：筛选、编译与避坑指南)
