真的要手写一棵 C 红黑树吗很多人看到“平衡二叉树”和“红黑树”这两个词第一反应是背各种 case第二反应是打开资料发现红黑树插入删除居然有六七个分支然后默默关掉页面。但只要你用过 std::map、std::set就早就在和红黑树打交道了——C STL 的关联容器底层默认实现几乎都是红黑树。它不是考试专属玩具工程里一句map[key] value背后就是一棵红黑树在帮你保持有序并完成对数级别查找。这篇东西我想用真正写过、调试过红黑树的经验把“为什么需要它”“五条性质到底在说什么”“C 怎么落地”“STL 和数据库里的 B 树跟它什么关系”讲透。写到一半会给出一个可以直接跑通的红黑树核心实现后面还整理了我在实际项目中踩过的坑。适合正在学 C 数据结构、准备面试、或者想深入理解 STL 底层的人看。新手看不懂的地方我会用大白话解释有经验的人可以直接跳到实现部分。1. 先说结论这就是 C 里 map 的“骨架”1.1 红黑树在工程里的真实存在感很多同学把红黑树当成“面试魔咒”但它的存在感比你想象中强得多。C 标准库里的std::map、std::set、std::multimap、std::multiset主流实现libstdc、libc、MSVC STL底层都是红黑树。你在map里插入、删除、查找一个键平均和最坏时间复杂度都是 O(log n)。为什么不用哈希表因为红黑树能提供有序遍历而且最坏情况不会像哈希表那样因为冲突劣化到 O(n)。红黑树本质上是一棵“弱平衡”的二叉搜索树。它允许左右子树高度差超过 1但通过颜色约束把树高限制在 O(log n) 以内。相比 AVL 那种严格控制高度差不超过 1 的铁血纪律红黑树在插入删除时需要的结构调整更少所以 STL 在频繁增删场景下选它更划算。1.2 往工程落地前先想清楚三个问题你的场景是否需要有序键需要用lower_bound、find、顺序遍历才适合红黑树如果只按 key 查 valueunordered_map的哈希表通常更快。要不要支持重复键map不允许重复multimap允许。红黑树本身不关心键是否重复只是插入策略不同。内存和拷贝成本高不高红黑树每个节点要额外存颜色、左右孩子、父节点指针比哈希表节点重一些。如果键是可哈希的廉价类型哈希表往往更轻。想清楚这几个问题你就明白“STL 里为什么有 map 还有 unordered_map”了。2. 平衡二叉树与红黑树的底层逻辑2.1 二叉搜索树为何会退化成链表二叉搜索树BST的定义很简单左子树所有节点小于根右子树所有节点大于根。但只看定义的话它很容易长歪。按 1、2、3、4、5 的顺序插入会得到一棵纯右链的树查找 5 要一路走到叶子复杂度退化成 O(n)。这就是“不平衡”。平衡二叉树就是要在每次插入或删除后把树的高度拉回可控范围。AVL 树用高度差平衡因子判断一旦某个节点左右子树高度差超过 1就做旋转。红黑树不用高度用“颜色”约束最后同样能把树高控制住。2.2 红黑树五条性质逐条翻译成大白话红黑树的定义通常写成五条每个节点要么红色要么黑色。根节点是黑色。所有叶子节点NIL 空节点是黑色。红色节点的子节点必须是黑色。从任意节点到其每个叶子节点的路径上黑色节点数量相同。第一条是状态定义没什么好说的。第二条和第三条可以合并理解树不能以红色节点做根空叶子一律看成黑色。这里说的“叶子”不是我们日常说的“没有孩子的节点”而是指所有nullptr哨兵位置。第四条很关键红色节点不能挨着红色节点也就是“红红不相连”。第五条是整棵树的灵魂通常叫“黑高相等”任意节点往下走到任一空叶子经过的黑色节点数必须一样。把四条和五条合起来看一棵红黑树本质上是在保证“最长路径上的节点数不会超过最短路径的两倍”。为什么因为红色不能连续出现所以一条路径上红色节点数最多等于黑色节点数又因为每条路径黑色节点数相等所以最长路径长度最多 2 倍最短路径长度。这就是弱平衡。2.3 “黑高相等”如何保证 O(log n)如果一棵红黑树有 n 个节点它的高度 h 满足 h ≤ 2·log₂(n1)。证明思路很简单把所有红色节点去掉黑色节点会形成一棵“黑色平衡”的树这棵树的节点数至少是原树的一半而黑色全满的完全二叉树高度是 log 级别。所以红黑树高度是 O(log n)查找就不会退化。这也是为什么红黑树敢不用高度差只要颜色规则不被破坏性能就有下限保证。3. 旋转、变色与插入删除修复3.1 左旋、右旋的几何直观旋转是平衡二叉树的通用操作红黑树也只是换个花样用旋转。左旋就是把当前节点的右孩子“提上来”自己变成右孩子的左孩子右旋方向相反。用现实类比原来 A 是领导B 是 A 的右下手左旋后 B 当领导A 变成 B 的下属B 原来左下手过继给 A 当右下手。旋转之后中序遍历顺序不变所以它不会破坏 BST 的“左小右大”语义。旋转是调整结构、维护平衡的基础工具。用简单 ASCII 图表示右旋z / \ y t3 / \ t1 t2 右旋 y 上位后 y / \ t1 z / \ t2 t3左旋就是镜像对称。3.2 插入修复的三种局面插入新节点时默认把它染成红色。为什么选红色如果染黑会立刻破坏“黑高相等”所有经过它的路径黑色节点数都多了一个修复成本极高如果染红只可能破坏“红红不相连”影响范围更小。插入后如果新节点父亲是黑色直接结束整棵树依然合法。如果父亲是红色说明祖父一定存在而且祖父一定是黑色因为父亲是红父亲不能是根这时看叔叔祖父的另一个孩子的颜色分成三种情况叔叔是红色把父亲和叔叔都染黑祖父染红然后继续把祖父当成新插入的节点向上处理。这是最温和的“变色就能继续”的局面。叔叔是黑色且当前节点是父亲的右孩子先对父亲左旋把情况转成第三种本质上是把“拐弯”捋直。叔叔是黑色且当前节点是父亲的左孩子父亲染黑祖父染红再对祖父右旋局部重新平衡。我把这三种情况分别叫“变色上推”“左旋拐弯”“右旋定局”。背熟这三步插入修复就结束了最后记得把根强制染黑。3.3 删除修复为什么都说它比插入难删除的麻烦在于你删掉一个节点后如果这个节点是黑色某条路径上黑色节点数会少 1整棵树的“黑高相等”被破坏。所以删除后需要把缺失的黑色“补”回来。常见说法是让替代节点带上“双重黑色”然后在树里上推直到把多出来的一层黑色处理掉。标准做法分四个 case还是看兄弟节点的颜色和侄子节点的颜色兄弟是红色把兄弟染黑父亲染红旋转父亲把兄弟变成黑胡子兄弟然后继续。兄弟是黑色且兄弟的两个孩子都是黑色把兄弟染红问题向上推给父亲。兄弟是黑色兄弟的左孩子是红色、右孩子是黑色先把左孩子染黑兄弟染红右旋兄弟变成第四种情况。兄弟是黑色兄弟的右孩子是红色这是最理想的情况直接让兄弟继承父亲的颜色父亲染黑右孩子染黑然后左旋父亲问题解决。删除修复之所以难不是因为它算法更复杂而是因为 case 之间会相互转化而且每一步都在改变局部颜色状态。写代码的时候建议把每一个 case 的“入口条件”写成注释调试时能省很多时间。4. C 实现与完整代码下面这份实现我按教学优先的写法组织只存 key用哨兵节点nil代替所有空指针。这样做删除修复里即使操作的是“空叶子”也能安全访问color和parent逻辑和 CLRS 教材完全一致代码比一堆nullptr判断更干净。4.1 数据结构、哨兵与旋转#include iostream template typename T class RBTree { private: struct Node { T key; bool color; // true 红false 黑 Node* left; Node* right; Node* parent; Node(const T k, bool c, Node* nil) : key(k), color(c), left(nil), right(nil), parent(nil) {} }; Node* nil; Node* root; void leftRotate(Node* x) { Node* y x-right; x-right y-left; y-left-parent x; y-parent x-parent; if (x-parent nil) root y; else if (x x-parent-left) x-parent-left y; else x-parent-right y; y-left x; x-parent y; } void rightRotate(Node* x) { Node* y x-left; x-left y-right; y-right-parent x; y-parent x-parent; if (x-parent nil) root y; else if (x x-parent-right) x-parent-right y; else x-parent-left y; y-right x; x-parent y; } public: RBTree() { nil new Node(T{}, false, nullptr); nil-left nil-right nil-parent nil; root nil; } };注意nil自己成为一个黑色节点所有空位置都指向它。旋转函数里的y-left-parent x即使y-left是nil也安全因为nil有parent字段。4.2 插入与插入修复private: void insertFixup(Node* z) { while (z-parent-color true) { if (z-parent z-parent-parent-left) { Node* y z-parent-parent-right; // 叔叔 if (y-color true) { // 情况1叔叔红色变色后继续上推 z-parent-color false; y-color false; z-parent-parent-color true; z z-parent-parent; } else { // 情况2当前节点是右孩子先左旋父节点 if (z z-parent-right) { z z-parent; leftRotate(z); } // 情况3父黑、祖红、右旋祖父 z-parent-color false; z-parent-parent-color true; rightRotate(z-parent-parent); } } else { // 对称分支parent 是祖父的右孩子 Node* y z-parent-parent-left; if (y-color true) { z-parent-color false; y-color false; z-parent-parent-color true; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rightRotate(z); } z-parent-color false; z-parent-parent-color true; leftRotate(z-parent-parent); } } } root-color false; } public: void insert(const T key) { Node* z new Node(key, true, nil); Node* y nil; Node* x root; while (x ! nil) { y x; if (key x-key) x x-left; else if (key x-key) x x-right; else { delete z; return; // 已存在不处理重复键 } } z-parent y; if (y nil) root z; else if (key y-key) y-left z; else y-right z; insertFixup(z); }插入修复的核心就是三种情况。实际写代码时我建议把对称分支也完整写出来不要靠“这里对称”的注释脑补否则调试时会很痛苦。4.3 删除与删除修复删除操作先按普通 BST 删节点然后根据被删节点的原始颜色决定是否调用eraseFixup。只有被删节点是黑色时才需要修复因为只有黑色节点的减少会破坏黑高。private: Node* minimum(Node* x) const { while (x-left ! nil) x x-left; return x; } void transplant(Node* u, Node* v) { if (u-parent nil) root v; else if (u u-parent-left) u-parent-left v; else u-parent-right v; v-parent u-parent; } void eraseFixup(Node* x) { while (x ! root x-color false) { if (x x-parent-left) { Node* w x-parent-right; if (w-color true) { w-color false; x-parent-color true; leftRotate(x-parent); w x-parent-right; } if (w-left-color false w-right-color false) { w-color true; x x-parent; } else { if (w-right-color false) { w-left-color false; w-color true; rightRotate(w); w x-parent-right; } w-color x-parent-color; x-parent-color false; w-right-color false; leftRotate(x-parent); x root; } } else { Node* w x-parent-left; if (w-color true) { w-color false; x-parent-color true; rightRotate(x-parent); w x-parent-left; } if (w-right-color false w-left-color false) { w-color true; x x-parent; } else { if (w-left-color false) { w-right-color false; w-color true; leftRotate(w); w x-parent-left; } w-color x-parent-color; x-parent-color false; w-left-color false; rightRotate(x-parent); x root; } } } x-color false; } Node* findNode(const T key) const { Node* cur root; while (cur ! nil) { if (key cur-key) return cur; else if (key cur-key) cur cur-left; else cur cur-right; } return nil; } public: void erase(const T key) { Node* z findNode(key); if (z nil) return; Node* y z; Node* x; bool yOriginalColor y-color; if (z-left nil) { x z-right; transplant(z, z-right); } else if (z-right nil) { x z-left; transplant(z, z-left); } else { y minimum(z-right); yOriginalColor y-color; x y-right; if (y-parent z) { x-parent y; } else { transplant(y, y-right); y-right z-right; y-right-parent y; } transplant(z, y); y-left z-left; y-left-parent y; y-color z-color; } if (yOriginalColor false) eraseFixup(x); delete z; }这里最难理解的是“后继补位”分支当被删节点有两个孩子时实际真正删除的是右子树里的最小节点 y然后把 y 的内容搬到 z 的位置再给 y 换上 z 的颜色。这样不会破坏红黑树颜色结构只是物理位置上换了人。4.4 查找、遍历与自检函数public: bool contains(const T key) const { return findNode(key) ! nil; } void inorder(std::ostream os std::cout) const { inorderRec(root, os); os \n; } private: void inorderRec(Node* n, std::ostream os) const { if (n nil) return; inorderRec(n-left, os); os n-key ; inorderRec(n-right, os); } public: // 校验红黑树五条性质是否合法返回高度用于测试 int checkValid() const { bool ok true; int blackHeight 0; validateRec(root, ok, blackHeight); return ok ? blackHeight : -1; } private: void validateRec(Node* n, bool ok, int blackCount) const { if (n nil) { blackCount 1; return; } int lb 0, rb 0; validateRec(n-left, ok, lb); validateRec(n-right, ok, rb); if (lb ! rb) ok false; // 性质5 if (n-color true (n-left-color true || n-right-color true)) ok false; // 性质4 blackCount lb (n-color false ? 1 : 0); } };checkValid会在每次操作后返回黑高。如果返回 -1说明性质被破坏。我写红黑树时基本把它当成“测试仪器”每次插入删除后都跑一遍比肉眼快得多。5. 红黑树在 STL / 数据库 / 工程中的不同表现5.1 map 和 set 为什么选红黑树而不是 AVLAVL 要求任何节点的左右子树高度差不超过 1查找性能确实更好但为了维持这种铁血平衡插入删除时的旋转次数往往比红黑树多。红黑树允许最多两倍高度差读操作稍微慢一点点但写操作更省。工程场景里map的插入删除比 AVL 更频繁所以 STL 选红黑树。这不是说 AVL 没有用武之地它适合“查询远多于修改”的场景比如数据库内存索引、只读配置表。不要在面试时说“红黑树比 AVL 快”这个说法不严谨准确说法是“红黑树在频繁插入删除时调整成本更低AVL 查询更严格但调整更频繁”。5.2 B 树和红黑树有什么关系网上经常有人把 B 树和红黑树搞混其实 B 树不是红黑树。B 树是多路搜索树一个节点存多个 key适合磁盘 IO 的块读写红黑树是内存里的二叉搜索树。数据库 InnoDB 索引选 B 树是因为它能用一次磁盘 IO 读取多条索引记录且叶子节点链式相连非常适合范围扫描。红黑树在数据库领域并非主角但不少存储引擎的内存缓冲、日志索引、锁管理里会用红黑树做有序结构。Redis 的有序集合 zset 底层是“跳表 哈希表”的组合也不是红黑树不过 Redis 里某些内部数据结构确实可以用红黑树思路理解。碰到“B 树是红黑树吗”这类问题直接回答不是抓准三点B 树是多路、叶子链式、面向磁盘红黑树是二叉、面向内存。5.3 工程中还有哪些地方藏着红黑树Linux 内核的 CFS 调度器早年用红黑树管理进程后来改成红黑树队列的组合。Linux 虚拟内存管理中的vm_area_struct查找用红黑树。很多内存分配器会用红黑树管理空闲块。C 的std::map/std::set不必多说。能熟练写出红黑树后再看这些系统源码会顺畅很多因为它们大多是“红黑树 自定义比较规则”的壳。6. 面试与实战中的高频坑6.1 五个让我调试到深夜的 bug插入修复里忘了把根染黑。性质2要求根是黑色但插入后向上变色的过程中可能把根变红循环结束后必须统一处理。左右对称写反。右侧分支的旋转方向完全是左侧的镜像很多人在eraseFixup右侧分支里习惯性复用左旋导致树结构错乱。我的办法是每次对称分支都写完整注释。删除后继时没有正确处理y-parent z的情况。如果 y 就是 z 的直接右孩子不能先做transplant(y, y-right)否则会把 z 和 y 的父子关系弄断。哨兵节点的parent被反复覆盖。单哨兵实现里transplant到 nil 时会把nil-parent指向某个父节点其他位置的 nil 的 parent 可能还是旧的。只要当前访问的 x 的 parent 正确就不会出错但如果你在调试时打印所有节点看到 nil 的 parent 乱跳会非常慌。忘记把新节点的左右孩子指向 nil。插入新节点时Node构造函数已经处理了但如果你自己malloc再赋值很容易让新节点的 left/right 是随机值后续检查n-left-color直接崩。6.2 如何快速验证一棵树的合法性我强烈建议写一个checkValid()在每次插入删除后调用同时打印中序序列确认没有破坏 BST 有序性。验证分三步先遍历中序看是否单调递增再递归检查性质4——红色节点的孩子不能是红最后检查性质5——每个节点的左右子树黑高必须相等。实测下来这个自检函数帮我抓到的 bug 比单元测试还多。写红黑树如果没有这一步调试会非常痛苦因为树一旦歪了你根本不知道是插入问题还是删除问题。6.3 面试这样回答能加分面试官问你红黑树别急着背 case。先讲“为什么要平衡”再讲“为什么红黑树允许一定不平衡”最后说“插入的关键是变色上推删除的关键是兄弟节点分担黑色”。把五条性质和 O(log n) 的证明讲清楚已经超过大多数候选人。如果被追问“会不会手写”我的建议是不要从零默写整个类先写旋转再写插入修复的三个 case删除修复能说出四个 case 的转化关系就够了。工程面试更看重思路不要求你 20 分钟默写 300 行。我在实际写红黑树的过程中最大的体会是它不需要死记每个 case关键是理解“黑色节点数必须相等”这个不变式。只要这个核心守住所有旋转变色都是在朝这个目标调整。最后再分享一个小技巧调红黑树时建议把颜色打印出来用R和B标识再配合中序遍历序列检查定位问题比单看数字快得多。红黑树不是魔法它只是把“黑高相等”这件事执行得足够彻底而已。