红黑树这玩意儿估计是每个C程序员心里的一道坎。平时用 STL 的 map、set 用得飞起底层就是红黑树一到面试或者自己想手写一个才发现从“懂原理”到“能写出来”之间隔着一条鸿沟。我当年第一次完整地把红黑树用 C 撸出来前后花了快一个星期中间不知道删了多少次删除修复的代码。这篇博文就是把那段踩坑经历整理出来从节点设计、旋转、插入、删除到验证给你一份可以直接照着敲的完整实现。适合正在学习数据结构、准备面试、或者想深入理解 STL 源码的人看完之后你能自己手写一棵红黑树并且讲清楚每一步为什么要这么干。1. 红黑树是什么以及为什么值得手写一遍1.1 五大性质先看懂规则红黑树本质上还是一棵二叉搜索树它只是在 BST 的基础上额外维护了“颜色”信息通过红黑两种颜色的约束保证树高接近 O(log n)。它靠的是下面这五条性质每个节点要么是红色要么是黑色。根节点是黑色。每个叶子节点NIL 空节点都是黑色。红色节点的两个孩子必须是黑色也就是不能出现两个连续的红色节点。从任意节点出发到它每个后代叶子节点的所有简单路径上黑色节点的数量相同。这五条性质里第 4 条和第 5 条是核心。第 4 条限制了红色节点不能连成串第 5 条限制了黑色节点的分布必须均匀。两条夹在一起就保证了任何一条路径的长度不会超过最短路径的两倍最短路径全是黑节点最长路径只能黑白交替。这也是红黑树“近似平衡”的含义。很多初学者会把性质 5 记成“黑高相等”但实际写代码的时候最容易漏掉的就是对空节点的处理。性质 3 说空叶子是黑色的这就意味着我们在写isBlack辅助函数时对空指针也要返回 true这一点在后面删除修复的代码里会特别关键。1.2 为什么选红黑树而不是 AVL 树先明确一个事实红黑树和 AVL 树都是自平衡二叉搜索树查找的时间复杂度都是 O(log n)。但红黑树在 C STL 里被 map、set 采用而没有选 AVL这背后是有原因的。AVL 树的平衡条件太严格它要求每个节点的左右子树高度差绝对值不超过 1。这带来的问题是插入或删除一个节点后可能需要沿着路径一路旋转回根节点最坏情况下删除的旋转次数是 O(log n)。红黑树的平衡条件相对宽松它允许左右子树高度差最多到一倍但换来的是插入和删除操作平均只需要常数次旋转。对于 map 这种既要频繁查找、又要频繁插入删除的容器来说红黑树的综合表现更稳。可以这么理解AVL 是“强迫症患者”每次变动都要把高度差压到最小红黑树是“实用主义者”只要保证大差不差、不会退化成链表就行。工程场景下插入删除远比理论分析频繁红黑树的这个取舍很聪明。另外STL 的 map 要求按 key 有序迭代红黑树作为中序遍历天然有序的平衡树正好满足这个需求。用哈希表虽然查找更快但做不到有序遍历。1.3 整体设计模板类加颜色枚举我实现的时候选择了模板类这样这棵树不光能存 int还能像 map 一样存任意可比较的类型。节点结构里除了 key、value还需要三个指针和颜色位。enum Color { RED, BLACK }; template typename Key, typename Value struct RBNode { Key key; Value value; Color color; RBNode* left; RBNode* right; RBNode* parent; RBNode(const Key k, const Value v) : key(k), value(v), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} };这里有两个细节值得说。第一新节点的颜色先默认染成红色原因后面插入部分会细讲。第二left、right、parent 三个指针全都要维护红黑树比普通 BST 麻烦就麻烦在“三指针联动”——子节点变化时必须同步更新父指针任何一个指针没更新都会造成后续操作的崩溃。关于哨兵节点和空指针的取舍STL 的 rb_tree 实现里用了 header 哨兵节点代码写起来更干净因为空指针不需要特判。但教学代码为了让读者好理解一般直接用 nullptr 表示空节点配合辅助函数来处理空节点颜色。我这份实现就是空指针版本代码量多一点但每一步都能和变量对应上。2. 旋转操作一切调整的地基2.1 左旋的图解与代码旋转是红黑树最基础的操作插入和删除的修复全都建立在旋转之上。左旋的意思是把某个节点 x 的右孩子 y 提上来让 x 变成 y 的左孩子原本 y 的左子树变成 x 的右子树。旋转有一个很重要的性质旋转不会破坏二叉搜索树的顺序性。因为这是一次局部调整只牵扯到几个节点中序遍历的结果在旋转前后完全一致。这也是为什么旋转可以安全地用来恢复平衡。先看左旋的代码void leftRotate(RBNodeKey, Value* x) { RBNodeKey, Value* y x-right; x-right y-left; if (y-left ! nullptr) { y-left-parent x; } y-parent x-parent; if (x-parent nullptr) { root y; } else if (x x-parent-left) { x-parent-left y; } else { x-parent-right y; } y-left x; x-parent y; }这段代码的步骤我习惯记成四句话先过继左孩再上挂祖先然后顶替位置最后认祖归宗。第一句“先过继左孩”y 的左孩子要改挂到 x 的右孩子位置因为 y 比 x 大所以 y 的左子树里所有节点都在 x 和 y 之间挂到 x 的右边正好不破坏顺序。第二句“再上挂祖先”y 要取代 x 的位置所以 y 的 parent 要先指向 x 原来的 parent。第三句“顶替位置”让 x 原来的父节点把指针指向 y如果 x 本来是根那 y 直接成为新根。第四句“认祖归宗”最后把 x 挂到 y 的左侧y 成为 x 的父节点。2.2 右旋的镜像实现右旋就是左旋的完全镜像逻辑一模一样只是方向相反。把节点 y 的左孩子 x 提上来y 变成 x 的右孩子原本 x 的右子树变成 y 的左子树。void rightRotate(RBNodeKey, Value* y) { RBNodeKey, Value* x y-left; y-left x-right; if (x-right ! nullptr) { x-right-parent y; } x-parent y-parent; if (y-parent nullptr) { root x; } else if (y y-parent-left) { y-parent-left x; } else { y-parent-right x; } x-right y; y-parent x; }初学者最容易把左旋右旋的指针关系搞混。我的记忆方式是左旋一定是“右孩子上位”右旋一定是“左孩子上位”。代码里旋转的第一步都是先把对侧子树过继给原节点这个对侧子树是唯一的“第三方”处理好它就成功了一半。2.3 每个指针都要维护到位我在调试红黑树时遇到最多的崩溃几乎都出在旋转代码上。总结下来主要是三个坑第一个坑是过继节点的父指针忘记更新。比如左旋时如果 y 的左孩子不为空必须把它 parent 改成 x。漏了这一句后续访问这个节点的 parent 就会得到一个错误的指针轻则验证失败重则死循环。第二个坑是根节点的处理。旋转时如果 x 恰好是根x-parent 是空指针这时候不能访问 x-parent-left必须先特判把 root 指针直接指向新的根。第三个坑是旋转前必须先弄清楚节点关系。左旋要求传入的节点必须有右孩子右旋要求传入的节点必须有左孩子。调用之前一定要保证这一点否则空指针解引用直接崩溃。插入修复里我们会把旋转写在特判过的分支里就是担心这个问题。3. 插入操作新节点先染红再慢慢补课3.1 先做普通 BST 插入新节点必须是红色插入的前半段和普通 BST 完全一样从根节点开始key 比当前节点小就往左走大就往右走直到找到空位置把新节点挂上去。后半段是颜色修复。关键问题新节点到底染红还是染黑结论是染红。我们一条条过如果染黑性质 5 一定被破坏因为这条路径上的黑色节点凭空多了一个而且这个多出来的黑色根本无法通过局部旋转消除修复代价极大如果染红最多破坏性质 4也就是出现连续的红色节点这种情况可以通过旋转加变色来修复。两害相权取其轻所以新节点一定染红。标准库或教科书里还有一种说法如果插入的节点恰好是根节点直接染黑如果父节点是黑色新插入的红色节点不破坏任何性质什么都不用做。这两类情况占了大多数插入操作真正需要修复的只是“父节点也是红色”的情况。3.2 三个 Case叔叔节点决定了怎么修插入修复的循环条件是“当前节点的父节点为红色”也就是出现了两个连续红色节点。修复逻辑根据叔叔节点的状态分三种情况这里假设当前节点 z 的父节点 P 是祖父 G 的左孩子镜像情况对称处理。Case 1叔叔节点 U 是红色。处理方法是把 P 和 U 同时染黑把 G 染红然后把 z 指向 G 继续向上循环。这种做法可以理解为“用祖父的红色去吸收父辈和叔叔的黑色”把矛盾上推两层。Case 2叔叔节点 U 是黑色且 z 是 P 的右孩子。这属于“内部插入”的情况直接对祖父旋转解决不了问题。需要先把 z 指向 P对 z 做一次左旋把结构变成 Case 3 的样子再进入 Case 3。Case 3叔叔节点 U 是黑色且 z 是 P 的左孩子。这是“外部插入”的情况一步到位把 P 染黑G 染红对 G 右旋。旋转之后P 成为子树根黑色节点上移红色节点散到两侧性质恢复。三个 Case 的顺序不能乱很多写法容易漏掉 Case 2 到 Case 3 的转化。实际上 Case 2 的操作本质是“先把问题旋转成最容易处理的形态再一次性解决”。3.3 插入修复完整代码把上面的思路落到代码注意叔叔节点可能为空需要用辅助函数判断void insertFixup(RBNodeKey, Value* z) { while (isRed(z-parent)) { if (z-parent z-parent-parent-left) { RBNodeKey, Value* uncle z-parent-parent-right; if (isRed(uncle)) { z-parent-color BLACK; uncle-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; leftRotate(z); } z-parent-color BLACK; z-parent-parent-color RED; rightRotate(z-parent-parent); } } else { RBNodeKey, Value* uncle z-parent-parent-left; if (isRed(uncle)) { z-parent-color BLACK; uncle-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rightRotate(z); } z-parent-color BLACK; z-parent-parent-color RED; leftRotate(z-parent-parent); } } } root-color BLACK; }辅助函数是这套代码的骨架static bool isRed(RBNodeKey, Value* node) { return node ! nullptr node-color RED; } static bool isBlack(RBNodeKey, Value* node) { return node nullptr || node-color BLACK; }注意我在两个分支里访问z-parent-parent的时候其实有一个潜在假设如果 z-parent 是红色且不是根根永远是黑色那祖父节点一定存在。这个假设成立吗成立。因为性质 4 不允许根是红色的所以红色父节点必有祖父。这也是循环里为什么敢连续解引用两层父指针的原因想明白这一点代码读起来就不虚了。插入修复循环结束后无论中途怎么变色最后一行都会把根节点强制染黑。这是一种兜底可以顺手把 Case 1 里“祖父染红但祖父其实是根”的情况修正掉。4. 删除操作最难啃的硬骨头4.1 删除的三种形态与“后继替换”策略删除是红黑树里最复杂的部分因为它牵扯到的情况矩阵非常大。我的经验是先把“删节点”这件事拆成三类再分别处理如果待删除节点 z 没有左孩子直接用右孩子顶替 z 的位置如果 z 没有右孩子直接用左孩子顶替如果 z 两个孩子都在就找 z 的后继节点右子树里的最小节点用后继节点的 key/value 覆盖 z然后把后继节点从原来的位置删掉。为什么搞这么麻烦因为红黑树作为平衡树删除一个有两个孩子的节点时如果直接把这个节点摘掉会牵扯太多指针关系而且很难保证颜色修复的局部性。用后继替换之后真正从树里摘除的节点“后继”最多有一个右孩子问题就被简化成了“删除只有一个孩子或没有孩子的节点”。这个思想在 BST 删除里就有红黑树只是在这个基础上增加了颜色修复。我说句实话删除部分我又想讲清楚又不希望代码堆积太多。但如果只讲思路不给代码读者自己写的时候依然会被空指针问题折磨。所以下面我尽量把每一行代码为什么这么写解释到位。4.2 删除黑色节点后问题从哪里来删除红色节点很简单因为红色节点不影响黑高删除后所有性质自动保持。删除黑色节点就出事了这条路径上的黑色节点少了一个性质 5 被破坏。假设被摘除的节点是 y替代它位置的节点是 x。如果 y 是黑色那么经过 x 的这条路径就比其他路径少了一个黑色节点。修复的目标就是想办法让 x 这条路径“多出一个黑色”或者让其他路径“少掉一个黑色”重新达成平衡。删除修复的套路是以 x 为抓手反复处理它的兄弟节点。如果 x 的兄弟节点 w 是红色说明 x 的父亲是黑色我们可以通过旋转把 w 变成黑色转化为兄弟是黑色的情况如果 w 是黑色再根据 w 的两个孩子的颜色细分四种情况。这里要注意一个细节x 可以是空指针。当被删节点 y 没有孩子时替代它的就是 nullptr。因为我们约定空节点是黑色的所以修复逻辑依然可以继续只是访问 x-parent 这类代码不能做了需要把 x 的父节点单独用一个变量存下来。这也是我这份代码里 deleteFixup 函数比教科书多了一个 parent 参数的原因。4.3 四个 Case删除修复的完整心法假设 x 是删除后的替代节点初始时它可能是空指针也可能是某个子树的根。下面假设 x 是父节点 parent 的左孩子镜像情况对称。Case 1兄弟节点 w 是红色。处理方法是把 w 染黑、parent 染红然后对 parent 左旋重新更新 w 为 parent 的新右孩子。这样做的目的是把红色的兄弟“降级”成黑色兄弟因为接下来的处理都建立在兄弟是黑色的前提下。Case 2兄弟 w 是黑色且 w 的两个孩子都是黑色。处理方法很简单把 w 染红把 x 提升到 parent继续循环。这一步的本质是让 parent 这棵子树整体少了一个黑色把这个“欠账”上移。Case 3兄弟 w 是黑色w 的左孩子是红色、右孩子是黑色。这一步是为了转化成 Case 4。把 w 染红、w 的左孩子染黑然后右旋 w更新 w 为 parent 的新右孩子。处理后w 的右孩子变成红色正好符合 Case 4 的条件。Case 4兄弟 w 是黑色w 的右孩子是红色。这是最终解决的一步把 w 染成 parent 的颜色parent 染黑w 的右孩子染黑然后左旋 parent把 x 置为根循环结束。这一步的思想是让兄弟子树贡献出一个黑色节点补上 x 路径亏掉的黑高。四个 Case 的触发顺序是固定的而且 Case 2 是唯一可能让循环继续的情况其他 Case 处理后基本都会结束循环。这意味着删除操作最坏情况下需要 O(log n) 次 Case 2但旋转次数在均摊意义下依然是常数。4.4 完整删除代码含空指针处理先看替换操作 transplant它用 v 去替换 u 的位置void transplant(RBNodeKey, Value* u, RBNodeKey, Value* v) { if (u-parent nullptr) { root v; } else if (u u-parent-left) { u-parent-left v; } else { u-parent-right v; } if (v ! nullptr) { v-parent u-parent; } }这里有一个关键u 有父节点时要更新父节点的孩子指针v 不为空时要更新父指针。空指针的父指针不能赋值所以必须用 if 判断。然后是删除主函数。我额外维护了一个xParent变量因为当 x 为空指针时我们无法通过 x-parent 拿到父节点必须在替换之前把父节点保存下来void erase(const Key key) { RBNodeKey, Value* z find(root, key); if (z nullptr) return; RBNodeKey, Value* y z; RBNodeKey, Value* x nullptr; RBNodeKey, Value* xParent nullptr; Color yOriginalColor y-color; if (z-left nullptr) { x z-right; xParent z-parent; transplant(z, z-right); } else if (z-right nullptr) { x z-left; xParent z-parent; transplant(z, z-left); } else { y treeMinimum(z-right); yOriginalColor y-color; x y-right; if (y-parent z) { xParent y; } else { xParent y-parent; 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; } delete z; if (yOriginalColor BLACK) { deleteFixup(x, xParent); } }删除修复函数是全书代码里最长的一块注意我用辅助函数屏蔽了空指针的访问void deleteFixup(RBNodeKey, Value* x, RBNodeKey, Value* parent) { while (x ! root isBlack(x)) { if (x parent-left) { RBNodeKey, Value* w parent-right; if (isRed(w)) { w-color BLACK; parent-color RED; leftRotate(parent); w parent-right; } if (isBlack(w-left) isBlack(w-right)) { w-color RED; x parent; parent x-parent; } else { if (isBlack(w-right)) { if (w-left ! nullptr) w-left-color BLACK; w-color RED; rightRotate(w); w parent-right; } w-color parent-color; parent-color BLACK; if (w-right ! nullptr) w-right-color BLACK; leftRotate(parent); x root; parent nullptr; } } else { RBNodeKey, Value* w parent-left; if (isRed(w)) { w-color BLACK; parent-color RED; rightRotate(parent); w parent-left; } if (isBlack(w-left) isBlack(w-right)) { w-color RED; x parent; parent x-parent; } else { if (isBlack(w-left)) { if (w-right ! nullptr) w-right-color BLACK; w-color RED; leftRotate(w); w parent-left; } w-color parent-color; parent-color BLACK; if (w-left ! nullptr) w-left-color BLACK; rightRotate(parent); x root; parent nullptr; } } } if (x ! nullptr) { x-color BLACK; } root-color BLACK; }删除里的循环条件isBlack(x)对空指针返回 true所以当 x 为空时循环也能进入。这个设计是删除修复能够正确处理“删一个黑色叶子节点”情况的前提。如果把空指针当非黑处理这部分代码立刻就会出问题。5. 如何验证你的红黑树真的写对了5.1 有序性检查中序遍历写完这几个关键函数之后千万不能直接跑一两次就说“OK”。红黑树的隐蔽 bug 太多了很多错误在特定序列下才会触发。我自己的做法是三道验证层层递进。第一步就是验证 BST 的有序性。红黑树首先是二叉搜索树中序遍历结果必须是升序的。如果这一点都不满足后面所有验证都白搭。void inorder(RBNodeKey, Value* node, std::vectorKey out) { if (node nullptr) return; inorder(node-left, out); out.push_back(node-key); inorder(node-right, out); } bool isSorted(const std::vectorKey v) { for (size_t i 1; i v.size(); i) { if (v[i - 1] v[i]) return false; } return true; }5.2 红黑性质自动校验第二步是写一个递归校验函数把五条性质全部自动化。这个函数返回某个节点的黑高同时在递归过程中检查性质 4 和性质 5。int validateNode(RBNodeKey, Value* node) { if (node nullptr) return 1; int leftBlackHeight validateNode(node-left); int rightBlackHeight validateNode(node-right); if (leftBlackHeight ! rightBlackHeight) { valid false; } if (isRed(node) (isRed(node-left) || isRed(node-right))) { valid false; } if (node-left ! nullptr node-left-parent ! node) { valid false; } if (node-right ! nullptr node-right-parent ! node) { valid false; } return leftBlackHeight (node-color BLACK ? 1 : 0); } bool validate() { valid true; if (root ! nullptr root-color ! BLACK) { valid false; } validateNode(root); return valid; }这段代码不仅仅检查了颜色和黑高还额外检查了子节点的 parent 指针是否回指正确。这是个很容易被忽略的检查点旋转代码里只要漏掉一个 parent 赋值红黑性质可能依然是“合法”的但树的结构已经完全错乱了。把 parent 也纳入验证能抓出这一类隐蔽 bug。5.3 随机插入删除压力测试第三步是压力测试。随机生成大量 key先插入再删除每一步都调用 validate() 检查。只有经过几千几万次操作之后依然保持性质成立这棵树才算真正能交付。void stressTest(int times, int range) { std::mt19937 rng(12345); std::setKey checker; for (int i 0; i times; i) { int key rng() % range; if (rng() % 2 0) { insert(key, key); checker.insert(key); } else { erase(key); checker.erase(key); } if (!validate()) { std::cout Validation failed at step i \n; return; } } std::cout Stress test passed. Size checker.size() \n; }我自己的测试经验是规模至少要上万次操作而且要用随机数种子覆盖各种插入删除顺序。只用递增序列测会漏掉大量旋转分支。用 10000 次随机操作反复跑基本能把插入的三个 Case 和删除的四个 Case 都触发一遍。另外我还会把测试 key 的范围缩小一些比如 0 到 20这样会产生大量重复 key 操作和删除不存在的 key 操作能顺便测出 erase 找不到 key 的边界处理。6. 我在手写过程中踩过的坑6.1 空指针当“黑色节点”理解不透红黑树的性质 3 说所有叶子节点都是黑色这里的叶子节点其实是空节点。很多代码崩溃就崩在这一点删除修复里访问w-left-color结果w-left是空指针。我最后的解决方式是统一用isRed和isBlack两个辅助函数它们对空指针有明确处理空指针不是红、是黑。这相当于把性质 3 内置到每一处代码里之后在修改颜色前先判空就不会再出现空指针解引用的问题。6.2 旋转时父指针没更新导致的死循环我第一次写左旋的时候把 x-right 挂到 y-left 之后忘记设置y-left-parent x结果测试时插入 3 个节点就死循环了。因为后续查找或旋转时沿着 parent 链走会回到错误的节点形成一个环。这个教训告诉我旋转代码里四处 parent 赋值一个都不能少。我自己调试时甚至会给每个指针赋值打日志确认所有指针关系都正确后再删掉日志。虽然笨但好用。6.3 删除时 delete 太早指针悬空删除操作里transplant之后还不能立刻 delete 原节点因为如果在两个孩子都在的情况下后继节点的 key/value 已经覆盖了 z但 z 的指针还被 y-left 这些位置引用着。正确的时机是等所有指针调整完毕、修复结束之后再统一 delete z。更隐蔽的问题是如果 z 的一个孩子不存在transplant(z, z-right)之后 z 的 parent 还指向旧父节点但 z 已经没有任何树内指针指向它了这时 delete 安全。但如果 z 有两个孩子z 的左孩子要挂到后继节点 y 的左侧这个操作发生在 transplant 之后所以 z 的左右孩子指针在 delete 前必须还在。这就是为什么代码里delete z要放在所有调整之后。6.4 调试利器把树打印成括号表示法红黑树太抽象光看变量很难定位问题。我写了一个简单的小函数把这棵树输出成类似B(1R(0B(_,_) , 2R(_,_) ) )这样的文本每个节点用颜色字母标记空节点用下划线。这样出问题时直接打印能用肉眼看出旋转之后树的结构长什么样。void dump(RBNodeKey, Value* node) { if (node nullptr) { std::cout _; return; } std::cout node-key (node-color RED ? R : B) (; dump(node-left); std::cout ,; dump(node-right); std::cout ); }这个函数我强烈建议每一个写树结构的人都要有一个。遇到 bug 先打印再和中序序列对照几十秒钟就能定位是旋转问题还是颜色问题。我后来重新看 CLRS 源码时也总是习惯性加上这种打印比纯靠脑子推演高效得多。7. 常见问题速查表问题现象排查思路插入后连续红节点未修复validate 报错出现连续红检查 Case 2 是否把 z 指向了父节点是否漏掉左旋/右旋旋转后 parent 指针错乱删插入随机序列时死循环在 validate 里检查 parent 回指单独测试旋转操作删除黑节点后黑高不等validate 报黑高不一致检查 deleteFixup 的 x 是否为空以及 Case 2 是否正确上移erase 找不到 key删除操作无效果检查 find 函数注意空树时 root 为空的情况删除的节点是根节点root 变为空或错误节点检查 transplant 里对根节点的特判空指针解引用崩溃运行到 deleteFixup 时崩溃检查 isBlack/isRed 是否对空指针正确处理重复插入不处理插入相同 key 时未更新 value在 insert 末尾判断是否已存在相同 key这份速查表是我自己调试时常用的路径。说句实话红黑树这种东西看十遍原理不如亲手写一遍、错一遍、再改一遍。只要你能把上述问题都经历一遍红黑树的每个角落基本都打通了。最后再分享一个小技巧如果你在实现中实在卡住可以拿 C STL 的std::map当参照物插入删除相同的 key 序列再用我的 dump 函数对比输出虽然 STL 用了哨兵节点结构细节不同但红黑树整体形态应该是一致的。这比盯着代码干瞪眼有效得多。