企业官网建设流程全解析

红黑树源码这个东西，我这些年前前后后读了好几遍，每次都有新收获。第一次翻开 Linux 内核的 lib/rbtree.c 时，说实话看得很吃力，满屏的 __rb_parent_color、____rb_erase_color，光看名字就觉得头大。但当我真正把插入、删除、旋转、变色这条线捋顺之后，再去翻 GCC 标准库里那份几百行的 stl_tree.h，发现原来 STL 里 map、set 的底层 rb_tree 源码就是同一套思想换了件衣裳。

这篇文章我不打算讲什么高深理论，就把 rb_tree 源码怎么读、内核版本和 STL 版本各自的门道、以及怎么把内核那份 rbtree 搬到自己的工程里使用，全部摊开讲清楚。适合三类人看：一是准备面试、需要手撕红黑树的同学；二是做内核驱动或者嵌入式开发，想在工程里管理大量有序节点的朋友；三是纯粹想提升源码阅读功力的开发者。读完你会发现，红黑树没有传说中那么可怕，真正牛的其实是工程实现里那些看似不起眼的细节。

1. 为什么 rb_tree 源码值得一读再读

1.1 红黑树在真实世界的藏身之处

很多人对红黑树的印象停留在《算法导论》第13章，觉得它只是一个考试重点、面试考点。但实际上，红黑树是现代软件系统里最常用的平衡树结构，藏得比你想象中深得多。

先说最常见的：C++ 的 std::map、std::set、std::multimap、std::multiset，在 GCC 的 libstdc++ 里底层就是 _Rb_tree。你用 map 存键值对的时候，每一次插入、删除、查找，背后都在和红黑树的旋转函数打交道。再看 Linux 内核，CFS 调度器用来管理可运行进程的就绪队列，用的是红黑树；虚拟内存管理里，进程的 VMA（虚拟内存区域）是以红黑树组织的；高精度定时器、epoll 的事件管理，也都有红黑树的身影。CFS 调度器每次要选出 vruntime 最小的进程，实际上就是红黑树的“最左节点”查找，时间复杂度 O(log n)。

再看中间件领域，Redis 的有序集合 zset，当成员数量超过阈值并且元素是 skiplist 编码时，底层有一层 dict + skiplist；但在某些实现和相关的有序结构里，红黑树同样大量出现。Nginx 的定时器管理，早期版本用的就是红黑树，通过 key 值直接定位到最近的超时事件。可以说，从数据库的索引思想到网络框架的事件管理，红黑树的应用几乎无处不在。

所以读 rb_tree 源码，不只是为了应付面试，而是你在真实工程里迟早要面对的东西。当你需要在几十万个节点里快速插入、删除、查找有序数据时，手写链表性能不够，用 AVL 树旋转太频繁，红黑树就是那个性能和实现复杂度平衡得最好的选择。

1.2 两个经典源码流派：内核版与 STL 版

市面上能读到的 rb_tree 源码，大致分两个流派。

第一个流派是 Linux 内核的实现，文件位置在 lib/rbtree.c 和 include/linux/rbtree.h。这套实现的风格极其克制，为了节省内存，把节点的父指针和颜色塞进了同一个无符号长整型字段里，旋转和删除修复函数用循环而不是递归，大量使用宏和内联函数。内核里所有红黑树节点都是嵌入到自定义结构体中的，通过 container_of 宏找到宿主结构，这种“侵入式”设计使得节点管理非常高效，不需要额外的内存池。

第二个流派是 GCC libstdc++ 里的 _Rb_tree，也就是 stl_tree.h。这套实现更贴近教材上的经典伪代码，颜色用 _Rb_tree_color 枚举，节点有独立的内存分配策略，模板化程度很高。如果你读的是《STL源码剖析》这本书里的 rb_tree，那对应的大概是 SGI STL 的早期实现，结构上更清晰一些，适合入门读。

我的建议是，入门先读教材理解算法，进阶读内核源码学工程技巧，最后再回头啃 STL 的模板实现去理解 C++ 泛型设计。两条路线都能让你对 rb_tree 源码的理解上一个台阶。

2. 动手读源码前必须吃透的底层原理

