深度解析红黑树（RBT）：从十二字口诀到 C++ 工程实现

Hello大家好，这里是小丑爱！

在高级数据结构中，红黑树（Red-Black Tree） 无疑是最负盛名的平衡树之一。它不仅是 C++ STL 中 std::map 和 std::set 的底层基石，也广泛应用于 Linux 内核的调度器和 Nginx 的定时器。

一、 核心定义：十二字口诀

红黑树本质上是一棵满足特定“颜色规则”的二叉排序树（BST）。为了方便记忆，我们可以将其性质总结为：

左根右，根叶黑，不红红，黑路同

1. 左根右：满足二叉排序树的基本性质，即左子树 < 根 < 右子树。
2. 根叶黑：根结点必为黑色；所有叶结点（虚构的空结点 NIL）也必为黑色。
3. 不红红：不存在两个相邻的红结点（红结点的父子皆为黑）。
4. 黑路同：从任一结点到其每个叶子的所有简单路径上，所含黑色结点的数量相同。

关键概念：黑高（Black Height）

从某结点出发（不含该结点）到达一个叶结点的简单路径上的黑结点总数。红黑树的黑高即为根结点的黑高。

---

二、 红黑树的硬核结论

为什么红黑树被称为“近似平衡”？

1. 路径长度限制：从根到叶结点的最长路径不大于最短路径的 2 倍。
   • 最短路径：全黑。
   • 最长路径：黑红相间（受限于“不红红”性质）。
2. 树高保证：拥有 n个内部结点的红黑树，其高度 h ≤ 2log₂(n + 1)。
3. 性能折中：查找、插入和删除的复杂度均为 O(log n)。相较于 AVL 树的严格平衡，红黑树在动态插入和删除时需要的旋转次数更少，更适合增删频繁的场景。

---

三、 插入操作：看“叔叔”的眼色

插入新结点时，我们初始着为红色（原因：涂成黑色会立即破坏“黑路同”性质，代价更大）。如果父结点也是红色，则违反了“不红红”，需要修复。

修复的核心逻辑在于观察 叔叔结点 (Uncle) 的颜色：

1. 叔叔是红色的（染色 + 变新）

• 动作：将父和叔染色为黑，爷染色为红。
• 后续：将爷结点看作新结点，继续向上递归。

2. 叔叔是黑色的（旋转 + 染色）

根据新结点（N）、父（P）、爷（G）的相对位置： * LL型：右单旋，父换爷+染色 * RR型：左单旋，父换爷+染色 * LR型：左、右双旋，儿换爷+染色 * RL型：右、左双旋，儿换爷+染色

---

四、 删除操作：处理“双黑”结点

删除操作的处理方式同 BST 类似，但如果删除的是黑色结点，会破坏“黑路同”特性。此时引入“双黑”结点的概念，并根据 兄弟结点 (Sibling) 的颜色及孩子情况进行 4 种 Case 的调整。

• Case 1：兄弟是红色的。
• Case 2：兄弟是黑色的，且兄弟的孩子全黑。
• Case 3：兄弟是黑色的，兄弟孩子“内红外黑”。
• Case 4：兄弟是黑色的，兄弟孩子“外红”。

为了方便分析，我们假设当前双黑结点 N 是其父结点 P 的左孩子，它的兄弟结点为 S。（如果是右孩子，方向完全对称）。

Case 1：兄弟 S 是红色的

这是唯一一种兄弟是红色的情况。既然兄弟是红色的，那么根据“不红红”性质，父结点 P 必然是黑色的，且兄弟的孩子必然都是黑色的。

• 痛点：兄弟是红色的，我们没办法从兄弟那里“借”黑色过来帮忙。
• 策略：通过旋转，把兄弟变成黑色的。
• 操作：
  1. 将兄弟 S 染为黑色。
  2. 将父结点 P 染为红色。
  3. 对父结点 P 进行左旋。
• 结果：旋转后，N 的新兄弟变成了原兄弟 S 的一个黑色子结点。双黑问题并没有立刻解决，但这将情况转换成了 Case 2、3 或 4，然后继续处理。

---

Case 2：兄弟 S 是黑色的，且兄弟的两个孩子全黑

兄弟是黑色的，而且兄弟的两个孩子也是黑色的。这说明兄弟结点“很穷”，没有多余的红色结点可以借给我们用来染色补偿。

• 策略：既然大家都缺黑色，那就一起把“黑色”推给父结点。
• 操作：
  1. 把兄弟 S 染为红色（相当于从兄弟身上剥夺了一个黑色）。
  2. 双黑结点 N 脱去一层黑色，变回普通的黑色结点。
  3. 剥夺出来的这一层黑色，推给父结点 P。
• 结果：
  • 如果父结点 P 原本是红色的，它吸收了这个黑色后变成黑色，修复完成！
  • 如果父结点 P 原本是黑色的，它吸收了这个黑色后变成了新的“双黑”结点。此时，我们将 P 视作新的 N，继续向上层循环这 4 种 Case。

---

Case 3：兄弟 S 是黑色的，兄弟孩子“内红外黑”

