16、红黑树的插入：插入操作的3种情况、变色与旋转、C语言实现要点
红黑树的插入，说实话，是很多人学树结构时的一道坎。我当年第一次看《算法导论》里那堆 case 分析，差点把书扔了。但后来在实际项目中写内存分配器时，才发现这东西真香——它保证了最坏情况下的查找效率，不像普通 BST 那样容易退化成链表。
今天咱们就把红黑树的插入拆开揉碎了讲。你只要记住三个核心操作：变色、左旋、右旋。所有复杂的 case 分析，最终都落到这三板斧上。
16.1 红黑树的五大性质（先过一遍）
在讲插入之前，咱们得先确认一个共识：红黑树本质上是一棵自平衡的二叉搜索树。它通过给每个节点涂上红色或黑色，并遵守以下五条规则，来保证树的高度不超过 2log(n+1)：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 叶子节点（NIL）是黑色。
- 红色节点的两个子节点必须是黑色（不能有连续的红节点）。
- 从任意节点到其每个叶子节点的所有路径上，黑色节点数量相同。
嗯，这里要注意：第 3 条说的叶子节点不是我们通常理解的左右孩子为 NULL，而是指 NIL 哨兵节点。我在项目中习惯用一个全局的 NIL 节点来统一处理，省得每次判空写一堆 if。
16.2 插入操作的核心思路
红黑树的插入分两步走：
- 先按普通 BST 的方式插入，新节点默认涂成红色。
- 再通过变色和旋转修复，让树重新满足红黑树性质。
为什么新节点默认是红色？说白了，如果涂成黑色，那从根到该节点的路径上就多了一个黑节点，会直接破坏性质 5，修复起来更麻烦。涂成红色只可能破坏性质 4（不能有连续红节点），修复范围更小。
16.3 插入后的三种情况（核心）
插入新节点后，如果它的父节点是黑色，那万事大吉，直接结束。如果父节点是红色，就出现了连续红节点，需要根据叔叔节点的颜色分三种情况处理。
为了方便描述，我们约定几个符号：
- N：新插入的节点
- P：N 的父节点
- G：N 的祖父节点
- U：N 的叔叔节点（P 的兄弟）
情况 1：叔叔节点 U 是红色
这是最简单的情况。直接把 P 和 U 变黑，G 变红。然后把 G 当作新插入的节点，继续向上检查。
为什么？因为 P 和 U 都是红色，它们变黑后，G 到子树的路径上黑节点数不变。但 G 变红了，如果 G 的父节点也是红色，就需要继续处理。
情况 2：叔叔节点 U 是黑色，且 N 是 P 的内侧子节点
这里「内侧」指的是：如果 P 是 G 的左孩子，N 是 P 的右孩子；或者 P 是 G 的右孩子，N 是 P 的左孩子。说白了就是 N 和 P 的方向相反。
处理方式：对 P 做一次旋转，让 N 和 P 的角色互换，然后转化为情况 3。
举个例子：如果 P 是 G 的左孩子，N 是 P 的右孩子，那就对 P 做一次左旋。旋转后，N 到了原来 P 的位置，P 成了 N 的左孩子。这时候 N 和 P 的方向就一致了。
情况 3：叔叔节点 U 是黑色，且 N 是 P 的外侧子节点
「外侧」就是 N 和 P 方向相同。比如 P 是 G 的左孩子，N 也是 P 的左孩子。
处理方式：对 G 做一次旋转（方向与 P 相反），然后交换 P 和 G 的颜色。
具体来说：如果 P 是 G 的左孩子，N 是 P 的左孩子，那就对 G 做右旋。旋转后，P 成为新的子树根，G 成为 P 的右孩子。然后把 P 涂黑，G 涂红。
这样处理后，子树根是黑色，它的两个孩子都是红色，性质 4 和性质 5 都满足了。
16.4 三种情况的总结表格
| 情况 | 叔叔颜色 | N 与 P 的位置关系 | 操作 |
|---|---|---|---|
| 1 | 红色 | 任意 | P、U 变黑，G 变红，将 G 作为新 N 继续向上 |
| 2 | 黑色 | 内侧（方向相反） | 对 P 旋转，转化为情况 3 |
| 3 | 黑色 | 外侧（方向相同） | 对 G 旋转，交换 P 和 G 的颜色 |
16.5 左旋与右旋的 C 语言实现
旋转是红黑树最基础的操作。说白了就是调整节点之间的父子关系，同时保持 BST 的性质不变。
左旋：把某个节点往下压，让它的右孩子升上来。右旋反过来。
// 左旋：以 x 为轴心，将 x 的右孩子 y 旋转上来
void left_rotate(RBTree *tree, Node *x) {
Node *y = x->right; // y 是 x 的右孩子
x->right = y->left; // 把 y 的左子树过继给 x 的右子树
if (y->left != NIL) {
y->left->parent = x;
}
y->parent = x->parent; // y 的父指针指向 x 的父节点
if (x->parent == NIL) {
tree->root = y; // x 是根，旋转后 y 成为新根
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x; // x 成为 y 的左孩子
x->parent = y;
}
// 右旋：对称实现，把 left 和 right 互换即可
void right_rotate(RBTree *tree, Node *y) {
Node *x = y->left;
y->left = x->right;
if (x->right != NIL) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == NIL) {
tree->root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
x->right = y;
y->parent = x;
}
16.6 插入修复的 C 语言实现
插入修复函数是核心中的核心。它把上面三种情况串起来，用循环或递归处理。
void rb_insert_fixup(RBTree *tree, Node *z) {
while (z->parent->color == RED) {
// 判断父节点是祖父节点的左孩子还是右孩子
if (z->parent == z->parent->parent->left) {
Node *y = z->parent->parent->right; // 叔叔节点
if (y->color == RED) {
// 情况 1：叔叔是红色
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent; // 向上传递
} else {
// 叔叔是黑色
if (z == z->parent->right) {
// 情况 2：内侧，先左旋
z = z->parent;
left_rotate(tree, z);
}
// 情况 3：外侧，右旋 + 变色
z->parent->color = BLACK;
z->parent->parent->color = RED;
right_rotate(tree, z->parent->parent);
}
} else {
// 对称情况：父节点是祖父节点的右孩子
// 把上面的 left 和 right 互换，逻辑完全对称
Node *y = z->parent->parent->left;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
right_rotate(tree, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
left_rotate(tree, z->parent->parent);
}
}
}
tree->root->color = BLACK; // 确保根节点是黑色
}
你想想看，这个函数其实就两个分支（父节点是左孩子还是右孩子），每个分支里再根据叔叔颜色和 N 的位置做判断。代码看着长，但逻辑很清晰。
16.7 红黑树插入的知识体系图
下面这张图把插入操作的完整流程画出来了，从插入新节点到修复结束，一目了然。
16.8 C 语言实现要点总结
最后，我把自己在实际编码中踩过的坑和总结的经验列出来，希望能帮你少走弯路：
- 哨兵节点 NIL 一定要全局唯一：不要在每个节点里都存一个 NIL，浪费内存。用一个全局的静态变量，所有空指针都指向它。
- 旋转时先更新 parent 指针：我习惯先处理子节点的 parent，再处理父节点的 child，这样不容易丢指针。
- 插入修复用 while 循环：不要用递归，因为最坏情况下要一直向上回溯到根，递归容易栈溢出。
- 最后一定要把根涂黑：不管中间怎么变，最后一行 tree->root->color = BLACK 不能少。这是性质 2 的要求。
- 对称代码不要复制粘贴：父节点是左孩子和右孩子的代码逻辑完全对称，但很多人直接复制后忘了改 left 和 right。我建议写一个宏或者辅助函数来生成对称代码。
好了，红黑树的插入就讲到这里。记住那三种情况，记住旋转的代码结构，剩下的就是多写多练。下一节咱们会讲红黑树的删除，那才是真正的硬骨头——不过有了插入的基础，你已经有底气去啃它了。