2.1 五条不变量与“近似平衡”的精髓

红黑树之所以叫红黑树，是因为每个节点多了一个颜色属性，非红即黑。它通过五条不变量来维持树的平衡：

• 节点只有红、黑两种颜色。
• 根节点是黑色的。
• 叶子节点（NIL 空节点）是黑色的。
• 红色节点的两个子节点必须是黑色的，不能出现连续的红色节点。
• 从任意一个节点出发，到它所有叶子节点的路径上，黑色节点的数量必须相同。

第五条也就是常说的“黑高相等”。为什么这五条规则就能让树保持相对平衡？这里有个经典的推导结论：在一棵红黑树中，最长路径的长度不会超过最短路径的两倍。最短路径自然就是全黑路径，而最长路径由于不能有连续红色节点，只能是“黑-红-黑-红”交替，所以红色节点的数量被限制住了。这个“最长不超过最短两倍”的松散平衡，就是红黑树降低旋转频率的关键。

作为对比，AVL 树严格要求左右子树高度差不超过 1，这种高度平衡在查找时确实更优，但代价是插入删除时的旋转次数明显更多。红黑树牺牲了一点点查找性能（毕竟是 O(log n) 级别的松平衡，常数差别不大），换来了插入删除时的重平衡操作显著减少。这就是为什么工程上 map、set、内核调度器普遍选择红黑树而不是 AVL 树的核心原因。

2.2 旋转、变色与插入删除的整体流程

读源码之前，脑子里必须先把旋转和变色这招学会。旋转是红黑树调整结构的基本单位，分左旋和右旋两种。左旋就是某个节点下沉为左子节点，它的右孩子上升为父节点；右旋方向相反。旋转过程会改变树的结构，但不会改变中序遍历的顺序，所以它不破坏二叉搜索树的有序性。这正是旋转能用来调整平衡而不打乱数据顺序的根本原因。

插入的整体流程是这样的：先按照普通二叉搜索树的规则，把新节点放到合适的位置，然后把新节点染成红色，再沿着父节点向上修复。为什么要染红？因为插入一个红色节点，只可能破坏“不能有连续红色节点”这一条规则，而不会破坏“黑高相等”。如果插入的是黑色节点，那么从根到这条新路径上的黑色节点数就会比别的路径多 1，整棵子树的黑高全部不匹配，修复起来极其麻烦。所以“默认染红”是工程上的最优选择。

插入修复分几种情况：如果父节点是黑色，直接结束，什么也不用做；如果父节点是红色，就得看叔父节点的颜色。叔父是红色就做颜色翻转，父和叔变黑、祖父变红，然后把祖父当成新节点继续向上检查；叔父是黑色就通过旋转来调整，分成左左、左右、右右、右左四种情况，本质是先旋转成“一条线”，再旋转加变色。理解了这四种情况，你会发现它们只是对称变换，记住一种就行。

删除的流程要复杂一个量级。因为删掉一个节点之后，如果它原本是黑色，那么某些路径上的黑高就会少 1，出现“双黑”问题。删除修复的核心就是处理这个“双黑”节点。如果兄弟节点是红色，先通过旋转把兄弟变黑；如果兄弟是黑色且它的两个子节点都是黑色，就把兄弟染红，让双黑向上冒泡；如果兄弟是黑色且它的右子节点是红色，就可以直接旋转加变色收尾。这些情况我在后面的源码拆解里会详细展开。

2.3 为什么新节点必须染红：一个容易被忽略的底层逻辑

我见过不少人读红黑树源码，读到 rb_insert_color 里有个颜色翻转的分支时，就很困惑：为什么新节点一开始要是红色的？干脆让它是黑色的，不是少一次修复吗？

这里面的关键在“黑高”这个概念上。红黑树的所有叶子节点是 NIL 空节点，它们都是黑色。当你插入一个黑色节点时，从根到这条新路径上的黑色节点数量，会比同一棵子树下其他路径多出一个，这就直接破坏了第五条不变量。而第五条不变量的破坏是“结构性”的，它会波及到所有包含这条路径的祖先节点，修复时往往需要一路上溯到根节点，代价极大。