所谓“内”和“外”，是相对于双黑结点 N 的位置。因为 N 是左孩子，所以 S 的左孩子就是“内”（靠得近），右孩子就是“外”（离得远）。

此时的局面是：兄弟 S 是黑色的，S 的左孩子（内）是红色，S 的右孩子（外）是黑色。

• 痛点：我们要把情况转化为最容易解决的 Case 4（外侧有红孩子），所以需要把这个红色的内侧孩子转到外侧去。
• 操作：
  1. 将兄弟 S 染为红色。
  2. 将 S 的左孩子（内红）染为黑色。
  3. 对兄弟 S 进行右旋。
• 结果：旋转后，N 的新兄弟变黑了，并且新兄弟的右孩子（外侧）变成了红色。这完美地转换成了 Case 4。

---

Case 4：兄弟 S 是黑色的，兄弟孩子“外红”

这是最终极、也是最能终结问题的情况。兄弟是黑色的，且兄弟的右孩子（外侧）是红色的（左孩子是什么颜色无所谓）。

• 策略：通过旋转和借用这个红色的外侧孩子，彻底消化掉 N 的双黑属性。
• 操作：
  1. 将兄弟 S 的颜色染成父结点 P 的颜色。
  2. 将父结点 P 染为黑色。
  3. 将兄弟 S 的右孩子（外红）染为黑色。
  4. 对父结点 P 进行左旋。
• 结果：经过这一套组合拳，左旋操作把父结点 P 压到了左边，补足了 N 这条路径上缺失的黑色。而原本兄弟那边的红色外侧孩子被染黑，补足了兄弟那条路径上的黑色。双黑属性彻底消除，红黑树重新平衡，结束！

---

梳理一下这 4 种 Case 的状态流转机制：

如果把这 4 种 Case 看作一个状态机，它的流转非常清晰：

• Case 1 → 必然转化为 Case 2, 3 或 4。
• Case 3 → 必然转化为 Case 4。
• Case 4 → 终结（树恢复平衡）。
• Case 2 → 终结（如果父结点原为红），或者 向上递归（如果父结点原为黑）。

注意！！！

这个部分的内容小丑爱强烈建议大家用可视化工具帮助理解

USFCA Visualization

非常好用！！！

---

五、 C++ 工程实现

下面是一个完整的红黑树类定义，采用了 NIL 哨兵结点方案，可以有效减少代码中对空指针的判断。但是一般来说用不到吧。太复杂了。

#include <iostream>

// 定义颜色枚举
enum Color { RED, BLACK };

// 红黑树节点结构
struct Node {
    int data;
    Color color;
    Node *left, *right, *parent;

    Node(int val) : data(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

class RBTree {
private:
    Node *root;
    Node *NIL; // 哨兵节点，代表所有的外部叶子节点(黑色)

    // 左旋
    void leftRotate(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 == nullptr) {
            root = y;
        } else if (x == x->parent->left) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }
        y->left = x;
        x->parent = y;
    }

    // 右旋
    void rightRotate(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 == nullptr) {
            root = x;
        } else if (y == y->parent->left) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }
        x->right = y;
        y->parent = x;
    }

    // 插入修复
    void insertFixup(Node *k) {
        Node *u;
        while (k->parent->color == RED) {
            if (k->parent == k->parent->parent->left) {
                u = k->parent->parent->right; // 叔叔节点
                if (u->color == RED) {
                    // Case 1: 叔叔是红色
                    u->color = BLACK;
                    k->parent->color = BLACK;
                    k->parent->parent->color = RED;
                    k = k->parent->parent;
                } else {
                    if (k == k->parent->right) {
                        // Case 2: 叔叔是黑色，当前节点是右孩子
                        k = k->parent;
                        leftRotate(k);
                    }
                    // Case 3: 叔叔是黑色，当前节点是左孩子
                    k->parent->color = BLACK;
                    k->parent->parent->color = RED;
                    rightRotate(k->parent->parent);
                }
            } else {
                // 对称情况：父节点是祖父节点的右孩子
                u = k->parent->parent->left; 
                if (u->color == RED) {
                    u->color = BLACK;
                    k->parent->color = BLACK;
                    k->parent->parent->color = RED;
                    k = k->parent->parent;
                } else {
                    if (k == k->parent->left) {
                        k = k->parent;
                        rightRotate(k);
                    }
                    k->parent->color = BLACK;
                    k->parent->parent->color = RED;
                    leftRotate(k->parent->parent);
                }
            }
            if (k == root) break;
        }
        root->color = BLACK; // 根节点始终为黑
    }

    // 节点替换（用于删除操作）
    void transplant(Node *u, Node *v) {
        if (u->parent == nullptr) {
            root = v;
        } else if (u == u->parent->left) {
            u->parent->left = v;
        } else {
            u->parent->right = v;
        }
        v->parent = u->parent;
    }

    // 寻找子树的最小节点
    Node* treeMinimum(Node *node) {
        while (node->left != NIL) {
            node = node->left;
        }
        return node;
    }

    // 删除修复
    void removeFixup(Node *x) {
        Node *s;
        while (x != root && x->color == BLACK) {
            if (x == x->parent->left) {
                s = x->parent->right; // 兄弟节点
                // Case 1: 兄弟是红色
                if (s->color == RED) {
                    s->color = BLACK;
                    x->parent->color = RED;
                    leftRotate(x->parent);
                    s = x->parent->right;
                }
                // Case 2: 兄弟是黑色，且两个侄子都是黑色
                if (s->left->color == BLACK && s->right->color == BLACK) {
                    s->color = RED;
                    x = x->parent;
                } else {
                    // Case 3: 兄弟是黑色，左侄子红，右侄子黑
                    if (s->right->color == BLACK) {
                        s->left->color = BLACK;
                        s->color = RED;
                        rightRotate(s);
                        s = x->parent->right;
                    }
                    // Case 4: 兄弟是黑色，右侄子是红色
                    s->color = x->parent->color;
                    x->parent->color = BLACK;
                    s->right->color = BLACK;
                    leftRotate(x->parent);
                    x = root;
                }
            } else {
                // 对称情况：当前节点是右孩子
                s = x->parent->left;
                if (s->color == RED) {
                    s->color = BLACK;
                    x->parent->color = RED;
                    rightRotate(x->parent);
                    s = x->parent->left;
                }
                if (s->right->color == BLACK && s->left->color == BLACK) {
                    s->color = RED;
                    x = x->parent;
                } else {
                    if (s->left->color == BLACK) {
                        s->right->color = BLACK;
                        s->color = RED;
                        leftRotate(s);
                        s = x->parent->left;
                    }
                    s->color = x->parent->color;
                    x->parent->color = BLACK;
                    s->left->color = BLACK;
                    rightRotate(x->parent);
                    x = root;
                }
            }
        }
        x->color = BLACK;
    }

    // 中序遍历辅助函数
    void inorderHelper(Node *node) {
        if (node != NIL) {
            inorderHelper(node->left);
            std::cout << node->data << "(" << (node->color == RED ? "R" : "B") << ") ";
            inorderHelper(node->right);
        }
    }

