C++红黑树实现：从插入修正到平衡验证

插入与修正

插入逻辑分两步：先像普通 BST 一样找到位置插入，然后回头修复颜色冲突。如果插入时父节点是黑色，什么都不用做；只有父节点是红色才需要调整。

调整的核心在于看叔叔节点的颜色。

叔叔是红色

这种情况最简单：parent 和 uncle 都变黑，grandfather 变红。然后 grandfather 可能又和它的父节点冲突，于是把 grandfather 当成新插入的红色节点向上递归处理。如果递归到根节点，记得强制把它刷黑。

叔叔不存在或是黑色

这时候就需要旋转了。根据当前节点、父节点、祖父节点的位置关系，可以分为四种类型：

• LL：父在祖左，子在父左 → 右单旋祖父，父变黑，祖变红。
• RR：父在祖右，子在父右 → 左单旋祖父，父变黑，祖变红。
• LR：父在祖左，子在父右 → 先左旋父（变成 LL），再右旋祖父，然后当前节点变黑，祖变红。
• RL：父在祖右，子在父左 → 先右旋父（变成 RR），再左旋祖父，当前节点变黑，祖变红。

旋转代码和 AVL 差不多，区别是不用维护平衡因子，只需要处理好父指针和颜色。写左旋的时候尤其要注意父节点是根的情况，_root 要重新绑定。

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

下面是完整的 insert 实现，把查找、插入和修正合在一起：

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

自平衡验证

写完插入逻辑之后，最好有个自查工具。我一般会检查两件事：根必须是黑色，以及所有叶子路径上的黑色节点数量一致。

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

这里 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;
}

和 AVL 的区别

AVL 追求严格平衡，任何操作后子树高度差不超过 1。这在查询密集的场景很有优势，但一旦写入频繁，为了维持平衡而做的旋转代价就上来了。红黑树通过放宽平衡条件，换取了更少的旋转次数。工程上很少用 AVL，STL 用红黑树是权衡后的结果——大多数系统的读写比例没那么极端。

如果你自己写个测试，对比有序插入和随机插入下的树高和旋转次数，红黑树的优势会很明显。