C++ 红黑树核心原理与完整实现

3. 红黑树的插入与平衡调整

插入是红黑树最复杂的部分。新节点默认插入为红色，若违反规则则需调整。

3.1 插入流程

1. 若树为空，新节点设为根并染黑。
2. 若树非空，按 BST 规则插入，新节点染红。
3. 检查是否违反规则（主要是父子同红），若不违反直接结束；若违反，根据叔叔节点颜色分情况处理。

3.2 三种调整情况

假设当前节点为 cur，父节点为 p，祖父节点为 g，叔叔节点为 u。

情况一：叔叔节点存在且为红色

此时 p 和 u 均为红色，g 必为黑色。

• 策略：变色。p 和 u 变黑，g 变红。
• 后续：将 g 视为新的 cur 继续向上检查。若 g 变为根，则强制染黑。

情况二：叔叔节点不存在或为黑色，且为左左/右右型

• 策略：单旋 + 变色。
• 左左型：以 g 为轴右旋，p 变黑，g 变红。
• 右右型：以 g 为轴左旋，p 变黑，g 变红。
• 结果：调整后无需继续向上，因为局部已满足性质。

情况三：叔叔节点不存在或为黑色，且为左右/右左型

• 策略：双旋 + 变色。
• 左右型：先以 p 左旋，再以 g 右旋。
• 右左型：先以 p 右旋，再以 g 左旋。
• 变色：旋转后 cur 变黑，g 变红。

3.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->_left;
        } else if (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false; // 重复节点
        }
    }

    cur = new Node(kv);
    cur->_col = RED;
    cur->_parent = parent;

    if (parent->_kv.first < kv.first) parent->_right = cur;
    else parent->_left = cur;

    // 修复红黑树性质
    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        
        if (grandfather->_left == parent) {
            Node* uncle = grandfather->_right;
            
            // 情况一：叔叔存在且为红
            if (uncle && uncle->_col == RED) {
                grandfather->_col = RED;
                parent->_col = BLACK;
                uncle->_col = BLACK;
                cur = grandfather;
                parent = cur->_parent;
            } 
            // 情况二 & 三：叔叔黑或不存在
            else {
                if (parent->_left == cur) {
                    // 左左型：右单旋
                    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) {
                grandfather->_col = RED;
                parent->_col = BLACK;
                uncle->_col = BLACK;
                cur = grandfather;
                parent = cur->_parent;
            } 
            else {
                if (parent->_right == cur) {
                    // 右右型：左单旋
                    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;
}

4. 验证与测试

编写完红黑树后，验证至关重要。主要检查两点：无连续红节点、任意路径黑节点数相等。

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

5. 关于删除

红黑树的删除操作比插入更为复杂，涉及更多的旋转和变色组合。在实际工程中，建议直接使用标准库中的 std::map 或 std::set。若需深入理解，可参考《算法导论》相关章节。