尧图网站建设 
如果你写过或者用过std::map大概率会好奇过一个问题它怎么能在插入、删除、查找上都是O(log n)而且遍历时还能保持有序答案就是红黑树。C标准库里的std::map/std::set/std::multimap底层实现几乎都基于红黑树。这篇内容是我这段时间系统性整理C进阶知识时整理的一份“红黑树及其实现”笔记希望能帮那些准备面试、想看 STL 源码、或者想自己手写一棵平衡树的朋友把这块硬骨头啃下来。红黑树看起来复杂其实核心就三件事节点颜色、旋转、插入/删除后的颜色修复。很多教程一上来就甩出五种性质、四种情况然后把人绕晕。我不打算这么讲。我先把底层逻辑讲明白再给完整可运行的C实现代码最后分享我实际调试过程中踩过的坑和排查技巧。这篇不是抄书是我自己动手写、跑测试、和std::map对拍之后沉淀下来的实战经验。1. 整体设计思路为什么要自己实现红黑树1.1 传统二叉搜索树的致命弱点二叉搜索树BST本身是很直观的结构左子树比根小右子树比根大。如果插入顺序比较理想比如随机数据树的高度约等于O(log n)查找效率非常高。但一旦数据有序插入比如依次插入1,2,3,4,5,6树就退化成一个单链表高度变成n查找复杂度退化成O(n)。我第一次碰到这个问题是在背STL源码时当时想不明白明明 BST 这么好理解为什么标准库要采用红黑树后来自己造数据模拟了几组才发现普通 BST 的退化问题太致命了。对于服务端程序里动不动插入几十万、几百万个 key 的场景退化成链表意味着灾难。红黑树就是专门解决这个问题的它通过节点的颜色约束和插入删除后的自平衡操作保证树的高度始终维持在O(log n)。1.2 为什么是红黑树而不是 AVL 树或 B 树很多初学者会问平衡树不是还有 AVL 树吗AVL 的平衡条件更严格查找效率理论上更稳定为什么std::map偏偏选红黑树关键在于“平衡的代价”。AVL 树要求任意节点的左右子树高度差不超过 1所以它维护的是“绝对平衡”。这个约束很强插入或删除一个节点后很容易触发一连串复杂的旋转。红黑树则不同它允许左右子树高度差最多达到两倍必须通过颜色性质来约束把平衡要求放宽了一些。换来的是更少的旋转次数插入操作最多只需要 2 次旋转删除操作最多需要 3 次旋转。对于频繁插入删除的应用来说红黑树的整体效率更高。至于 B 树那是另一个思路。B 树是多叉平衡树一个节点可以放很多 key主要用于磁盘或数据库索引因为它的节点大、层级浅能减少磁盘 IO。红黑树是二叉树适合在内存中工作两者不是同一个东西。网上有人问“B树是红黑树吗”答案显然不是但两者都是为了解决“有序数据的高效查找”这个命题只是一个面向磁盘、一个面向内存。1.3 我这次实现的工程目标我给自己定的实现目标很简单基于模板写一个RBTree容器类支持insert、erase、find、中序遍历然后用随机数据验证红黑树五条性质再和std::map对拍确保行为一致。这个目标看起来简单实际动手才发现坑不少。因为我是用C模板来实现的所以还要考虑“如何写出能像 STL 一样灵活支持不同 key/value 类型的代码”。最终我采用了模板参数传入 key 类型、value 类型和比较器的方式这个设计思路和 STL 基本一致。2. 红黑树核心原理五种性质到底在约束什么2.1 五条性质的直观理解红黑树的定义不复杂但教科书式的描述往往太抽象。我用自己的话翻译一下每个节点要么是红色要么是黑色。这条没什么好解释的就是定义。根节点是黑色。根节点如果能变成红色会让很多边界情况不好处理。每个叶子节点NIL 空节点是黑色。注意这里说的叶子是空节点不是普通意义上的末端节点。如果一个节点是红色那它的两个孩子必须是黑色。这个性质直接限制了红色节点不能连续出现。从任意节点出发到其所有叶子节点的路径上黑色节点的数量必须相同。这条性质叫“黑高一致”。前四条还算好理解第五条是红黑树的灵魂。它保证的是一棵有 n 个内部节点的红黑树高度最多不超过2 * log2(n1)。为什么因为从根到叶子的最短路径是全黑路径设黑高为bh最短路径长度就是bh。由于红色节点不能连续任意路径上的红色节点数最多等于黑色节点数所以最长路径长度最多是2*bh。这样最长路径和最短路径的比值控制在 2 倍以内树就不会退化。2.2 黑高和树高的数学关系黑高black-height是从某个节点出发到叶子路径上黑色节点的个数不包括该节点本身。对于一棵有 n 个内部节点的红黑树根的黑高至少是log2(n1)因为黑高为bh的树至少有2^bh - 1个内部节点类似满二叉树。而实际树高最多是2*bh所以树高h 2*log2(n1)时间复杂度就是O(log n)。说句实话这个数学推导我在第一次看的时候也觉得绕但后来画了几个例子就明白了。红黑树并没有要求左右子树高度绝对相等它只通过“路径上黑色数量一致”就把高度差限制在了两倍范围内。这个设计非常巧妙代价低效果却足够好。2.3 用 2-3-4 树的视角理解红黑树我自己的经验是如果只背五条性质看代码还是懵但如果把红黑树当作 2-3-4 树的“二叉化编码”一切豁然开朗。2-3-4 树是一种多叉树每个节点可以存储 1 个、2 个或 3 个关键字分别对应 2 个、3 个、4 个孩子。红黑树可以理解为把 2-3-4 树的每个节点“摊开”成若干个二叉树节点黑色节点是 2-3-4 树节点的“父节点”红色节点是和黑色父节点同属一个 2-3-4 树节点的其他关键字。所以你就明白了2-3-4 树的一个三节点两个关键字、三个孩子在红黑树里表现为“一个黑节点 一个红孩子”。2-3-4 树的一个四节点三个关键字、四个孩子在红黑树里表现为“一个黑节点 两个红孩子”。红色节点不能有红色孩子对应了 2-3-4 树节点不会再嵌套其他节点。所有叶子在同一层对应红黑树的黑高一致。有了这个对应关系插入删除时的各种情况就有了意义插入红节点相当于在 2-3-4 树的节点里加关键字要是塞不下了就把中间关键字“上提”并变色这就是变色和旋转的由来。在我看来不理解 2-3-4 树红黑树的代码就是死记硬背理解了写起来就是顺水推舟。3. 节点设计与基本操作实现3.1 节点结构定义要写红黑树第一步是设计节点。除了左右的 child 指针我增加了 parent 指针。原因是修复操作需要从当前节点一路向上回溯到根节点没有 parent 指针就只能用一个栈记录路径代码会别扭很多。enum class Color : bool { RED, BLACK }; template typename K, typename V struct RBNode { K key; V value; Color color; RBNode *left; RBNode *right; RBNode *parent; RBNode(const K k, const V v, Color c, RBNode* nil) : key(k), value(v), color(c), left(nil), right(nil), parent(nil) {} };value 可以直接用模板V但这里有个小设计点对于仿 STL 的 mapvalue 应该作为pairconst K, V存在并且不能随意赋值 key。不过我的目的只是学习红黑树机制所以分开存 key 和 value代码更直观。3.2 哨兵节点设计红黑树的实现里几乎所有空指针都指向一个“哨兵节点” nil。为什么要这么做因为红黑树性质 3 说叶子节点是黑色的而且删除修复的时候经常要访问空节点的兄弟、父节点。如果直接使用nullptr每次判断都要先检查是否为空代码会非常啰嗦。哨兵节点把所有空指针统一起来旋转和修复代码就可以无脑访问x-left、x-right同时nil的颜色固定为黑色。我为了实现上的清晰把 nil 声明为类内对象初始化时把它的左右孩子和父指针都指向自己根节点初始化为 nilRBNode* nil; RBNode* root;注意因为所有空指针都指向同一个 nil所以千万别写delete nil之类的代码。这是一个隐含约定后面调试的时候容易踩坑。3.3 左旋和右旋旋转的本质是“换爹”旋转是红黑树的基本操作分为左旋和右旋。很多教程用黑话描述“把右孩子提上来”我觉得最直观的理解是旋转是在局部交换两棵子树的父子关系但保持中序遍历顺序不变。以左旋为例假设要旋转节点x它的右孩子是y。左旋之后y 变成子树根x 变成 y 的左孩子y 原来的左孩子过继给 x 当右孩子。整个过程不改变中序序列。void rotateLeft(RBNode* x) { RBNode* 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; }右旋完全对称把right和left互换即可。写旋转的时候有四个指针要更新顺序很容易错。我的经验是每次写完后自己画一棵三层小树手动推一遍中序遍历确认旋转前后的序列一致再往下写。3.4 前驱和后继红黑树要支持中序遍历就得有找前驱小于当前 key 的最大节点和后继大于当前 key 的最小节点的能力。删除操作里如果被删节点有两个孩子我们通常用它的前驱或后继的值来覆盖它然后删除那个前驱/后继节点这样问题就转成了“删除最多只有一个孩子的节点”。RBNode* treeMinimum(RBNode* node) { while (node-left ! nil) node node-left; return node; } RBNode* treeMaximum(RBNode* node) { while (node-right ! nil) node node-right; return node; } RBNode* successor(RBNode* node) { if (node-right ! nil) return treeMinimum(node-right); RBNode* p node-parent; while (p ! nil node p-right) { node p; p p-parent; } return p; }这个前驱后继函数很简单但是删除时能不能写对直接决定后面的修复操作是否安全。4. 插入修复的完整实现4.1 插入新节点为什么是红色的插入一个新节点第一步是像普通 BST 一样把它挂到树上。关键问题是新节点应该是红色还是黑色如果插入黑色节点那么从根到该节点的路径上黑色数一定比其他路径多 1直接破坏性质 5黑高一致。要修复黑高不一致得从根到叶一路调整摊子铺得非常大。如果插入红色节点则可能破坏性质 4红节点不能有红孩子但性质 4 只影响局部连续红色区域修复时只要从插入点往上慢慢“消红”即可。所以实际实现里新节点一律先染红插入后统一调用insertFixup处理。4.2 插入修复的三种情况插入修复的核心是处理“当前节点是红色父节点也是红色”的冲突。按照叔叔节点的颜色和形状我分成三种情况处理。先说一个我自己的记忆口诀看叔叔扭直线变色收尾。情况条件操作Case 1父节点为红叔叔节点为红父、叔变黑祖父变红将祖父作为新的当前节点向上继续检查Case 2父节点为红叔叔节点为黑当前节点与父节点不在同一方向折线先对父节点旋转一次变为直线形态转入 Case 3Case 3父节点为红叔叔节点为黑当前节点与父节点在同一方向直线祖父节点旋转一次父变黑、祖父变红为什么叔叔节点这么关键因为红黑树性质要求每条路径黑高一致当新插入一个红色节点时如果叔叔也是红色就可以把父和叔同时变黑把红色“顶”给祖父然后继续从祖父向上检查。如果叔叔是黑色光靠变色解决不了问题因为把父变黑会让这条路径黑高多 1必须配合旋转去调整树的形状。下面给完整代码。为了对称性我只展示了当前节点在左侧分支的情况右侧分支是完全镜像的。void insertFixup(RBNode* z) { while (z-parent-color Color::RED) { if (z-parent z-parent-parent-left) { RBNode* y z-parent-parent-right; if (y-color Color::RED) { // Case 1: 叔叔是红色 z-parent-color Color::BLACK; y-color Color::BLACK; z-parent-parent-color Color::RED; z z-parent-parent; } else { if (z z-parent-right) { // Case 2: 折线先左旋成直线 z z-parent; rotateLeft(z); } // Case 3: 直线右旋祖父并变色 z-parent-color Color::BLACK; z-parent-parent-color Color::RED; rotateRight(z-parent-parent); } } else { // 镜像情况左右互换即可 RBNode* y z-parent-parent-left; if (y-color Color::RED) { z-parent-color Color::BLACK; y-color Color::BLACK; z-parent-parent-color Color::RED; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rotateRight(z); } z-parent-color Color::BLACK; z-parent-parent-color Color::RED; rotateLeft(z-parent-parent); } } } root-color Color::BLACK; }注意最后一行无论上面经历了多少变色操作根节点统一强制为黑色。这个做法很关键。因为 Case 1 在处理过程中可能把根节点染红最后必须兜底变为黑。4.3 插入的复杂度分析红黑树插入的时间复杂度是O(log n)。修复循环中每执行一次 Case 1当前节点 z 就向上移动两层而树高是O(log n)所以最多执行O(log n)次。Case 2 和 Case 3 最多各执行一次也就是最多 2 次旋转。这也是红黑树在工程上受欢迎的原因变色便宜旋转昂贵而旋转次数被严格限制住了。我实测过插入 100 万个随机整数std::map和手写红黑树的耗时差距通常在 10% 以内差别主要来自分配器和节点结构设计而不是平衡算法本身。5. 删除修复的完整实现5.1 删除问题的转化双黑节点删除是红黑树里最折磨人的环节。我的做法是先不急着处理颜色而是用一个统一的方法把问题简化如果被删节点有两个孩子就找它的后继节点用后继的 key/value 覆盖被删节点然后转去删除那个后继节点。因为后继节点一定没有左孩子或者最多只有一个右孩子这样问题就变成了“删除最多只有一个孩子的节点”。删除这种节点时根据它的颜色不同后续处理也完全不同如果被删节点是红色直接删除即可不会影响黑高。如果被删节点是黑色删除后这条路径上的黑色节点数就少了一个性质 5 被破坏。为了补上消失的黑色标准做法是引入一个概念叫“双黑”节点。什么意思呢就是当前节点逻辑上承担了两个黑色节点的角色需要把多出来的黑色往树上传导直到找到机会释放它。5.2 删除修复的四种情况删除修复的循环条件是x 不是根节点且 x 的颜色是黑色。这里的 x 是“顶替”被删节点位置的那个节点。在循环里我们根据 x 的兄弟节点 w 的颜色以及 w 的两个孩子的颜色分成四种情况处理。我先把表格列出来方便对照情况兄弟节点状态处理方式Case 1兄弟 w 是红色对父节点旋转w 变黑、父变红重新获取兄弟节点Case 2兄弟 w 是黑色且 w 的两个孩子都是黑色把 w 变红将问题上抛给父节点Case 3兄弟 w 是黑色w 的左孩子是红色、右孩子是黑色对兄弟节点旋转兄弟左孩子变黑、兄弟变红重新获取兄弟节点Case 4兄弟 w 是黑色w 的右孩子是红色父节点与兄弟交换颜色兄弟右孩子变黑对父节点旋转结束这个表格背下来没用重要的是理解每种情况为什么这样处理。Case 1 本质上是通过旋转把“红兄弟”变成“黑兄弟”从而转化到 Case 2、3、4。Case 2 是兄弟这边没有多余的红色节点可以“借力”只能把兄弟变红把当前这个双黑节点和兄弟一起释放掉让父节点继承双黑的责任。Case 3 是把“近红侄子”转到远侧凑成 Case 4 的标准形状。Case 4 是终点通过父节点旋转并交换颜色双黑节点消失修复结束。5.3 删除实现代码删除主流程最让人头疼的地方是指针维护。我最开始用nullptr实现时代码里到处是判空后来统一用了哨兵节点代码清爽了一截。void transplant(RBNode* u, RBNode* 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 erase(const K key) { RBNode* z findNode(key); if (z nil) return; RBNode* y z; RBNode* x nil; Color yOrigColor 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 treeMinimum(z-right); yOrigColor 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 (yOrigColor Color::BLACK) { eraseFixup(x); } delete z; }这里最需要注意的是x可能是哨兵节点 nil。transplant函数会无条件执行v-parent u-parent这句话在 v 是 nil 时会让 nil 的 parent 指向被替换节点的父节点。因为这个 nil 是共享的它的 parent 会被反复改写但在每一次修复过程中x 所代表的“删除位置”父节点刚好正确所以 eraseFixup 能正常工作。这个细节在哨兵实现里极端重要。5.4 删除修复代码删除修复函数比插入长不少核心还是左右对称。我贴出左侧分支版本右侧分支镜像即可void eraseFixup(RBNode* x) { while (x ! root x-color Color::BLACK) { if (x x-parent-left) { RBNode* w x-parent-right; if (w-color Color::RED) { // Case 1 w-color Color::BLACK; x-parent-color Color::RED; rotateLeft(x-parent); w x-parent-right; } if (w-left-color Color::BLACK w-right-color Color::BLACK) { // Case 2 w-color Color::RED; x x-parent; } else { if (w-right-color Color::BLACK) { // Case 3 w-left-color Color::BLACK; w-color Color::RED; rotateRight(w); w x-parent-right; } // Case 4 w-color x-parent-color; x-parent-color Color::BLACK; w-right-color Color::BLACK; rotateLeft(x-parent); x root; } } else { // 左右镜像 RBNode* w x-parent-left; if (w-color Color::RED) { w-color Color::BLACK; x-parent-color Color::RED; rotateRight(x-parent); w x-parent-left; } if (w-right-color Color::BLACK w-left-color Color::BLACK) { w-color Color::RED; x x-parent; } else { if (w-left-color Color::BLACK) { w-right-color Color::BLACK; w-color Color::RED; rotateLeft(w); w x-parent-left; } w-color x-parent-color; x-parent-color Color::BLACK; w-left-color Color::BLACK; rotateRight(x-parent); x root; } } } x-color Color::BLACK; }我写这个函数的时候反复出错后来总结了一个经验每处理完一个 Case立刻画一次当前的树形变化尤其是 Case 1 到 Case 4 的流程转换必须亲眼看清楚 w 变成了哪个节点否则乱改指针就会写出无法修复的局面。删除修复的旋转次数也很有保证Case 1 最多执行一次后就会转成 Case 2/3/4Case 3 后马上转 Case 4Case 4 结束循环。再加上 Case 2 可能向上传导O(log n)次但每次只是变色所以删除操作最多 3 次旋转耗时依然是O(log n)。6. 容器封装与测试验证6.1 把红黑树封装成类模板我把上面所有逻辑封装成一个RBTree类模板对外只暴露insert、erase、find、inorderTraversal方法。类内部持有哨兵节点 nil 和根节点 root。template typename K, typename V, typename Comp std::lessK class RBTree { public: using Node RBNodeK, V; RBTree() { nil new Node(K{}, V{}, Color::BLACK, nullptr); nil-left nil-right nil-parent nil; root nil; } ~RBTree() { clear(root); delete nil; } void insert(const K key, const V val); void erase(const K key); bool contains(const K key) const; V operator[](const K key); void inorderTraversal() const; private: Node* nil; Node* root; Comp comp; // 内部函数rotateLeft / rotateRight / insertFixup / eraseFixup ... };这里要有意识地处理内存释放。红黑树的节点都是 new 出来的析构时必须递归删除所有真实节点但注意不能把哨兵节点也删掉否则其他地方还在用 nil 就会崩溃。6.2 用随机数据验证红黑树性质写完了不能拍脑袋说能用。我要用一个自带检查器的测试来验证性质。检查器递归遍历整棵树返回每条路径的黑高同时检查空节点必须是黑色。根节点必须是黑色。红色节点的两个孩子必须是黑色。所有叶子路径的黑高必须一致。这个检查器本身也是理解红黑树的产物。我写的测试代码类似下面这样int validate(Node* node, int blackCount, int expectedBlack) { if (node nil) { if (expectedBlack 0) expectedBlack blackCount; return expectedBlack blackCount ? 0 : -1; } if (node-color Color::BLACK) blackCount; if (node-color Color::RED) { if (node-left-color ! Color::BLACK || node-right-color ! Color::BLACK) { return -1; } } int left validate(node-left, blackCount, expectedBlack); int right validate(node-right, blackCount, expectedBlack); return (left 0 right 0) ? 0 : -1; }测试跑法很简单随机生成 10000 个整数插入每插入 100 个就调用一次validate确认树仍然是合法红黑树。然后随机删除其中 5000 个每次删除后也调用一次validate。只有所有断言都通过才算这个实现基本可靠。6.3 与 std::map 对拍做完了性质校验我还会做对拍测试用同样一组随机操作序列分别作用在手写红黑树和std::map上每一步都比较find结果和中序遍历序列是否一致。对拍测试看起来简单实际上很能发现隐蔽 bug。我最开始实现的时候删除修复的Case 3写错了方向导致只删除特定组合的数据时会丢节点。普通随机测试偶尔能跳过去对拍几百个随机序列后就暴露了。所以我的建议是自己实现容器类后一定要和标准库做随机对拍这是找出逻辑错误性价比最高的方式。6.4 性能观察分别插入 100 万个随机整数手写红黑树和std::map在Release模式下的耗时非常接近。std::map因为有成熟的分配器封装节点内存分配效率会稍高一点手写版本如果直接new/delete性能会略差但差距不会超过一到两倍。如果后续想继续优化可以把节点的内存分配改成内存池或使用std::allocator。不过对于理解红黑树算法本身这个级别已经足够了。7. 常见问题排查与经验技巧7.1 最容易踩的坑第一坑旋转时指针更新顺序不对。旋转涉及四个节点的 parent 重定向只要顺序错了树结构就乱了。我写过一个口诀先断、再接、再换色。先处理子树的归属关系再更新父指针最后才做节点颜色变化。第二坑忘记把根节点设置为黑色。修复过程中可能通过 Case 1 把根节点染红如果最后不统一置黑根节点红色的树仍然可能满足其他性质但在很多边界情况下会出问题。所以insertFixup末尾必须加一行root-color Color::BLACK;。第三坑删除时没有考虑x可能为 nil。如果哨兵节点不是全局独一无二的那修复时访问x-parent可能拿到错误值。我的建议是先不考虑自己的“创新优化”老老实实按哨兵节点的标准实现走一遍通了之后再改。7.2 红黑树的调试技巧调红黑树跟调普通二叉树不一样普通二叉树只要看节点挂没挂对红黑树还要看颜色和黑高。我用的调试方案是三步走最小用例调试。手动模拟插入几个固定值每一步都打印树的结构和颜色对照教科书案例。性质校验器。写完立即写validate()每次插入/删除后都跑一遍一旦报错立刻定位。二分排查。如果某次随机测试挂了就把操作序列二分找到第一个导致 validate 失败的插入/删除操作这时情况已经很局部很快能定位到是哪个 Case 写错了。还有个土办法但很实用在旋转和变色函数里加日志输出记录操作类型和当前节点 key。出错后回放日志一步步对比正常树的结构很快就能发现问题。7.3 面试和工程中的实际建议面试中红黑树的高频问题无非这几个新插入节点为什么是红色插入修复最多几次旋转删除修复为什么比插入复杂红黑树和 AVL 树的区别是什么最长路径为什么不超过最短路径的两倍这些问题如果只背答案面试官追问一个“为什么”就露馅。最好是亲手写一遍并且真的跑过测试那些“为什么”自然就记住了。比如插入修复的 Case 2/3 为什么要旋转而不是直接变色是因为叔叔是黑色时变色会导致某条路径黑高增加性质 5 被破坏。不实际撞过这个问题很难说得清楚。工程上绝大多数时候我们直接使用std::map或std::set就行没必要自己造轮子。但理解红黑树的价值在于你看源码时能看懂_Rb_tree到底在干嘛遇到性能瓶颈时知道它的瓶颈在哪遇到自定义容器需求时也能知道应该在哪些方面改动。底层数据结构的“手感”就是靠这种动手实践积累起来的。最后分享一个我自己的笨办法。我最初学红黑树时对着代码背了三遍都没记住。真正开窍是在一个周末我把红黑树和 2-3-4 树的对应关系画了一遍再回去看插入删除的各个 Case发现每一步变色、每一次旋转都在做同一件事维护 2-3-4 树节点的分裂与合并。从那以后红黑树对我而言就从“一堆 case 的记忆题”变成了“一套有逻辑规则的算法”。建议你可以先画一棵 2-3-4 树然后把它“翻译”成红黑树多练几组插入删除再回到代码里看实现。这样学完你再去读std::map源码会收获一种研究底层实现的踏实感。如果你也在学 C 的数据结构红黑树是值得花时间啃下来的一个点。 C++红黑树从原理到实现：std::map底层平衡机制深入剖析
如果你写过或者用过std::map大概率会好奇过一个问题它怎么能在插入、删除、查找上都是O(log n)而且遍历时还能保持有序答案就是红黑树。C标准库里的std::map/std::set/std::multimap底层实现几乎都基于红黑树。这篇内容是我这段时间系统性整理C进阶知识时整理的一份“红黑树及其实现”笔记希望能帮那些准备面试、想看 STL 源码、或者想自己手写一棵平衡树的朋友把这块硬骨头啃下来。红黑树看起来复杂其实核心就三件事节点颜色、旋转、插入/删除后的颜色修复。很多教程一上来就甩出五种性质、四种情况然后把人绕晕。我不打算这么讲。我先把底层逻辑讲明白再给完整可运行的C实现代码最后分享我实际调试过程中踩过的坑和排查技巧。这篇不是抄书是我自己动手写、跑测试、和std::map对拍之后沉淀下来的实战经验。1. 整体设计思路为什么要自己实现红黑树1.1 传统二叉搜索树的致命弱点二叉搜索树BST本身是很直观的结构左子树比根小右子树比根大。如果插入顺序比较理想比如随机数据树的高度约等于O(log n)查找效率非常高。但一旦数据有序插入比如依次插入1,2,3,4,5,6树就退化成一个单链表高度变成n查找复杂度退化成O(n)。我第一次碰到这个问题是在背STL源码时当时想不明白明明 BST 这么好理解为什么标准库要采用红黑树后来自己造数据模拟了几组才发现普通 BST 的退化问题太致命了。对于服务端程序里动不动插入几十万、几百万个 key 的场景退化成链表意味着灾难。红黑树就是专门解决这个问题的它通过节点的颜色约束和插入删除后的自平衡操作保证树的高度始终维持在O(log n)。1.2 为什么是红黑树而不是 AVL 树或 B 树很多初学者会问平衡树不是还有 AVL 树吗AVL 的平衡条件更严格查找效率理论上更稳定为什么std::map偏偏选红黑树关键在于“平衡的代价”。AVL 树要求任意节点的左右子树高度差不超过 1所以它维护的是“绝对平衡”。这个约束很强插入或删除一个节点后很容易触发一连串复杂的旋转。红黑树则不同它允许左右子树高度差最多达到两倍必须通过颜色性质来约束把平衡要求放宽了一些。换来的是更少的旋转次数插入操作最多只需要 2 次旋转删除操作最多需要 3 次旋转。对于频繁插入删除的应用来说红黑树的整体效率更高。至于 B 树那是另一个思路。B 树是多叉平衡树一个节点可以放很多 key主要用于磁盘或数据库索引因为它的节点大、层级浅能减少磁盘 IO。红黑树是二叉树适合在内存中工作两者不是同一个东西。网上有人问“B树是红黑树吗”答案显然不是但两者都是为了解决“有序数据的高效查找”这个命题只是一个面向磁盘、一个面向内存。1.3 我这次实现的工程目标我给自己定的实现目标很简单基于模板写一个RBTree容器类支持insert、erase、find、中序遍历然后用随机数据验证红黑树五条性质再和std::map对拍确保行为一致。这个目标看起来简单实际动手才发现坑不少。因为我是用C模板来实现的所以还要考虑“如何写出能像 STL 一样灵活支持不同 key/value 类型的代码”。最终我采用了模板参数传入 key 类型、value 类型和比较器的方式这个设计思路和 STL 基本一致。2. 红黑树核心原理五种性质到底在约束什么2.1 五条性质的直观理解红黑树的定义不复杂但教科书式的描述往往太抽象。我用自己的话翻译一下每个节点要么是红色要么是黑色。这条没什么好解释的就是定义。根节点是黑色。根节点如果能变成红色会让很多边界情况不好处理。每个叶子节点NIL 空节点是黑色。注意这里说的叶子是空节点不是普通意义上的末端节点。如果一个节点是红色那它的两个孩子必须是黑色。这个性质直接限制了红色节点不能连续出现。从任意节点出发到其所有叶子节点的路径上黑色节点的数量必须相同。这条性质叫“黑高一致”。前四条还算好理解第五条是红黑树的灵魂。它保证的是一棵有 n 个内部节点的红黑树高度最多不超过2 * log2(n1)。为什么因为从根到叶子的最短路径是全黑路径设黑高为bh最短路径长度就是bh。由于红色节点不能连续任意路径上的红色节点数最多等于黑色节点数所以最长路径长度最多是2*bh。这样最长路径和最短路径的比值控制在 2 倍以内树就不会退化。2.2 黑高和树高的数学关系黑高black-height是从某个节点出发到叶子路径上黑色节点的个数不包括该节点本身。对于一棵有 n 个内部节点的红黑树根的黑高至少是log2(n1)因为黑高为bh的树至少有2^bh - 1个内部节点类似满二叉树。而实际树高最多是2*bh所以树高h 2*log2(n1)时间复杂度就是O(log n)。说句实话这个数学推导我在第一次看的时候也觉得绕但后来画了几个例子就明白了。红黑树并没有要求左右子树高度绝对相等它只通过“路径上黑色数量一致”就把高度差限制在了两倍范围内。这个设计非常巧妙代价低效果却足够好。2.3 用 2-3-4 树的视角理解红黑树我自己的经验是如果只背五条性质看代码还是懵但如果把红黑树当作 2-3-4 树的“二叉化编码”一切豁然开朗。2-3-4 树是一种多叉树每个节点可以存储 1 个、2 个或 3 个关键字分别对应 2 个、3 个、4 个孩子。红黑树可以理解为把 2-3-4 树的每个节点“摊开”成若干个二叉树节点黑色节点是 2-3-4 树节点的“父节点”红色节点是和黑色父节点同属一个 2-3-4 树节点的其他关键字。所以你就明白了2-3-4 树的一个三节点两个关键字、三个孩子在红黑树里表现为“一个黑节点 一个红孩子”。2-3-4 树的一个四节点三个关键字、四个孩子在红黑树里表现为“一个黑节点 两个红孩子”。红色节点不能有红色孩子对应了 2-3-4 树节点不会再嵌套其他节点。所有叶子在同一层对应红黑树的黑高一致。有了这个对应关系插入删除时的各种情况就有了意义插入红节点相当于在 2-3-4 树的节点里加关键字要是塞不下了就把中间关键字“上提”并变色这就是变色和旋转的由来。在我看来不理解 2-3-4 树红黑树的代码就是死记硬背理解了写起来就是顺水推舟。3. 节点设计与基本操作实现3.1 节点结构定义要写红黑树第一步是设计节点。除了左右的 child 指针我增加了 parent 指针。原因是修复操作需要从当前节点一路向上回溯到根节点没有 parent 指针就只能用一个栈记录路径代码会别扭很多。enum class Color : bool { RED, BLACK }; template typename K, typename V struct RBNode { K key; V value; Color color; RBNode *left; RBNode *right; RBNode *parent; RBNode(const K k, const V v, Color c, RBNode* nil) : key(k), value(v), color(c), left(nil), right(nil), parent(nil) {} };value 可以直接用模板V但这里有个小设计点对于仿 STL 的 mapvalue 应该作为pairconst K, V存在并且不能随意赋值 key。不过我的目的只是学习红黑树机制所以分开存 key 和 value代码更直观。3.2 哨兵节点设计红黑树的实现里几乎所有空指针都指向一个“哨兵节点” nil。为什么要这么做因为红黑树性质 3 说叶子节点是黑色的而且删除修复的时候经常要访问空节点的兄弟、父节点。如果直接使用nullptr每次判断都要先检查是否为空代码会非常啰嗦。哨兵节点把所有空指针统一起来旋转和修复代码就可以无脑访问x-left、x-right同时nil的颜色固定为黑色。我为了实现上的清晰把 nil 声明为类内对象初始化时把它的左右孩子和父指针都指向自己根节点初始化为 nilRBNode* nil; RBNode* root;注意因为所有空指针都指向同一个 nil所以千万别写delete nil之类的代码。这是一个隐含约定后面调试的时候容易踩坑。3.3 左旋和右旋旋转的本质是“换爹”旋转是红黑树的基本操作分为左旋和右旋。很多教程用黑话描述“把右孩子提上来”我觉得最直观的理解是旋转是在局部交换两棵子树的父子关系但保持中序遍历顺序不变。以左旋为例假设要旋转节点x它的右孩子是y。左旋之后y 变成子树根x 变成 y 的左孩子y 原来的左孩子过继给 x 当右孩子。整个过程不改变中序序列。void rotateLeft(RBNode* x) { RBNode* 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; }右旋完全对称把right和left互换即可。写旋转的时候有四个指针要更新顺序很容易错。我的经验是每次写完后自己画一棵三层小树手动推一遍中序遍历确认旋转前后的序列一致再往下写。3.4 前驱和后继红黑树要支持中序遍历就得有找前驱小于当前 key 的最大节点和后继大于当前 key 的最小节点的能力。删除操作里如果被删节点有两个孩子我们通常用它的前驱或后继的值来覆盖它然后删除那个前驱/后继节点这样问题就转成了“删除最多只有一个孩子的节点”。RBNode* treeMinimum(RBNode* node) { while (node-left ! nil) node node-left; return node; } RBNode* treeMaximum(RBNode* node) { while (node-right ! nil) node node-right; return node; } RBNode* successor(RBNode* node) { if (node-right ! nil) return treeMinimum(node-right); RBNode* p node-parent; while (p ! nil node p-right) { node p; p p-parent; } return p; }这个前驱后继函数很简单但是删除时能不能写对直接决定后面的修复操作是否安全。4. 插入修复的完整实现4.1 插入新节点为什么是红色的插入一个新节点第一步是像普通 BST 一样把它挂到树上。关键问题是新节点应该是红色还是黑色如果插入黑色节点那么从根到该节点的路径上黑色数一定比其他路径多 1直接破坏性质 5黑高一致。要修复黑高不一致得从根到叶一路调整摊子铺得非常大。如果插入红色节点则可能破坏性质 4红节点不能有红孩子但性质 4 只影响局部连续红色区域修复时只要从插入点往上慢慢“消红”即可。所以实际实现里新节点一律先染红插入后统一调用insertFixup处理。4.2 插入修复的三种情况插入修复的核心是处理“当前节点是红色父节点也是红色”的冲突。按照叔叔节点的颜色和形状我分成三种情况处理。先说一个我自己的记忆口诀看叔叔扭直线变色收尾。情况条件操作Case 1父节点为红叔叔节点为红父、叔变黑祖父变红将祖父作为新的当前节点向上继续检查Case 2父节点为红叔叔节点为黑当前节点与父节点不在同一方向折线先对父节点旋转一次变为直线形态转入 Case 3Case 3父节点为红叔叔节点为黑当前节点与父节点在同一方向直线祖父节点旋转一次父变黑、祖父变红为什么叔叔节点这么关键因为红黑树性质要求每条路径黑高一致当新插入一个红色节点时如果叔叔也是红色就可以把父和叔同时变黑把红色“顶”给祖父然后继续从祖父向上检查。如果叔叔是黑色光靠变色解决不了问题因为把父变黑会让这条路径黑高多 1必须配合旋转去调整树的形状。下面给完整代码。为了对称性我只展示了当前节点在左侧分支的情况右侧分支是完全镜像的。void insertFixup(RBNode* z) { while (z-parent-color Color::RED) { if (z-parent z-parent-parent-left) { RBNode* y z-parent-parent-right; if (y-color Color::RED) { // Case 1: 叔叔是红色 z-parent-color Color::BLACK; y-color Color::BLACK; z-parent-parent-color Color::RED; z z-parent-parent; } else { if (z z-parent-right) { // Case 2: 折线先左旋成直线 z z-parent; rotateLeft(z); } // Case 3: 直线右旋祖父并变色 z-parent-color Color::BLACK; z-parent-parent-color Color::RED; rotateRight(z-parent-parent); } } else { // 镜像情况左右互换即可 RBNode* y z-parent-parent-left; if (y-color Color::RED) { z-parent-color Color::BLACK; y-color Color::BLACK; z-parent-parent-color Color::RED; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rotateRight(z); } z-parent-color Color::BLACK; z-parent-parent-color Color::RED; rotateLeft(z-parent-parent); } } } root-color Color::BLACK; }注意最后一行无论上面经历了多少变色操作根节点统一强制为黑色。这个做法很关键。因为 Case 1 在处理过程中可能把根节点染红最后必须兜底变为黑。4.3 插入的复杂度分析红黑树插入的时间复杂度是O(log n)。修复循环中每执行一次 Case 1当前节点 z 就向上移动两层而树高是O(log n)所以最多执行O(log n)次。Case 2 和 Case 3 最多各执行一次也就是最多 2 次旋转。这也是红黑树在工程上受欢迎的原因变色便宜旋转昂贵而旋转次数被严格限制住了。我实测过插入 100 万个随机整数std::map和手写红黑树的耗时差距通常在 10% 以内差别主要来自分配器和节点结构设计而不是平衡算法本身。5. 删除修复的完整实现5.1 删除问题的转化双黑节点删除是红黑树里最折磨人的环节。我的做法是先不急着处理颜色而是用一个统一的方法把问题简化如果被删节点有两个孩子就找它的后继节点用后继的 key/value 覆盖被删节点然后转去删除那个后继节点。因为后继节点一定没有左孩子或者最多只有一个右孩子这样问题就变成了“删除最多只有一个孩子的节点”。删除这种节点时根据它的颜色不同后续处理也完全不同如果被删节点是红色直接删除即可不会影响黑高。如果被删节点是黑色删除后这条路径上的黑色节点数就少了一个性质 5 被破坏。为了补上消失的黑色标准做法是引入一个概念叫“双黑”节点。什么意思呢就是当前节点逻辑上承担了两个黑色节点的角色需要把多出来的黑色往树上传导直到找到机会释放它。5.2 删除修复的四种情况删除修复的循环条件是x 不是根节点且 x 的颜色是黑色。这里的 x 是“顶替”被删节点位置的那个节点。在循环里我们根据 x 的兄弟节点 w 的颜色以及 w 的两个孩子的颜色分成四种情况处理。我先把表格列出来方便对照情况兄弟节点状态处理方式Case 1兄弟 w 是红色对父节点旋转w 变黑、父变红重新获取兄弟节点Case 2兄弟 w 是黑色且 w 的两个孩子都是黑色把 w 变红将问题上抛给父节点Case 3兄弟 w 是黑色w 的左孩子是红色、右孩子是黑色对兄弟节点旋转兄弟左孩子变黑、兄弟变红重新获取兄弟节点Case 4兄弟 w 是黑色w 的右孩子是红色父节点与兄弟交换颜色兄弟右孩子变黑对父节点旋转结束这个表格背下来没用重要的是理解每种情况为什么这样处理。Case 1 本质上是通过旋转把“红兄弟”变成“黑兄弟”从而转化到 Case 2、3、4。Case 2 是兄弟这边没有多余的红色节点可以“借力”只能把兄弟变红把当前这个双黑节点和兄弟一起释放掉让父节点继承双黑的责任。Case 3 是把“近红侄子”转到远侧凑成 Case 4 的标准形状。Case 4 是终点通过父节点旋转并交换颜色双黑节点消失修复结束。5.3 删除实现代码删除主流程最让人头疼的地方是指针维护。我最开始用nullptr实现时代码里到处是判空后来统一用了哨兵节点代码清爽了一截。void transplant(RBNode* u, RBNode* 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 erase(const K key) { RBNode* z findNode(key); if (z nil) return; RBNode* y z; RBNode* x nil; Color yOrigColor 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 treeMinimum(z-right); yOrigColor 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 (yOrigColor Color::BLACK) { eraseFixup(x); } delete z; }这里最需要注意的是x可能是哨兵节点 nil。transplant函数会无条件执行v-parent u-parent这句话在 v 是 nil 时会让 nil 的 parent 指向被替换节点的父节点。因为这个 nil 是共享的它的 parent 会被反复改写但在每一次修复过程中x 所代表的“删除位置”父节点刚好正确所以 eraseFixup 能正常工作。这个细节在哨兵实现里极端重要。5.4 删除修复代码删除修复函数比插入长不少核心还是左右对称。我贴出左侧分支版本右侧分支镜像即可void eraseFixup(RBNode* x) { while (x ! root x-color Color::BLACK) { if (x x-parent-left) { RBNode* w x-parent-right; if (w-color Color::RED) { // Case 1 w-color Color::BLACK; x-parent-color Color::RED; rotateLeft(x-parent); w x-parent-right; } if (w-left-color Color::BLACK w-right-color Color::BLACK) { // Case 2 w-color Color::RED; x x-parent; } else { if (w-right-color Color::BLACK) { // Case 3 w-left-color Color::BLACK; w-color Color::RED; rotateRight(w); w x-parent-right; } // Case 4 w-color x-parent-color; x-parent-color Color::BLACK; w-right-color Color::BLACK; rotateLeft(x-parent); x root; } } else { // 左右镜像 RBNode* w x-parent-left; if (w-color Color::RED) { w-color Color::BLACK; x-parent-color Color::RED; rotateRight(x-parent); w x-parent-left; } if (w-right-color Color::BLACK w-left-color Color::BLACK) { w-color Color::RED; x x-parent; } else { if (w-left-color Color::BLACK) { w-right-color Color::BLACK; w-color Color::RED; rotateLeft(w); w x-parent-left; } w-color x-parent-color; x-parent-color Color::BLACK; w-left-color Color::BLACK; rotateRight(x-parent); x root; } } } x-color Color::BLACK; }我写这个函数的时候反复出错后来总结了一个经验每处理完一个 Case立刻画一次当前的树形变化尤其是 Case 1 到 Case 4 的流程转换必须亲眼看清楚 w 变成了哪个节点否则乱改指针就会写出无法修复的局面。删除修复的旋转次数也很有保证Case 1 最多执行一次后就会转成 Case 2/3/4Case 3 后马上转 Case 4Case 4 结束循环。再加上 Case 2 可能向上传导O(log n)次但每次只是变色所以删除操作最多 3 次旋转耗时依然是O(log n)。6. 容器封装与测试验证6.1 把红黑树封装成类模板我把上面所有逻辑封装成一个RBTree类模板对外只暴露insert、erase、find、inorderTraversal方法。类内部持有哨兵节点 nil 和根节点 root。template typename K, typename V, typename Comp std::lessK class RBTree { public: using Node RBNodeK, V; RBTree() { nil new Node(K{}, V{}, Color::BLACK, nullptr); nil-left nil-right nil-parent nil; root nil; } ~RBTree() { clear(root); delete nil; } void insert(const K key, const V val); void erase(const K key); bool contains(const K key) const; V operator[](const K key); void inorderTraversal() const; private: Node* nil; Node* root; Comp comp; // 内部函数rotateLeft / rotateRight / insertFixup / eraseFixup ... };这里要有意识地处理内存释放。红黑树的节点都是 new 出来的析构时必须递归删除所有真实节点但注意不能把哨兵节点也删掉否则其他地方还在用 nil 就会崩溃。6.2 用随机数据验证红黑树性质写完了不能拍脑袋说能用。我要用一个自带检查器的测试来验证性质。检查器递归遍历整棵树返回每条路径的黑高同时检查空节点必须是黑色。根节点必须是黑色。红色节点的两个孩子必须是黑色。所有叶子路径的黑高必须一致。这个检查器本身也是理解红黑树的产物。我写的测试代码类似下面这样int validate(Node* node, int blackCount, int expectedBlack) { if (node nil) { if (expectedBlack 0) expectedBlack blackCount; return expectedBlack blackCount ? 0 : -1; } if (node-color Color::BLACK) blackCount; if (node-color Color::RED) { if (node-left-color ! Color::BLACK || node-right-color ! Color::BLACK) { return -1; } } int left validate(node-left, blackCount, expectedBlack); int right validate(node-right, blackCount, expectedBlack); return (left 0 right 0) ? 0 : -1; }测试跑法很简单随机生成 10000 个整数插入每插入 100 个就调用一次validate确认树仍然是合法红黑树。然后随机删除其中 5000 个每次删除后也调用一次validate。只有所有断言都通过才算这个实现基本可靠。6.3 与 std::map 对拍做完了性质校验我还会做对拍测试用同样一组随机操作序列分别作用在手写红黑树和std::map上每一步都比较find结果和中序遍历序列是否一致。对拍测试看起来简单实际上很能发现隐蔽 bug。我最开始实现的时候删除修复的Case 3写错了方向导致只删除特定组合的数据时会丢节点。普通随机测试偶尔能跳过去对拍几百个随机序列后就暴露了。所以我的建议是自己实现容器类后一定要和标准库做随机对拍这是找出逻辑错误性价比最高的方式。6.4 性能观察分别插入 100 万个随机整数手写红黑树和std::map在Release模式下的耗时非常接近。std::map因为有成熟的分配器封装节点内存分配效率会稍高一点手写版本如果直接new/delete性能会略差但差距不会超过一到两倍。如果后续想继续优化可以把节点的内存分配改成内存池或使用std::allocator。不过对于理解红黑树算法本身这个级别已经足够了。7. 常见问题排查与经验技巧7.1 最容易踩的坑第一坑旋转时指针更新顺序不对。旋转涉及四个节点的 parent 重定向只要顺序错了树结构就乱了。我写过一个口诀先断、再接、再换色。先处理子树的归属关系再更新父指针最后才做节点颜色变化。第二坑忘记把根节点设置为黑色。修复过程中可能通过 Case 1 把根节点染红如果最后不统一置黑根节点红色的树仍然可能满足其他性质但在很多边界情况下会出问题。所以insertFixup末尾必须加一行root-color Color::BLACK;。第三坑删除时没有考虑x可能为 nil。如果哨兵节点不是全局独一无二的那修复时访问x-parent可能拿到错误值。我的建议是先不考虑自己的“创新优化”老老实实按哨兵节点的标准实现走一遍通了之后再改。7.2 红黑树的调试技巧调红黑树跟调普通二叉树不一样普通二叉树只要看节点挂没挂对红黑树还要看颜色和黑高。我用的调试方案是三步走最小用例调试。手动模拟插入几个固定值每一步都打印树的结构和颜色对照教科书案例。性质校验器。写完立即写validate()每次插入/删除后都跑一遍一旦报错立刻定位。二分排查。如果某次随机测试挂了就把操作序列二分找到第一个导致 validate 失败的插入/删除操作这时情况已经很局部很快能定位到是哪个 Case 写错了。还有个土办法但很实用在旋转和变色函数里加日志输出记录操作类型和当前节点 key。出错后回放日志一步步对比正常树的结构很快就能发现问题。7.3 面试和工程中的实际建议面试中红黑树的高频问题无非这几个新插入节点为什么是红色插入修复最多几次旋转删除修复为什么比插入复杂红黑树和 AVL 树的区别是什么最长路径为什么不超过最短路径的两倍这些问题如果只背答案面试官追问一个“为什么”就露馅。最好是亲手写一遍并且真的跑过测试那些“为什么”自然就记住了。比如插入修复的 Case 2/3 为什么要旋转而不是直接变色是因为叔叔是黑色时变色会导致某条路径黑高增加性质 5 被破坏。不实际撞过这个问题很难说得清楚。工程上绝大多数时候我们直接使用std::map或std::set就行没必要自己造轮子。但理解红黑树的价值在于你看源码时能看懂_Rb_tree到底在干嘛遇到性能瓶颈时知道它的瓶颈在哪遇到自定义容器需求时也能知道应该在哪些方面改动。底层数据结构的“手感”就是靠这种动手实践积累起来的。最后分享一个我自己的笨办法。我最初学红黑树时对着代码背了三遍都没记住。真正开窍是在一个周末我把红黑树和 2-3-4 树的对应关系画了一遍再回去看插入删除的各个 Case发现每一步变色、每一次旋转都在做同一件事维护 2-3-4 树节点的分裂与合并。从那以后红黑树对我而言就从“一堆 case 的记忆题”变成了“一套有逻辑规则的算法”。建议你可以先画一棵 2-3-4 树然后把它“翻译”成红黑树多练几组插入删除再回到代码里看实现。这样学完你再去读std::map源码会收获一种研究底层实现的踏实感。如果你也在学 C 的数据结构红黑树是值得花时间啃下来的一个点。