相比之下，插入红色节点，影响的只是局部是否存在连续红节点，这是可以沿着祖先链一路检查、通过变色和旋转快速修复的。简单说，红色节点的问题是“点状”的，黑色节点的问题是“面状”的。内核源码里那几行颜色判断，就是建立在这个取舍之上。

3. 内核 rbtree 源码里的工程智慧

3.1 struct rb_node 的低 bit 颜色存储

打开 include/linux/rbtree.h，第一眼看到的就是这个结构体：

struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long))));

很多初读内核源码的人会愣住：父指针和颜色怎么塞在一个字段里？答案就在对齐上。在 64 位系统里，malloc 或 kmalloc 返回的地址通常是 16 字节甚至是更严格的对齐，这意味着rb_node 指针的低 4 位二进制必然是 0。既然最低一位本来就没人用，那就拿它来存颜色：约定最低位为 0 表示红色，最低位为 1 表示黑色。

这样设计的好处是实实在在的。一个 rb_node 在 64 位系统下只占 24 字节（两个指针加一个 unsigned long），如果你单独加一个 int 字段存颜色，整个结构体可能因为填充直接变成 32 字节，内存开销多出三分之一。内核里可能有几十万个 rb_node 节点共存，这个节省非常可观。

对应的辅助内联函数也很有趣。读父节点指针时，要把最低位遮掉：

#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))

注意这里遮掉了低 2 位而不是只遮 1 位。早期内核只用了 1 位存颜色，后来为了给 rb_augmented（增强红黑树）留空间，统一遮到 3。这个宏还专门加了 READ_ONCE/WRITE_ONCE 之类的内存屏障处理，在并发场景下保证读到的一致值，这套细节在用户态实现里往往被简化掉。

3.2 rb_insert_color 的插入修复源码拆解

内核里插入新节点，第一步是主动建立链接关系，把新节点接进树里，然后调用 rb_insert_color 修复颜色。rb_link_node 做的事情很简单：

static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) { node->__rb_parent_color = (unsigned long)parent; node->rb_left = node->rb_right = NULL; *rb_link = node; }

注意这里新节点的 __rb_parent_color 就是父节点指针本身，颜色位是 0，也就是红色。这正印证了上面说的“默认染红”。

接下来看插入修复的主逻辑，我用伪代码把内核的核心流程还原一下：

