408

数据结构

红黑树

---

定位信息

项目	内容
章节	第六章 查找 · 6.5
知识单元编号	DS-06-05
核心概念	红黑树五条性质、旋转与重新着色、插入调整、删除调整
前置知识	二叉搜索树（BST）、AVL 树旋转
考试权重	★★★（选择题高频，综合题偶有涉及）

---

知识点讲解

一、红黑树的定义与五条性质

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，通过对每个结点着红色或黑色，并满足以下五条性质来保证树的"近似平衡"：

1. 每个结点是红色或黑色（二色性）；
2. 根结点是黑色（根黑）；
3. 叶子结点（NIL/空结点）是黑色（叶黑）；
4. 如果一个结点是红色，则它的两个子结点都是黑色（红不相邻/红红不连续）；
5. 从任一结点到其每个叶子的所有路径上，黑色结点的数量相同（黑高相同）。

黑高（Black-Height）： 从某结点（不含该结点）到叶子路径上的黑色结点数，记为 bh(x)。

二、红黑树 vs AVL 树对比表

对比维度	AVL 树	红黑树
平衡标准		BF
树高上界	O(log₂ n)	O(2log₂(n+1)) ≈ O(log n)
查找效率	更快（更矮）	略慢于 AVL
插入调整	最多 2 次旋转	最多 2 次旋转 + O(log n) 次变色
删除调整	O(log n) 次旋转	最多 3 次旋转 + O(log n) 次变色
适用场景	查找密集	插入删除频繁（如 STL map, Java TreeMap）
实际效率	查找快，修改旋转多	综合效率更均衡

三、红黑树的插入操作

插入步骤：

1. 按 BST 规则插入新结点，默认着红色（因为红色不破坏性质 5）；
2. 检查是否违反红黑树性质（主要是性质 4：红红相邻）；
3. 通过重新着色和/或旋转修复。

插入修复的三种情况（假设 x 为新插入结点，p 为父结点，u 为叔结点，g 为祖父结点）：

情况	条件	操作
情况 1	叔结点 u 是红色	将 p 和 u 变黑，g 变红，x 上移到 g 继续检查
情况 2	叔结点 u 是黑色，x 是 p 的右孩子（且 p 是 g 的左孩子）	对 p 做左旋，转化为情况 3
情况 3	叔结点 u 是黑色，x 是 p 的左孩子（且 p 是 g 的左孩子）	p 变黑，g 变红，对 g 做右旋

四、红黑树插入伪代码（C 风格，核心框架）

// 颜色定义
#define RED   0
#define BLACK 1

// 红黑树结点定义
typedef struct RBNode {
    KeyType key;
    int color;                   // RED 或 BLACK
    struct RBNode *left;
    struct RBNode *right;
    struct RBNode *parent;       // 父指针（红黑树常需要）
} RBNode, *RBTree;

// 左旋操作
void RB_LeftRotate(RBTree *root, RBNode* x) {
    RBNode* y = x->right;        // y 是 x 的右孩子
    x->right = y->left;          // y 的左子树变为 x 的右子树
    if (y->left != NULL)
        y->left->parent = x;
    y->parent = x->parent;       // y 替代 x 的位置
    if (x->parent == NULL)
        *root = y;               // x 是根结点
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;                 // x 成为 y 的左孩子
    x->parent = y;
}

// 右旋操作（与左旋对称）
void RB_RightRotate(RBTree *root, RBNode* y) {
    RBNode* 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;
}

// 插入修复（核心逻辑）
void RB_InsertFixup(RBTree *root, RBNode* z) {
    while (z->parent != NULL && z->parent->color == RED) {
        RBNode* p = z->parent;
        RBNode* g = p->parent;       // 祖父结点
        if (p == g->left) {
            RBNode* u = g->right;    // 叔结点
            if (u != NULL && u->color == RED) {
                // 情况 1：叔结点红色 → 变色，上移
                p->color = BLACK;
                u->color = BLACK;
                g->color = RED;
                z = g;                // 继续向上检查
            } else {
                if (z == p->right) {
                    // 情况 2：叔黑，z 是右孩子 → 左旋父结点
                    z = p;
                    RB_LeftRotate(root, z);
                    p = z->parent;
                    g = p->parent;
                }
                // 情况 3：叔黑，z 是左孩子 → 变色 + 右旋祖父
                p->color = BLACK;
                g->color = RED;
                RB_RightRotate(root, g);
            }
        } else {
            // 对称情况：p 是 g 的右孩子
            // ... 类似处理，左右镜像
        }
    }
    (*root)->color = BLACK;          // 根结点始终为黑（性质 2）
}

五、红黑树的关键性质

性质	结论
高度上界	h ≤ 2log₂(n+1)
黑高下界	bh(x) ≥ h/2
查找时间	O(log n)
插入时间	O(log n)，最多 2 次旋转
删除时间	O(log n)，最多 3 次旋转
n 个结点的红黑树	高度不超过 2log₂(n+1)，比 AVL 树高最多多一倍

