红黑树源码这个东西我这些年前前后后读了好几遍每次都有新收获。第一次翻开 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。这个函数代码很长我强烈建议你配合注释读原文。它的核心思路是把“被删节点是黑色”造成的问题抽象成当前子树少了一个黑色节点我们需要通过旋转和变色让其他路径“匀”一个黑色节点过来。我把四种情况总结成一张速查表场景兄弟节点颜色兄弟的子节点情况处理动作情况1红色任意旋转把兄弟变成黑色转化成情况2/3/4情况2黑色两个都是黑色兄弟染红问题向上冒泡一层情况3黑色左子红、右子黑右旋兄弟子树把红色节点转到右侧情况4黑色右子红左旋兄弟上位完成收尾这个表看起来简单实际写代码时每一步都要仔细更新父子关系。内核源码里的写法是先把兄弟节点取出来根据兄弟和侄子们的颜色分支出处理最后通过 __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 的四种情况会有一种豁然开朗的感觉。红黑树源码这份功课早晚要补趁早补完后面看任何平衡树相关的代码都会轻松许多。