C++ 红黑树详解：原理、实现与性能对比

• 采用三叉链的方式实现，保存父节点的地址。
• 默认构造函数将三个指针初始化为 nullptr，初始化结点颜色为 Red。

红黑树设计

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

public:
    bool insert(const std::pair<K, V>& kv);
    // ... 其他接口

private:
    void RotateL(Node* parent);
    void RotateR(Node* parent);
    // ... 辅助函数
};

红黑树的插入实现

1. 空树的插入

当对一棵空的红黑树进行插入时，直接插入并把其颜色设置为黑色即可。

2. 新插入节点的父亲为黑色

在非空情况下，插入节点的颜色必定是红色。如果父亲是黑色，不会违反红黑树的任何一条性质，插入结束。

3. 新插入节点的父亲为红色

此时需要调整以维持性质。

（1）叔叔存在且为红色：变色 + 继续向上处理

• 让父亲变为黑色。
• 让父亲的父亲 (grandfather) 变为红色。
• 让叔叔节点变为黑色。
• 如果爷爷变红导致祖父以上出现连续红色，重复上述操作。
• 注意 grandfather 到根的时候需要把根变为黑色。

（2）叔叔不存在或叔叔为黑色：旋转 + 变色

• LL 型：右单旋 + 变色。
• RR 型：左单旋 + 变色。
• LR 型：左右双旋 + 变色。
• RL 型：右左双旋 + 变色。

4. 旋转操作

这里的旋转操作和 AVL 树的旋转操作一致，只需把 AVL 树中的更新平衡因子的步骤去掉。

左单旋

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;
        curNode->_right = parent;
        parent->_parent = curNode;
    } else {
        Node* ppNode = parent->_parent;
        if (parent == ppNode->_left) ppNode->_left = curNode;
        else ppNode->_right = curNode;
        curNode->_parent = ppNode;
        curNode->_right = parent;
        parent->_parent = curNode;
    }
}

5. 插入的完整代码

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

5. 验证红黑树

求树的高度

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

判断树是否是红黑树

判断是否平衡

bool isBalance() { return _isBalance(_root); }
bool _isBalance(Node* root = _root) {
    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);
}

6. 红黑树与 AVL 树性能测试对比

红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O(logN)。红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优。

测试代码

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
// #include "AVL_Tree.h"
using namespace std;

int main() {
    const int N = 10000000;
    vector<int> v;
    v.reserve(N);
    srand(time(0));
    for (size_t i = 0; i < N; i++) {
        v.push_back(rand() + i * i + 2); // 插入随机数据
    }

    RBTree<int, int> rbt;
    for (auto e : v) {
        rbt.insert(make_pair(e, e));
    }
    cout << "红黑树是否平衡：" << rbt.isBalance() << endl;
    cout << "红黑树的高度：" << rbt.Height() << endl;
    cout << "红黑树的旋转次数：" << rbt._rotateCount << endl;

    // AVLTree<int, int> avlt;
    // for (auto e : v) {
    //     avlt.insert(make_pair(e, e));
    // }
    // cout << "AVL 树是否平衡：" << avlt.isBalance() << endl;
    // cout << "AVL 树的高度：" << avlt.height() << endl;
    // cout << "AVL 树的旋转次数：" << avlt._rotateCount << endl;

    return 0;
}

7. 结语

红黑树作为一种'近似平衡'的二叉搜索树，通过颜色标记与旋转调整，在插入与删除操作频繁的场景下有效避免了 AVL 树的高频旋转问题。它在时间复杂度上与 AVL 树相同，都是 O(logN)，但实际应用中更具工程价值，因此成为了 STL map、set 等容器的底层数据结构。

本文自底向上实现了红黑树的插入、变色与旋转机制，并通过与 AVL 树的对比，揭示了红黑树在平衡效率与维护开销上的折中之美。

红黑树的核心思想：不追求完美平衡，而是保证最长路径不超过最短路径的 2 倍；通过简单的局部旋转与变色操作实现全局近似平衡；用颜色规则取代复杂的高度平衡因子，使得结构更简洁、效率更高。