Appearance
红黑树
平衡与维护成本的权衡
AVL 树够平衡，但删除一个结点可能触发从叶子到根的连锁旋转——Linux 内核的进程调度、Java 的 TreeMap、C++ 的 std::map 都不愿意为每次删除付这个代价。红黑树的策略是放松平衡条件：不要求左右子树高度严格相等，只要求任意路径上的黑色结点数相同。代价是树可能比 AVL 高出一倍（最坏 2log₂(n+1) vs 1.44log₂(n+2)），但插入最多转 2 次、删除最多转 3 次，维护成本可控。
408 考研中，红黑树是树与二叉树章节的重要考点，常与 AVL 树对比考查。
核心思想
红黑树的核心特点：
- 每个节点非红即黑：用 1 bit 额外空间存储颜色信息
- 弱平衡策略：不要求左右子树高度严格相等，只要求任意路径上的黑色节点数相同（黑高相等）
- 最长路径 ≤ 2 × 最短路径：由性质推导得出，保证最坏情况下仍为 O(log n)
黑高（Black Height） 的定义：从某节点出发（不含该节点）到任一叶节点路径上的黑色节点数。整棵树的黑高 = 根节点的黑高。
节点结构：
c
typedef enum { RED, BLACK } Color;
typedef struct RBNode {
int key;
Color color;
struct RBNode *left, *right, *parent;
} RBNode;交互可视化
通过下方的交互动画，你可以逐步观察红黑树的执行过程：
操作详解
五条性质
红黑树必须同时满足以下五条性质：
| 编号 | 性质 | 说明 |
|---|---|---|
| ① | 每个节点是红色或黑色 | 用颜色标记区分节点 |
| ② | 根节点是黑色 | 根必须为黑 |
| ③ | 叶节点（NIL）是黑色 | 这里的叶节点指外部的空节点，不是普通叶节点 |
| ④ | 红节点的两个子节点都是黑色 | 即不存在连续的两个红节点（"不红红"） |
| ⑤ | 从任一节点到其所有叶节点的路径上，黑色节点数目相同 | 即黑高相等 |
⚠️ 易错：性质③中的'叶结点'是指 NIL 空结点（外部结点），不是通常意义上的叶子结点（没有子树的内部结点）。408 题目说'红黑树的叶结点是黑色'指的就是这些 NIL 结点。画红黑树时一定要把 NIL 结点画出来，否则容易在计算黑高时出错。
关键推论：由性质④和⑤可得——最长路径（红黑交替）不超过最短路径（全黑）的 2 倍，因此含 n 个内部节点的红黑树高度 h ≤ 2log₂(n+1)。
插入操作
红黑树的插入分两步：按 BST 规则插入 → 着色并调整。
关键步骤：
- 按照二叉搜索树的规则找到插入位置
- 新节点染为红色（若染黑则必破坏性质⑤，染红只可能破坏性质④）
- 若破坏了红黑性质，则进行调整（变色 / 旋转）
⚠️ 易错：新插入结点必须染红。如果染黑，则该路径的黑高比其他路径多 1，必定破坏性质⑤；染红则只可能破坏性质④（当父结点也是红色时）。408 选择题常问'为什么新结点染红而不染黑'。
c
// 插入节点（简化版）
void rbInsert(RBTree *T, int key) {
RBNode *z = createNode(key);
z->color = RED; // 新节点染红
// 按 BST 规则插入 z
bstInsert(T, z);
// 插入后调整
rbInsertFixup(T, z);
}插入后调整
插入红色节点后，只有当父节点也是红色时才需要调整（违反性质④）。设当前节点为 z，根据叔节点（uncle）的颜色分三种情况：
情况一：叔节点为红色（变色即可）
- 将父节点和叔节点染黑，祖父节点染红
- z 指向祖父节点，继续向上检查
G(黑) G(红) ← 继续向上
/ \ 变色 / \
P(红) U(红) → P(黑) U(黑)
/ /
z(红) z(红)情况二：叔节点为黑色，z 是"折线"形（先旋转变直线）
- z 是父节点的右孩子（父是祖父的左孩子），对 P 左旋，转化为情况三
- （镜像情况类似，对 P 右旋）
情况三：叔节点为黑色，z 是"直线"形（旋转 + 变色）
- 对祖父节点 G 右旋（若 P 是 G 的左孩子）
- P 染黑，G 染红
G(黑) P(黑)
/ \ 右旋G / \
P(红) U(黑) → z(红) G(红)
/ \
z(红) U(黑)插入调整最多旋转 2 次，其余操作为 O(log n) 的变色上溯。
c
void rbInsertFixup(RBTree *T, RBNode *z) {
while (z->parent && z->parent->color == RED) {
if (z->parent == z->parent->parent->left) {
RBNode *uncle = z->parent->parent->right;
if (uncle && uncle->color == RED) {
// 情况一：叔节点红色
z->parent->color = BLACK;
uncle->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
} else {
if (z == z->parent->right) {
// 情况二：折线 → 左旋转为直线
z = z->parent;
leftRotate(T, z);
}
// 情况三：直线 → 右旋 + 变色
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(T, z->parent->parent);
}
} else {
// 镜像处理（parent 是右孩子，左右互换）
// ... 对称操作
}
}
T->root->color = BLACK; // 保证性质②
}删除操作
红黑树的删除分两步：先按 BST 规则删除节点，再修复可能被破坏的红黑性质。
BST 删除的三种情况（与普通 BST 相同）：
- 被删节点无孩子 → 直接删除
- 被删节点有一个孩子 → 用孩子替代
- 被删节点有两个孩子 → 找中序后继（或前驱），把后继的值复制过来，转化为删除后继节点（后继节点最多只有一个右孩子）
删完之后，关键在于被实际移除的节点是什么颜色：
- 删除的是红色节点 → 黑高不变，五条性质均满足，直接结束
- 删除的是黑色节点 → 从该节点到叶子的所有路径黑高减 1，破坏性质⑤，需要调整
调整时引入一个概念：设 x 为替代被删黑色节点位置的节点（可以是真实节点，也可以是 NIL 哨兵）。x 额外"携带"了一重黑色（双重黑），目标是通过旋转和变色消除这重多余的黑色。调整依据的是 x 的兄弟节点颜色，共四种情况。
⚠️ 易错：插入调整看叔父节点颜色，删除调整看兄弟节点颜色，两者经常混淆。
删除后调整
以 x 是其父节点的左孩子为例，右孩子情况完全对称。设 w 为 x 的兄弟节点。
情况 1：兄弟 w 是红色
P(黑) W(黑)
/ \ → / \
x(双黑) W(红) P(红) Wr
/ \ / \
Wl Wr x(双黑) Wl操作：w 染黑，P（父节点）染红，对 P 左旋。旋转后 x 的新兄弟是原来的 Wl，为黑色，转化为情况 2/3/4 继续处理。
情况 2：兄弟 w 是黑色，w 的两个孩子都是黑色
P(任意色) P(双黑或根)
/ \ → / \
x(双黑) W(黑) x(普通黑) W(红)
/ \ / \
Wl(黑) Wr(黑) Wl(黑) Wr(黑)操作：w 染红，x 的双重黑上溯给父节点 P。若 P 原本是红色，直接染黑，调整结束；若 P 是黑色，则 P 变为新的双重黑节点，继续向上迭代。最坏情况迭代到根，根直接去掉一重黑（整棵树黑高减 1，仍合法）。
情况 3：兄弟 w 是黑色，w 的左孩子（近侄）红，右孩子（远侄）黑
P P
/ \ / \
x W(黑) → x Wl(黑)
/ \ \
Wl(红) Wr(黑) W(红)
\
Wr(黑)操作：Wl（近侄）染黑，w 染红，对 w 右旋。转化为情况 4（兄弟黑 + 远侄红）。
情况 4：兄弟 w 是黑色，w 的右孩子（远侄）红
P(任意色) W
/ \ → / \
x(双黑) W(黑) P(黑) Wr(黑)
/ \ / \
Wl Wr(红) x(黑) Wl操作：w 取 P 的颜色，P 染黑，Wr（远侄）染黑，对 P 左旋。x 的双重黑消除，调整结束。
四种情况的转化关系：
情况1 ──→ 情况2/3/4
情况3 ──→ 情况4
情况4 ──────────→ 结束（常数步）
情况2 ──→ 上溯（最多 O(log n) 次）⚠️ 易错：情况 2 是唯一可能导致迭代的情况，其余三种（1/3/4）都能在常数步内终止。所以删除旋转次数最多 3 次（情况 1 → 情况 3 → 情况 4，每次 1 次旋转）。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查找 | O(log n) | 树高 ≤ 2log₂(n+1) |
| 插入 | O(log n) | 查找位置 O(log n) + 调整最多旋转 2 次 |
| 删除 | O(log n) | 查找位置 O(log n) + 调整最多旋转 3 次 |
红黑树 vs AVL 树对比：
| 对比项 | 红黑树 | AVL 树 |
|---|---|---|
| 平衡条件 | 黑高相等（弱平衡） | 左右子树高度差 ≤ 1（严格平衡） |
| 最大高度 | 2log₂(n+1) | 1.44log₂(n+2) |
| 查找效率 | 略低于 AVL | 更优 |
| 插入旋转次数 | ≤ 2 次 | ≤ 2 次 |
| 删除旋转次数 | ≤ 3 次 | O(log n) 次 |
| 适用场景 | 频繁插入/删除（如 Linux 内核、STL map） | 查找密集型场景 |
⚠️ 易错：红黑树的最大高度是 2log₂(n+1)，AVL 树是约 1.44log₂n。所以对于查找密集型操作，AVL 树效率更高；对于频繁插入删除的场景，红黑树更优（旋转次数有常数上界）。408 简答题常考'在什么场景下选 AVL，什么场景下选红黑树'。
考研高频考点
- ⭐ 红黑树的五条性质（选择题/判断题高频，务必逐条记牢）
- ⭐ 含 n 个内部节点的红黑树高度上界 h ≤ 2log₂(n+1)（填空题/证明题）
- ⭐ 红黑树 vs AVL 树的对比：平衡条件、旋转次数、适用场景（简答题/选择题常考）
- ⭐ 插入调整三种情况的判断与操作（叔红变色、叔黑折线双旋、叔黑直线单旋）
- ⭐ 删除调整四种情况的判断（兄弟红→转化；兄弟黑+双黑侄→上溯；兄弟黑+近红远黑→双旋；兄弟黑+远红→单旋）
- 黑高的定义与计算（概念题）
- 新插入节点为什么染红而不染黑（选择题偶考）
- 红黑树中最短路径与最长路径的关系（最长 ≤ 2 × 最短）