企业官网建设流程全解析

咕咕咕……这篇红黑树的学习笔记，我从年初鸽到现在才完整梳理出来。红黑树这几个字，在面试、算法竞赛、阅读标准库源码时几乎绕不开，但真正要把插入删除等原理讲透，光靠背“五条性质”远远不够。很多人的体验是：看插入时还能跟上，到删除处理“双黑”就断片，再遇到“B+树是红黑树吗”这种追问，更是答不到点子上。这篇文章我就用实践推导的方式，把红黑树的平衡机制、插入删除全流程、与 B+树的纠葛，以及工程实现时最容易被坑的地方一次性说清楚。

1. 红黑树入门：它不是普通平衡树，而是“适度平衡”的二叉搜索树

1.1 普通二叉搜索树最大的问题

二叉搜索树本身很好懂：左小右大，查找时不断二分。可是插入顺序一旦很“倒霉”，比如按 1、2、3、4、5 依次插入，树就会退化成一棵“链表”。这时候查找复杂度从 O(log n) 直接掉到 O(n)。所以“平衡”两个字不是锦上添花，而是保证性能下限的关键。

AVL 树是第一种严格平衡思路：要求任何节点的左右子树高度差不超过 1。它确实能保证 O(log n)，但代价是每次插入删除都可能需要旋转，而且旋转点频繁散布在整棵树各处。AVL 很“完美主义”，但工程上往往不是为了完美，而是为了成本可控。

红黑树放弃了严格的“全树高度差不超过 1”，改用一个更松弛的平衡指标。它的好处是，插入删除时只需要局部调整，旋转次数更少。别小看这个差异：在频繁插入删除的场景下，红黑树的综合成本往往比 AVL 更低。

1.2 五条性质背后，真正起作用的只有两条

红黑树的标准定义是五条性质：

1. 每个节点不是红色就是黑色；
2. 根节点是黑色；
3. 每个叶子节点（NIL）是黑色，这个 NIL 是哨兵节点，不是普通意义上的空指针；
4. 红色节点不能有红色子节点，即不允许连续红色；
5. 从任意节点到其所有 NIL 叶子的路径上，黑色节点数量相同。

很多人第一次看到第五条会被吓到：什么叫做“黑色节点数量相同”？其实就是说，不管从根节点往左走到底还是往右走到底，沿途遇到的黑色节点个数必须一致。这又叫做黑色高度相等。

一旦黑高相等，再配合第四条“不允许连续红色”，就能推出一条关键结论：一条路径上红色节点的数量不可能超过黑色节点数量。所以最短路径全是黑节点，最长路径是“黑红交替”，最长路径最多是最短路径的两倍。即使树不是严格等高，它的高度仍然被限制在 O(log n) 以内。

红黑树牺牲了一点平衡精度，换来更少的重平衡操作。这个交易在内存数据结构的真实场景里非常划算。

1.3 把红节点“并”到父节点：红黑树等价于 2-3-4 树

理解红黑树还有一条极好的捷径：把每个红色节点向上“并入”它的黑色父节点。如果两个子节点都是红色，就可以和父节点合并成一个“大节点”，这个大节点里最多有三个键，两个或三个子指针。

这样拆开来看，红黑树其实等价于一棵 2-3-4 树，也就是 B 树的一个特例。2-3-4 树里的“节点分裂”和“节点合并”，映射到红黑树就是颜色翻转和旋转。

这条等价关系特别重要，等我们后面讲插入删除时，可以把操作拆成：先做普通的二叉搜索树操作，再通过颜色翻转模拟节点分裂合并，最后用旋转修复树的结构。理解了这个，红黑树的很多“规定动作”就不再是死记硬背，而是有逻辑的。

提示：面试中如果被问到“红黑树和 B+ 树的关系”，这条等价性也能帮你答得更深。红黑树是内存版的平衡二叉系，B+ 树是磁盘版的多路平衡系，但它们的底层结构并不相同。

2. 插入操作：为什么说“叔节点”是主角

2.1 新节点为什么必须染成红色

红黑树的插入流程，第一步是按照普通二叉搜索树规则，把新节点放到某个叶子位置。问题来了：新节点应该先染成红色还是黑色？

如果染成黑色，那么这条新路径上的黑色节点数量就会比其他路径多 1，直接破坏了“黑高相等”这一全局性质。这是最难修复的问题，因为黑色多了一个，你得从根到叶子重新算所有路径，几乎没法只靠局部旋转收场。

如果染成红色，那么黑高没有被破坏，唯一的风险是“连续红色”。如果父节点是黑色，直接结束；如果父节点是红色，再通过变色和旋转去修复。很明显，红色带来的问题只存在于局部，修复成本可控。这就是为什么所有标准教材都默认新插入节点为红色。