public:
    RBTree() {
        NIL = new Node(0);
        NIL->color = BLACK;
        root = NIL;
    }

    // 插入节点
    void insert(int key) {
        Node *node = new Node(key);
        node->parent = nullptr;
        node->data = key;
        node->left = NIL;
        node->right = NIL;
        node->color = RED; // 新节点默认为红色

        Node *y = nullptr;
        Node *x = root;

        // 寻找插入位置
        while (x != NIL) {
            y = x;
            if (node->data < x->data) {
                x = x->left;
            } else {
                x = x->right;
            }
        }

        node->parent = y;
        if (y == nullptr) {
            root = node;
        } else if (node->data < y->data) {
            y->left = node;
        } else {
            y->right = node;
        }

        // 如果是根节点，直接染黑并返回
        if (node->parent == nullptr) {
            node->color = BLACK;
            return;
        }
        // 如果父节点是根节点，不会破坏规则，直接返回
        if (node->parent->parent == nullptr) {
            return;
        }

        // 核心：修复红黑树性质
        insertFixup(node);
    }

    // 删除节点
    void remove(int data) {
        Node *z = NIL;
        Node *node = root;
        // 查找节点
        while (node != NIL) {
            if (node->data == data) {
                z = node;
            }
            if (node->data <= data) {
                node = node->right;
            } else {
                node = node->left;
            }
        }

        if (z == NIL) {
            std::cout << "Node not found in the tree" << std::endl;
            return;
        }

        Node *y = z;
        Node *x;
        Color y_original_color = y->color;

        if (z->left == NIL) {
            x = z->right;
            transplant(z, z->right);
        } else if (z->right == NIL) {
            x = z->left;
            transplant(z, z->left);
        } else {
            y = treeMinimum(z->right);
            y_original_color = y->color;
            x = y->right;
            if (y->parent == z) {
                x->parent = y;
            } else {
                transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }
            transplant(z, y);
            y->left = z->left;
            y->left->parent = y;
            y->color = z->color;
        }
        delete z;
        
        // 核心：如果删除的节点原始颜色是黑色，需要修复
        if (y_original_color == BLACK) {
            removeFixup(x);
        }
    }

    // 打印中序遍历（包含颜色信息）
    void printInOrder() {
        inorderHelper(root);
        std::cout << std::endl;
    }
};

int main() {
    RBTree tree;
    
    // 测试插入
    int elements[] = {55, 40, 65, 60, 75, 57};
    for (int el : elements) {
        tree.insert(el);
    }
    
    std::cout << "插入后中序遍历 (R=红, B=黑): ";
    tree.printInOrder();

    // 测试删除
    std::cout << "删除节点 40..." << std::endl;
    tree.remove(40);
    
    std::cout << "删除后中序遍历: ";
    tree.printInOrder();

    return 0;
}

六、 总结：AVL 还是 RBT？

特性	AVL 树	红黑树 (RBT)
平衡程度	严格平衡（高度差  ≤ 1）	适度平衡
查找性能	极佳	优秀
插入/删除代价	较高（频繁旋转）	较低
应用场景	查找密集的场景（如数据库索引）	频繁变动的数据集（如内存管理）