红黑树，这三个字几乎是每个写算法的人绕不开的一道坎。我最早认真啃它，是因为翻 JDK 的 TreeMap 源码，看到满屏的 rotateLeft、rotateRight 和颜色翻转一脸懵；后来做 Linux 后台开发，发现内核的 CFS 调度器、epoll、Nginx 的定时器里全是红黑树的影子，这才下定决心彻底搞懂它。如果你也准备手写一棵红黑树，或者想在面试前把插入、删除的来龙去脉捋清楚，这篇文章就是按我当年踩坑总结出来的思路写的，不讲废话，直接讲原理配上能跑的代码。
1. 红黑树到底解决了什么问题
1.1 从二叉搜索树的退化说起
普通二叉搜索树（BST）的规则很简单：左子树小、右子树大。这个结构本身没毛病，问题出在它不限制树的形状。如果你按 1、2、3、4、5……的顺序插入，BST 会直接退化成一条链表，查找时间复杂度从期望的 O(log n) 变成 O(n)。我在实际项目里就遇到过这种情况：一张加了索引的表达式中，代码不小心用有序数据反复触发最坏情况，查询直接崩到秒级，排查很久才意识到是树形索引退化了。
红黑树本质上也是一种 BST，但它通过额外约束让整棵树保持“近似平衡”，保证树高始终在一个可控范围内。所谓近似平衡，不是说左右子树高度严格相等，而是最长的路径不会超过最短路径的两倍。这个性质对工程来说非常关键：无论你按什么顺序插入、删除，红黑树都能把查找、插入、删除的整体复杂度稳定压在 O(log n)。
1.2 平衡的代价与收益
平衡二叉树这个家族里，AVL 树是另一个代表。AVL 要求任意节点的左右子树高度差不超过 1，这个约束非常严格，树确实更矮，查找常数也更小，但代价是插入和删除时为了维持“高度差不超过 1”需要频繁旋转，甚至可能一路旋转到根。红黑树选择了“松绑”：它不关心子树具体差几层，只要求从根到叶子的所有路径上黑色节点数量相等，且红色节点不能连续出现。这个看似奇怪的规则，换来的是插入时最多两次旋转、删除时最多三次旋转，而且调整操作通常是局部变色，成本大幅下降。
所以选平衡树时，并没有谁绝对碾压谁，而是看场景。查找居多、插入删除极少，AVL 更合适；插入删除频繁、还需要稳定 O(log n) 保证，红黑树更合适。我自己的经验是，做通用集合类、内核模块、缓存管理这类写多读也多的组件，红黑树几乎是默认答案。
2. 红黑树的五条性质：规则与背后的意图
2.1 逐条拆解五条性质
红黑树的全部规则就是下面这五条，任何一棵合法的红黑树必须同时满足：
| 编号 | 性质 | 大白话解释 |
|---|---|---|
| 1 | 每个节点非红即黑 | 颜色是节点的额外标记字段 |
| 2 | 根节点是黑色 | 树的根基必须稳定 |
| 3 | 所有叶子节点（NIL）是黑色 | 这里的叶子指的是空节点，不是我们平时说的数据叶子 |
| 4 | 红色节点的两个子节点必须是黑色 | 不能出现连续两个红节点 |
| 5 | 从任意节点到其每个叶子节点的路径上，黑色节点数量相同 | 这个数量就叫“黑高” |
很多人背性质背得很熟，但不理解为什么是这五条。其实核心就是第 4 条加第 5 条。第 5 条保证了所有路径的黑高一致，第 4 条限制了红色节点的串联，于是任何路径上红色节点数量不可能超过黑色节点数量，最长路径顶多是一半黑一半红交替，而最短路径可以全是黑。两者一比，最长路径最多是最短路径的两倍，这就保证了树不会过度倾斜。
2.2 黑高与树高的数学推导
我们把从某个节点出发，到叶子节点路径上黑色节点的个数（包含该节点自身，不包含 NIL 叶子）称为该节点的黑高，记作 bh。一棵包含 n 个内部节点的红黑树，它的高度 h 最多是 2 * log2(n + 1)。这个上界怎么来的？我当年第一次看到推导时觉得绕，后来用反证思路理解就顺了。
假设一棵黑高为 bh 的树，它至少要有多少节点？如果一棵全是黑节点，那它最紧凑，满二叉树的节点数是 2^bh - 1。如果允许红节点，节点数只会更多，不会更少。又因为第 4 条限制了红黑交替，所以整棵树的高度 h 最多是黑高的两倍，即 bh >= h / 2。把这个带进 n >= 2^bh - 1，就得到 n >= 2^(h/2) - 1，也就是 h <= 2log2(n + 1)。虽然这个上界比 AVL 的 1.44log2(n+1) 宽松，但从工程角度看，2 倍也是常数级别，O(log n) 的承诺依然成立，而实现和旋转成本却低了不少。
3. 旋转：红黑树的原子操作
3.1 旋转的本质
红黑树的调整不管是插入还是删除，最终都会落到两类操作上：变色和旋转。旋转分左旋和右旋，它们的作用是在不破坏 BST 中序顺序的前提下，把一个节点往下“沉”，把它的子节点往上“提”。
左旋的场景：如果你有一个节点 x，它的右孩子 y 不想当孩子了，想当爹，那就围绕 x 做一次左旋。左旋完成后，y 变成子树的新根，x 变成 y 的左孩子，而 y 原来的左孩子会过继给 x，变成 x 的右孩子。仔细看，这个过继操作保证了 BST 的顺序性不变：y 的左孩子原本大于 x、小于 y，左旋后它成为 x 的右孩子，依然大于 x、小于 y，非常自然。
右旋就是镜像对称操作，把左孩子提上来，自己沉下去。旋转操作的时间复杂度是 O(1)，因为它只改动常数个指针。这是红黑树所有调整操作的“地基”，插入删除那些令人头大的 case，本质上都是在安排旋转和变色的顺序。
3.2 左旋与右旋的代码实现
旋转代码看起来简单，但写起来最容易出错的地方往往不是旋转本身，而是父指针的维护。我贴一段自己项目里用过的 C 风格实现，假设节点结构里带 parent 指针。
typedef struct rb_node { int key; int color; // 0 黑，1 红 struct rb_node *left, *right, *parent; } rb_node; void rotate_left(rb_node **root, rb_node *x) { rb_node *y = x->right; x->right = y->left; if (y->left != NULL) { y->left->parent = x; } y->parent = x->parent; if (x->parent == NULL) { *root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } void rotate_right(rb_node **root, rb_node *y) { rb_node *x = y->left; y->left = x->right; if (x->right != NULL) { x->right->parent = y; } x->parent = y->parent; if (y->parent == NULL) { *root = x; } else if (y == y->parent->left) { y->parent->left = x; } else { y->parent->right = x; } x->right = y; y->parent = x; }这段代码里有几个地方值得你多看两眼。第一，所有子节点指针更新后，都要同步更新子节点的 parent。第二，如果 x 是根，旋转后必须更新树的 root 指针，否则后续操作会从旧根出发导致完全错乱。第三，判断 x 是父节点的左孩子还是右孩子时，必须用原本的父子关系，不能在更新 parent 之后再判断。
4. 插入实操：从变色到再平衡
4.1 插入流程总览
插入操作的思路分三步。第一步，按普通 BST 的规则找到插入位置，把新节点挂到树上。第二步，把新节点涂成红色。第三步，从新节点开始向上修复，让整棵树重新满足五条性质。
很多初学者会问：为什么新节点一定要是红色？道理很简单：如果你涂黑色，那么从根到新节点这条路径上的黑高立刻比别的路径多 1，直接违反第 5 条，而这个性质是最难修复的。涂红色则不会破坏黑高，最多只会出现连续红节点，也就是可能违反第 4 条，但第 4 条是局部约束，修复起来代价小得多。这个选择背后就是典型的“把问题限制在容易处理的场景”。
修复过程关注三个节点：当前节点 z、它的父节点 p、它的叔节点 u（即 p 的兄弟）。当 z 的父节点是黑色时，直接结束，因为这棵树依然合法。需要处理的，就是父节点为红色的情况，它按叔叔节点的颜色和位置分裂成三种 case。
4.2 三种情况的处理策略
第一种，叔叔节点是红色。这种情况最温柔，不需要旋转，只需要变色：把父节点和叔叔节点都变成黑色，把祖父节点变成红色。这样做的效果是，原来从祖父到两个子路径上的黑高保持不变，但“红色往上移动”到了祖父。接下来把 z 指向祖父，继续向上检查。注意如果祖父正好是根，最后一步要把根强制涂黑。
第二种，叔叔节点是黑色，且 z 是父节点的“内侧”孩子。所谓内侧，是指父节点是左孩子而 z 是右孩子，或者父节点是右孩子而 z 是左孩子，也就是形成了 LR 或 RL 的形状。这时候直接对祖父旋转没法一步到位，需要先对父节点做一次旋转，把它转化成第三种情况。比如父是左孩子、z 是右孩子，就先对父节点左旋，然后 z 和父的角色互换，变成“父是左孩子且 z 也是左孩子”的形状。
第三种，叔叔节点是黑色，且 z 是父节点的“外侧”孩子，也就是 LL 或 RR 形状。这时对祖父节点做一次旋转，让父节点顶替祖父的位置，然后交换父和祖父的颜色：父变黑，祖父变红。这样整棵子树的黑高恢复原状，连续红节点也消除了，调整可以直接结束。
这三种情况的判断顺序不是随意定的。变色的 case 会把问题抛给上一层，靠循环解决；而旋转的 case 一旦执行，整棵子树立刻合法，循环就终止了。所以说红黑树插入最坏情况下只需两次旋转，但变色操作的次数可以沿着路径累积到 O(log n)。
4.3 插入代码实现
下面是我整理好的插入修复函数，代码里我故意保留了“插入后统一修复”的结构，方便你对照上面的 case 理解。
void rb_insert_fixup(rb_node **root, rb_node *z) { while (z->parent != NULL && z->parent->color == 1) { rb_node *p = z->parent; rb_node *g = p->parent; rb_node *u = (p == g->left) ? g->right : g->left; if (u != NULL && u->color == 1) { // case 1: 叔红，变色后上移 u->color = 0; p->color = 0; g->color = 1; z = g; } else { if (p == g->left) { if (z == p->right) { // case 2 的内侧情况，先左旋父节点 z = p; rotate_left(root, z); p = z->parent; } // case 3: 外侧情况，右旋祖父并变色 rotate_right(root, g); p->color = 0; g->color = 1; break; } else { if (z == p->left) { z = p; rotate_right(root, z); p = z->parent; } rotate_left(root, g); p->color = 0; g->color = 1; break; } } } (*root)->color = 0; }这里要注意，case 2 我直接沿用了“z = p 再重新取 p”的写法，这样代码结构上和教科书版一致，逻辑更清晰。实际生产代码里有人会写得更高压缩，但可读性差很多，我建议先按这个清晰版本理解，再慢慢优化。
5. 删除实操：最麻烦的双黑问题
5.1 删除流程与替换删除法
删除比插入复杂，核心难点在于：如果删掉一个黑色节点，那么从根到它叶子路径上的黑高就少 1，这会破坏第 5 条“所有路径黑高相同”的性质，而且不像插入那样有个“红色往上提”的简单策略，删除修复的这个黑色缺失会一直存在，直到我们通过旋转和变色把它补回来。
先说删除节点的基本策略。如果待删节点 z 最多只有一个非空子节点，那就直接用子节点顶替它，这种最简单。如果 z 有两个非空子节点，标准做法是“替换删除”：找到 z 的中序后继 y，把 y 的 key 值拷贝到 z，然后删除 y。因为 y 是右子树的最左节点，它最多只有一个非空右孩子，这样问题又退化到单子节点场景。这个技巧很巧妙地避免了直接删除有两个孩子的节点时复杂的子链接操作。
真正需要修复的，是实际被删除的节点 y 为黑色的情况。我们把顶替 y 位置的那个节点记为 x，如果 x 是红色，直接把它涂黑就能补回黑高，万事大吉；如果 x 也是黑色，那么这棵子树相对于外界“少了一个黑”，我们把这种情况称为 x 带有“双黑”，修复的目标就是消除这个双黑。
5.2 兄弟节点的四种情况
删除修复是在循环中处理的，每次处理时双黑节点 x 处于某个父节点 p 之下，我们关注 x 的兄弟节点 w。为便于描述，假设 x 是 p 的左孩子，右边情况对称。
第一种情况，w 是红色。这说明父节点 p 一定是黑色，且 w 的两个孩子都是黑色。处理方式是左旋 p，把 w 提上来，然后染色：w 变黑，p 变红。经过这次操作，x 的兄弟变成原来 w 的左孩子，一个黑色节点，问题转化到后面的 case 2、3、4。
第二种情况，w 是黑色，且 w 的两个孩子都是黑色。这是最“温和”的向上抛问题：把 w 变成红色，这样 x 和 w 两侧的黑高各少 1，双黑被吸收到 p 身上，x 指向 p，循环继续。注意如果 p 是红色，循环结束后把它涂黑即可。
第三种情况，w 是黑色，w 的左孩子是红色，右孩子是黑色。个案型处理：对 w 右旋，把 w 的左孩子提上来，染黑顶替的节点，w 变红。这样处理之后，新兄弟节点变成了此前 w 的左孩子，它有一个红色右孩子，正好满足第四种情况的前提。
第四种情况，w 是黑色，w 的右孩子是红色。这是唯一能结束循环的旋转 case：对 p 左旋，w 继承 p 的颜色，p 变成黑色，w 的右孩子变成黑色。这一步把黑高缺口完美补上，x 直接指向根节点，循环终止。
综合来看，删除修复最多三次旋转，但变色和向上传播可以一路走到根，所以时间复杂度是 O(log n)。我当年写删除时最常犯的错误，就是漏掉“x 可能是 NIL 节点”的情况——实际被删的是黑色叶节点，顶替它的就是空节点 NIL，代码里必须允许 x 本身为 NULL，但不能对 NULL 解引用。
5.3 删除修复代码实现
为了方便理解，我把删除修复也按“x 是左孩子”和“x 是右孩子”两个分支来写，镜像逻辑直接复制后左右互换，虽然代码长了点，但比用 helper 隐藏对称性更容易读。
void rb_delete_fixup(rb_node **root, rb_node *x, rb_node *parent) { while (x != *root && (x == NULL || x->color == 0)) { if (x == parent->left) { rb_node *w = parent->right; if (w->color == 1) { // case 1: 兄弟红 w->color = 0; parent->color = 1; rotate_left(root, parent); w = parent->right; } if ((w->left == NULL || w->left->color == 0) && (w->right == NULL || w->right->color == 0)) { // case 2: 兄弟黑，且兄弟的孩子全黑 w->color = 1; x = parent; parent = x->parent; } else { if (w->right == NULL || w->right->color == 0) { // case 3: 兄弟的右孩子黑，左孩子红 if (w->left != NULL) { w->left->color = 0; } w->color = 1; rotate_right(root, w); w = parent->right; } // case 4: 兄弟的右孩子红 w->color = parent->color; parent->color = 0; if (w->right != NULL) { w->right->color = 0; } rotate_left(root, parent); x = *root; break; } } else { // 镜像逻辑，不再逐行解释 rb_node *w = parent->left; if (w->color == 1) { w->color = 0; parent->color = 1; rotate_right(root, parent); w = parent->left; } if ((w->left == NULL || w->left->color == 0) && (w->right == NULL || w->right->color == 0)) { w->color = 1; x = parent; parent = x->parent; } else { if (w->left == NULL || w->left->color == 0) { if (w->right != NULL) { w->right->color = 0; } w->color = 1; rotate_left(root, w); w = parent->left; } w->color = parent->color; parent->color = 0; if (w->left != NULL) { w->left->color = 0; } rotate_right(root, parent); x = *root; break; } } } if (x != NULL) { x->color = 0; } }呼，这段代码我每个分支都测试过随机插入删除，但这属于“需要仔细对待”的代码，你抄进自己的工程后，一定要跑随机验证，不要看一遍就认为没问题。
6. 常见问题与排查技巧实录
6.1 调试红黑树的心法
手写红黑树的调试期是最痛苦的，很容易出现“看起来对，但随机操作几万次后某个性质被破坏”的幽灵问题。我的经验是：不要用人眼盯着树看，也不要只靠单测用例，而是写一个校验器，每次插入删除后都自动验证五条性质是否成立。
一个合格的校验器要检查四件事：根是否是黑、红节点的孩子是否是黑、所有路径黑高是否一致、树的中序序列是否有序。为了让校验器能找到问题节点，我习惯在递归函数里返回“以当前节点为根的子树黑高”，一旦发现某条路径黑高不一致，立刻打印出该节点的 key 和左右子树的黑高，这样能快速定位到失衡的局部。
下面是我常用的递归校验代码，基于 Python 写，方便测试时快速验证。
def check_rb(node, is_root=False): # 返回黑高，非法返回 -1 if node is None: return 1 # NIL 叶子算一个黑高 if is_root and node.color != 'black': print('root is not black') return -1 if node.color == 'red': if node.left and node.left.color == 'red': print('red-red at', node.key) return -1 if node.right and node.right.color == 'red': print('red-red at', node.key) return -1 lh = check_rb(node.left) if lh < 0: return -1 rh = check_rb(node.right) if rh < 0: return -1 if lh != rh: print('black height mismatch at', node.key, lh, rh) return -1 return lh + (1 if node.color == 'black' else 0)这个校验器虽然简单，但非常管用。我每次写完插入或删除，会随机生成几十万条操作序列，穿插插入和删除，每步结束后都跑一遍校验，一旦报错就二分定位到具体操作，极大缩短了排查时间。
6.2 最容易踩的三个坑
第一个坑是 NIL 节点处理。很多教材画树时，黑高是从“真正的叶子节点”算的，但代码里叶子其实就是空指针。如果你在递归里没有把空节点当作黑色叶子处理，插入删除的黑高逻辑很容易写错。我建议统一约定：NULL 就是黑色 NIL 叶子，这样代码条件判断里到处都要写“== NULL || color == 0”，看着烦，但对。
第二个坑是 parent 指针不同步。旋转代码里容易漏掉更新孩子节点的 parent，或者漏掉判断“当前节点是不是根”，结果 list 遍历时出现环形指针，程序直接死循环。排查这种问题很折磨，所以我建议旋转函数里先更新所有孩子 parent，再更新父 parent，再更新 root，每一步都按顺序来。
第三个坑是删除修复的循环条件。修复循环必须在 x 成为根节点或 x 为红色时终止。如果你把“x == NULL”漏在循环条件外，就会在删除黑色叶节点时对空指针解引用。我吃过的亏是：循环写成 while(x != root && x->color == 0)，结果 x 为 NULL 时直接崩溃，改成允许 NULL 的版本后才稳定。
7. 红黑树的工程应用与选型建议
7.1 你身边那些看不见的红黑树
红黑树并不只是面试题，它是很多基础组件的核心结构。我最早从 Java 的 TreeMap 和 TreeSet 开始认识它，这两个类底层就是红黑树，要求 key 可排序且支持范围查询。C++ 的 std::map 和 std::set 也是红黑树，标准库对它迭代器的稳定性保证，正是来自红黑树插入删除对结构局部性的控制。
Linux 内核里红黑树用得更多：CFS 调度器用它管理进程调度实体，保证每次都能以 O(log n) 找到最小虚拟运行时间的进程；epoll 用它管理被监听的文件描述符。Nginx 的定时器也是经典的红黑树应用，通过 key 是超时时间，快速找到最快到期的定时器。你会发现，凡是需要“动态插入、删除、频繁查找最值”的场景，红黑树都是高频选择。
7.2 红黑树、AVL 与跳表的取舍
选型时我经常要比较红黑树、AVL 和跳表。AVL 的树更矮，查找性能理论更好，但删除旋转次数比红黑树多，对写多场景不友好。跳表实现异常简单，区间查询和并发改造都容易，Redis 的有序集合就用的跳表，但它需要额外的层指针，内存占用偏高，而且最坏情况下没有严格的平衡保证。红黑树的优势是内存紧凑、插入删除旋转次数有硬上限、树高稳定，劣势是实现复杂、对并发场景需要额外加锁。
如果是写一个通用有序集合，红黑树基本可以无脑选；如果需求特别看重实现简单和并发读多写多，跳表值得考虑；如果场景几乎是静态数据、只做高频查找，AVL 依然能打。没有“最强的数据结构”，只有“最匹配当前场景的结构”，这句话我是在调了无数次优之后才真正认同的。
7.3 我的建议路线
最后给你一条我自己验证过的学习路径。第一步别急着背 case，先把五条性质写在一张纸上。第二步实现二叉搜索树的查找、插入、删除，至少搞清楚中序后继。第三步实现旋转。第四步加校验器。第五步写插入修复，跑随机测试。第六步写删除修复，继续跑随机测试。每一步都让前面的代码可运行、可验证，再进入下一步。
从看着 TreeMap 源码头晕，到自己把红黑树完整跑通，我最大的体会是：红黑树学习的真正门槛不在那六个 case，而在你能不能把“为什么新节点是红色”“为什么删除会产生双黑”“为什么旋转不破坏有序性”这几个为什么想透。想透之后，case 只是若干种形状的组合，你完全可以现场推导出来。如果你也想彻底告别对红黑树的恐惧，我建议今天就写个校验器，再开始写插入，多跑几轮随机测试，那比看十遍教程都管用。
