最近在准备给一个学弟讲STL源码翻到std::map底层那段_Rb_tree的时候他问我“这红黑树到底难在哪为什么网上教程全是‘看图理解’一到自己写就废” 我回想了一下自己两年前从C开始写红黑树的过程确实有点话想说。红黑树这个东西理论上有五大性质插入有四种情况删除有八种情况听起来像劝退现场。但如果你从“它到底想解决什么问题”出发先把动机想透再把每一种情况为什么那样处理想透红黑树其实是三大平衡树AVL、红黑树、B树里最适合手写一遍、也最能让你理解“自平衡到底在平衡什么”的结构。这篇是“从C开始的编程生活”系列的第22篇我会用C把红黑树从节点定义、旋转、插入修复到删除修复完整写一遍每一段代码都讲清楚背后的判断依据。文章不追求那种“半小时学会红黑树”的压缩饼干式教学而是尽量还原我踩坑、试错、最后跑通的全过程。适合已经掌握二叉树和C类封装想真正把红黑树啃下来的朋友如果你是要应付GESP三级或面试算法基础这篇的插入删除流程也能让你从“背结论”升级为“推结论”。1. 为什么非要是红黑树从二叉树到自平衡的演进1.1 二叉搜索树的天生缺陷先回到最基础的问题我们为什么要一棵“平衡”的搜索树普通二叉搜索树BST插入、查找、删除的平均时间复杂度是O(log n)但那个“平均”有个前提——树得接近满二叉树。一旦你按有序序列插入节点比如依次插入1、2、3、4、5……这棵树会退化成一个只有右孩子链高度直接变成n查找一个节点要遍历整条链时间复杂度退化到O(n)。你写一个数据量为百万级的数据库索引插入一组有序ID整棵树直接变成链表那还玩什么。所以问题的核心是在BST的基础上通过某种规则在插入/删除后对树进行局部调整让树的高度始终保持在O(log n)级别。这个调整就是“自平衡”。1.2 AVL树为什么“太严了”先看一眼AVL树它的平衡条件是任意节点的左右子树高度差绝对值不超过1。这个条件非常强几乎让树永远保持严格的全满形态。好处是查找性能在最坏情况下都极其稳定坏处是——为了维持这个严格的平衡插入和删除时往往需要大量旋转操作。我当年用AVL做实验连续插入有序数据时几乎每插入两三个节点就要旋转一次。旋转本身是O(1)不改变复杂度级别但实际工程里旋转次数多了加上树的形态变化剧烈性能开销和缓存局部性损失是实打实的。红黑树换了一种思路不要求高度严格相等而是用颜色约束“树的左右子树高度差在一个可控范围内”。代价是查找时最坏高度比AVL略高最高约为2log₂(n1)但换来的是更少的旋转次数和更稳定的插入删除性能。STL和Linux内核不约而同都选择了红黑树不是没道理的。1.3 红黑树到底“平衡”了什么红黑树不需要左右子树高度严格一致而是要保证任何一条从根到叶子NIL的路径上黑色节点的数量相同且红色节点的连续出现受到限制。这两条约束合在一起就形成了一个非常实用的平衡效果最长路径不会超过最短路径的2倍。怎么理解这个“2倍”因为最短路径全是黑色节点最长路径是在黑节点之间插入红节点串起来的但红节点不能连续所以任意路径上红节点数量至多等于黑节点数量。黑高一样的前提下最长路径最多是2倍最短路径。这个平衡程度虽然不如AVL的“高度差不超过1”但已经足够保证任何搜索、插入操作都走了O(log n)路径——因为高度被限定在2log₂(n1)以内证明用到了黑高的性质后面我会展开算。红黑树的另一个工程优势是旋转局部性强。插入修复时最多做2次旋转删除修复时最多做3次旋转其余变化都是变色。这比AVL那种“调整后可能一路传递到根”的场景更可控。STL的std::map为什么选红黑树而不选AVL正是因为它在“查询性能略损一点点”和“插入删除性能显著提升”之间找到了最佳的工程折中。你去看 libstdc 的源码_Rb_tree那一整套实现就是红黑树的第一手工程样本。2. 五个性质读一遍不如亲手画一张图2.1 五条性质的逐条拆解红黑树的五条性质教科书上写得很简洁但初学的时候完全不知道每条性质在干什么。我用我自己的理解方式重新说一遍每个节点要么是红色要么是黑色。根节点是黑色。叶子节点NIL是黑色。注意这个“叶子”不是我们平时说的左右孩子为空的节点而是所有空指针统一视作一个黑色NIL节点。在C实现里你用nullptr表示NIL所有人都会自觉认为nullptr是黑的。如果一个节点是红色那么它的两个孩子都是黑色。换句话说红色节点的父节点不能是红色红节点不能连续出现。从任意节点到其每个后代叶子NIL的路径上经过的黑色节点数量相同。这个相同数量就叫黑高。这几个性质为什么要这样设计性质4保证了不会出现“红色长链”性质5保证了每条路径的黑色“骨架”是均衡的。两个合在一起最长路径不超过最短路径2倍的结论就出来了。2.2 黑高与树高的数学关系把NIL当成黑叶子之后黑高记作 bh(T)。假设一棵红黑树的高度是h我们要证明 h ≤ 2log₂(n1)。第一步先证明“以x为根的子树至少包含 2^bh(x) - 1 个内部节点”。用数学归纳法高度为0时节点数0 2^0 - 1对任意节点x两个孩子如果有的黑高要么是bh(x)要么是bh(x)-1当x是红节点时但绝不会小于bh(x)-1。于是整棵子树节点数 ≥ (2^(bh(x)-1) - 1) (2^(bh(x)-1) - 1) 1 2^bh(x) - 1。第二步因为根的黑高至少是 h/2红节点至多占一半且不能连续所以 n ≥ 2^(h/2) - 1解得 h ≤ 2log₂(n1)。这个证明不用背关键是理解黑高是红黑树保持平衡的“骨架”而红色节点只是骨架上的“装饰”装饰再密也不能超过骨架的一半长度。我当年把这些性质手抄在纸上每个性质画一棵小树验证很快就从“背性质”变成“理解性质”了。2.3 一个手画示例将 10、20、30、40、50、60 依次插入为了直观我举个具体例子。依次插入 10、20、30、40、50、60 这些值如果用普通BST这棵树会歪成一条只有右孩子的链高6层。红黑树插入时会怎么处理插入10根节点染黑。插入20比10大成为右孩子。新节点默认红色父节点10是黑色无需调整。插入30成为20的右孩子。20是红色违反性质4。此时叔叔10的另一个孩子NIL是黑色进入“叔叔为黑LR/LL”分支对10左旋再把10染红、20染黑。树变成20为根左右孩子各10和30。插入40父30是红色叔叔10是红色直接变色20变红10和30变黑。检查根20的父是NIL且为黑但根不能是红把20再染黑。此时10、20、30、40四个节点的树黑高一致。插入50父40红叔叔NIL黑对30左旋再变色。树形态逐步向平衡靠拢。插入60情况类似需要变色旋转。这个过程你手动画一遍会非常清晰地看到变色是最先尝试的手段只有在变色解决不了结构问题时才动用旋转。这和我们人脑想问题的思路完全一致——能局部调整解决的不要大动干戈。3. 插入变色、旋转与四种情况的完整推导3.1 节点结构与基础操作在写插入修复之前先把C节点结构和旋转写好。为了方便调试和后续删除操作我选择带父指针的节点并用一个成员nil作为统一的空叶子表示。这样写代码清晰但代价是修改时得格外小心所有nullptr都要替换成this-nil。#include iostream enum Color { RED, BLACK }; template typename T struct Node { T data; Color color; Node* parent; Node* left; Node* right; Node(const T val, Color c, Node* p, Node* l, Node* r) : data(val), color(c), parent(p), left(l), right(r) {} }; template typename T class RedBlackTree { public: RedBlackTree() { nil new NodeT(T(), BLACK, nullptr, nullptr, nullptr); root nil; } void insert(const T val) { NodeT* y nil; NodeT* x root; while (x ! nil) { y x; if (val x-data) x x-left; else x x-right; } NodeT* z new NodeT(val, RED, y, nil, nil); if (y nil) root z; else if (z-data y-data) y-left z; else y-right z; z-parent y; insertFixup(z); } // 中序遍历验证结构 void inorder() { inorder(root); } private: NodeT* root; NodeT* nil; void inorder(NodeT* x) { if (x ! nil) { inorder(x-left); std::cout x-data ( (x-color RED ? R : B) ) ; inorder(x-right); } } void rotateLeft(NodeT* x) { NodeT* y x-right; x-right y-left; if (y-left ! nil) 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 rotateRight(NodeT* x) { NodeT* y x-left; x-left y-right; if (y-right ! nil) 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; } void insertFixup(NodeT* z) { while (z-parent-color RED) { if (z-parent z-parent-parent-left) { NodeT* y z-parent-parent-right; // 叔叔 if (y-color RED) { z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; rotateLeft(z); } z-parent-color BLACK; z-parent-parent-color RED; rotateRight(z-parent-parent); } } else { NodeT* y z-parent-parent-left; // 叔叔 if (y-color RED) { z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rotateRight(z); } z-parent-color BLACK; z-parent-parent-color RED; rotateLeft(z-parent-parent); } } } root-color BLACK; } };3.2 为什么新节点默认是红色插入新节点时我把节点颜色设为红色而不是黑色。这个选择直接影响性质5黑高相等。如果新节点是黑色那么它所在的这条路径凭空多出一个黑节点整条路径的黑高都变了需要修复的范围会扩散到树的其他分支。但如果新节点是红色性质5不会被破坏唯一可能违反的是性质4红节点不能连续出现。而性质4一旦被违反只需要沿着“父节点是红色”的路径向上回溯修复修复范围被牢牢控制在从新节点到根的局部区域。一句话红色节点把破坏面最小化让修复问题局部化。这是红黑树设计的智慧所在。3.3 四种情况分类的底层逻辑插入修复的循环条件是while (z-parent-color RED)。既然父节点是红色祖父节点一定是黑色红不连红真正导致性质4被破坏的根源就是“父红叔红”或“父红叔黑”两种大分支。每种大分支内部再根据“z是父亲的左孩子还是右孩子”进一步分子情况。所以网上常说的“插入四种情况”本质上是这个分类逻辑的自然展开情况编号父节点叔叔节点z的位置处理方式1红红任意父、叔变黑祖父变红z上移两级2红黑右内侄对父节点旋转转化为情况33红黑左外侄祖父变红父变黑祖父旋转情况1是“局部变色”把红节点往上传直到不再违反性质4。情况2和3是“旋转变色”本质上是把“连续红节点”的结构重新分布让红节点从属于不同路径从而把黑色骨架拉直。3.4 为什么叔叔是红色时用变色是黑色时用旋转这个区别要理解透。叔叔红色意味着“当前局部区域的黑节点数足够多可以容纳更多红节点”——祖父本来是黑的把祖父染红父和叔染黑黑高不变性质4在局部恢复。叔叔黑色则意味着一侧的黑高比另一侧多光靠变色解决不了“祖父一侧路径黑多、另一侧黑少”的不平衡必须通过旋转把多出来的黑色节点挪到对侧去。每次旋转前先做一次小旋转情况2把“弯曲的红链”拉直成“直线红链”情况3再对祖父旋转这样一次大旋转就能把两个红孩子分配到两边同时恢复黑高。我调试红黑树最深的感受是变色是在“同层”交换颜色旋转是在“跨层”改变结构。当局部结构无法用变色平衡时就要靠旋转重新分配黑高。能变色的先变色变不了色再旋转这个优先级顺序贯穿了所有修复逻辑。4. 删除比插入绕十倍但掌握套路就没那么难删除之所以比插入复杂是因为删除一个节点会直接破坏性质5黑高相等。插入时新节点是红色黑高天然不受影响删除时你删掉的节点可能是黑色这等于在一条路径上永久砍掉了一个黑节点靠变色已经无法恢复。4.1 删除分两个阶段BST删除 红黑修复第一阶段和普通BST删除完全一致找后继节点然后把后继的值拷贝到删除位置或者直接移动节点指针本质上是把“删除目标”转化为“删除一个最多只有一个孩子的节点”。第二阶段才进入红黑修复修复的目标就是处理“被删节点是黑色”造成的黑高缺失。我把“被删节点是黑色”导致的缺失继续往下推删除后占据删除位置的节点可以是后继节点或者原位置的孩子被看作“携带双重黑色”double black。这个概念初看很抽象我就是为了理解它专门把删除代码跑了几十遍双重黑不是真正的颜色而是一种标记表示这个节点沿路径的黑高比其他位置多承担了一个“债务”。修复的过程就是不断向父节点、兄弟节点“转移债务”直到遇到一个能一次性平账的节点。4.2 删除修复的四种情况先看关键代码这是删除的核心部分void deleteFixup(NodeT* x) { while (x ! root x-color BLACK) { if (x x-parent-left) { NodeT* w x-parent-right; // 兄弟 if (w-color RED) { // 情况1兄弟是红色把兄弟变黑父变红左旋父 w-color BLACK; x-parent-color RED; rotateLeft(x-parent); w x-parent-right; } if (w-left-color BLACK w-right-color BLACK) { // 情况2兄弟是黑色且孩子全黑兄弟变红债务上移 w-color RED; x x-parent; } else { if (w-right-color BLACK) { // 情况3兄弟是黑右侄黑左侄红先转成情况4 w-left-color BLACK; w-color RED; rotateRight(w); w x-parent-right; } // 情况4兄弟是黑右侄是红一次旋转变色解决 w-color x-parent-color; x-parent-color BLACK; w-right-color BLACK; rotateLeft(x-parent); x root; } } else { // 对称逻辑 NodeT* w x-parent-left; if (w-color RED) { w-color BLACK; x-parent-color RED; rotateRight(x-parent); w x-parent-left; } if (w-right-color BLACK w-left-color BLACK) { w-color RED; x x-parent; } else { if (w-left-color BLACK) { w-right-color BLACK; w-color RED; rotateLeft(w); w x-parent-left; } w-color x-parent-color; x-parent-color BLACK; w-left-color BLACK; rotateRight(x-parent); x root; } } } x-color BLACK; } void remove(const T val) { NodeT* z root; while (z ! nil) { if (val z-data) z z-left; else if (val z-data) z z-right; else break; } if (z nil) return; NodeT* y z; NodeT* x nullptr; Color y_origin_color 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); y_origin_color 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; } delete z; if (y_origin_color BLACK) deleteFixup(x); }4.3 四种情况的逻辑推导与记忆方法先理解分类依据修复时x是那个“带债务”的节点核心判断对象是它的兄弟节点w。情况1兄弟是红色。红色兄弟说明两边黑高悬殊明显没法直接局部修。我们把兄弟染黑、父染红、然后旋转父——这一步不直接解决问题但把兄弟变成了黑色并让新的兄弟变成原来兄弟的儿子从而把问题收敛到“兄弟是黑色”的情况。我把这步叫作“换一个兄弟再来谈”。情况2兄弟是黑色且兄弟两个儿子都是黑色。这种情况说明兄弟这侧“没有多余的黑节点可以借出来”那就把兄弟染红相当于兄弟这侧黑高减1让债务上升到父节点然后把父节点当作新的x继续向上处理。情况3兄弟是黑色兄弟的近侄是红色远侄是黑色。这个形态没法直接旋转先把近侄通过旋转变成远侄红的情况从而转到情况4。这步是纯粹的“姿态转换”。情况4兄弟是黑色兄弟的远侄是红色。这是唯一能真正“平账”的情况把父节点颜色赋给兄弟父染黑、远侄染黑、再旋转父。旋转后佩戴债务的节点获得一个额外的黑节点债主债务清零整个循环结束x root。记忆口诀可以这样总结“红兄换人黑兄子全黑则上移近侄红先旋转远侄红则平账。” 这四个情况对应着思考问题的顺序先排除红兄弟再排除全黑侄再调整内侄最后靠外侄收尾。4.4 一个删除案例的完整验证假设树里有节点序列 {10, 20, 30, 40, 50, 60}红黑树形态是20为根黑10和30是它的两个孩子红、黑不定细节其他节点按层分布。删除40而40是某个红色节点那么黑高不变不需要修复。测试时要专门挑“黑节点删除”来触发修复路径比如先构造一棵全是黑节点的树插入1、2、3、4、5后连续变色然后删除根节点你会发现这几乎是删除修复最复杂的路径——兄弟节点为黑、侄子全黑、父节点需要递归向上修正的多层链条全都会走一遍。调试实践我每次删除一个节点都写一个验证函数遍历树检查五条性质是否全部满足如果违反正则打印节点路径。这个函数虽然跑起来慢但比人眼盯着几十个节点的颜色靠谱得多。后面第6节我会给出验证思路。5. 从课堂到战场红黑树在STL与真实项目中的样子5.1 std::map与std::set其实就长这样你每天用的std::map、std::set在 libstdc 里就是_Rb_tree的一层包装。std::map的元素是pairconst Key, Tstd::set的元素是Key底层同一套红黑树。用红黑树而不是哈希表核心原因是有序性。哈希表的查找是O(1)但你要做范围查询lower_bound、upper_bound、找最小最大值、顺序遍历哈希表就麻烦了。红黑树天然支持有序遍历begin()是树的最左节点迭代器走中序后继。这就是为什么数据库索引和关联容器更多选择树结构而不是哈希结构。STL源码里有一个细节值得注意STL红黑树并不是用nullptr表示NIL叶子而是用一个指向header哨兵节点的指针。header的父指针指向根节点左指针指向树的最小节点右指针指向最大节点。这样做的好处是begin()和rbegin()直接通过header-left和header-right拿节点无需从根开始查找。这个设计是工程上对教科书红黑树的一个经典优化面试提到STL红黑树时能说出这一点会让人觉得你真的去看过源码而不是只背过性质。5.2 封装一个最小可用的红黑树容器学完红黑树最大的成就感来自把它封装成一个可以替代std::set的最小容器。我当时折腾了一个周末写了insert、remove、find、中序遍历、以及一个简易的迭代器。关键点在于迭代器的operator要用“右孩子非空则找右子树最左节点否则向上找到第一个不是右孩子的祖先”这套逻辑和STL的实现思路一致。class iterator { public: NodeT* node; NodeT* nil_; iterator(NodeT* n, NodeT* nil) : node(n), nil_(nil) {} const T operator*() const { return node-data; } iterator operator() { if (node-right ! nil_) { node node-right; while (node-left ! nil_) node node-left; } else { NodeT* p node-parent; while (p ! nil_ node p-right) { node p; p p-parent; } node p; } return *this; } bool operator(const iterator other) const { return node other.node; } bool operator!(const iterator other) const { return node ! other.node; } };封装完成后我写了一个随机测试程序随机生成10万个整数插入我的红黑树容器再逐个查找、删除过程中每个操作后都调用性质验证函数。最终跑过一个晚上无崩溃那种成就感比看任何教程都强。5.3 红黑树、AVL树与跳表的选型对比如果你在真实项目里需要一棵自平衡搜索树怎么选我自己的经验是需求场景推荐选择理由需要严格的最坏时间保证主要用于查询AVL树高度更矮查询最坏情况更优大量插入删除且插入删除性能更重要红黑树旋转次数少重平衡成本低需要有序遍历范围查询红黑树STL容器已实现无需自己造轮子并发读写且写操作频繁跳表无旋转无锁定路径分段锁更容易磁盘存储、数据库索引B树 / B树节点按页大小组织减少IO次数有一说一如果你不是在学习、面试、或者维护一个已有的红黑树库生产环境直接用std::map就行。自己造红黑树的轮子价值在于彻底理解自平衡机制而不在于替代STL。写一遍之后再看STL源码你会发现很多设计都是顺着同一个思路展开的比如迭代器哨兵、节点分配器、异常安全处理。6. 我的调试经验与几个必须避开的坑6.1 验证函数红黑树调试的“安全网”手写红黑树最大的痛就是“代码看着对跑起来错”而且错误往往是几万次插入后才出现的悬垂指针问题。我在写的第二天就写了一个验证函数每一步插入删除之后都调用它能自动遍历整棵树检查五条性质int validate(NodeT* x) { if (x nil) return 1; // NIL叶子视为黑色 if (x-color RED (x-left-color ! BLACK || x-right-color ! BLACK)) { std::cerr 违反性质4红节点孩子必须为黑 std::endl; exit(1); } int lh validate(x-left); int rh validate(x-right); if (lh ! rh) { std::cerr 违反性质5黑高不一致 std::endl; exit(1); } return lh (x-color BLACK ? 1 : 0); }有了这个函数之后我每次吞掉一个bug就把对应的输入序列固定下来构造一个最小复现用例再人肉推演一遍这棵树应该变成什么样。这个习惯特别重要它让我不再依赖“蒙对了就好”而是真正把树的每一步变化刻进脑子里。6.2 我踩过的四个经典坑第一个坑是NIL节点不统一。刚开始我用nullptr表示叶子旋转代码里到处判断if (x ! nullptr)结果漏了某条分支导致在某次旋转中把nullptr挂上了父指针最后崩溃在迭代器遍历。后来我统一改成成员nil所有指针操作都假设nil是一个真实存在的节点判断逻辑简化为x ! nil代码反而清晰多了。第二个坑是旋转后父指针更新遗漏。左旋右旋不是简单的指针交换还要维护三代关系——旋转节点的父节点、子节点、以及祖父节点的指向。我漏过一次“祖父指向新根”的更新导致根节点在旋转后失去父指针后续插入时整棵树断链。排查方法很简单每次旋转后打印根节点和几个关键子孙的父指针和手推的结果对比。第三个坑是删除修复忘了处理x root的情况。删除循环的终止条件是x root但如果你删除的就是根节点且删除后根是红色的必须在循环外把root-color BLACK执行一遍否则根可能变红性质2被破坏。这个坑尤其隐蔽因为它只在频繁删除根节点的测试序列里才出现。第四个坑是递归删除导致栈溢出。有些教程用递归方式删除但红黑树高度在最坏情况下是2log₂n对于百万级数据量递归深度已经不小如果树因为bug退化成链递归深度直接拉满栈就爆了。我的实现里所有删除都改成迭代写法这是我在处理大数据量测试时强制自己做的优化。6.3 我建议的学习路线如果你现在刚开始接触红黑树我建议按这个顺序推进能少走很多弯路先手工模拟插入过程拿一组数字比如8、3、11、1、5、9、14在纸上画出每一步插入后的树标上颜色跑通所有插入情况。再手工模拟删除过程从这棵树里按顺序删黑色节点体会“双重黑”的传递。写最小实现只写节点、左旋右旋、插入、查找不写删除先把插入跑通。加删除使用验证函数反复测试构造专门触发各种情况的用例。对照STL源码读bits/stl_tree.h看_Rb_tree如何用哨兵节点优化迭代器看_Rb_tree_insert_and_rebalance和_Rb_tree_erase_and_rebalance的实现。扩展成容器加迭代器、find、clear封装成你自己的set。走完这六步红黑树对你来说就不再是“背下来又忘掉”的章节了而是“亲手重建过”的结构。以后面试聊到红黑树你可以直接说出旋转的细节、为什么用变色不用全重平衡、STL为什么选红黑树而不是AVL——这些都不是背的而是真的从代码里长出来的。我个人在这条路上最大的感受是红黑树的代码一行一行写下来比看十遍教科书更折磨人但也更刻骨铭心。每当你深夜debug到怀疑人生然后第二天醒来发现自己昨天漏的那条父指针赋值时你对这个树的敬畏和理解就又深了一层。希望这篇系列第22篇能让你的C编程生活里多一棵能亲手造出来的既红又黑的大树。 C++手写红黑树：从旋转变色到STL源码的完整实现
最近在准备给一个学弟讲STL源码翻到std::map底层那段_Rb_tree的时候他问我“这红黑树到底难在哪为什么网上教程全是‘看图理解’一到自己写就废” 我回想了一下自己两年前从C开始写红黑树的过程确实有点话想说。红黑树这个东西理论上有五大性质插入有四种情况删除有八种情况听起来像劝退现场。但如果你从“它到底想解决什么问题”出发先把动机想透再把每一种情况为什么那样处理想透红黑树其实是三大平衡树AVL、红黑树、B树里最适合手写一遍、也最能让你理解“自平衡到底在平衡什么”的结构。这篇是“从C开始的编程生活”系列的第22篇我会用C把红黑树从节点定义、旋转、插入修复到删除修复完整写一遍每一段代码都讲清楚背后的判断依据。文章不追求那种“半小时学会红黑树”的压缩饼干式教学而是尽量还原我踩坑、试错、最后跑通的全过程。适合已经掌握二叉树和C类封装想真正把红黑树啃下来的朋友如果你是要应付GESP三级或面试算法基础这篇的插入删除流程也能让你从“背结论”升级为“推结论”。1. 为什么非要是红黑树从二叉树到自平衡的演进1.1 二叉搜索树的天生缺陷先回到最基础的问题我们为什么要一棵“平衡”的搜索树普通二叉搜索树BST插入、查找、删除的平均时间复杂度是O(log n)但那个“平均”有个前提——树得接近满二叉树。一旦你按有序序列插入节点比如依次插入1、2、3、4、5……这棵树会退化成一个只有右孩子链高度直接变成n查找一个节点要遍历整条链时间复杂度退化到O(n)。你写一个数据量为百万级的数据库索引插入一组有序ID整棵树直接变成链表那还玩什么。所以问题的核心是在BST的基础上通过某种规则在插入/删除后对树进行局部调整让树的高度始终保持在O(log n)级别。这个调整就是“自平衡”。1.2 AVL树为什么“太严了”先看一眼AVL树它的平衡条件是任意节点的左右子树高度差绝对值不超过1。这个条件非常强几乎让树永远保持严格的全满形态。好处是查找性能在最坏情况下都极其稳定坏处是——为了维持这个严格的平衡插入和删除时往往需要大量旋转操作。我当年用AVL做实验连续插入有序数据时几乎每插入两三个节点就要旋转一次。旋转本身是O(1)不改变复杂度级别但实际工程里旋转次数多了加上树的形态变化剧烈性能开销和缓存局部性损失是实打实的。红黑树换了一种思路不要求高度严格相等而是用颜色约束“树的左右子树高度差在一个可控范围内”。代价是查找时最坏高度比AVL略高最高约为2log₂(n1)但换来的是更少的旋转次数和更稳定的插入删除性能。STL和Linux内核不约而同都选择了红黑树不是没道理的。1.3 红黑树到底“平衡”了什么红黑树不需要左右子树高度严格一致而是要保证任何一条从根到叶子NIL的路径上黑色节点的数量相同且红色节点的连续出现受到限制。这两条约束合在一起就形成了一个非常实用的平衡效果最长路径不会超过最短路径的2倍。怎么理解这个“2倍”因为最短路径全是黑色节点最长路径是在黑节点之间插入红节点串起来的但红节点不能连续所以任意路径上红节点数量至多等于黑节点数量。黑高一样的前提下最长路径最多是2倍最短路径。这个平衡程度虽然不如AVL的“高度差不超过1”但已经足够保证任何搜索、插入操作都走了O(log n)路径——因为高度被限定在2log₂(n1)以内证明用到了黑高的性质后面我会展开算。红黑树的另一个工程优势是旋转局部性强。插入修复时最多做2次旋转删除修复时最多做3次旋转其余变化都是变色。这比AVL那种“调整后可能一路传递到根”的场景更可控。STL的std::map为什么选红黑树而不选AVL正是因为它在“查询性能略损一点点”和“插入删除性能显著提升”之间找到了最佳的工程折中。你去看 libstdc 的源码_Rb_tree那一整套实现就是红黑树的第一手工程样本。2. 五个性质读一遍不如亲手画一张图2.1 五条性质的逐条拆解红黑树的五条性质教科书上写得很简洁但初学的时候完全不知道每条性质在干什么。我用我自己的理解方式重新说一遍每个节点要么是红色要么是黑色。根节点是黑色。叶子节点NIL是黑色。注意这个“叶子”不是我们平时说的左右孩子为空的节点而是所有空指针统一视作一个黑色NIL节点。在C实现里你用nullptr表示NIL所有人都会自觉认为nullptr是黑的。如果一个节点是红色那么它的两个孩子都是黑色。换句话说红色节点的父节点不能是红色红节点不能连续出现。从任意节点到其每个后代叶子NIL的路径上经过的黑色节点数量相同。这个相同数量就叫黑高。这几个性质为什么要这样设计性质4保证了不会出现“红色长链”性质5保证了每条路径的黑色“骨架”是均衡的。两个合在一起最长路径不超过最短路径2倍的结论就出来了。2.2 黑高与树高的数学关系把NIL当成黑叶子之后黑高记作 bh(T)。假设一棵红黑树的高度是h我们要证明 h ≤ 2log₂(n1)。第一步先证明“以x为根的子树至少包含 2^bh(x) - 1 个内部节点”。用数学归纳法高度为0时节点数0 2^0 - 1对任意节点x两个孩子如果有的黑高要么是bh(x)要么是bh(x)-1当x是红节点时但绝不会小于bh(x)-1。于是整棵子树节点数 ≥ (2^(bh(x)-1) - 1) (2^(bh(x)-1) - 1) 1 2^bh(x) - 1。第二步因为根的黑高至少是 h/2红节点至多占一半且不能连续所以 n ≥ 2^(h/2) - 1解得 h ≤ 2log₂(n1)。这个证明不用背关键是理解黑高是红黑树保持平衡的“骨架”而红色节点只是骨架上的“装饰”装饰再密也不能超过骨架的一半长度。我当年把这些性质手抄在纸上每个性质画一棵小树验证很快就从“背性质”变成“理解性质”了。2.3 一个手画示例将 10、20、30、40、50、60 依次插入为了直观我举个具体例子。依次插入 10、20、30、40、50、60 这些值如果用普通BST这棵树会歪成一条只有右孩子的链高6层。红黑树插入时会怎么处理插入10根节点染黑。插入20比10大成为右孩子。新节点默认红色父节点10是黑色无需调整。插入30成为20的右孩子。20是红色违反性质4。此时叔叔10的另一个孩子NIL是黑色进入“叔叔为黑LR/LL”分支对10左旋再把10染红、20染黑。树变成20为根左右孩子各10和30。插入40父30是红色叔叔10是红色直接变色20变红10和30变黑。检查根20的父是NIL且为黑但根不能是红把20再染黑。此时10、20、30、40四个节点的树黑高一致。插入50父40红叔叔NIL黑对30左旋再变色。树形态逐步向平衡靠拢。插入60情况类似需要变色旋转。这个过程你手动画一遍会非常清晰地看到变色是最先尝试的手段只有在变色解决不了结构问题时才动用旋转。这和我们人脑想问题的思路完全一致——能局部调整解决的不要大动干戈。3. 插入变色、旋转与四种情况的完整推导3.1 节点结构与基础操作在写插入修复之前先把C节点结构和旋转写好。为了方便调试和后续删除操作我选择带父指针的节点并用一个成员nil作为统一的空叶子表示。这样写代码清晰但代价是修改时得格外小心所有nullptr都要替换成this-nil。#include iostream enum Color { RED, BLACK }; template typename T struct Node { T data; Color color; Node* parent; Node* left; Node* right; Node(const T val, Color c, Node* p, Node* l, Node* r) : data(val), color(c), parent(p), left(l), right(r) {} }; template typename T class RedBlackTree { public: RedBlackTree() { nil new NodeT(T(), BLACK, nullptr, nullptr, nullptr); root nil; } void insert(const T val) { NodeT* y nil; NodeT* x root; while (x ! nil) { y x; if (val x-data) x x-left; else x x-right; } NodeT* z new NodeT(val, RED, y, nil, nil); if (y nil) root z; else if (z-data y-data) y-left z; else y-right z; z-parent y; insertFixup(z); } // 中序遍历验证结构 void inorder() { inorder(root); } private: NodeT* root; NodeT* nil; void inorder(NodeT* x) { if (x ! nil) { inorder(x-left); std::cout x-data ( (x-color RED ? R : B) ) ; inorder(x-right); } } void rotateLeft(NodeT* x) { NodeT* y x-right; x-right y-left; if (y-left ! nil) 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 rotateRight(NodeT* x) { NodeT* y x-left; x-left y-right; if (y-right ! nil) 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; } void insertFixup(NodeT* z) { while (z-parent-color RED) { if (z-parent z-parent-parent-left) { NodeT* y z-parent-parent-right; // 叔叔 if (y-color RED) { z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; rotateLeft(z); } z-parent-color BLACK; z-parent-parent-color RED; rotateRight(z-parent-parent); } } else { NodeT* y z-parent-parent-left; // 叔叔 if (y-color RED) { z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rotateRight(z); } z-parent-color BLACK; z-parent-parent-color RED; rotateLeft(z-parent-parent); } } } root-color BLACK; } };3.2 为什么新节点默认是红色插入新节点时我把节点颜色设为红色而不是黑色。这个选择直接影响性质5黑高相等。如果新节点是黑色那么它所在的这条路径凭空多出一个黑节点整条路径的黑高都变了需要修复的范围会扩散到树的其他分支。但如果新节点是红色性质5不会被破坏唯一可能违反的是性质4红节点不能连续出现。而性质4一旦被违反只需要沿着“父节点是红色”的路径向上回溯修复修复范围被牢牢控制在从新节点到根的局部区域。一句话红色节点把破坏面最小化让修复问题局部化。这是红黑树设计的智慧所在。3.3 四种情况分类的底层逻辑插入修复的循环条件是while (z-parent-color RED)。既然父节点是红色祖父节点一定是黑色红不连红真正导致性质4被破坏的根源就是“父红叔红”或“父红叔黑”两种大分支。每种大分支内部再根据“z是父亲的左孩子还是右孩子”进一步分子情况。所以网上常说的“插入四种情况”本质上是这个分类逻辑的自然展开情况编号父节点叔叔节点z的位置处理方式1红红任意父、叔变黑祖父变红z上移两级2红黑右内侄对父节点旋转转化为情况33红黑左外侄祖父变红父变黑祖父旋转情况1是“局部变色”把红节点往上传直到不再违反性质4。情况2和3是“旋转变色”本质上是把“连续红节点”的结构重新分布让红节点从属于不同路径从而把黑色骨架拉直。3.4 为什么叔叔是红色时用变色是黑色时用旋转这个区别要理解透。叔叔红色意味着“当前局部区域的黑节点数足够多可以容纳更多红节点”——祖父本来是黑的把祖父染红父和叔染黑黑高不变性质4在局部恢复。叔叔黑色则意味着一侧的黑高比另一侧多光靠变色解决不了“祖父一侧路径黑多、另一侧黑少”的不平衡必须通过旋转把多出来的黑色节点挪到对侧去。每次旋转前先做一次小旋转情况2把“弯曲的红链”拉直成“直线红链”情况3再对祖父旋转这样一次大旋转就能把两个红孩子分配到两边同时恢复黑高。我调试红黑树最深的感受是变色是在“同层”交换颜色旋转是在“跨层”改变结构。当局部结构无法用变色平衡时就要靠旋转重新分配黑高。能变色的先变色变不了色再旋转这个优先级顺序贯穿了所有修复逻辑。4. 删除比插入绕十倍但掌握套路就没那么难删除之所以比插入复杂是因为删除一个节点会直接破坏性质5黑高相等。插入时新节点是红色黑高天然不受影响删除时你删掉的节点可能是黑色这等于在一条路径上永久砍掉了一个黑节点靠变色已经无法恢复。4.1 删除分两个阶段BST删除 红黑修复第一阶段和普通BST删除完全一致找后继节点然后把后继的值拷贝到删除位置或者直接移动节点指针本质上是把“删除目标”转化为“删除一个最多只有一个孩子的节点”。第二阶段才进入红黑修复修复的目标就是处理“被删节点是黑色”造成的黑高缺失。我把“被删节点是黑色”导致的缺失继续往下推删除后占据删除位置的节点可以是后继节点或者原位置的孩子被看作“携带双重黑色”double black。这个概念初看很抽象我就是为了理解它专门把删除代码跑了几十遍双重黑不是真正的颜色而是一种标记表示这个节点沿路径的黑高比其他位置多承担了一个“债务”。修复的过程就是不断向父节点、兄弟节点“转移债务”直到遇到一个能一次性平账的节点。4.2 删除修复的四种情况先看关键代码这是删除的核心部分void deleteFixup(NodeT* x) { while (x ! root x-color BLACK) { if (x x-parent-left) { NodeT* w x-parent-right; // 兄弟 if (w-color RED) { // 情况1兄弟是红色把兄弟变黑父变红左旋父 w-color BLACK; x-parent-color RED; rotateLeft(x-parent); w x-parent-right; } if (w-left-color BLACK w-right-color BLACK) { // 情况2兄弟是黑色且孩子全黑兄弟变红债务上移 w-color RED; x x-parent; } else { if (w-right-color BLACK) { // 情况3兄弟是黑右侄黑左侄红先转成情况4 w-left-color BLACK; w-color RED; rotateRight(w); w x-parent-right; } // 情况4兄弟是黑右侄是红一次旋转变色解决 w-color x-parent-color; x-parent-color BLACK; w-right-color BLACK; rotateLeft(x-parent); x root; } } else { // 对称逻辑 NodeT* w x-parent-left; if (w-color RED) { w-color BLACK; x-parent-color RED; rotateRight(x-parent); w x-parent-left; } if (w-right-color BLACK w-left-color BLACK) { w-color RED; x x-parent; } else { if (w-left-color BLACK) { w-right-color BLACK; w-color RED; rotateLeft(w); w x-parent-left; } w-color x-parent-color; x-parent-color BLACK; w-left-color BLACK; rotateRight(x-parent); x root; } } } x-color BLACK; } void remove(const T val) { NodeT* z root; while (z ! nil) { if (val z-data) z z-left; else if (val z-data) z z-right; else break; } if (z nil) return; NodeT* y z; NodeT* x nullptr; Color y_origin_color 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); y_origin_color 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; } delete z; if (y_origin_color BLACK) deleteFixup(x); }4.3 四种情况的逻辑推导与记忆方法先理解分类依据修复时x是那个“带债务”的节点核心判断对象是它的兄弟节点w。情况1兄弟是红色。红色兄弟说明两边黑高悬殊明显没法直接局部修。我们把兄弟染黑、父染红、然后旋转父——这一步不直接解决问题但把兄弟变成了黑色并让新的兄弟变成原来兄弟的儿子从而把问题收敛到“兄弟是黑色”的情况。我把这步叫作“换一个兄弟再来谈”。情况2兄弟是黑色且兄弟两个儿子都是黑色。这种情况说明兄弟这侧“没有多余的黑节点可以借出来”那就把兄弟染红相当于兄弟这侧黑高减1让债务上升到父节点然后把父节点当作新的x继续向上处理。情况3兄弟是黑色兄弟的近侄是红色远侄是黑色。这个形态没法直接旋转先把近侄通过旋转变成远侄红的情况从而转到情况4。这步是纯粹的“姿态转换”。情况4兄弟是黑色兄弟的远侄是红色。这是唯一能真正“平账”的情况把父节点颜色赋给兄弟父染黑、远侄染黑、再旋转父。旋转后佩戴债务的节点获得一个额外的黑节点债主债务清零整个循环结束x root。记忆口诀可以这样总结“红兄换人黑兄子全黑则上移近侄红先旋转远侄红则平账。” 这四个情况对应着思考问题的顺序先排除红兄弟再排除全黑侄再调整内侄最后靠外侄收尾。4.4 一个删除案例的完整验证假设树里有节点序列 {10, 20, 30, 40, 50, 60}红黑树形态是20为根黑10和30是它的两个孩子红、黑不定细节其他节点按层分布。删除40而40是某个红色节点那么黑高不变不需要修复。测试时要专门挑“黑节点删除”来触发修复路径比如先构造一棵全是黑节点的树插入1、2、3、4、5后连续变色然后删除根节点你会发现这几乎是删除修复最复杂的路径——兄弟节点为黑、侄子全黑、父节点需要递归向上修正的多层链条全都会走一遍。调试实践我每次删除一个节点都写一个验证函数遍历树检查五条性质是否全部满足如果违反正则打印节点路径。这个函数虽然跑起来慢但比人眼盯着几十个节点的颜色靠谱得多。后面第6节我会给出验证思路。5. 从课堂到战场红黑树在STL与真实项目中的样子5.1 std::map与std::set其实就长这样你每天用的std::map、std::set在 libstdc 里就是_Rb_tree的一层包装。std::map的元素是pairconst Key, Tstd::set的元素是Key底层同一套红黑树。用红黑树而不是哈希表核心原因是有序性。哈希表的查找是O(1)但你要做范围查询lower_bound、upper_bound、找最小最大值、顺序遍历哈希表就麻烦了。红黑树天然支持有序遍历begin()是树的最左节点迭代器走中序后继。这就是为什么数据库索引和关联容器更多选择树结构而不是哈希结构。STL源码里有一个细节值得注意STL红黑树并不是用nullptr表示NIL叶子而是用一个指向header哨兵节点的指针。header的父指针指向根节点左指针指向树的最小节点右指针指向最大节点。这样做的好处是begin()和rbegin()直接通过header-left和header-right拿节点无需从根开始查找。这个设计是工程上对教科书红黑树的一个经典优化面试提到STL红黑树时能说出这一点会让人觉得你真的去看过源码而不是只背过性质。5.2 封装一个最小可用的红黑树容器学完红黑树最大的成就感来自把它封装成一个可以替代std::set的最小容器。我当时折腾了一个周末写了insert、remove、find、中序遍历、以及一个简易的迭代器。关键点在于迭代器的operator要用“右孩子非空则找右子树最左节点否则向上找到第一个不是右孩子的祖先”这套逻辑和STL的实现思路一致。class iterator { public: NodeT* node; NodeT* nil_; iterator(NodeT* n, NodeT* nil) : node(n), nil_(nil) {} const T operator*() const { return node-data; } iterator operator() { if (node-right ! nil_) { node node-right; while (node-left ! nil_) node node-left; } else { NodeT* p node-parent; while (p ! nil_ node p-right) { node p; p p-parent; } node p; } return *this; } bool operator(const iterator other) const { return node other.node; } bool operator!(const iterator other) const { return node ! other.node; } };封装完成后我写了一个随机测试程序随机生成10万个整数插入我的红黑树容器再逐个查找、删除过程中每个操作后都调用性质验证函数。最终跑过一个晚上无崩溃那种成就感比看任何教程都强。5.3 红黑树、AVL树与跳表的选型对比如果你在真实项目里需要一棵自平衡搜索树怎么选我自己的经验是需求场景推荐选择理由需要严格的最坏时间保证主要用于查询AVL树高度更矮查询最坏情况更优大量插入删除且插入删除性能更重要红黑树旋转次数少重平衡成本低需要有序遍历范围查询红黑树STL容器已实现无需自己造轮子并发读写且写操作频繁跳表无旋转无锁定路径分段锁更容易磁盘存储、数据库索引B树 / B树节点按页大小组织减少IO次数有一说一如果你不是在学习、面试、或者维护一个已有的红黑树库生产环境直接用std::map就行。自己造红黑树的轮子价值在于彻底理解自平衡机制而不在于替代STL。写一遍之后再看STL源码你会发现很多设计都是顺着同一个思路展开的比如迭代器哨兵、节点分配器、异常安全处理。6. 我的调试经验与几个必须避开的坑6.1 验证函数红黑树调试的“安全网”手写红黑树最大的痛就是“代码看着对跑起来错”而且错误往往是几万次插入后才出现的悬垂指针问题。我在写的第二天就写了一个验证函数每一步插入删除之后都调用它能自动遍历整棵树检查五条性质int validate(NodeT* x) { if (x nil) return 1; // NIL叶子视为黑色 if (x-color RED (x-left-color ! BLACK || x-right-color ! BLACK)) { std::cerr 违反性质4红节点孩子必须为黑 std::endl; exit(1); } int lh validate(x-left); int rh validate(x-right); if (lh ! rh) { std::cerr 违反性质5黑高不一致 std::endl; exit(1); } return lh (x-color BLACK ? 1 : 0); }有了这个函数之后我每次吞掉一个bug就把对应的输入序列固定下来构造一个最小复现用例再人肉推演一遍这棵树应该变成什么样。这个习惯特别重要它让我不再依赖“蒙对了就好”而是真正把树的每一步变化刻进脑子里。6.2 我踩过的四个经典坑第一个坑是NIL节点不统一。刚开始我用nullptr表示叶子旋转代码里到处判断if (x ! nullptr)结果漏了某条分支导致在某次旋转中把nullptr挂上了父指针最后崩溃在迭代器遍历。后来我统一改成成员nil所有指针操作都假设nil是一个真实存在的节点判断逻辑简化为x ! nil代码反而清晰多了。第二个坑是旋转后父指针更新遗漏。左旋右旋不是简单的指针交换还要维护三代关系——旋转节点的父节点、子节点、以及祖父节点的指向。我漏过一次“祖父指向新根”的更新导致根节点在旋转后失去父指针后续插入时整棵树断链。排查方法很简单每次旋转后打印根节点和几个关键子孙的父指针和手推的结果对比。第三个坑是删除修复忘了处理x root的情况。删除循环的终止条件是x root但如果你删除的就是根节点且删除后根是红色的必须在循环外把root-color BLACK执行一遍否则根可能变红性质2被破坏。这个坑尤其隐蔽因为它只在频繁删除根节点的测试序列里才出现。第四个坑是递归删除导致栈溢出。有些教程用递归方式删除但红黑树高度在最坏情况下是2log₂n对于百万级数据量递归深度已经不小如果树因为bug退化成链递归深度直接拉满栈就爆了。我的实现里所有删除都改成迭代写法这是我在处理大数据量测试时强制自己做的优化。6.3 我建议的学习路线如果你现在刚开始接触红黑树我建议按这个顺序推进能少走很多弯路先手工模拟插入过程拿一组数字比如8、3、11、1、5、9、14在纸上画出每一步插入后的树标上颜色跑通所有插入情况。再手工模拟删除过程从这棵树里按顺序删黑色节点体会“双重黑”的传递。写最小实现只写节点、左旋右旋、插入、查找不写删除先把插入跑通。加删除使用验证函数反复测试构造专门触发各种情况的用例。对照STL源码读bits/stl_tree.h看_Rb_tree如何用哨兵节点优化迭代器看_Rb_tree_insert_and_rebalance和_Rb_tree_erase_and_rebalance的实现。扩展成容器加迭代器、find、clear封装成你自己的set。走完这六步红黑树对你来说就不再是“背下来又忘掉”的章节了而是“亲手重建过”的结构。以后面试聊到红黑树你可以直接说出旋转的细节、为什么用变色不用全重平衡、STL为什么选红黑树而不是AVL——这些都不是背的而是真的从代码里长出来的。我个人在这条路上最大的感受是红黑树的代码一行一行写下来比看十遍教科书更折磨人但也更刻骨铭心。每当你深夜debug到怀疑人生然后第二天醒来发现自己昨天漏的那条父指针赋值时你对这个树的敬畏和理解就又深了一层。希望这篇系列第22篇能让你的C编程生活里多一棵能亲手造出来的既红又黑的大树。