红黑树、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; ...)报错，就加上-std=c99编译选项。这些都属于 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 没维护、对称情况漏写、插入后根节点没染黑。如果你也正在写这棵树，建议先跑通插入和校验，再碰删除。删除修复的四种情况，能不看资料独立推一遍，那才算真正吃透了。
