红黑树

为什么需要红黑树

普通二叉搜索树（BST）在最坏情况下会退化为链表，查找效率降为 O(n)。AVL 树通过严格的平衡因子（左右子树高度差 ≤ 1）解决了这个问题，但每次插入/删除后可能需要多次旋转来恢复平衡，维护代价较高。

红黑树是一种弱平衡的二叉搜索树。它通过对节点着色并施加约束，保证树的高度不超过 2log₂(n+1)，从而在查找效率和维护成本之间取得更好的折中。在 408 考研中，红黑树是树与二叉树章节的重要考点，常与 AVL 树对比考查。

核心思想

红黑树的核心特点：

每个节点非红即黑：用 1 bit 额外空间存储颜色信息
弱平衡策略：不要求左右子树高度严格相等，只要求任意路径上的黑色节点数相同（黑高相等）
最长路径 ≤ 2 × 最短路径：由性质推导得出，保证最坏情况下仍为 O(log n)

黑高（Black Height） 的定义：从某节点出发（不含该节点）到任一叶节点路径上的黑色节点数。整棵树的黑高 = 根节点的黑高。

节点结构：

typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    int key;
    Color color;
    struct RBNode *left, *right, *parent;
} RBNode;

交互可视化

通过下方的交互动画，你可以逐步观察红黑树的执行过程：

加载可视化中...

操作详解

五条性质

红黑树必须同时满足以下五条性质：

编号	性质	说明
①	每个节点是红色或黑色	用颜色标记区分节点
②	根节点是黑色	根必须为黑
③	叶节点（NIL）是黑色	这里的叶节点指外部的空节点，不是普通叶节点
④	红节点的两个子节点都是黑色	即不存在连续的两个红节点（"不红红"）
⑤	从任一节点到其所有叶节点的路径上，黑色节点数目相同	即黑高相等

关键推论：由性质④和⑤可得——最长路径（红黑交替）不超过最短路径（全黑）的 2 倍，因此含 n 个内部节点的红黑树高度 h ≤ 2log₂(n+1)。

插入操作

红黑树的插入分两步：按 BST 规则插入 → 着色并调整。

关键步骤：

按照二叉搜索树的规则找到插入位置
新节点染为红色（若染黑则必破坏性质⑤，染红只可能破坏性质④）
若破坏了红黑性质，则进行调整（变色 / 旋转）

// 插入节点（简化版）
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) 的变色上溯。

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;  // 保证性质②
}

复杂度分析

操作	时间复杂度	说明
查找	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）	查找密集型场景

考研高频考点

⭐ 红黑树的五条性质（选择题/判断题高频，务必逐条记牢）
⭐ 含 n 个内部节点的红黑树高度上界 h ≤ 2log₂(n+1)（填空题/证明题）
⭐ 红黑树 vs AVL 树的对比：平衡条件、旋转次数、适用场景（简答题/选择题常考）
⭐ 插入调整三种情况的判断与操作（叔红变色、叔黑折线双旋、叔黑直线单旋）
黑高的定义与计算（概念题）
新插入节点为什么染红而不染黑（选择题偶考）
红黑树中最短路径与最长路径的关系（最长 ≤ 2 × 最短）

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

红黑树 ​

为什么需要红黑树 ​

核心思想 ​

交互可视化 ​

操作详解 ​

五条性质 ​

插入操作 ​

插入后调整 ​

复杂度分析 ​

考研高频考点 ​

相关文章