咕咕咕……这篇红黑树的学习笔记我从年初鸽到现在才完整梳理出来。红黑树这几个字在面试、算法竞赛、阅读标准库源码时几乎绕不开但真正要把插入删除等原理讲透光靠背“五条性质”远远不够。很多人的体验是看插入时还能跟上到删除处理“双黑”就断片再遇到“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 五条性质背后真正起作用的只有两条红黑树的标准定义是五条性质每个节点不是红色就是黑色根节点是黑色每个叶子节点NIL是黑色这个 NIL 是哨兵节点不是普通意义上的空指针红色节点不能有红色子节点即不允许连续红色从任意节点到其所有 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 双黑修复的四种形态双黑节点的修复主要围绕“兄弟节点”展开。设当前需要修复的节点为 xx 的父节点为 px 的兄弟节点为 s。s 的情况决定了四种处理策略。兄弟情况处理方式最终结果s 为红对 p 旋转一次s 染成黑色p 染成红色然后继续修复原来的红兄弟变成黑兄弟转入后续黑兄弟分支s 为黑s 的两个子节点都是黑s 染红双黑上移给 p如果 p 红p 染黑结束如果 p 黑继续修复 ps 为黑远侄子为红绕 p 旋转s 继承 p 的颜色p 染黑远侄子染黑双黑消除修复结束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 树度数二叉每个节点最多两个孩子多路一个节点可以有几十到几百个孩子数据存储每个节点都存完整键值内部节点只存索引键数据在叶子查找路径每层只能二分树高约 log2 n每层多路比较树高约 logm n存储层级主要面向内存主要面向磁盘/SSD顺序访问中序遍历不够连续叶子链表天然适合范围查询重平衡颜色翻转 旋转节点拆分与合并其实红黑树可以认为是一种特殊的 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::setJava 的 TreeMap、TreeSetLinux 内核里的 rbtreeNginx 的定时器和 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 树是红黑树吗”这类递进问题。这棵被鸽了很久的红黑树笔记终于写完了如果你正卡在删除修复的对称逻辑里记住一个诀窍先修好校验器让程序替你做黑高论证。