C++ 红黑树原理与实现详解

3. 红黑树的插入实现

插入逻辑分为两步：先按二叉搜索树（BST）规则找到位置插入，再根据红黑树性质进行修正。

插入策略

1. 空树：直接插入并设为黑色。
2. 非空树：新结点默认为红色。如果父节点是黑色，无需调整；如果父节点是红色，则违反性质 3，需要调整。

调整逻辑

当父节点为红色时，我们需要检查叔叔节点（Parent 的兄弟）的颜色。

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

此时 Parent 和 Uncle 都是红色，Grandfather 必然是黑色。

• 操作：将 Parent 和 Uncle 变为黑色，Grandfather 变为红色。
• 后续：Grandfather 变红可能导致祖父与其父冲突，因此将 Grandfather 视为当前新插入节点，继续向上递归处理。若 Grandfather 最终变成根节点，则强制设为黑色。

情况二：叔叔不存在或为黑色

此时需要通过旋转来解决冲突，具体取决于当前节点、父节点、祖父节点的相对位置。

1. LL 型（左左）：父节点在祖父左侧，当前节点在父节点左侧。
   • 操作：右单旋 + 变色（父变黑，祖父变红）。
2. RR 型（右右）：父节点在祖父右侧，当前节点在父节点右侧。
   • 操作：左单旋 + 变色（父变黑，祖父变红）。
3. LR 型（左右）：父节点在祖父左侧，当前节点在父节点右侧。
   • 操作：先左单旋（转为 LL 型），再右单旋 + 变色。
4. RL 型（右左）：父节点在祖父右侧，当前节点在父节点左侧。
   • 操作：先右单旋（转为 RR 型），再左单旋 + 变色。

旋转操作

旋转逻辑与 AVL 树类似，但无需更新平衡因子，只需维护指针关系和颜色。

// 左单旋
void RotateL(Node* parent) {
    if (parent == nullptr || parent->_right == nullptr) return;
    Node* curNode = parent->_right;
    Node* curLeft = curNode->_left;

    parent->_right = curLeft;
    if (curLeft) curLeft->_parent = parent;

    if (parent == _root) {
        _root = curNode;
        curNode->_parent = nullptr;
        parent->_parent = curNode;
        curNode->_left = parent;
    } else {
        Node* ppNode = parent->_parent;
        if (parent == ppNode->_left) ppNode->_left = curNode;
        else ppNode->_right = curNode;
        curNode->_parent = ppNode;
        parent->_parent = curNode;
        curNode->_left = parent;
    }
}

// 右单旋
void RotateR(Node* parent) {
    if (parent == nullptr || parent->_left == nullptr) return;
    Node* curNode = parent->_left;
    Node* curRight = curNode->_right;

    parent->_left = curRight;
    if (curRight) curRight->_parent = parent;

    if (parent == _root) {
        _root = curNode;
        curNode->_parent = nullptr;
        parent->_parent = curNode;
        curNode->_right = parent;
    } else {
        Node* ppNode = parent->_parent;
        if (parent == ppNode->_left) ppNode->_left = curNode;
        else ppNode->_right = curNode;
        curNode->_parent = ppNode;
        parent->_parent = curNode;
        curNode->_right = parent;
    }
}

完整插入代码

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

    Node* parent = nullptr;
    Node* curNode = _root;

    while (curNode) {
        if (kv.first < curNode->_kv.first) {
            parent = curNode;
            curNode = curNode->_left;
        } else if (kv.first > curNode->_kv.first) {
            parent = curNode;
            curNode = curNode->_right;
        } else {
            return false; // 不允许重复
        }
    }

    curNode = new Node(kv);
    if (curNode->_kv.first < parent->_kv.first)
        parent->_left = curNode;
    else
        parent->_right = curNode;
    curNode->_parent = parent;

    // 调整红黑树性质
    while (parent && parent->_col == Red) {
        Node* grandFather = parent->_parent;

        if (parent == grandFather->_left) {
            Node* uncle = grandFather->_right;
            if (uncle && uncle->_col == Red) {
                // 变色
                parent->_col = uncle->_col = Black;
                grandFather->_col = Red;
                curNode = grandFather;
                parent = curNode->_parent;
            } else {
                // 旋转
                if (curNode == parent->_left) {
                    RotateR(grandFather);
                    parent->_col = Black;
                    grandFather->_col = Red;
                } else {
                    RotateL(parent);
                    RotateR(grandFather);
                    curNode->_col = Black;
                    grandFather->_col = Red;
                }
                break;
            }
        } else {
            Node* uncle = grandFather->_left;
            if (uncle && uncle->_col == Red) {
                parent->_col = uncle->_col = Black;
                grandFather->_col = Red;
                curNode = grandFather;
                parent = curNode->_parent;
            } else {
                if (curNode == parent->_right) {
                    RotateL(grandFather);
                    parent->_col = Black;
                    grandFather->_col = Red;
                } else {
                    RotateR(parent);
                    RotateL(grandFather);
                    curNode->_col = Black;
                    grandFather->_col = Red;
                }
                break;
            }
        }
    }
    _root->_col = Black;
    return true;
}

4. 验证红黑树

判断是否平衡

主要检查两点：根节点是否为黑，以及每条路径上的黑色节点数量是否一致。

bool isBalance() {
    return _isBalance(_root);
}

bool _isBalance(Node* root = nullptr) {
    if (root == nullptr) return true;
    if (root->_col != Black) return false;

    int benchmark = 0;
    Node* cur = _root;
    while (cur) {
        if (cur->_col == Black) ++benchmark;
        cur = cur->_left;
    }
    return CheckColour(root, 0, benchmark);
}

bool CheckColour(Node* root, int blacknum, int benchmark) {
    if (root == nullptr) {
        if (blacknum != benchmark) return false;
        return true;
    }

    if (root->_col == Black) ++blacknum;

    if (root->_col == Red && root->_parent && root->_parent->_col == Red) {
        std::cout << root->_kv.first << "出现连续红色节点" << std::endl;
        return false;
    }

    return CheckColour(root->_left, blacknum, benchmark) &&
           CheckColour(root->_right, blacknum, benchmark);
}

注意 CheckColour 中 blacknum 采用传值方式，确保每条递归路径独立计数。

求树的高度

int Height() {
    return _Height(_root);
}

int _Height(Node* root = nullptr) {
    if (root == nullptr) return 0;
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

5. 性能对比

红黑树与 AVL 树的时间复杂度均为 O(log N)。区别在于：

• AVL 树：严格平衡，查询效率高，但插入/删除时的旋转代价大。
• 红黑树：近似平衡，插入/删除时的旋转次数少，工程实践中更常用（如 STL map/set）。

测试通常包括插入有序数据和随机数据，观察树的高度及旋转次数。红黑树在处理大量数据时，旋转次数显著低于 AVL 树。

6. 结语

红黑树通过颜色标记与旋转调整，在插入与删除操作频繁的场景下有效避免了 AVL 树的高频旋转问题。它不追求完美平衡，而是保证最长路径不超过最短路径的 2 倍，用简单的局部操作换取全局效率，是 C++ STL 底层数据结构的重要基石。