void rb_insert_color(struct rb_node *node, struct rb_root *root) { struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; while (parent) { // 父节点是黑色，整棵树合法，直接返回 if (!rb_is_red(parent)) return; // 走到这里，父节点是红色，需要处理连续红节点 gparent = rb_red_parent(parent); if (parent == gparent->rb_left) { tmp = gparent->rb_right; if (tmp && rb_is_red(tmp)) { // 叔父是红色，变色上溯 rb_set_parent_color(tmp, gparent, RB_BLACK); rb_set_parent_color(parent, gparent, RB_BLACK); node = gparent; continue; } // 叔父是黑色，先调整方向再旋转 if (parent->rb_right == node) { // 左右情况，先左旋 tmp = parent->rb_right; parent->rb_right = node->rb_left; ... // 交换 parent 和 node 的角色 } // 左左情况，右旋 + 变色 rb_set_parent_color(parent, gparent, RB_BLACK); rb_set_parent_color(gparent, parent, RB_RED); __rb_rotate_left(gparent, root); return; } else { // 对称处理右边 } } // 根节点强制染黑 WRITE_ONCE(root->rb_node->__rb_parent_color, RB_BLACK); }

这段代码最值得玩味的是那个 while 循环的出口条件。循环里如果一直遇到叔父红色，就会一路把祖父染红、自己上溯到祖父节点，继续上一层的判断。直到某次父节点是黑色，循环退出；或者一路冲上根节点，最后一句强制把根染黑。根节点为什么必须是黑的？因为如果根是红的，它的两个子节点如果是红的，就会形成连续红节点；而且根节点染黑不改变任何路径的黑高，所以最后一道保险就是无条件让根变黑。

你可能注意到我这里刻意省略了旋转的部分细节，因为旋转的具体代码比较长。内核把旋转封装成了 __rb_rotate_left 和 __rb_rotate_right 两个函数，它们的共同特点是：传入 root 指针，因为旋转可能会导致新的子树根节点，需要把新的根节点挂回全局根节点。这也是后来很多人移植内核 rbtree 时最容易出错的地方：忘记更新 root 指针。

3.3 ____rb_erase_color 删除修复源码拆解

删除在 rb_erase 里分成两部分。第一部分是找后继节点、把值搬过去、摘除物理节点；第二部分是如果摘除的节点是黑色，就调用 ____rb_erase_color 修复黑高。

找后继的逻辑在 rb_next，它的实现非常精妙：

struct rb_node *rb_next(const struct rb_node *node) { if (RB_EMPTY_NODE(node)) return NULL; if (node->rb_right) { // 有右子树，找右子树的最左节点 node = node->rb_right; while (node->rb_left) node = node->rb_left; return (struct rb_node *)node; } // 没有右子树，向上找第一个“从左子树走上来的祖先” while (rb_parent(node) && node == rb_parent(node)->rb_right) node = rb_parent(node); return rb_parent(node); }

这里有一个内核特有的宏 RB_EMPTY_NODE，它判断的是 node 的 __rb_parent_color 是否等于 node 自身。如果节点被移除后，内核会把它的父指针指向自己，形成一种特殊标记，表示这个节点不再属于任何树。这个设计在用户态很少见到，但本质上是一种廉价的状态标记。

删除修复的核心是 ____rb_erase_color。这个函数代码很长，我强烈建议你配合注释读原文。它的核心思路是：把“被删节点是黑色”造成的问题，抽象成当前子树少了一个黑色节点，我们需要通过旋转和变色让其他路径“匀”一个黑色节点过来。

我把四种情况总结成一张速查表：

这个表看起来简单，实际写代码时每一步都要仔细更新父子关系。内核源码里的写法是先把兄弟节点取出来，根据兄弟和侄子们的颜色分支出处理，最后通过 __rb_rotate_set_parents 这个函数一段一段地调整。真正的工程代码里全是位运算和内联函数，读的时候要有耐心。

3.4 rb_augmented 与区间管理

新版内核 rbtree 还有一个增强特性：rb_augmented。它允许每个节点额外维护一些聚合信息，比如子树里的最大范围、最小值等。以虚拟内存管理为例，内核通过红黑树维护进程的 VMA 区域，每个节点存一个 [start, end] 区间，而聚合信息可以让内核在查找“包含某地址的 VMA”时，快速跳过整棵不可能命中的子树，优化查找效率。

增强 rbtree 的使用方式是：在调用 rb_insert_augmented 和 rb_erase_augmented 时，传入一个 rb_augment_callbacks 结构体，里面包含 rotate 和 propagate 两个回调函数。rotate 负责在旋转时更新子树聚合信息，propagate 负责在节点上溯时把新的聚合值传递给祖先。这套机制让普通红黑树变成了一种“可扩展平衡区间树”，思想很值得借鉴。

4. 徒手实现一个迷你 rb_tree 源码

4.1 数据结构定义

读源码是一回事，真正自己写一遍又是另一回事。我在工程里用过内核版 rbtree，也在面试前手写过迷你版。下面给出一个可直接运行的迷你 C 实现核心，方便你对照源码理解。

typedef enum { RB_RED = 0, RB_BLACK = 1 } rb_color; typedef struct rb_node { struct rb_node *parent; struct rb_node *left; struct rb_node *right; rb_color color; int key; // 以便验证，实际工程中通常是结构体内的数据 } rb_node; typedef struct { rb_node *root; } rb_tree;

这个定义简化了内核的低 bit 颜色存储，直接用一个 enum 字段，逻辑更清晰。如果你想进阶挑战，完全可以按照内核的方式把 parent 和 color 合并成一个 unsigned long，那样内存效率更高也更贴近真实工程。

4.2 左旋右旋与插入实现

左旋操作的要点是：拿到当前节点的右孩子，让右孩子上位，当前节点成为右孩子的左孩子，同时处理右孩子的左子树挂到当前节点的右孩子位置。写成代码：

static void rb_rotate_left(rb_tree *tree, rb_node *node) { rb_node *r = node->right; node->right = r->left; if (r->left) r->left->parent = node; r->parent = node->parent; if (node->parent == NULL) tree->root = r; else if (node == node->parent->left) node->parent->left = r; else node->parent->right = r; r->left = node; node->parent = r; }

右旋完全对称，不再赘述。插入时先按普通 BST 规则找位置，然后执行修复函数。修复函数对照内核版可以精简成这样：

static void rb_insert_fixup(rb_tree *tree, rb_node *node) { while (node != tree->root && node->parent->color == RB_RED) { if (node->parent == node->parent->parent->left) { rb_node *uncle = node->parent->parent->right; if (uncle && uncle->color == RB_RED) { node->parent->color = RB_BLACK; uncle->color = RB_BLACK; node->parent->parent->color = RB_RED; node = node->parent->parent; } else { if (node == node->parent->right) { node = node->parent; rb_rotate_left(tree, node); } node->parent->color = RB_BLACK; node->parent->parent->color = RB_RED; rb_rotate_right(tree, node->parent->parent); } } else { // 对称处理 } } tree->root->color = RB_BLACK; }

这里最关键的细节是：判断叔父颜色时，如果叔父是 NULL，也当作黑色处理。很多初写者在这里只判断非空就访问 color，结果空指针解引用，实际 NIL 节点是黑色，NULL 就是黑。

4.3 删除与修复

删除修复的迷你版实现，我建议直接参考内核的 ____rb_erase_color 改写。核心是维护一个节点 x，表示“双黑”节点所在位置。这里给出修复主循环的骨架：

static void rb_delete_fixup(rb_tree *tree, rb_node *node, rb_node *parent) { while (node != tree->root && (node == NULL || node->color == RB_BLACK)) { if (node == parent->left) { rb_node *sibling = parent->right; if (sibling && sibling->color == RB_RED) { sibling->color = RB_BLACK; parent->color = RB_RED; rb_rotate_left(tree, parent); sibling = parent->right; } if ((sibling->left == NULL || sibling->left->color == RB_BLACK) && (sibling->right == NULL || sibling->right->color == RB_BLACK)) { sibling->color = RB_RED; node = parent; parent = parent->parent; } else { if (sibling->right == NULL || sibling->right->color == RB_BLACK) { sibling->left->color = RB_BLACK; sibling->color = RB_RED; rb_rotate_right(tree, sibling); sibling = parent->right; } sibling->color = parent->color; parent->color = RB_BLACK; sibling->right->color = RB_BLACK; rb_rotate_left(tree, parent); node = tree->root; break; } } else { // 对称处理 } } if (node) node->color = RB_BLACK; }

删除修复是最容易写错的部分，因为情况分支多，且每一轮循环后 node 和 parent 的指向都会变化。我的经验是，写完之后一定要配合随机插入删除的验证程序跑一轮 fuzz，光靠肉眼检查基本不可能保证正确。

4.4 中序遍历验证正确性

写完插入删除，第一件事不是看平衡，而是验证中序遍历是否严格有序。中序遍历可以这样写：

static void rb_inorder(rb_node *node, void (*visit)(rb_node *)) { if (!node) return; rb_inorder(node->left, visit); visit(node); rb_inorder(node->right, visit); }

如果遍历输出的 key 序列是递增的，说明 BST 结构没有被破坏。紧接着再检查红黑性质：根节点是黑、没有连续红节点、每条路径黑高相等。这三个检查加在一起，基本能保证实现没有结构性问题。

5. 把内核 rbtree 搬到自己的工程里

5.1 移植步骤与注意事项

内核的 rbtree 实现质量很高，很多人想直接在用户态或者嵌入式工程里用。直接复制 rbtree.c 和 rbtree.h 肯定编译不过，因为里面充斥着内核特有的宏。我踩过不少坑，整理一下移植步骤：

第一步，把内核头文件里依赖的宏统一替换掉。常见的有 BUG_ON 替换成 assert、WARN_ON 替换成打印、READ_ONCE/WRITE_ONCE 直接去掉或者换成普通赋值、unlikely/likely 直接删掉。

第二步，处理 struct rb_node 的对齐属性。内核里用attribute((aligned(sizeof(long))))，用户态也要保留，因为低 bit 颜色方案依赖指针对齐。实际使用中 malloc 返回的地址在对齐上没问题，但如果你的节点是从一个 char 数组缓冲区偏移出来的，就要小心偏移量是否对齐。

第三步，把 rb_root 初始化为 RB_ROOT，就像初始化任何数据结构一样。没有这句话，根节点指向随机地址，插入第一个节点可能直接崩溃。

第四步，确保你的宿主结构体里 rb_node 成员是第一个或者偏移足够对齐。推荐把 rb_node 放在结构体第一个字段，这样 from 指针就是 rb_node 本身，省去 container_of 的偏移计算。

5.2 用户态验证与随机 fuzz

移植完成以后，写一个验证程序。我一般这么干：随机插入一百万个整数，插入过程中每十万次中序遍历一次，检查是否有序；然后随机删除一半节点，删除过程再检查黑高和连续红约束；最后整棵树删空，确保没有内存泄漏。

这个 fuzz 程序看起来不起眼，但它是检验红黑树实现是否正确的试金石。我自己手写迷你版的时候，就是在随机删除那一步暴露出问题：删除修复里情况3转情况4时，忘了更新兄弟节点指针，导致后续判断用了旧节点，树结构直接错乱。这种bug靠读代码极难发现，靠 fuzz 一跑就现形。

6. 常见问题与排查技巧实录

6.1 三个高频问题定位思路

移植和使用 rb_tree 过程中，下面这些问题出现频率最高：

问题一：插入后根节点变了，树变得混乱。多半是更新根节点失败。旋转函数里要判断 node->parent 是否为 NULL，如果是，则应该把新的子树根节点赋给 tree->root。写代码时最容易漏掉这个判断，或者判断写反了。

问题二：低 bit 颜色方案里，节点颜色读取异常。检查一下你取的节点地址是否真的对齐到 4 字节。如果自己写内存池或者对象池，分配的地址可能不是 page 对齐的，这时最低位不是可靠的。稳妥做法是页面级对齐，或者干脆用独立的 color 字段。

问题三：STL 里 map 删除了一个迭代器，后续遍历崩溃。这不是红黑树实现问题，是迭代器失效。红黑树删除一个节点后，只有指向被删节点的迭代器失效，其他迭代器不失效——这恰恰是 STL 选择红黑树而不是数组或链表作为底层结构的优势之一。但如果你在遍历过程中删除了当前迭代器，应该先自增保存下一个迭代器再删除。

6.2 调试红黑树的三板斧

最后分享我调试红黑树的三板斧。第一板斧是开一个 debug 开关，每次插入删除后校验整棵树的红黑性质；第二板斧是随机 fuzz，同时记录每次操作的 key，方便崩溃时用同样的随机种子复现；第三板斧是写一个 dump 函数，输出整棵树的括号表示或者缩进结构，用眼睛直观地看树形。

尤其是 dump 这个工具，看着树的结构一点点调整，很快就能建立直觉。比如插入触发叔父红变色时，你会发现中间几层同时变色；走旋转分支时，子树根节点会整体迁移。这种直觉一旦建立，再回头读内核源码，理解速度会有质变。

另外一个常见的面试加分项是，思考红黑树和 B+ 树、跳表的取舍。我会在面试中这样回答：内存中数据量中等、插入删除频繁、需要稳定迭代器时选红黑树；磁盘存储、范围查询、块式读写时选 B+ 树；并发读写频繁且想要简单的概率平衡时选跳表。这个回答比单纯背性质有用得多，因为你把数据结构和应用场景挂上了钩。

我对红黑树源码最深的体会是：读十遍都不如自己动手写一遍有用。我建议大家拿到一份源码，不管是我上面这份迷你版还是内核原版，先自己在本地跑通插入和查找，再一步一步加删除和修复。写删除修复时卡住很正常，卡住说明你对“双黑”这个概念还没有真正吃透，这时候回看 ____rb_erase_color 的四种情况，会有一种豁然开朗的感觉。红黑树源码这份功课，早晚要补，趁早补完，后面看任何平衡树相关的代码都会轻松许多。