2.2 插入后为什么要看叔节点

插入完成后，可能出现“新插入节点 z、父节点 p、祖父节点 g”都是红色？不对，祖父 g 通常必须是黑色，因为父 p 是红色时，祖父一定是黑色，否则插入前就违反了性质 4。现在需要看看与 p 同层的另一个子节点，也就是 z 的叔节点 u。

叔节点分三大类情况：

情况一：叔节点是红色。

这是最好处理的情况。把父节点 p 和叔节点 u 都染黑，再把祖父 g 染红。这样祖父以下的局部黑高保持不变，只是连续红色问题被上移到了祖父 g 和 g 的父节点之间。于是把 z 指向 g，继续向上一层修复。

情况二：叔节点是黑色（或者不存在），且 z 和父节点在祖父同一侧。

比如 z 是 p 的右孩子，p 是 g 的右孩子，这就是 RR 型；对称的 LL 型同理。这种情况下只需要旋转加变色：对祖父做一次左旋，然后把 p 染黑、g 染红。修复结束，因为旋转后新子树根是黑色，不会再向上传播。

情况三：叔节点是黑色（或者不存在），但 z 在父节点“内部”。

比如 p 是 g 的左孩子，z 是 p 的右孩子，也就是 LR 型。这种情况不能直接旋转祖父，否则结构会变得不对劲。标准做法是先绕 p 做一次左旋，让 z 移动到外侧，把 LR 型变成 LL 型，再按情况二处理。反过来 RL 型则先右旋再左旋。

为什么叔节点的颜色如此关键？因为叔节点的颜色直接决定了“黑色路径的黑高能不能被局部修复”。叔红说明祖父的左右两侧黑高都已经填充完整，只要变色就可以；叔黑说明另一侧已经没有多余黑色可以“借”，只能靠旋转改变树的形态。

2.3 插入修复伪代码与一次实机推演

我把插入修复的流程整理成逐步伪代码：

