C++ STL 核心数据结构：红黑树详解

情况 3：变色 + 双旋 当 c 为红，p 为红，且 u 不存在或为黑时：

• 左右型（p 是 g 左孩子，c 是 p 右孩子）：先以 p 为中心左单旋，再以 g 为中心右单旋。c 染黑，g 染红。
• 右左型（p 是 g 右孩子，c 是 p 左孩子）：先以 p 为中心右单旋，再以 g 为中心左单旋。c 染黑，g 染红。
• 效果：将不平衡结构转化为情况 2 的可处理形态。

代码实现

节点存储结构

红黑树节点需要存储键值对、左右子指针、父指针以及颜色信息。

enum Colour {
    RED,
    BLACK
};

template<class K, class V>
struct RBTreeNode {
    pair<K, V> _kv;
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};

类模板定义

template<class K, class V>
class RBTree {
private:
    typedef RBTreeNode<K, V> Node;
    Node* _root = nullptr;

    // 私有辅助函数
    void _InOrder(Node* root);
    int _Height(Node* root);
    int _Size(Node* root);
    bool Check(Node* root, int blackNum, const int refNum);

public:
    // 公有接口
    Node* Find(const K& key);
    bool Insert(const pair<K, V>& kv);
    void InOrder();
    bool IsRBTree();
};

核心逻辑实现

查找

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

插入与调整

插入过程分为定位、连接和调整三个阶段。调整阶段需循环处理直到满足红黑性质。

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

    Node* current = _root;
    Node* parent = nullptr;

    // 1. 查找插入位置
    while (current) {
        if (current->_kv.first < kv.first) {
            parent = current;
            current = current->_right;
        } else if (current->_kv.first > kv.first) {
            parent = current;
            current = current->_left;
        } else {
            return false; // 键已存在
        }
    }

    // 2. 创建并连接新节点
    current = new Node(kv);
    current->_col = RED;
    if (kv.first < parent->_kv.first) {
        parent->_left = current;
    } else {
        parent->_right = current;
    }
    current->_parent = parent;

    // 3. 调整平衡
    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        
        if (parent == grandfather->_left) {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) {
                // 变色
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;
                current = grandfather;
                parent = grandfather->_parent;
            } else {
                // 旋转
                if (current == parent->_left) {
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    RotateL(parent);
                    RotateR(grandfather);
                    current->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        } else {
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED) {
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;
                current = grandfather;
                parent = grandfather->_parent;
            } else {
                if (current == parent->_right) {
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                } else {
                    RotateR(parent);
                    RotateL(grandfather);
                    current->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return true;
}

旋转操作

void RotateR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = parent->_left->_right;
    Node* pParent = parent->_parent;

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

    parent->_parent = subL;
    subL->_right = parent;

    if (parent == _root) {
        _root = subL;
        subL->_parent = nullptr;
    } else {
        if (parent == pParent->_left) {
            pParent->_left = subL;
        } else {
            pParent->_right = subL;
        }
        subL->_parent = pParent;
    }
}

void RotateL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = parent->_right->_left;
    Node* pParent = parent->_parent;

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

    parent->_parent = subR;
    subR->_left = parent;

    if (parent == _root) {
        _root = subR;
        subR->_parent = nullptr;
    } else {
        if (parent == pParent->_left) {
            pParent->_left = subR;
        } else {
            pParent->_right = subR;
        }
        subR->_parent = pParent;
    }
}

验证方法

直接通过最长路径与最短路径的倍数关系验证是不可靠的，应严格校验四条核心规则：

1. 颜色合法性（枚举天然保证）。
2. 根节点为黑色。
3. 红色节点的子节点必须为黑色（反向校验父节点更高效）。
4. 任意路径黑色节点数量一致（前序遍历计数对比）。

bool Check(Node* root, int blackNum, const int refNum) {
    if (root == nullptr) {
        return refNum == blackNum;
    }
    if (root->_col == RED && root->_parent->_col == RED) {
        return false;
    }
    if (root->_col == BLACK) {
        blackNum++;
    }
    return Check(root->_left, blackNum, refNum) && 
           Check(root->_right, blackNum, refNum);
}

bool IsRBTree() {
    if (!_root) return true;
    if (_root->_col == RED) return false;
    
    int refNum = 0;
    Node* current = _root;
    while (current) {
        if (current->_col == BLACK) ++refNum;
        current = current->_left;
    }
    return Check(_root, 0, refNum);
}

性能对比

为了直观展示红黑树与 AVL 树的性能差异，我们在百万级数据规模下进行了测试。测试包括插入耗时、查找耗时、树的高度及节点数量。

void TestBST() {
    const int N = 1000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; i++) {
        v.push_back(rand() + i);
    }

    // AVL 树测试
    AVLTree<int, int> avl;
    size_t begin1 = clock();
    for (auto it : v) avl.Insert(make_pair(it, it));
    size_t end1 = clock();

    // 红黑树测试
    RBTree<int, int> rb;
    size_t begin2 = clock();
    for (auto it : v) rb.Insert(make_pair(it, it));
    size_t end2 = clock();

    cout << "AVL Insert: " << end1 - begin1 << endl;
    cout << "RB Insert: " << end2 - begin2 << endl;
    // ... 后续查找与平衡性验证
}

运行结果表明，在大量随机数据插入场景下，红黑树的总耗时通常低于 AVL 树，这得益于其较少的旋转次数。两者在查找性能和最终平衡性上表现相当，均能满足高效检索的需求。