红黑树完全指南:从五条规则到插入删除修复的图解与代码

红黑树是计算机科学里最有名也最难写对的数据结构之一。Linux 内核的进程调度、虚拟内存管理、epoll 红黑树,Java 的 TreeMap、C++ STL 的 map/set,Nginx 的定时器,Go runtime 的 timer —— 全在它身上。但很多人对它的认知停在"一种自平衡二叉搜索树",问起细节就讲不清。这篇文章从动机讲起,把红黑树的五条规则、旋转、插入修复、删除修复用图解 + 代码讲透。

为什么需要红黑树

普通二叉搜索树(BST)的查询/插入/删除复杂度是 O(log n) —— 但前提是树"平衡"。最坏情况下,有序数据按顺序插入会让树退化成链表,操作变成 O(n)。要避免这种退化,需要在插入和删除时自动调整树形。

历史上出现过多种自平衡 BST:AVL 树、Treap、Splay 树、跳表(SkipList)、红黑树。其中红黑树的优势在于:插入/删除时旋转次数有上界(最多 3 次旋转 + 若干次染色),而 AVL 树虽然查询稍快但平衡更严格,旋转更频繁。在写多读少或写读各半的场景,红黑树综合性能最优 —— 这正是它被各种系统选中的原因。

红黑树的五条铁律

红黑树是一棵特殊的二叉搜索树,每个节点额外维护一个"颜色"(红或黑)。它满足:

1. 每个节点要么红,要么黑。
2. 根节点是黑。
3. 所有叶子节点(NIL,空节点)是黑。
4. 红节点的子节点必须是黑(不能两个红连在一起)。
5. 从任意节点到其所有后代叶子的路径上,黑节点数量相同(称为"黑高")。

这五条共同保证了:最长路径不会超过最短路径的 2 倍。证明很简洁 —— 黑高相同意味着两条路径黑节点数相同,而红节点不能连续,所以一条路径上红节点数最多和黑节点数相等。最长路径(红黑交替)长度 ≤ 2 × 黑高 = 2 × 最短路径。这就是红黑树高度被卡在 O(log n) 的根源。

旋转:平衡的基本动作

所有自平衡 BST 都靠"旋转"调整树形。旋转保持中序遍历不变(也就是不破坏 BST 性质)。

// 左旋:把节点 x 的右子节点 y 提到 x 的位置
//     x                 y
//    / \               / \
//   a   y     ==>    x   c
//      / \          / \
//     b   c        a   b
//
// 右旋:把节点 x 的左子节点 y 提到 x 的位置(左旋的镜像)

// 用 C 实现节点定义
typedef enum { RED, BLACK } Color;
typedef struct Node {
    int key;
    Color color;
    struct Node *left, *right, *parent;
} Node;

Node *NIL;  // 全局哨兵节点,所有 NULL 都指向它,简化判断