---

记忆辅助

1. "根黑叶黑红不连，每条路径黑高同" — 红黑树五条性质的口诀。
2. "插入默认红色，破坏性质 4 才调整" — 新结点默认着红，因为红色不破坏性质 5。
3. "叔红变色上移，叔黑旋转变色" — 插入修复的两种核心策略。
4. "AVL 严格矮胖，红黑近似高瘦" — AVL 更严格平衡但旋转更多，红黑近似平衡但修改更高效。

---

例题精解

例题 1：红黑树插入与调整

在一棵空红黑树中依次插入 {10, 20, 15}，画出每步插入后的红黑树（标注颜色）。

解题四步法：

① 审题： 按序列插入，每步检查红黑树性质。

② 分析： 新结点默认红色，根结点最终强制变黑。

③ 过程：

• 插入 10： 新结点红色 → 是根 → 强制变黑。

  [10]B     (B=黑)

• 插入 20： 20 > 10，插入右子，着红色。检查：红红相邻？20 红，父 10 黑，不违反。✅

  [10]B
      \
      [20]R    (R=红)

• 插入 15： 15 > 10 → 15 < 20，插入 20 的左子，着红色。
  • 检查：15 红，父 20 红 → 违反性质 4！
  • 叔结点（10 的左子）= NIL = 黑色
  • 15 是 20 的左孩子，20 是 10 的右孩子 → RL 型
  • 先对 20 右旋（转化为 RR 型），再对 10 左旋：

  失衡状态：         对20右旋后：        对10左旋+变色后：
  [10]B              [10]B               [15]B
      \                  \               /    \
      [20]R              [15]R         [10]R  [20]R
      /                     \
  [15]R                    [20]R

然后：15 变黑，10 和 20 变红？不，标准做法：对 10 左旋后，15 成为根，将 15 设为黑，10 和 20 设为红。

实际上更简单的做法：对 15 做 RL 调整——先对 20 右旋使 15 上移，再对 10 左旋，最后将 15 着黑、10 着红、20 着红。

    [15]B
   /    \
 [10]R  [20]R

④ 结论： 插入 15 触发 RL 型失衡，通过右旋 + 左旋 + 重新着色修复，最终根为 15（黑），10 和 20 为红色。

---

例题 2：红黑树性质判断

判断以下着色方案是否为合法的红黑树，说明原因：

      [10]B
      /    \
   [5]R   [15]B
   /  \       \
 [3]B [7]B  [20]R

解题四步法：

① 审题： 逐条验证五条性质。

② 分析： 逐一检查每条性质。

③ 验证：

• 性质 1（每个结点红或黑）：✅ 所有结点有颜色
• 性质 2（根黑）：✅ 10 是黑色
• 性质 3（叶子黑）：✅ NIL 结点视为黑色
• 性质 4（红结点的孩子必须黑）：✅
  • 5 是红色，左子 3（黑）、右子 7（黑）→ 合法
  • 20 是红色，左右子 NIL（黑）→ 合法
• 性质 5（每条路径黑高相同）：
  • 10→5→3→NIL：黑结点数 = 2（10, 3）
  • 10→5→7→NIL：黑结点数 = 2（10, 7）
  • 10→15→NIL：黑结点数 = 2（10, 15）
  • 10→15→20→NIL：黑结点数 = 2（10, 15）
  • ✅ 所有路径黑高 = 2

④ 结论： 合法的红黑树。五条性质全部满足，黑高为 2。

---

考情分析

维度	说明
考频	选择题高频，综合题偶有
题型	选择题（性质判断、插入调整判断、与 AVL 对比）、综合题（插入过程模拟）
命题趋势	红黑树性质的综合判断；插入修复三种情况的识别
常见陷阱	叔结点为 NIL 时视为黑色；新结点默认红色不是黑色

---

易错点

1. 新插入的结点默认着红色！ 不是黑色。因为红色只可能破坏性质 4（红红相邻），而黑色会破坏性质 5（黑高），更难修复。
2. NIL 叶子结点是黑色！ 性质 3 指的是外部结点（空指针），不是普通的叶子结点。判断路径黑高时要算到 NIL。
3. 红黑树的"近似平衡"保证树高 ≤ 2log₂(n+1)。 比 AVL 树高最多一倍，但插入删除时的旋转次数更少，综合性能更好。
4. 插入修复最多需要 2 次旋转（情况 2 + 情况 3 各一次），但变色可能向上递归。 删除修复最多需要 3 次旋转。

---

来源标注

来源	说明
王道考研	2026 版数据结构讲义 · 第六章 查找
天勤考研	数据结构高分笔记 · 查找部分
严蔚敏	《数据结构（C 语言版）》第 9 章
教材参考	《算法导论》（CLRS）红黑树章节；《数据结构》（第 5 版）李春葆