深入解析C++红黑树实现机制

C++ 中红黑树是一种自平衡二叉搜索树，其底层实现通过一套严格的规则保证树的平衡，从而确保插入、删除、查找等操作的时间复杂度稳定在 O(log n)。以下是其核心实现机制的解析：

一、红黑树的核心特性（平衡的基础）

红黑树的节点分为红色或黑色，且必须满足以下 5 条规则：

节点颜色：每个节点要么是红色，要么是黑色。根节点：根节点必须是黑色。叶子节点（NIL 节点）：所有叶子节点（空节点，通常用 NIL 标记）都是黑色。红色节点的子节点：若一个节点是红色，则它的两个子节点必须是黑色（即不存在连续的红色节点）。路径黑色平衡：从任意节点到其所有叶子节点的路径中，黑色节点的数量必须相同（称为“黑高”）。

二、节点结构设计

红黑树的节点通常包含以下成员：


template <typename T>
struct Node {
    T data;          // 存储的数据
    Node* left;      // 左子节点
    Node* right;     // 右子节点
    Node* parent;    // 父节点（用于旋转和平衡）
    bool is_red;     // 颜色标记（true 为红，false 为黑）
    // 构造函数
    Node(const T& val) : data(val), left(nullptr), right(nullptr), parent(nullptr), is_red(true) {}
};

parent 指针：关键设计，用于在插入/删除后追溯祖先节点，进行平衡调整。默认颜色：新插入节点默认为红色（减少对“黑高”的影响，降低调整复杂度）。

三、核心操作：旋转（平衡的关键手段）

当插入或删除节点破坏红黑树特性时，通过旋转调整树的结构，配合颜色修改恢复平衡。旋转分为两种：

1. 左旋（Left Rotation）

以节点 x 为支点，将其右子树 y 旋转为新的父节点，x 成为 y 的左子节点，y 的左子树转为 x 的右子树。


// 左旋示意图：x 为支点，y 是 x 的右子节点
//      x               y
//                    /
//        y    →     x
//       /           
//      T2           T2
void left_rotate(Node* x) {
    Node* y = x->right;    // y 是 x 的右子节点
    x->right = y->left;    // x 的右子树指向 y 的左子树（T2）
    if (y->left != nullptr) {
        y->left->parent = x;  // T2 的父节点更新为 x
    }
    y->parent = x->parent;   // y 继承 x 的父节点
    if (x->parent == nullptr) {
        root = y;  // 若 x 是根节点，y 成为新根
    } else if (x == x->parent->left) {
        x->parent->left = y;  // x 是左子节点时，y 替代其位置
    } else {
        x->parent->right = y; // x 是右子节点时，y 替代其位置
    }
    y->left = x;    // x 成为 y 的左子节点
    x->parent = y;  // x 的父节点更新为 y
}

2. 右旋（Right Rotation）

与左旋对称，以节点 y 为支点，将其左子树 x 旋转为新的父节点。


// 右旋示意图：y 为支点，x 是 y 的左子节点
//        y           x
//       /             
//      x       →       y
//                    /
//        T2         T2
void right_rotate(Node* y) {
    Node* x = y->left;     // x 是 y 的左子节点
    y->left = x->right;    // y 的左子树指向 x 的右子树（T2）
    if (x->right != nullptr) {
        x->right->parent = y;  // T2 的父节点更新为 y
    }
    x->parent = y->parent;   // x 继承 y 的父节点
    if (y->parent == nullptr) {
        root = x;  // 若 y 是根节点，x 成为新根
    } else if (y == y->parent->left) {
        y->parent->left = x;  // y 是左子节点时，x 替代其位置
    } else {
        y->parent->right = x; // y 是右子节点时，x 替代其位置
    }
    x->right = y;   // y 成为 x 的右子节点
    y->parent = x;  // y 的父节点更新为 x
}

四、插入操作与平衡调整

插入流程：

按二叉搜索树规则插入新节点（默认为红色）。检查是否破坏红黑树特性（主要是“连续红色节点”问题），通过颜色修改和旋转恢复平衡。

插入后的调整场景（核心）

设新节点为 z，其父节点为 p，祖父节点为 g（必存在，否则无需调整），叔叔节点为 u（p 的兄弟）：

场景 1：u 是红色
解决：将 p 和 u 改为黑色，g 改为红色，然后以 g 为新节点继续向上检查。场景 2：u 是黑色（或 NIL），且 z 是 p 的右子节点，p 是 g 的左子节点（“右右”或“左右”形态）
解决：先对 p 左旋（转为场景 3），再对 g 右旋，最后修改 p 和 g 的颜色。场景 3：u 是黑色（或 NIL），且 z 是 p 的左子节点，p 是 g 的左子节点（“左左”形态）
解决：对 g 右旋，交换 p 和 g 的颜色。

最终确保根节点为黑色。

五、删除操作与平衡调整

删除流程更复杂，核心是：

按二叉搜索树规则删除节点（找到前驱/后继节点替代，简化为删除叶子或单孩子节点）。若删除的是黑色节点，会破坏“黑高”平衡，需通过双重黑色（double black） 标记和调整恢复：
若兄弟节点是红色，先旋转转为兄弟节点为黑色的场景。若兄弟节点是黑色，且其孩子节点满足条件，通过旋转+颜色修改消除“双重黑色”。若无法通过兄弟节点调整，将“双重黑色”向上传递，直到根节点（最后将根节点的双重黑色转为单黑色）。