红黑树大概是数据结构里退学率最高的一章没有之一。链表、栈、队列这些结构说白了就是换种方式组织数据看两遍代码基本能上手。但红黑树不一样它天生带着一堆规则、旋转、变色、再平衡哪怕你对着博客把插入的六种情况看完了合上电脑自己动手画一棵树不到三个节点就会卡住。这篇文章就是我自己学习红黑树时踩坑、卡壳、又慢慢想通之后的记录梳理成一份偏实操的学习笔记希望能帮到那些和我一样被红黑树反复折磨的读者。红黑树本质上是一棵自平衡二叉搜索树核心价值在于无论数据怎么插入、怎么删除它都能把树的高度限制在一个可控范围内保证查找、插入、删除的时间复杂度稳定在 O(log n)。听起来很美但真正学起来你会发现难的不是“它是什么”而是“它为什么这样做”。这篇内容不打算堆公式也不打算把所有代码贴一遍而是针对我当时最疑惑的几个点为什么节点要分红和黑、为什么插入新节点一定是红色、为什么删除比插入难这么多、为什么旋转之后还要变色逐一拆开讲。无论你是在准备面试、看 STL 源码还是单纯想搞懂红黑树原理这份记录都值得花点时间读完。1. 第一个疑惑:为什么二叉搜索树会“长歪”1.1 一棵退化的树有多离谱二叉搜索树有一个很朴素的规则左子树所有节点都比根小右子树所有节点都比根大。按这个规则插入数据理想情况下树会左右均匀分布查找效率自然高。但问题在于这个“理想情况”完全取决于插入顺序。假如数据是这样到达的50、60、70、80、90二叉搜索树会怎么构建每次新节点都比上一个节点大全部插入右子树结果树就退化成了一条链。看起来像一棵树实际上就是一张单向链表。这时候查找最后一个节点时间复杂度直接变成 O(n)和线性扫描没什么区别。数据量大起来这种退化会让系统性能从“秒回”变成“肉眼可见的卡顿”。我当时最朴素的疑惑是那为什么不每次插入后检查一下树歪了就手动掰正这个想法方向是对的但“掰正”这件事远比想象中复杂。你不仅要调整节点位置还得保证二叉搜索树的中序遍历顺序不变也就是说调整前后这棵树“读”出来的元素序列必须完全一致。稍微动错一个节点整棵树的搜索性质就崩了。1.2 平衡不是“对称”而是“高度可控”初学者容易把“平衡”理解成左右子树的节点数量一样多或者树长得像满二叉树那样对称。实际上平衡树追求的从来不是绝对对称而是高度可控。只要能把树的高度控制在 O(log n) 量级最坏情况的查找路径就不会太长。AVL 树就是一种严格平衡的方案它要求任意节点的左右子树高度差不超过 1。这个约束非常苛刻所以 AVL 树的平衡性极好但代价是插入和删除后需要频繁旋转维护成本高。红黑树则放宽了条件它允许左右子树高度差更大但通过颜色约束把最长路径控制在最短路径的两倍以内。这个“两倍以内”是理解红黑树的关键。为什么是两倍因为红黑树有一条规则是“红色节点的两个子节点必须是黑色”再配合每条路径上黑色节点数相同任何一条路径上最多只能交替出现红黑节点。如果一条路径全是黑色节点另一条路径红黑交替那么后者的长度顶多就是前者的两倍。这就能保证树不会像链表那样无限退化同时又比 AVL 树少了大量旋转操作整体性能更均衡。2. 红黑树的“红”与“黑”到底在约束什么2.1 五条规则的白话解读正式场合里红黑树的定义有五条规则几乎每本教材都有。但我学的时候觉得逐字背下来没什么用真正需要的是理解每条规则在物理层面上限制了什么。节点不是红色就是黑色。这就是颜色标记没有更多含义。根节点必须是黑色。这条规则是为了处理边界情况更统一本质上是人为约定。每个叶子节点NIL 空节点都是黑色。这条最容易忽略很多画图时把 NIL 画掉导致理解偏差。红色节点的两个子节点必须是黑色。这条的意思是红色节点不能连续出现整棵树上不允许出现“红-红”这种父子组合。从任意节点到其所有后代叶节点的路径上黑色节点数量相同。第五条也就是“黑高相等”它才是最核心的平衡保证。前几条规则看起来很散其实都是为第五条服务的。连续红色禁止是在限制路径长度黑高相等是在确保所有路径的黑色骨架一致。2.2 从黑高的角度理解树的高度上限“黑高”这个词我第一次看到时完全没概念。其实它就是一个节点到叶子节点的路径上黑色节点的个数根节点的黑高就是整棵树的黑高。因为每条路径上黑色节点数相同所以根到叶子最短的那条路径理论上是全黑路径长度为黑高 h。而最长路径呢只能黑红交替因为红色不能连续出现所以最长路径最多也就是 h 个红色节点交替出现总节点数不会超过 2h。这就直接导出了根到任意叶子路径长度不超过 2h 的结论。也就是说红黑树的高度上限大约是 2log₂(n1)和 log₂(n1) 是同阶的只是常数变成 2。虽然比 AVL 树的 1.44log₂(n1) 宽松但依然属于对数级别不会轻易退化。用大白话说红黑树给出了一个“最矮不会矮过全黑最高不会高过红黑交替”的区间在这个区间内怎么折腾性能都在可控范围内。我当时有一个特别大的顿悟红黑树不是靠颜色来“好看”颜色只是为了实现黑高统一、长度受限这套逻辑而引入的一个轻量标记。标记本身没有效果但通过标记约束了树的结构实现了平衡。3. 插入阶段旋转变色比想象中难3.1 为什么新插入的节点必须是红色看插入代码时大多数教科书都会先把新节点涂成红色。我当时非常不理解红黑树要求红色不能连续你插入红色不是主动制造违规吗答案是插入新节点时只要把节点涂成红色就不会破坏“黑高相等”这条最重要的规则因为黑色节点数没变。此时唯一可能被破坏的规则就是“红色节点不能有红色子节点”。这个问题相对好修因为红色违规是局部性的只需要在局部做变色和旋转不用牵扯整棵树。反过来如果新节点涂成黑色它所在路径上就多了一个黑色节点黑高立刻不相等。黑高不相等意味着整棵树可能有多条路径都受影响修复范围会扩大到全局代价大得多。所以插入用红色本质是一门“先保主要矛盾、再处理次要矛盾”的策略。3.2 叔叔节点的颜色是分情况的关键新节点插入后如果父节点是黑色那就皆大欢喜什么也不用做。麻烦的是父节点也是红色构成了“红-红”违规。这时候先看爷爷节点的另一个孩子也就是叔叔节点情况就分成了两大类。第一类叔叔节点是红色。这种情况比较好处理因为爷爷节点必然是黑色红红父子已经违规但爷爷在孩子插入前是合法的所以爷爷一定是黑色。那就把父节点和叔叔节点都涂成黑色把爷爷涂成红色。这样处理完后“红-红”违规从当前层转移到了爷爷层爷爷带着它在更高一层再检查。这就像把一个小火苗往上一层推最终推到根节点直接把根涂黑就全部搞定了。第二类叔叔节点是黑色。这时候直接变色解决不了问题因为爷爷一侧的路径被改动了黑高。如果父节点是爷爷的左孩子新节点是父节点的左孩子也就是“左左”形态那就针对爷爷做一次右旋然后把父节点涂黑、爷爷涂红颜色和结构同步调整黑高保持稳定。如果新节点是父节点的右孩子“左右”形态就要先在父节点处做一次左旋变成“左左”再走上面的流程。我当时记这四个方向的时候特别痛苦后来发现其实不需要背“左左”“左右”“右左”“右右”你只需要记住一个原则如果当前节点和父节点同向就旋转一次如果是异向就先转一次让它们同向再转一次结束。最终结果永远是爷爷变成红色原来的父节点变成黑色新节点保持红色。3.3 用“三个角色”替代“六种情况”很多文章为了严谨把插入修复写成六种情况我看完第一反应是这谁能记住。后来我自己总结其实不必要分那么细只要记住三个角色新节点、父节点、叔叔节点。父节点是黑色直接结束。叔叔节点是红色变色向上递归。叔叔节点是黑色旋转加变色先定向再旋转。我在纸上画过几十棵随机树验证了这个思路确实能覆盖所有情况。真正写代码时只需要在当前节点循环向上处理每次都判断父节点、叔叔节点的颜色一层一层往上收代码量并不大。旋转的过程本质上是把一棵子树的根换掉左旋就是把新的根提升上来原来的根挂到新根的左子树下右旋同理只是方向相反。这个操作理解透了插入修复最多不会超过两次旋转。4. 删除阶段双黑问题才是真正的分水岭4.1 删除一个节点为什么这么麻烦插入节点的目标很单纯新节点是红色顶多破坏局部红红规则。删除节点就完全不一样了因为你不知道删掉的是红色节点还是黑色节点。如果删除的是红色节点一切好说黑高不变红色规则也没被破坏红色节点的子节点必须是黑色删除红色节点不会产生连续红。真正麻烦的是删除黑色节点。某条路径上少了一个黑色节点整个黑高系统就崩了所有路径的黑色数不统一。更隐蔽的问题是如果被删除的黑色节点只有左孩子或者只有右孩子总之后继节点被顶上来或者删除的节点有左右两个孩子需要找后继节点来替换整个过程会更加复杂。总之红色删除不破坏平衡黑色删除才需要修复。4.2 “双重黑”到底是什么我第一次看删除代码时遇到“双黑”这个概念整个人都是懵的。书上说删除黑色节点后要给它顶替上来的节点标记成“双重黑”。这是什么意思我当时是这么理解过来的删掉一个黑色节点相当于从整棵树里拿走了一个黑色。为了让黑高重新统一我们就“欠”了这条路径一个黑色。这个“欠账”用一个虚拟的双黑标记来表达意思是这个节点现在要承担一个额外黑色额度的责任。修复的过程本质上就是想办法把这个“双黑”标记消除。消除的途径无非两种一是通过旋转从兄弟子树那边“借”一个黑色过来补上二是把标记向上传播让父节点变成双黑然后在更高层继续处理。这个思路一旦打通删除修复就不再是记流程而是理解“欠账和还账”。4.3 删除修复的四类对应关系删除修复同样看兄弟节点准确说是看兄弟节点的颜色和兄弟节点的孩子颜色。以被删节点是父节点的左孩子为例右孩子完全对称兄弟节点是红色。这种情况下把父节点左旋兄弟节点变黑、父节点变红然后问题就转换成了兄弟节点是黑色的情形继续处理。兄弟节点是黑色且兄弟的两个孩子都是黑色。把兄弟节点涂红双黑标记上移到父节点。父节点如果原来是红色变成黑色任务结束如果原来是黑色就继续循环处理。兄弟节点是黑色且兄弟节点的左孩子是红色、右孩子是黑色。先在兄弟节点处右旋交换兄弟节点和它右孩子的颜色转换成“兄弟右孩子是红色”的情形。兄弟节点是黑色且兄弟节点的右孩子是红色。直接对父节点左旋把兄弟节点变成父节点的颜色父节点变黑兄弟右孩子变黑双黑标记消除。这四个方向的确比插入复杂但逻辑核心是一致的尽可能用旋转把黑色往双黑节点所在路径上推实在推不动就把问题向上传导。我写代码时发现真正容易出错的是第二步“兄弟的两个孩子都是黑色涂红兄弟把问题向上移”这一支因为它不改变树的拓扑只是换颜色初学者很容易漏掉向上循环这一步。很多人问删除修复最多会触发几次旋转答案是三次以内并不会无限循环因为每次旋转之后树的高度都会趋于收敛最终肯定会在有限步内结束。复杂度依然是 O(log n)只是常数比插入大一些这也是红黑树删除比插入慢的真实感受来源。5. 红黑树和各种“近亲”怎么选5.1 红黑树和 AVL 树的取舍面试里最常见的对比就是红黑树和 AVL 树。二者的相同点是都能保证 O(log n) 的查找不同点在于平衡的严格程度和操作代价。AVL 树要求高度差不超过 1所以它更“矮胖”查找速度确实优于红黑树。但只要涉及插入和删除AVL 树就可能要一直旋转到根节点频繁修改树结构带来的开销相当可观。红黑树放宽了高度要求但每次插入最多两次旋转、删除最多三次旋转整体平衡和修改的代价要低得多。如果场景是查询远多于写入比如数据库索引页AVL 树或者更严格的结构可能更合适。如果是频繁插入删除比如一个通用的映射容器红黑树显然更均衡。Linux 内核的 CFS 调度器也用红黑树管理进程C STL 的 map、set 也用它这些场景都是读写混合的典型代表红黑树刚好能打。5.2 红黑树和 B 树、跳表的边界红黑树是内存里的平衡搜索结构B树通常用在磁盘存储里因为它的节点可以包含大量键值单次磁盘 IO 能够读取更多数据树更矮。数据库索引用 B树主要不是因为它比红黑树快多少而是磁盘 IO 的次数才是瓶颈B树通过大度数和叶子节点链表做了优化。至于跳表它用多层链表实现有序结构逻辑上比红黑树简单得多实现难度低调试也容易。Redis 的有序集合就用跳表。但跳表的空间开销更大最坏情况依赖随机性红黑树则是一个确定性的结构适合对上限有要求的场景。5.3 为什么很多底层库里红黑树是默认选项说句实话红黑树的性能未必在每项指标上都是第一但它是一个非常稳的折中方案。各种操作的时间复杂度在最坏情况下都是对数级别而且实现是一棵标准二叉树不涉及复杂的内存管理对缓存也相对友好。相比跳表红黑树不需要额外链表层级相比 B树红黑树不需要大节点和磁盘管理逻辑。如果你需要的是一个通用、可靠、有序的键值映射红黑树绝对是性价比最高的选择之一。这也是为什么你只要打开了 map 或 set 的源码大概率能看到红黑树内核的原因。6. 学习红黑树时我踩过的坑6.1 纸上画图很容易把 NIL 节点漏掉红黑树的很多规则依赖叶节点 NIL尤其是删除修复时兄弟节点两个“孩子”指的就是真实节点或 NIL 节点。我最初画图时默认省略 NIL导致判断兄弟孩子是否有红色节点时经常出错。后面我学乖了在纸上画图时一定用一个小方框把 NIL 节点标出来。看起来麻烦但思考路径时特别有用。尤其判断“兄弟节点的两个孩子都是黑色”这条分支如果漏掉 NIL就会把 NIL 当不存在然后走错分支。6.2 把旋转当作“手术”而不是“魔法”很多人看旋转代码觉得像魔术很难理解为什么旋转之后树仍然是二叉搜索树。其实旋转的本质是选中一个节点当“新根”把原来根摘下来重新挂接三个子树。整个过程只是改变了几个指针中序遍历顺序完全不变。我自己练习的时候做了一个小工具输入节点序列然后手动在纸上标出每次左旋、右旋前后树的形态。做了七八组数据之后旋转这个操作就不再神秘了。困难多半来自第一次接触时的抽象感多画几次就能建立肌肉记忆。6.3 不要用“背完整套代码”来学习红黑树我见过不少人学习红黑树的目标是“把插入、删除的全部代码默写下来”。坦白说这件事对理解和面试的意义都不大。算法面试如果考到红黑树通常是考察你对平衡树原理的理解或者让你手写实现多想想怎么裁剪成简化版本很少要求你把所有修复分支一字不差写出来。真正有效的方法是三步走第一步理解红黑树的五个性质尤其是黑高的意义第二步手动在白板上模拟插入和删除的每一种情形感受颜色和旋转的配合逻辑第三步再打开别人的实现代码逐行对照你理解的思路去验证。经过这三步你自己就能写出足够正确的实现而不是背下别人的代码。7. 写在最后的一点实际操作心得红黑树的难点不在于代码量有多大而在于它把多个抽象概念层层叠加在一起二叉搜索树的有序性、颜色标记、路径黑高、旋转操作、递归修复。每一层单独拿出去都不难叠在一起却让人容易顾此失彼。我的建议是学习的时候把关注点收窄一次只解决一个维度的问题。第一遍只关注插入而且只关注插入后如何通过变色处理“红-红”冲突第二遍再加入旋转第三遍再处理删除而且先把删除节点的情况归类为“删红节点不用管、删黑节点才要修”。把一个维度啃透了再叠加下一个会发现整体难度明显下降。如果你正准备面试不妨准备一道典型的场景题为什么哈希表很常见却还要用红黑树答案其实就是有序遍历和范围查询的需求以及最坏情况下哈希冲突导致 O(n) 的风险。能把这个逻辑讲清楚比把十条代码背下来更能说明你真的理解了红黑树。希望这份学习记录能帮你少走一些弯路就像当年如果有个前辈这样告诉我我也会少掉很多头发。