void left_rotate(Node **root, Node *x) {
    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(Node **root, 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) *root = x;
    else if (y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;
    x->right = y;
    y->parent = x;
}

记忆口诀:左旋让右孩子上来,右旋让左孩子上来;旋转后那对父子的位置交换,被搬动的中间子树挂到原父节点上。

插入:先按 BST 插入,再修复

关键设计:新节点一律染成红色。为什么?因为如果染成黑,会立刻破坏"黑高相同"(规则 5),修复起来更复杂;染红只可能破坏"红不连"(规则 4),处理起来简单得多。

void rb_insert(Node **root, int key) {
    Node *z = malloc(sizeof(Node));
    z->key = key; z->color = RED;
    z->left = z->right = NIL;

    // 1. 正常 BST 插入
    Node *y = NIL, *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;

    // 2. 修复红黑性质
    rb_insert_fixup(root, z);
}

插入修复:三种情形

新节点 z 红色,可能破坏的只有"红不连"。修复时一直循环到 z.parent 不再是红,处理时分三种情形(以 z 的父节点是祖父的左孩子为例,反向对称):

// uncle = 祖父的另一个孩子(z 的叔叔)
//
// Case 1:叔叔是红
//   把 父 和 叔 都染黑,祖父染红,把 z 移到祖父继续处理
//   (因为红色冲突可能被推到了祖父那一层)
//
//        G(黑)              G(红)
//        / \                / \
//       P   U(红)  -->     P  U(黑)
//      /                   /
//     z(红)              z(红)
//
// Case 2:叔叔是黑,z 是右孩子(三角形)
//   左旋父节点,转化成 Case 3
//
//        G                  G
//        / \                / \
//       P   U(黑)  -->     z   U
//        \                /
//         z(红)          P(红)
//
// Case 3:叔叔是黑,z 是左孩子(一字形)
//   父染黑、祖父染红,右旋祖父。完成。
//
//        G(黑)              P(黑)
//        /                 / \
//       P(红)     -->    z   G(红)
//      /                    /
//     z(红)              (空,或原 P 的右子)

void rb_insert_fixup(Node **root, Node *z) {
    while (z->parent->color == RED) {
        Node *gp = z->parent->parent;
        if (z->parent == gp->left) {
            Node *u = gp->right;
            if (u->color == RED) {       // Case 1
                z->parent->color = BLACK;
                u->color = BLACK;
                gp->color = RED;
                z = gp;
            } else {
                if (z == z->parent->right) {   // Case 2
                    z = z->parent;
                    left_rotate(root, z);
                }
                z->parent->color = BLACK;      // Case 3
                gp->color = RED;
                right_rotate(root, gp);
            }
        } else {
            // 对称版本:父在祖父的右边,操作镜像翻转
            Node *u = gp->left;
            if (u->color == RED) {
                z->parent->color = BLACK;
                u->color = BLACK;
                gp->color = RED;
                z = gp;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    right_rotate(root, z);
                }
                z->parent->color = BLACK;
                gp->color = RED;
                left_rotate(root, gp);
            }
        }
    }
    (*root)->color = BLACK;    // 根始终是黑
}

删除:更复杂,但同样有套路

删除分两步:先按 BST 删除(找到节点,可能用后继替换),再判断是否破坏红黑性质 —— 如果删除的是黑节点,某条路径黑高减 1,需要"补一个黑"。

// 后继替换:如果被删节点 z 有两个子,
// 用它"中序后继"y(右子树最小节点)的 key 覆盖 z,然后实际删 y
//
// 真正被"删除"的节点:要么没子,要么只有一个子(被 y 替换的那种)
// 用 x 表示替换后填上来的节点
//
// 如果被删节点本来是红:直接删完事,红黑性质不破坏
// 如果被删节点是黑:x 处的黑高比兄弟少 1,需要修复

删除修复的四种情形

修复循环里,x 表示"少了一个黑"的位置,我们试图把这个"缺失的黑"消化掉。每一步以 x 是父节点左孩子为例,反向对称。w 表示 x 的兄弟。

// Case 1:兄弟 w 是红
//   父染红、w 染黑,左旋父。转化为 w 为黑的情形继续处理。
//
// Case 2:w 是黑,w 的两个子都是黑
//   w 染红,x = x.parent 上移。黑高问题向上传递。
//
// Case 3:w 是黑,w 的右子是黑、左子是红
//   w 的左子染黑、w 染红,右旋 w。转化为 Case 4。
//
// Case 4:w 是黑,w 的右子是红
//   w 染成父亲的颜色,父染黑,w 的右子染黑,左旋父。完成。
//
// 完整代码篇幅长,关键是循环条件:x 不是根 && x 是黑色

记不住这四种情形完全正常 —— 工程上几乎没人手写红黑树,标准库都给好了。理解到"插入修复涉及叔叔,删除修复涉及兄弟,二者都是为了把局部破坏的黑高/红连规则转化为合法状态"这个层面,已经足够支撑面试和代码阅读。

JavaScript 版的简化实现

