C++ 进阶：STL 红黑树实现与原理分析

情况 2：变色 + 单旋

当叔叔节点 u 不存在，或 u 存在但为黑色时，仅靠变色无法解决连续红节点问题，需结合旋转 + 变色。

• 场景 A（左左型）：p 是 g 的左孩子，c 是 p 的左孩子。以 g 为旋转中心右单旋，p 染黑，g 染红。
• 场景 B（右右型）：p 是 g 的右孩子，c 是 p 的右孩子。以 g 为旋转中心左单旋，p 染黑，g 染红。

情况 3：变色 + 双旋

当叔叔节点 u 不存在，或 u 存在但为黑色，且结构为左右型或右左型时：

• 场景 1（左右型）：p 是 g 的左孩子，c 是 p 的右孩子。先以 p 为中心左单旋，再以 g 为中心右单旋。变色：c 染黑，g 染红。
• 场景 2（右左型）：p 是 g 的右孩子，c 是 p 的左孩子。先以 p 为中心右单旋，再以 g 为中心左单旋。变色：c 染黑，g 染红。

三、验证操作

直接通过最长路径与最短路径的倍数关系来验证红黑树是不可行的。正确的做法是直接校验红黑树的 4 条核心规则：

1. 颜色合法性：枚举定义天然保证。
2. 根节点颜色：直接检查根节点是否为黑色。
3. 红色节点的子节点合法性：反向校验，遍历节点时检查当前节点的父节点颜色。若父节点为红色且当前节点也为红色，即违规。
4. 路径黑色节点数量一致性：通过前序遍历 + 传递黑色节点计数实现。以第一条路径的黑色节点数量为参考值，后续逐一对比。

// 判断一棵树是不是红黑树
bool IsRBTree() {
    // 特殊情况：空树
    if (_root == nullptr) 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);
}

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

代码实现

红黑树的存储结构

节点的存储结构

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

enum Colour { RED, BLACK };

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

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

树的存储结构

类模板封装了根节点指针及各类操作接口。

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

    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        _InOrder(root->_right);
    }

    bool Check(Node* root, int blackNum, const int refNum) {
        if (root == nullptr) {
            if (refNum != blackNum) return false;
            return true;
        }
        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);
    }

public:
    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;

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

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

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

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

    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

    bool IsRBTree() {
        if (_root == nullptr) 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);
    }
};

测试文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "RBTree.h"
void TestRBTree() {
    RBTree<int, int> rbTree;
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a) rbTree.Insert({ e, e });

    std::cout << "中序遍历结果：" << std::endl;
    rbTree.InOrder();

    std::cout << "红黑树平衡性验证结果：" << (rbTree.IsRBTree() ? "平衡（1）" : "不平衡（0）") << std::endl;

    int keyToFind = 7;
    auto foundNode = rbTree.Find(keyToFind);
    if (foundNode) std::cout << "找到节点：" << foundNode->_kv.first << ":" << foundNode->_kv.second << std::endl;
    else std::cout << "未找到节点：" << keyToFind << std::endl;

    std::cout << "树的高度：" << rbTree.Height() << std::endl;
    std::cout << "节点数量：" << rbTree.Size() << std::endl;
}
int main() {
    TestRBTree();
    return 0;
}

终极对决：AVL 树 vs 红黑树

性能对比

为了直观感受两者的差异，我们编写了一个测试程序，在一百万数据规模下对比插入和查找的性能。

#include "AVLTree.h"
#include "RBTree.h"
#include <vector>
#include <ctime>
using namespace std;

void TestBST() {
    cout << "测试一百万的数据规模下 AVL 树和红黑树的性能差距\n" << endl;
    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);

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

    size_t begin2 = clock();
    RBTree<int, int> rb;
    for (auto it : v) rb.Insert(make_pair(it, it));
    size_t end2 = clock();

    cout << "-----------插入操作的耗时-----------" << endl;
    cout << "AVL Insert:" << end1 - begin1 << endl;
    cout << "RB Insert:" << end2 - begin2 << endl;

    size_t begin3 = clock();
    for (auto it : v) avl.Find(it);
    size_t end3 = clock();

    size_t begin4 = clock();
    for (auto it : v) rb.Find(it);
    size_t end4 = clock();

    cout << "\n-----------查找操作的耗时-----------" << endl;
    cout << "AVL Find:" << end3 - begin3 << endl;
    cout << "RB Find:" << end4 - begin4 << endl;

    cout << "\n-----------是否平衡-----------" << endl;
    cout << "AVL IsBalance:" << avl.IsAVLTree() << endl;
    cout << "RB IsBalance:" << rb.IsRBTree() << endl;

    cout << "\n-----------树的高度-----------" << endl;
    cout << "AVL Height:" << avl.Height() << endl;
    cout << "RB Height:" << rb.Height() << endl;

    cout << "\n-----------插入节点的数量-----------" << endl;
    cout << "AVL Size:" << avl.Size() << endl;
    cout << "RB Size:" << rb.Size() << endl;
}

int main() {
    TestBST();
    return 0;
}

结论

从测试结果可以看出，红黑树在插入操作上通常比 AVL 树更快，因为红黑树不需要像 AVL 树那样频繁地重新平衡。而在查找操作上，两者性能相当。在实际工程中，如 C++ STL 选择红黑树作为 map 和 set 的底层容器，正是看中了其在动态插入场景下的整体稳定性。