C++ 手写红黑树：从插入到平衡验证，一次讲透 STL map 底层

插入逻辑

插入的大致过程

1. 按二叉搜索树规则找到要插入的位置。
2. 如果是空树，新增节点直接设为黑色；如果不是，新增节点必须为红色（否则会破坏规则 4 的等黑高约束）。
3. 如果新节点的父亲是黑色，插入完成；如果父亲是红色，违反了规则 3，需要进一步处理。

后面统一用 c 表示当前节点（cur），p 表示父节点（parent），g 表示祖父节点（grandfather），u 表示叔叔节点（uncle，即 p 的兄弟）。

三种调整情况

情况 1：变色

• 条件：c 为红，p 为红，g 为黑，u 存在且为红。
• 处理：将 p 和 u 变黑，g 变红，然后把 g 当成新的 c 继续向上修正。如果 g 是根，最后再把 g 变回黑色。

情况 2：单旋 + 变色

• 条件：c 为红，p 为红，g 为黑，u 不存在或为黑。
• 处理：
  • 当 p 是 g 的左孩子，c 是 p 的左孩子时：以 g 为轴做右单旋，然后把 p 变黑，g 变红。
  • 当 p 是 g 的右孩子，c 是 p 的右孩子时：以 g 为轴做左单旋，然后把 p 变黑，g 变红。

情况 3：双旋 + 变色

• 条件：c 为红，p 为红，g 为黑，u 不存在或为黑，且 c 与 p 的方向不一致。
• 处理：
  • 当 p 是 g 的左孩子，c 是 p 的右孩子时：先以 p 为轴左单旋，再以 g 为轴右单旋，最后把 c 变黑，g 变红。
  • 当 p 是 g 的右孩子，c 是 p 的左孩子时：先以 p 为轴右单旋，再以 g 为轴左单旋，最后把 c 变黑，g 变红。

插入代码实现

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 树的实现类似，只需要调整指针，不用维护平衡因子。

查找功能

按标准的二叉搜索树查找逻辑实现，时间复杂度 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 倍是不够的，因为即使长度满足条件，颜色规则也可能已被破坏。可靠的做法是检验三条性质：

1. 根节点是黑色。
2. 没有连续的红色节点。
3. 每条从根到 NIL 的路径上黑色节点数相等。

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);
}