C++ STL 红黑树原理与实现

红黑树概述

红黑树是一种自平衡二叉搜索树，由德国计算机科学家 Rudolf Bayer 在 1972 年发明。它通过额外的颜色标记和旋转操作来维持树的近似平衡，确保最坏情况下的基本操作（插入、删除、查找）时间复杂度为 O(log n)。

核心特性

1. 节点颜色：每个节点要么是红色，要么是黑色。
2. 根节点：根节点必须是黑色。
3. 叶子节点：所有叶子节点（NIL 节点，即空指针）都是黑色的。
4. 红节点规则：如果一个节点是红色的，则它的两个子节点都必须是黑色的（不存在连续的红色节点）。
5. 黑色高度：对每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

这些约束保证了从根到叶子的最长路径不会超过最短路径的两倍，从而实现了近似平衡。

效率分析

相比 AVL 树，红黑树对平衡性的要求稍低，因此在插入和删除时进行的旋转次数更少，性能更稳定。AVL 树追求严格平衡，查询效率高但维护成本高；红黑树在保持 O(log n) 复杂度的同时，牺牲了部分查询效率换取了更高的更新效率。这也是 C++ STL 中的 map 和 set 底层采用红黑树的主要原因。

基本操作

查找操作

查找逻辑与普通二叉搜索树一致，利用'左小右大'的特性递归或迭代向下查找。差异仅在于平衡维护机制不同，查找本身的二分比较形式保持一致。

插入操作

插入操作是在二叉搜索树的基础上，通过颜色调整和旋转操作来维持树的近似平衡。新插入的节点默认为红色。如果插入后破坏了红黑性质，则需要调整。

调整场景

我们定义以下变量以便描述：

• c (current)：当前触发调整的节点（新插入节点或其祖先）。
• p (parent)：c 的父节点。
• g (grandfather)：p 的父节点（祖父节点）。
• u (uncle)：p 的兄弟节点（叔叔节点）。

情况 1：变色 当 c 为红色，p 为红色，且叔叔节点 u 存在且为红色时：

• 将 p 和 u 染为黑色，g 染为红色。
• 将 g 视为新的当前节点，继续向上回溯检查。
• 若 g 变为根节点，需强制染回黑色。

情况 2：变色 + 单旋 当 c 为红色，p 为红色，且叔叔节点 u 不存在或为黑色时：

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

情况 3：变色 + 双旋 当 c 为红色，p 为红色，且叔叔节点 u 不存在或为黑色，但结构呈左右或右左型时：

• 左右型（p 是 g 左孩子，c 是 p 右孩子）：先以 p 为中心左单旋，再以 g 为中心右单旋，c 染黑，g 染红。
• 右左型（p 是 g 右孩子，c 是 p 左孩子）：先以 p 为中心右单旋，再以 g 为中心左单旋，c 染黑，g 染红。

验证操作

验证红黑树不能仅靠路径长度倍数关系，必须严格校验 4 条核心规则：

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

代码实现

存储结构

#pragma once
#include <iostream>
using namespace std;

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), _col(RED) {}
};

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

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

    int _Size(Node* root) {
        if (root == nullptr) return 0;
        return _Size(root->_left) + _Size(root->_right) + 1;
    }

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

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;
        if (kv.first < parent->_kv.first) parent->_left = current;
        else parent->_right = current;
        current->_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 = 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;
    }

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

    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() ? "平衡" : "不平衡") << 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 树对比

为了直观感受两者差异，我们对百万级数据进行插入和查找性能测试。

测试代码

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

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

    // 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 << "-----------插入操作的耗时-----------" << endl;
    cout << "AVL Insert:" << end1 - begin1 << endl;
    cout << "RB Insert:" << end2 - begin2 << endl;

    cout << "\n-----------查找操作的耗时-----------" << 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 << "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 树高度更低，查找速度略快，但两者均在 O(log n) 级别，差异在实际应用中往往可以忽略。综合来看，红黑树在通用场景下更具优势，这也是其成为 STL 首选数据结构的原因。