红黑树、C语言、200行代码实现这三个词放在一起基本就是学数据结构的人绕不过去的一道坎。工作里用到红黑树的地方实在太多Linux 内核定时器、Nginx、Redis再到 C 的 std::map 和 Java 的 TreeMap底层不是红黑树就是它的变体。我最早看《算法导论》第十三章时也被一堆 case 搞得晕头转向后来发现只要抓住它到底在约束什么代码写起来并没有想象中那么难。这篇文章我会把红黑树逐条拆开再用 C 语言从头实现一遍插入、删除、修复逻辑都附上代码和修改理由代码我自己跑过随机测试可以直接抄走参考。适合正在啃数据结构课程、准备算法面试或者想知道 map 底层为什么长这样的朋友。1. 红黑树五条性质到底在约束什么1.1 红黑树要解决的问题先说说平衡这件事普通的二叉查找树在随机数据下表现很好插入、查找、删除平均都是 O(log n)。但最怕一种情况数据按顺序进来比如 1、2、3、4…… 这样插下去树会一路往右偏变成一条链表。这时候查找一个节点要遍历全部元素复杂度直接变成 O(n)和数组遍历没什么区别。AVL 树想了一个办法严格限制左右子树高度差不超过 1不行就旋转。这种策略把树控得很平任何操作都是严格的 O(log n)。但代价是插入和删除后需要频繁旋转代价不小。很多写了很多次业务代码的工程师都有这种感觉读多写少的场景用 AVL 很好但写一多就有点吃力。红黑树选择了一条中间路线。它不要求左右子树高度一样而是用“红黑”这两种颜色加上几条简单的性质把树的高度控制在近似平衡。最长路径不会超过最短路径的两倍所以查找、插入、删除都能保持在 O(log n)。关键是它的旋转次数比 AVL 少适合频繁插入删除的场景。这就是为什么它成了工程界的“事实标准”。1.2 五条性质拆开来看其实就三件事红黑树的五条性质大家都背过但光靠背不够。我把它们拆成三组节点只有红黑两色根必须是黑的所有叶子节点也就是 NIL 哨兵节点都是黑的。这是“底色”保证树的起点和终点是稳定的。红色节点的两个子节点必须是黑色换句话说不能出现两个红色节点连着。这是对“红色”的约束防止树里出现长时间连续的节点链。从任何一个节点出发到它所有叶子节点的路径上黑色节点数量必须相同。这就是红黑树最核心的“黑高平衡”。用一句大白话理解黑色数量是基础工资红色算是加班费。红色不允许连续出现所以一条路径上最多是“黑红黑红”交替。既然每条路径的黑节点数一样那最长路径最多就是最短路径的两倍。1.3 红黑树的高度为什么一定是 O(log n)假设一棵红黑树的根节点到叶子的黑高是 h那么任意一条从根到叶子的路径长度最小是 h也就是全是黑节点的情况最大是 2h也就是黑红交替的情况。这样一棵包含 n 个节点的树它的高度最多也就是 2h而 h 本身是 O(log n) 的量级所以整棵树的高度是 O(log n)。这里有个容易被忽视的细节黑高这个概念不是算节点颜色的个数而是算到叶子路径上的黑色节点数NIL 哨兵也得算。很多人写红黑树代码出 bug就是因为验证黑高的时候没有把 NIL 算进去。2. 先把地基打好节点、哨兵和旋转2.1 为什么用哨兵节点而不是 NULL初学红黑树时我习惯用 NULL 表示空节点结果写修复逻辑时处处碰壁。你想如果某个节点的左孩子是 NULL那访问x-left-color就直接段错误。为了处理这种边界你不得不在代码里塞满if (x-left ! NULL)的判断逻辑瞬间就复杂了。工程里更干净的做法是搞一个全局哨兵节点 nil所有空指针都用它来表示。这个节点颜色是黑的它的 left、right、parent 都指向自己。这样任何节点都有“子节点”只是这个子节点是同一个哨兵而已。代码里不需要再判空行数能省下不少也是标题说“200 行实现”的技术前提。2.2 节点结构和初始化这是最基础的节点定义key 存值color 存颜色left/right/parent 三个指针指向真实节点或哨兵。typedef struct rb_node { int key; char color; // R 或 B struct rb_node *left, *right, *parent; } rb_node; static rb_node *nil; void rbtree_init(void) { nil (rb_node *)malloc(sizeof(rb_node)); nil-color B; nil-left nil-right nil-parent nil; }颜色用 char 存在容器实现里没问题但正式代码建议改成枚举类型typedef enum { RED, BLACK } color_t;可读性更好编译器也能帮忙查错。我这里为了贴近基础教学先用 char。2.3 左旋和右旋代码顺序不能乱旋转是红黑树所有调整的基础操作目的只有一个在不破坏二叉搜索树性质的前提下改变局部父子关系。左旋就是让某个节点的右孩子“升上来”右旋就是让左孩子“升上来”。拿左旋举例结构变化是这样的x y \ / \ y x c / \ \ b c b逻辑拆开就是三件事把 y 的左孩子 b 过继给 x把 y 的父指针指向 x 原来的父节点再把 x 变成 y 的左孩子。顺序错了树就断链了。void left_rotate(rb_node **root, rb_node *x) { rb_node *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 对调再把 x 和 y 的角色反过来。建议在一张纸上把节点画出来然后照着代码一步一步走会比光看代码理解快很多。3. 插入新增节点为什么默认染红3.1 先按 BST 规则挂上再修复颜色红黑树本质上还是棵二叉搜索树。插入第一步和普通 BST 没区别找到合适的空位把新节点挂上去。不同的是新节点的颜色一上来必须染成红色。为什么是红色因为如果染成黑色会立刻破坏“每条路径黑高相同”这条性质修复起来非常麻烦。而染成红色只可能破坏“红节点的子节点必须是黑色”这一条通过局部调整就能修回来。两害相权取其轻所以新节点默认红色。插入的核心还是寻找插入位置void rbtree_insert(rb_node **root, int key) { rb_node *z (rb_node *)malloc(sizeof(rb_node)); z-key key; z-left z-right z-parent nil; z-color R; rb_node *y nil; rb_node *x *root; while (x ! nil) { y x; x (key x-key) ? x-left : x-right; } z-parent y; if (y nil) { *root z; } else if (key y-key) { y-left z; } else { y-right z; } insert_fixup(root, z); }注意这里重复 key 的处理是插到右子树。严格来说红黑树不允许重复 key 会更严谨但为了示例简单我默认所有 key 唯一。实际工程里得根据业务场景决定是覆盖还是拒绝。3.2 插入修复的三种情况插入红色节点后只有两种情况没事要么新节点是根那直接染黑要么父节点是黑色那没有任何破坏。一旦父节点是红色就出现连续红节点了需要进入修复循环。修复时核心操作取决于“叔叔节点”的颜色。这里我以父节点是爷爷左孩子为例情况一叔叔是红色。此时把父节点和叔叔节点都染黑爷爷节点染红然后让 z 跳到爷爷的位置继续处理。这个操作不改变路径上的黑节点总数只是把问题往上推了两层。情况二叔叔是黑色且 z 是右孩子。这时候先对父节点做一次左旋把形状变成情况三的样子。这个步骤不染色只是调整结构。情况三叔叔是黑色且 z 是左孩子。把父节点染黑爷爷染红再对爷爷做一次右旋直接结束修复。对称情况就是把“左”和“右”全部反过来代码写的时候最容易漏的就是这一半。你在移植代码时一定要先在纸上画出对称的示意图再对照着写。插入完整修复代码如下void insert_fixup(rb_node **root, rb_node *z) { while (z-parent-color R) { if (z-parent z-parent-parent-left) { rb_node *y z-parent-parent-right; if (y-color R) { z-parent-color B; y-color B; z-parent-parent-color R; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; left_rotate(root, z); } z-parent-color B; z-parent-parent-color R; right_rotate(root, z-parent-parent); } } else { rb_node *y z-parent-parent-left; if (y-color R) { z-parent-color B; y-color B; z-parent-parent-color R; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; right_rotate(root, z); } z-parent-color B; z-parent-parent-color R; left_rotate(root, z-parent-parent); } } } (*root)-color B; }循环结束后强制把根节点染黑这一步很重要。如果顺着情况一一直往上升有可能把根节点染成红色所以最后必须强制清零。4. 删除双黑修正红黑树最难的关卡4.1 删除的基本套路找后继、替换、做标记删除比插入难很多。插入时新节点红色破坏的是“不连续红”这条性质局部调整就行。删除可能直接删除一个黑色节点导致某条路径上少了一个黑节点这就是黑高失衡。黑高失衡是全局性问题必须通过复杂的修复循环来解决。CLRS 里的做法是引入“双黑”概念。假设被删节点原本是黑色那顶替它的节点 x 就背上了“双重黑色”的债。修复的过程就是不断把双黑上移直到遇到红色节点或者根节点把债还清。删除节点分三种情况要删的节点没有左孩子或没有右孩子直接让孩子顶替它记录顶替节点的颜色。要删的节点有两个孩子这时要找它的后继节点 y右子树最小的节点来代替它y 再把原来的位置让出来。操作完成后y 的颜色保持和 z 原来一样所以实际被删掉颜色的是 y 原来的颜色。只有被删节点或替代节点的原始颜色是黑色才需要进入修复流程。先写一个替换节点的辅助函数。它只是把 u 的位置替换成 v不管 v 本身是什么颜色void rb_transplant(rb_node **root, rb_node *u, rb_node *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; }4.2 删除主逻辑下面这段代码把三种情况都处理了注释里写清楚了每个分支的意图void rbtree_delete(rb_node **root, int key) { rb_node *z rbtree_find(*root, key); if (z nil) return; rb_node *y z; rb_node *x; char y_original_color y-color; if (z-left nil) { x z-right; rb_transplant(root, z, z-right); } else if (z-right nil) { x z-left; rb_transplant(root, z, z-left); } else { y z-right; while (y-left ! nil) y y-left; y_original_color y-color; x y-right; if (y-parent z) { x-parent y; } else { rb_transplant(root, y, y-right); y-right z-right; y-right-parent y; } rb_transplant(root, z, y); y-left z-left; y-left-parent y; y-color z-color; } free(z); if (y_original_color B) { delete_fixup(root, x); } }这里有个细节很容易写错当 z 有两个孩子时y 被摘下来顶替 z。如果 y 不是 z 的直接右孩子那 y 原来的位置还需要用 y-right 去填补。如果 y 是 z 的直接右孩子则不需要额外处理 y-right因为 y 本身就待在正确的位置上。很多人就是在这里漏了一个分支导致树结构错乱。4.3 双黑修复的四种情况删除修复的循环里一句话总结就是把双黑节点往树的更高层推推不上去就靠旋转和染色解决。以 x 是父节点的左孩子为例四种情况如下兄弟节点 w 是红色说明父节点一定是黑色。把 w 染黑父染红对父左旋此时新的兄弟节点是原兄弟的黑色子节点问题规模没变但转入了下面几种情况。兄弟节点 w 是黑色且 w 的两个子节点都是黑色直接把 w 染红这样左子树和右子树的黑高都减一双黑上移给父节点。兄弟节点 w 是黑色w 的左子节点是红色、右子节点是黑色把 w 的左子节点染黑w 染红对 w 右旋。这一步把“远侄子为黑”的形状转成“远侄子为红”的形状。兄弟节点 w 是黑色w 的右子节点是红色这是最终情况。把 w 染成父节点的颜色父染黑w 的右子染黑对父左旋然后把 x 指向根节点循环结束。对称情况就是全部把 left 和 right 对调。这四种情况必须画图理解靠背代码很容易背错。完整修复代码如下void delete_fixup(rb_node **root, rb_node *x) { while (x ! *root x-color B) { if (x x-parent-left) { rb_node *w x-parent-right; if (w-color R) { w-color B; x-parent-color R; left_rotate(root, x-parent); w x-parent-right; } if (w-left-color B w-right-color B) { w-color R; x x-parent; } else { if (w-right-color B) { w-left-color B; w-color R; right_rotate(root, w); w x-parent-right; } w-color x-parent-color; x-parent-color B; w-right-color B; left_rotate(root, x-parent); x *root; } } else { rb_node *w x-parent-left; if (w-color R) { w-color B; x-parent-color R; right_rotate(root, x-parent); w x-parent-left; } if (w-right-color B w-left-color B) { w-color R; x x-parent; } else { if (w-left-color B) { w-right-color B; w-color R; left_rotate(root, w); w x-parent-left; } w-color x-parent-color; x-parent-color B; w-left-color B; right_rotate(root, x-parent); x *root; } } } x-color B; }5. 完整单文件 C 源码200 行左右的实现5.1 完整代码可以直接编译运行前面几节代码是打散的这节我把它们拼成一个完整的单文件。代码里包含了初始化、插入、删除、查找、打印和一个简单的红黑性质校验函数。注释里我尽量保留了关键点。#include stdio.h #include stdlib.h typedef struct rb_node { int key; char color; // R 或 B struct rb_node *left, *right, *parent; } rb_node; static rb_node *nil; void rbtree_init(void) { nil (rb_node *)malloc(sizeof(rb_node)); nil-color B; nil-left nil-right nil-parent nil; } rb_node *rbtree_find(rb_node *root, int key) { rb_node *x root; while (x ! nil) { if (key x-key) x x-left; else if (key x-key) x x-right; else return x; } return nil; } void left_rotate(rb_node **root, rb_node *x) { rb_node *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 right_rotate(rb_node **root, rb_node *y) { rb_node *x y-left; y-left x-right; if (x-right ! nil) x-right-parent y; x-parent y-parent; if (y-parent nil) { *root x; } else if (y y-parent-left) { y-parent-left x; } else { y-parent-right x; } x-right y; y-parent x; } void insert_fixup(rb_node **root, rb_node *z) { while (z-parent-color R) { if (z-parent z-parent-parent-left) { rb_node *y z-parent-parent-right; if (y-color R) { z-parent-color B; y-color B; z-parent-parent-color R; z z-parent-parent; } else { if (z z-parent-right) { z z-parent; left_rotate(root, z); } z-parent-color B; z-parent-parent-color R; right_rotate(root, z-parent-parent); } } else { rb_node *y z-parent-parent-left; if (y-color R) { z-parent-color B; y-color B; z-parent-parent-color R; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; right_rotate(root, z); } z-parent-color B; z-parent-parent-color R; left_rotate(root, z-parent-parent); } } } (*root)-color B; } void rbtree_insert(rb_node **root, int key) { rb_node *z (rb_node *)malloc(sizeof(rb_node)); z-key key; z-color R; z-left z-right z-parent nil; rb_node *y nil; rb_node *x *root; while (x ! nil) { y x; x (key x-key) ? x-left : x-right; } z-parent y; if (y nil) { *root z; } else if (key y-key) { y-left z; } else { y-right z; } insert_fixup(root, z); } void rb_transplant(rb_node **root, rb_node *u, rb_node *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 delete_fixup(rb_node **root, rb_node *x) { while (x ! *root x-color B) { if (x x-parent-left) { rb_node *w x-parent-right; if (w-color R) { w-color B; x-parent-color R; left_rotate(root, x-parent); w x-parent-right; } if (w-left-color B w-right-color B) { w-color R; x x-parent; } else { if (w-right-color B) { w-left-color B; w-color R; right_rotate(root, w); w x-parent-right; } w-color x-parent-color; x-parent-color B; w-right-color B; left_rotate(root, x-parent); x *root; } } else { rb_node *w x-parent-left; if (w-color R) { w-color B; x-parent-color R; right_rotate(root, x-parent); w x-parent-left; } if (w-right-color B w-left-color B) { w-color R; x x-parent; } else { if (w-left-color B) { w-right-color B; w-color R; left_rotate(root, w); w x-parent-left; } w-color x-parent-color; x-parent-color B; w-left-color B; right_rotate(root, x-parent); x *root; } } } x-color B; } void rbtree_delete(rb_node **root, int key) { rb_node *z rbtree_find(*root, key); if (z nil) return; rb_node *y z; rb_node *x; char y_original_color y-color; if (z-left nil) { x z-right; rb_transplant(root, z, z-right); } else if (z-right nil) { x z-left; rb_transplant(root, z, z-left); } else { y z-right; while (y-left ! nil) y y-left; y_original_color y-color; x y-right; if (y-parent z) { x-parent y; } else { rb_transplant(root, y, y-right); y-right z-right; y-right-parent y; } rb_transplant(root, z, y); y-left z-left; y-left-parent y; y-color z-color; } free(z); if (y_original_color B) { delete_fixup(root, x); } } void print_tree(rb_node *x, int depth) { if (x nil) return; print_tree(x-left, depth 1); printf(%*d%c\n, depth * 4, x-key, x-color); print_tree(x-right, depth 1); } int check_rb(rb_node *x, int *ok) { if (x nil) return 1; if (x-color R (x-left-color R || x-right-color R)) { *ok 0; } int lh check_rb(x-left, ok); int rh check_rb(x-right, ok); if (lh ! rh) { *ok 0; } return lh (x-color B); } int main(void) { rbtree_init(); rb_node *root nil; int a[] {7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13, 4, 15, 5}; for (int i 0; i (int)(sizeof(a) / sizeof(a[0])); i) { rbtree_insert(root, a[i]); } puts(---- before delete ----); print_tree(root, 0); rbtree_delete(root, 18); rbtree_delete(root, 7); puts(---- after delete 18,7 ----); print_tree(root, 0); int ok 1; check_rb(root, ok); puts(ok ? rb check OK : rb check FAIL); return 0; }5.2 为什么说 200 行够了细心的读者会发现这段代码算上打印、校验、main其实超过 200 行了。但如果把打印、校验、main 去掉只看红黑树的节点定义、旋转、插入、删除、修复核心逻辑确实在 200 行左右。能把代码压得这么短主要靠两个设计一是全局哨兵节点 nil省掉了几乎所有判空逻辑二是把旋转和插入/删除修复拆成独立函数代码可以复用。有些教材版本的代码动不动四五百行多半是把修复逻辑写进了插入和删除函数内部导致代码重复度高难以阅读。5.3 编译运行的环境提示这段代码是纯 C 写的没有依赖第三方库。Linux 或 macOS 下直接gcc rbtree.c -o rbtree ./rbtree就能跑。Windows 下用 VS Code 配好 MinGW 或 MSVC 环境也能直接编译。如果你用的编译器比较老遇到//注释或for (int i 0; ...)报错就加上-stdc99编译选项。这些都属于 C 语言环境配置的小问题与红黑树逻辑本身无关。6. 验证红黑树三个硬指标一个都不能少6.1 黑高一致、颜色不连续、中序有序手写红黑树最容易出现的问题是代码看起来是对的但树其实已经坏了。我在本地做随机测试时靠三个检查函数就能定位大多数问题颜色约束遍历所有节点如果某个红节点的子节点里有红色就说明性质被破坏。黑高一致从任意节点出发到叶子的黑色节点数必须一样。这是最敏感的检查只要旋转或染色出错黑高几乎一定对不上。中序有序红黑树首先得是二叉搜索树。中序遍历打印出来应该是升序否则说明旋转没把大小关系维护好。代码里的check_rb已经实现了前两个检查。中序遍历部分print_tree打印的是中序你看输出是不是升序就知道 BST 性质有没有被破坏。6.2 我的测试流程从 1 到 N 随机打乱我测试时不会只是插入一两个节点那样根本测不出问题。常用做法是生成一组从 1 到 N 的数字打乱顺序后依次插入再随机删除一部分每次操作后都跑一遍check_rb。比如插入 1 到 1000 的乱序序列再随机删除 500 个节点每一步都检查黑高和颜色。只要有一个环节漏写旋转或者染色逻辑检查立刻就能报出来。这套流程用脚本驱动比较省事但纯 C 也能写个循环做随机测试。6.3 一个小技巧打印树的时候把颜色带上调试红黑树时打印节点一定要把颜色一起打出来否则你很难判断染色逻辑是否正确。print_tree里用printf(%*d%c\n, depth * 4, x-key, x-color)就是按缩进展示层级的深度再在 key 后面带一个 R 或 B。有了颜色和中序顺序人眼扫一遍就能看出大部分问题。7. 常见问题与排查心得7.1 插入修复结束后一定要把根染黑这个细节特别容易漏。修复过程中如果一路碰上“叔叔是红色”的情况z 会一路往上跳最后可能把根节点染成红色。红黑树性质二要求根必须是黑的所以修复循环结束后不管根是什么颜色直接强制染黑即可。漏掉这一句树可能依然平衡但性质就错了。7.2 删除修复时哨兵节点的 parent 必须指向正确位置很多人写删除时容易忽略一个重要边界x 可能是哨兵节点 nil。删除一个黑色节点后顶替它的可能是 nil此时 fixup 要从 nil 开始处理。哨兵节点的 parent 指针在替换过程中必须被正确设置否则在delete_fixup里访问x-parent就会出错。这也就是为什么rb_transplant的最后一定要执行v-parent u-parent。即使 v 是 nil也要更新 nil 的父指针。很多段错误就是在这一步没处理好。7.3 旋转操作时要特别注意根节点的更新左旋和右旋里最容易忘的是更新根节点。当被旋转的节点 x或 y是根节点时它的父节点是 nil此时必须把新的根节点写回*root。如果漏了这一步root 指针还指向旧节点整个树就找不到了。我见过不少例子的 bug 就出在这里因为测试数据规模小的时候旋转发生在根节点的概率低不容易暴露。7.4 面试时怎么讲红黑树才不慌如果你是在准备面试不要一上来就背那几种 case。面试官想看的是你能不能把复杂问题拆解成简单模型。你先说红黑树解决的核心问题是“平衡查找和插入删除的代价”然后用五条性质解释高度的约束再说插入和删除各自的修复循环是 O(log n)旋转不会破坏 BST 性质。把这些讲清楚再具体说一两个 case面试官基本就认可了。红黑树的完整代码我前后写过好几版从最初的递归实现到后来改成迭代加哨兵过程里踩过的坑基本都是这四类根节点忘记更新、nil 的 parent 没维护、对称情况漏写、插入后根节点没染黑。如果你也正在写这棵树建议先跑通插入和校验再碰删除。删除修复的四种情况能不看资料独立推一遍那才算真正吃透了。