企业官网建设流程全解析

红黑树大概是数据结构里退学率最高的一章，没有之一。链表、栈、队列这些结构，说白了就是换种方式组织数据，看两遍代码基本能上手。但红黑树不一样，它天生带着一堆规则、旋转、变色、再平衡，哪怕你对着博客把插入的六种情况看完了，合上电脑自己动手画一棵树，不到三个节点就会卡住。这篇文章就是我自己学习红黑树时踩坑、卡壳、又慢慢想通之后的记录，梳理成一份偏实操的学习笔记，希望能帮到那些和我一样被红黑树反复折磨的读者。

红黑树本质上是一棵自平衡二叉搜索树，核心价值在于：无论数据怎么插入、怎么删除，它都能把树的高度限制在一个可控范围内，保证查找、插入、删除的时间复杂度稳定在 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₂(n+1)，和 log₂(n+1) 是同阶的，只是常数变成 2。虽然比 AVL 树的 1.44log₂(n+1) 宽松，但依然属于对数级别，不会轻易退化。用大白话说，红黑树给出了一个“最矮不会矮过全黑，最高不会高过红黑交替”的区间，在这个区间内怎么折腾，性能都在可控范围内。

我当时有一个特别大的顿悟：红黑树不是靠颜色来“好看”，颜色只是为了实现黑高统一、长度受限这套逻辑而引入的一个轻量标记。标记本身没有效果，但通过标记约束了树的结构，实现了平衡。

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) 的风险。能把这个逻辑讲清楚，比把十条代码背下来更能说明你真的理解了红黑树。希望这份学习记录能帮你少走一些弯路，就像当年如果有个前辈这样告诉我，我也会少掉很多头发。