C++ 实现红黑树：深入 STL map 底层原理

2.2 插入逻辑详解

插入新节点时，先按二叉搜索树规则找到位置。关键点在于：如果是空树，根节点设为黑色；否则新节点设为红色。因为如果新节点设为黑色，会直接破坏规则 4（黑色高度不一致）。

若父亲节点是黑色，无需调整。若父亲是红色，则违反规则 3，需通过变色或旋转修复。这里定义 cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点。

情况 1：叔叔存在且为红（变色）

当 p 和 u 都是红色时，将 p 和 u 变黑，g 变红。此时 g 可能违反规则 2（若 g 是根）或规则 3（若 g 的父亲也是红），所以将 g 视为新的 cur 继续向上检查。

情况 2：单旋 + 变色

当叔叔不存在或为黑色，且 cur 与 p 同侧（如左左或右右）时，进行单旋。例如 p 是 g 的左孩子，cur 是 p 的左孩子，则以 g 为轴右旋，并将 p 变黑、g 变红。

情况 3：双旋 + 变色

当叔叔不存在或为黑色，但 cur 与 p 异侧（如左右或右左）时，需先以 p 为轴旋转一次，再按情况 2 处理。例如 p 是 g 的左，cur 是 p 的右，先左旋 p，再右旋 g，最后调整颜色。

2.3 插入代码实现

下面展示完整的插入流程，包含了查找、插入及三种情况的修复逻辑。

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false; // 已存在
        }
    }

    cur = new Node(kv);
    cur->_col = RED;
    if (parent->_kv.first < kv.first) {
        parent->_right = cur;
    } else {
        parent->_left = cur;
    }
    cur->_parent = parent;

    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        if (parent == grandfather->_left) {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) {
                // 情况 1：变色
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // 情况 2/3：旋转
                if (cur == parent->_left) {
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        } else {
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED) {
                // 情况 1：变色
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // 情况 2/3：旋转
                if (cur == parent->_right) {
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return true;
}

旋转逻辑与 AVL 树类似，主要区别在于不需要维护平衡因子，只需调整指针和颜色。

2.4 查找功能

查找遵循标准二叉搜索树逻辑，时间复杂度 O(logN)。

Node* Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < key) {
            cur = cur->_right;
        } else if (cur->_kv.first > key) {
            cur = cur->_left;
        } else {
            return cur;
        }
    }
    return nullptr;
}

2.5 验证平衡性

验证不能只看路径长度，必须检查四条规则。递归检查每条路径的黑色节点数是否一致，以及是否存在连续红节点。

bool Check(Node* root, int blackNum, const int refNum) {
    if (root == nullptr) {
        if (refNum != blackNum) {
            cout << "存在黑色结点数量不相等的路径" << endl;
            return false;
        }
        return true;
    }
    if (root->_col == RED && root->_parent->_col == RED) {
        cout << root->_kv.first << "存在连续的红色结点" << endl;
        return false;
    }
    if (root->_col == BLACK) {
        blackNum++;
    }
    return Check(root->_left, blackNum, refNum) && 
           Check(root->_right, blackNum, refNum);
}

bool IsBalance() {
    if (_root == nullptr) return true;
    if (_root->_col == RED) return false;

    int refNum = 0;
    Node* cur = _root;
    while (cur) {
        if (cur->_col == BLACK) ++refNum;
        cur = cur->_left;
    }
    return Check(_root, 0, refNum);
}

通过上述步骤，我们完成了红黑树的核心构建。理解这些细节对于掌握 STL 容器（如 map, set）的底层行为至关重要。