void insertFixup(Node* z) { while (z && z->parent && z->parent->color == RED) { Node* g = z->parent->parent; if (z->parent == g->left) { Node* u = g->right; // 情况一：叔红 if (u != NIL && u->color == RED) { z->parent->color = BLACK; u->color = BLACK; g->color = RED; z = g; // 向上推进 } else { // 情况三：z 处于内侧重合，先转成外侧 if (z == z->parent->right) { z = z->parent; leftRotate(z); // 此时 z 变成原父节点 } // 情况二：LL z->parent->color = BLACK; g->color = RED; rightRotate(g); } } else { // 对称逻辑：父节点在祖父右边 Node* u = g->left; if (u != NIL && u->color == RED) { z->parent->color = BLACK; u->color = BLACK; g->color = RED; z = g; } else { if (z == z->parent->left) { z = z->parent; rightRotate(z); } z->parent->color = BLACK; g->color = RED; leftRotate(g); } } } root->color = BLACK; // 防止根被染红 }

只看代码还是不够，我建议你亲手推一遍“插入 1、2、3、4、5”。我用文字带一下关键节点：

• 插入 1：红色节点，根必须染黑；
• 插入 2：父 1 是黑，结束；
• 插入 3：父 2 红，叔是 NIL 视为黑，RR 型，左旋 1，染黑 2，染红 1；
• 插入 4：父 3 红，叔 1 红，变色，把祖父 2 染红，最后根强制染黑；
• 插入 5：父 4 红，叔 NIL 黑色，RR 型，左旋 3，染黑 4，染红 3。

推完你会发现，真正需要旋转的只有两种情况，其他时候都在变色。这也是红黑树插入“看起来复杂，实际写起来不算难”的原因。

3. 删除操作：双黑节点才是真正的硬骨头

3.1 删除前先理解替换删除

红黑树的删除比插入难，难点在于：删除节点可能有两条非空子树，红黑树不能直接移掉。删一个有两个孩子的节点，常规策略是找它的后继（右子树中的最小节点）或前驱，用后继的值替掉待删节点的值，然后问题转成“删除后继节点”。后继节点最多只有一个非空孩子，所以实际物理删除的节点最多带一个孩子。

如果物理删除的节点是红色，那就没任何影响：因为它只有一个孩子且大概率是 NIL，删除红色节点不会改变黑高，也不会形成连续红色。

如果物理删除的节点是黑色，麻烦来了：这一侧路径上的黑色节点数量减少了一个，整体黑高不再相等。把这条路径想象成“欠了一个黑色”，这个状态就叫做“双黑节点”。

3.2 双黑修复的四种形态

双黑节点的修复主要围绕“兄弟节点”展开。设当前需要修复的节点为 x，x 的父节点为 p，x 的兄弟节点为 s。s 的情况决定了四种处理策略。

这里的“远侄子”是指与 x 不在同一侧的子节点。如果 x 是父亲的左孩子，那 x 的兄弟 s 在右边，s 的右孩子就是远侄子。这个方向感一旦错乱，旋转就会转反，越修越乱。

为什么会有这么多分类？核心原因是“借贷”原则：x 这条路径少了一个黑色，要么从兄弟子树借一个黑色过来，要么把黑色欠账上推给父节点，让父节点所在的整棵子树重新平衡。

如果兄弟是黑色且侄子全黑，说明兄弟子树里没有红色节点可以“动员”，不能直接借黑。此时只好把兄弟染红，让兄弟侧也少一个黑，这样局部黑高一致了，但父节点这条整体路径比全局少了一个黑，于是“双黑”上移给父节点。

如果兄弟是黑色且远侄子红，就可以“动员”红侄子：旋转后远侄子变成新的子树根的一部分，染黑后补上了缺失的黑色。这是最有“操作感”的一类情况，也是删除修复的收尾动作。

3.3 删除修复伪代码与自查要点

删除修复的标准实现一般长这样：

void deleteFixup(Node* x) { while (x != root && x->color == BLACK) { if (x == x->parent->left) { Node* s = x->parent->right; // 兄弟红 if (s->color == RED) { s->color = BLACK; x->parent->color = RED; leftRotate(x->parent); s = x->parent->right; } // 兄弟黑，两个侄子黑 if (s->left->color == BLACK && s->right->color == BLACK) { s->color = RED; x = x->parent; // 双黑上移 } else { // 近侄子红，远侄子黑 if (s->right->color == BLACK) { s->left->color = BLACK; s->color = RED; rightRotate(s); s = x->parent->right; } // 远侄子红 s->color = x->parent->color; x->parent->color = BLACK; s->right->color = BLACK; leftRotate(x->parent); x = root; // 结束循环 } } else { // 对称逻辑，把 right 和 left 互换 } } x->color = BLACK; }

这段代码有一个前提：s 的两个孩子在修护过程中必须始终存在，所以实际实现中会引入 NIL 哨兵节点，不能直接用 C++ 里的 nullptr 去访问。很多人随手写红黑树时让 NIL 为空指针，最后在 deleteFixup 里疯狂段错误，就是因为没有建哨兵。

自查删除是否正确，有一个非常土但有效的方式：把删除前和删除后的树分别做一次“黑高校验”。从根出发，统计每条路径上的黑节点数量，必须一致。删除过程中只要哪一侧想不通，就是当前旋转并没有真正补回那个黑色“欠账”。

实操心得：我练习红黑树删除时，会在每次旋转后打印当前树的结构和黑高。这一步虽然麻烦，但远比自己脑内“追黑”可靠。不要迷信一次推演，红黑树的对称分支特别容易写反，必须靠程序化断言兜底。

4. B+ 树是红黑树吗？两个平衡树的“表亲”之争

4.1 B+ 树的形态与设计动机

先给结论：B+ 树不是红黑树。它们是平衡树家族里的两种不同实现，甚至在存储层级上都不是一回事。

B+ 树是一种多路搜索树，一个节点可以存储多个键，通常一个节点大小对齐磁盘页，比如 4KB 或 16KB。它内部节点只存索引键，不存真实数据；所有数据都放在叶子节点，并且叶子节点通过指针串成链表。B+ 树的“多叉”特性让树高非常低，三层 B+ 树就能支撑百万甚至亿级数据。

B+ 树最典型的场景是数据库索引和文件系统。磁盘随机 I/O 的代价远高于内存，所以宁可在一个节点里多做几次比较，也要减少树的高度，让一次查询尽量少访问磁盘页。

4.2 红黑树与 B+ 树的关键差异

红黑树和 B+ 树的差异可以通过一个表格看得更明白：

其实红黑树可以认为是一种特殊的 B 树：把红色节点和黑色父节点合并成一个多键节点后，它退化成 2-3-4 树，也就是 4 阶 B 树。这个等价关系藏在名字里，但也仅此而已。真正能叫 B+ 树的是另一套面向磁盘的设计，内部节点不存数据、叶子链表串联、通过扇出降低层高。

4.3 为什么总有人拿红黑树和 B+ 树比较

面试里问“B+ 树是红黑树吗”，其实是想确认你有没有把两者底层逻辑打通。红黑树和 B+ 树都解决“有序数据的高效查找问题”，也都靠“路径高度稳定”来保证复杂度。但红黑树面向内存场景，B+ 树面向磁盘场景，二者不是替代关系。

如果是在内存里维护一个有序集合，比如 C++ 的 std::map、Java 的 TreeMap，红黑树是完全正确的答案。如果数据量大到必须落盘，比如 MySQL InnoDB 的聚簇索引，B+ 树才是正确形态。很多人把红黑树硬塞到数据库索引里，结果就是树高超高、页扫描过多、IO 爆炸。

提示：聊到 B+ 树时，最好主动提一下叶子链表和范围查询。这是 B+ 树区别于普通 B 树、也区别于红黑树的标志性能力。

5. 工程实现里的红黑树：标准库、隐蔽坑点和自测技巧

5.1 你其实每天都被红黑树包围

红黑树不是只在教科书里存在。C++ 标准库的 std::map 和 std::set，Java 的 TreeMap、TreeSet，Linux 内核里的 rbtree，Nginx 的定时器和 epoll 数据结构，都能看到红黑树的身影。

为什么这些库都选择红黑树而不是 AVL？因为它们既要满足有序操作，又要承受大量插入删除。AVL 在查询上更“极端严格”，但每次插入删除都可能触发更多旋转。红黑树用稍宽松的平衡换取了更少的调整次数，整体吞吐量在动态数据集上更有优势。

我在实际项目中很少手写红黑树，但经常需要理解 std::map 的操作成本。比如一个订单簿系统需要按价格排序、频繁插入删除档位，std::map 的红黑树实现就是最合适的容器之一，它的每次操作稳定 O(log n)，没有哈希表的扩容抖动，也没有排序数组的插入成本。

5.2 手写红黑树最容易翻车的四个地方

第一，没有 NIL 哨兵。删除修复里需要访问“空孩子”的颜色，如果直接用空指针，代码会崩。正确的做法是维护一个全局 NIL 节点，颜色为黑色，左右孩子都指向自己。这样所有空指针判断都可以简化为颜色判断。

第二，旋转时父指针更新不全。左旋和右旋不只是改 child 指针，还要改 parent 指针。漏了 parent 指针，插入删除后的向上回溯就会断链。这是手写实现最常见的低级错误。

第三，插入修复里忘记给根节点兜底涂黑。修复循环可能一路把红色传到根节点，所以函数末尾必须强制 root->color = BLACK，不能根是红色就直接返回。

第四，删除时没有区分“真正删除的节点”和“替代节点”。很多人把待删除节点直接摘掉，却忘了它的后继可能也是黑色，结果黑高少一后没有触发修复。

5.3 用黑高断言代替人肉检查

红黑树调试最大的问题是“看不出来”。写一个检查黑高的递归函数，能在每次插入删除后自动校验：

int blackHeight(Node* p) { if (p == NIL) return 1; if (p->color == RED) { // 红节点不能有红子 if (p->left->color == RED || p->right->color == RED) { throw std::runtime_error("red violation"); } } int lh = blackHeight(p->left); int rh = blackHeight(p->right); if (lh != rh) { throw std::runtime_error("black height mismatch"); } return (p->color == BLACK ? 1 : 0) + lh; }

可以把它集成到每次 insert 和 delete 的最后一步。这个校验器的成本是 O(n)，测试时无所谓，线上关掉就行。有了它，你就不需要每次旋转后自己在纸上推演整个树的状态。

我自己的经验是，先把校验器写好，再去手写插入删除，错误定位速度至少提升一倍。否则，一棵树几百个节点，肉眼根本看不出哪条路径黑高少了一个。

5.4 红黑树并不是万能容器

红黑树解决的是“有序动态集合”场景。如果你只做按 key 查找，不需要范围遍历，哈希表可能更快，平均 O(1) 胜过红黑树。如果数据是只读的，一次性排序后存进数组，二分查找的内存局部性也远超红黑树的链式访问。

还有一个容易被忽略的点：红黑树节点是分散分配的，频繁插入删除会产生大量内存分配和释放。在高频交易、嵌入式等场景，这可能会成为瓶颈。内核里会引入 slab 缓存或预分配节点池来缓解。

所以选型时先问自己三个问题：要不要有序性？要不要范围查询？插入删除是否频繁？只有这些答案是“是”，红黑树才是你的主战场。否则，哈希表、跳表、B 树族甚至普通数组都可能更合适。

复盘红黑树的各个细节，我个人最大的体会是：不要把红黑树当成一套孤立的技巧，把它看成“内存里的适度平衡树”，把 B+ 树看成“磁盘上的多路平衡树”，把 2-3-4 树当成两者之间的桥梁。这样才能回答清楚“B+ 树是红黑树吗”这类递进问题。这棵被鸽了很久的红黑树笔记终于写完了，如果你正卡在删除修复的对称逻辑里，记住一个诀窍：先修好校验器，让程序替你做黑高论证。