C++ 红黑树详解：原理、旋转与完整实现

3.2 插入逻辑

3.2.1 插入过程

1. 按二叉搜索树规则插入新结点。
2. 如果是空树，新增结点是黑色；如果是非空树，新增结点必须是红色（避免破坏规则 5）。
3. 如果父结点是黑色，无需调整；如果父结点是红色，违反规则 3，需要修复。

3.2.2 三种修复情况

设 c 为新结点 (cur)，p 为父结点 (parent)，g 为祖父结点 (grandfather)，u 为叔叔结点 (uncle)。

情况 1：变色 c 为红，p 为红，g 为黑，u 存在且为红。将 p 和 u 变黑，g 变红。把 g 当做新的 c，继续往上更新。

注意：情况 1 只变色，不旋转。无论 c 是 p 的左还是右，处理方式一致。

情况 2：单旋 + 变色 c 为红，p 为红，g 为黑，u 不存在或 u 为黑。此时单纯变色无法解决连续红结点问题，需要旋转。

• 若 p 是 g 的左，c 是 p 的左：以 g 为轴右旋，p 变黑，g 变红。
• 若 p 是 g 的右，c 是 p 的右：以 g 为轴左旋，p 变黑，g 变红。

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

• 若 p 是 g 的左，c 是 p 的右：先以 p 为轴左旋，再以 g 为轴右旋，c 变黑，g 变红。
• 若 p 是 g 的右，c 是 p 的左：先以 p 为轴右旋，再以 g 为轴左旋，c 变黑，g 变红。

3.2.3 插入代码实现

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < kv.first) {
            parent = cur; cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
            parent = cur; cur = cur->_left;
        } else {
            return false; // 已存在
        }
    }
    // 插入红色结点
    cur = new Node(kv); cur->_col = RED;
    if (parent->_kv.first < kv.first) parent->_right = cur;
    else parent->_left = cur;
    cur->_parent = parent;

    // 修复红黑性质
    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        if (grandfather->_left == parent) {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) {
                // 情况 1：变色
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather; parent = cur->_parent;
            } else {
                // 情况 2 或 3：旋转 + 变色
                if (cur == parent->_left) {
                    RotateR(grandfather);
                    parent->_col = BLACK; grandfather->_col = RED;
                } else {
                    RotateL(parent); RotateR(grandfather);
                    cur->_col = BLACK; grandfather->_col = RED;
                }
                break;
            }
        } else {
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED) {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather; parent = cur->_parent;
            } else {
                if (cur == parent->_right) {
                    RotateL(grandfather);
                    parent->_col = BLACK; grandfather->_col = RED;
                } else {
                    RotateR(parent); RotateL(grandfather);
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return true;
}

3.3 旋转操作

3.3.1 右旋

以 parent 为轴，subL 上升，parent 下降为 subL 的右孩子。

3.3.2 左旋

以 parent 为轴，subR 上升，parent 下降为 subR 的左孩子。

3.3.3 双旋

左右双旋或右左双旋，本质是两次单旋的组合。

3.4 查找与辅助接口

查找逻辑与普通二叉搜索树一致，时间复杂度 O(log n)。

对于 Size()、Height() 等接口，采用双重设计：公共接口直接调用，私有递归函数接收 root 参数，兼顾封装性与递归需求。

3.5 验证红黑树

验证需检查四条规则：

1. 颜色类型正确。
2. 根结点为黑。
3. 无连续红结点（前序遍历检查父结点）。
4. 所有路径黑色结点数量相等（记录 left_bn 作为参考值比较）。

3.6 删除

红黑树的删除逻辑较为复杂，涉及多种情况下的颜色调整和旋转。通常建议参考《算法导论》或《STL 源码剖析》中的详细讲解，此处不再赘述。

4. 完整代码示例

RBTree.h

#pragma once
#include<iostream>
using namespace std;
#include<assert.h>

enum Color { BLACK, RED };

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

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

template<class K, class V>
struct RBTree {
    typedef RBTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv) {
        if (_root == nullptr) {
            _root = new Node(kv); _root->_col = BLACK; return true;
        }
        Node* parent = nullptr; Node* cur = _root;
        while (cur) {
            if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; }
            else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; }
            else { return false; }
        }
        cur = new Node(kv); cur->_col = RED;
        if (parent->_kv.first < kv.first) parent->_right = cur;
        else parent->_left = cur;
        cur->_parent = parent;

        while (parent && parent->_col == RED) {
            Node* grandfather = parent->_parent;
            if (grandfather->_left == parent) {
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK; grandfather->_col = RED;
                    cur = grandfather; parent = cur->_parent;
                } else {
                    if (cur == parent->_left) {
                        RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;
                    } else {
                        RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;
                    }
                    break;
                }
            } else {
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK; grandfather->_col = RED;
                    cur = grandfather; parent = cur->_parent;
                } else {
                    if (cur == parent->_right) {
                        RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;
                    } else {
                        RotateR(parent); RotateL(grandfather); grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return true;
    }

    void RotateR(Node* parent) {
        Node* subL = parent->_left; Node* subLR = subL->_right;
        parent->_left = subLR; if (subLR) subLR->_parent = parent;
        Node* parentParent = parent->_parent;
        subL->_right = parent; parent->_parent = subL;
        if (parent == _root) { _root = subL; subL->_parent = nullptr; }
        else {
            if (parentParent->_left == parent) parentParent->_left = subL;
            else parentParent->_right = subL;
            subL->_parent = parentParent;
        }
    }

    void RotateL(Node* parent) {
        Node* subR = parent->_right; Node* subRL = subR->_left;
        parent->_right = subRL; if (subRL) subRL->_parent = parent;
        Node* parentParent = parent->_parent;
        subR->_left = parent; parent->_parent = subR;
        if (parentParent == nullptr) { _root = subR; subR->_parent = nullptr; }
        else {
            if (parent == parentParent->_left) parentParent->_left = subR;
            else parentParent->_right = subR;
            subR->_parent = parentParent;
        }
    }

    void InOrder() { _InOrder(_root); cout << endl; }
    Node* Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_kv.first < key) cur = cur->_right;
            else if (cur->_kv.first > key) cur = cur->_left;
            else return cur;
        }
        return nullptr;
    }
    bool IsBalanceTree() {
        if (_root && _root->_col == RED) return false;
        int left_bn = 0; Node* cur = _root;
        while (cur) { if (cur->_col == BLACK) left_bn++; cur = cur->_left; }
        return _Checkcolor(_root, 0, left_bn);
    }
    int Height() { return _Height(_root); }
    int Size() { return _Size(_root); }
