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

C++ 红黑树详解

1. 什么是红黑树

概念与定义

红黑树是一种自平衡二叉搜索树，由德国计算机科学家 Rudolf Bayer 在 1972 年发明。它通过为每个结点增加一个存储位来表示结点的颜色（红色或黑色），并对从根节点到任意叶子节点路径上的节点颜色进行约束，从而保持树的左右两边的相对平衡。

红黑树确保没有一条路径会比其他路径长出 2 倍，即 2 * 最短路径 >= 最长路径，因而它是一种近似平衡的二叉搜索树。它在很多编程语言的库和实际应用场景中都有广泛使用，例如 C++ 的 STL 库中的 map 和 set 底层实现，Java 的 TreeMap 等库的实现。

红黑树示例

![图片：红黑树示例]

2. 红黑树的性质

1. 每个结点不是红色就是黑色。
2. 根节点是黑色的。
3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的。
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
5. 每个叶子结点都是黑色的 (此处的叶子结点指的是空结点)。

性质解读

• 左根右：由于它是二叉搜索树，所以左子树的值 < 根的值 < 右子树的值。
• 根叶黑：根节点和叶子节点 (NIL) 都是黑色的。
• 不红红：一条路径上不会出现两个连续的红色节点。
• 黑路同：任意两条路径上的黑色节点个数相同。

因此，红黑树的性质可以简记为：左根右，根叶黑，不红红，黑路同。

树的路径再认识

计算路径是从根节点到空结点 (NIL)。如果树路径的计算不包含空节点，可能会导致误判违反性质 4。

![图片：树路径计算]

3. 红黑树如何确保最长路径不超过最短路径的 2 倍？

• 最短路径（全黑路径）：极端场景下，最短路径就是全由黑色结点组成的路径。记为 bh (black height)。
• 最长路径（黑红间隔路径）：结合规则 2 和规则 3，极端场景下，最长路径会呈现一黑一红交替的结构，长度为 2*bh。
• 路径长度范围：任意从根到 NIL 结点的路径长度 h，都满足 bh ≤ h ≤ 2*bh，这保证了红黑树的近似平衡特性。

4. 红黑树的实现

整体架构设计

结点颜色的枚举类

enum Colour { Red, Black };

红黑树的结点定义

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

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

• 采用三叉链的方式实现，保存父节点的地址。
• 默认构造函数将三个指针初始化为 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;
                }
                ;
            }
        }  {
            Node* uncle = grandFather->_left;
             (uncle && uncle->_col == Red) {
                parent->_col = uncle->_col = Black;
                grandFather->_col = Red;
                curNode = grandFather;
                parent = curNode->_parent;
            }  {
                 (curNode == parent->_right) {
                    (grandFather);
                    parent->_col = Black;
                    grandFather->_col = Red;
                }  {
                    (parent);
                    (grandFather);
                    curNode->_col = Black;
                    grandFather->_col = Red;
                }
                ;
            }
        }
    }
    _root->_col = Black;
     ;
}

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;
    

     ;
}

7. 结语

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

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

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