下面给一个简化但能跑的 JS 版本,适合理解算法,不追求工业强度:

class Node {
    constructor(key, color = 'red') {
        this.key = key; this.color = color;
        this.left = this.right = this.parent = null;
    }
}

class RBTree {
    constructor() { this.root = null; }

    leftRotate(x) {
        const y = x.right;
        x.right = y.left;
        if (y.left) y.left.parent = x;
        y.parent = x.parent;
        if (!x.parent) this.root = y;
        else if (x === x.parent.left) x.parent.left = y;
        else x.parent.right = y;
        y.left = x; x.parent = y;
    }
    rightRotate(y) { /* 对称 */ }

    insert(key) {
        const z = new Node(key);
        let y = null, x = this.root;
        while (x) { y = x; x = (key < x.key) ? x.left : x.right; }
        z.parent = y;
        if (!y) this.root = z;
        else if (key < y.key) y.left = z;
        else y.right = z;
        this.insertFixup(z);
    }

    insertFixup(z) {
        while (z.parent && z.parent.color === 'red') {
            const gp = z.parent.parent;
            if (z.parent === gp.left) {
                const u = gp.right;
                if (u && u.color === 'red') {
                    z.parent.color = 'black'; u.color = 'black';
                    gp.color = 'red'; z = gp;
                } else {
                    if (z === z.parent.right) { z = z.parent; this.leftRotate(z); }
                    z.parent.color = 'black'; gp.color = 'red';
                    this.rightRotate(gp);
                }
            } else {
                // 镜像
            }
        }
        this.root.color = 'black';
    }
}

红黑树 vs B+ 树 vs 跳表

同样是"有序结构",这三个家伙各有舞台:

• 红黑树:适合"内存里的有序集合",每个节点很轻(2~4 个指针 + key),操作 O(log n),节点散落在内存里。STL map、Java TreeMap、Linux CFS 调度器全用它。
• B+ 树:适合"磁盘上的索引"。每个节点存几百个 key,矮胖,层数少,适配"一次 I/O 读一整块"的磁盘特性。MySQL、PostgreSQL 的索引都是它。
• 跳表:概念简单,实现起来比红黑树容易,性能接近。Redis 的有序集合 zset 选了跳表而不是红黑树,作者明说就是因为"跳表代码简单、并发友好、范围查询好实现"。

实战:用 Map 当红黑树用

除了 Linux 内核开发,日常工程里你几乎不会手写红黑树。但你会用它,只是名字不同:

// C++ STL map / set:底层就是红黑树
std::map<int, std::string> m;
m[1] = "one"; m[2] = "two";
auto it = m.lower_bound(1);    // 二分查找,O(log n)

// Java TreeMap / TreeSet:红黑树
TreeMap<Integer, String> tm = new TreeMap<>();
tm.firstKey(); tm.ceilingKey(5);

// Go 没有内置,用第三方包或自己实现
// 也可以用 btree 包或 redis 的 zset 思路用跳表

记住一个判断:当你需要"按 key 顺序遍历"或"找最接近某个 key 的元素"时,普通 HashMap 不够,要找有序映射 —— 这背后往往是红黑树或跳表。

写在最后

红黑树是"复杂度恰到好处"的工程经典 —— 它没有 AVL 那么严格(避免频繁旋转),也比简单 BST 鲁棒(避免最坏退化)。背后的五条规则不是凭空设计的,它们是从"想要 O(log n) 高度"反推出的最小约束集。

给学习者一个建议:不要试图一开始就背诵插入/删除修复的所有 case,先把五条规则、旋转、染色这三个基础动作搞熟,然后亲手在纸上画 1~10 这十个数依次插入的过程,把每个 case 走一遍 —— 走过两三次,你对"什么时候要旋转、什么时候只染色"的直觉就建立起来了。理解了这层,看 Linux 内核里那段几百行的 rbtree.c 就不再是天书。

—— 别看了 · 2026