private:
    int _Size(Node* root) { if (root == nullptr) return 0; return _Size(root->_left) + _Size(root->_right) + 1; }
    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;
    }
    bool _Checkcolor(Node* root, int root_cur_bn, const int left_bn) {
        if (root == nullptr) { if (root_cur_bn != left_bn) { cout << "黑色节点的数量不相等" << endl; return false; } return true; }
        if (root->_col == BLACK) root_cur_bn++;
        if (root->_col == RED && root->_parent && root->_parent->_col == RED) { cout << root->_kv.first << "存在连续的红色节点" << endl; return false; }
        return _Checkcolor(root->_left, root_cur_bn, left_bn) && _Checkcolor(root->_right, root_cur_bn, left_bn);
    }
    int _InOrder(Node* root) {
        if (root == nullptr) return 0;
        _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right);
        return 0;
    }
    Node* _root = nullptr;
};

Tree.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
#include"RBTree.h"

void TestRBTree1() {
    RBTree<int, int> t;
    int a[] = { 4,2,6,1,3,5,15,7,16,14 };
    for (auto e : a) {
        t.Insert({ e,e });
        cout << "Insert:" << e << "->";
        t.InOrder();
    }
}

void TestRBTree2() {
    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 begin2 = clock();
    RBTree<int, int> t;
    for (auto e : v) t.Insert(make_pair(e, e));
    size_t end2 = clock();
    cout << "Insert:" << end2 - begin2 << endl;
    cout << t.IsBalanceTree() << endl;
    cout << "Height:" << t.Height() << endl;
    cout << "Size:" << t.Size() << endl;
    size_t begin1 = clock();
    for (size_t i = 0; i < N; i++) t.Find((rand() + i));
    size_t end1 = clock();
    cout << "Find:" << end1 - begin1 << endl;
}

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

5. 总结

红黑树通过颜色约束实现了近似平衡，保证了 O(log n) 的时间复杂度。相比 AVL 树，它在插入时的旋转开销更小，更适合频繁插入的场景。掌握红黑树的原理与实现，对于理解 STL 容器底层机制至关重要。