C++ 红黑树原理与实现详解

红黑树的结点定义

红黑树结点为模版实现。这里我们使用 std::pair<K, V> 来存储我们的键值对数据。结点采用 struct 设计，默认权限为 public，方便下文的 RBTree 类访问成员。

template<class K, class V>
struct RBTreeNode {
    // 三叉链 RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent; // 红黑树需要旋转，因此设计为三叉链，保存父节点的地址
    pair<K, V> _kv;            // 键值对
    Colour _col;               // 表示结点的颜色

    // 新结点默认是红色的
    RBTreeNode(const pair<K, V>& kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(Red) {}
};

思考一下：在节点的定义中，为什么要将节点的默认颜色给成红色的？

红黑树设计

红黑树为模版实现。初始时根节点为空。

template<class K, class V>
class RBTree {
    typedef RBTreeNode<K, V> Node;
    RBTreeNode<K, V>* _root = nullptr;
public:
    // ... 对外共有接口
private:
    // ... 内部私有成员函数
};

红黑树的插入实现

1. 空树的插入

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

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

首先我们需要明确一点，在红黑树非空的情况下，我们插入一个节点的颜色必定是红色。

如果我们把插入节点的颜色设置为黑色的话，那么此时这棵红黑树就必然会违反黑路同的性质，插入黑色结点会对其他路径造成影响 (黑路同)，之后想要把每条路上的黑色节点数量调整为一样多的话就会非常麻烦。所以从这个角度来看，树非空的情况下我们插入的节点都设置为红色。

因此，插入一个红色节点，如果它的父亲是黑色，那么将不会违反红黑树的任何一条性质，插入结束。

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

我们插入的节点为红色，此时如果它的父亲也为红色，那么就会违反不红红的性质。那么此时让父亲变为黑色，但这也意味着父亲这条路径上多了一个黑色节点，违反了黑路同，我们需要调节黑色节点的数量。

此时可以让父亲的父亲 (grandfather) 变为红色 (由于变色前父亲为红，所以爷爷变色之前必然为黑)，再让叔叔节点变为黑色，这样一来，我们就可以同时满足不红红和黑路同两个性质了。

但是，此时由于爷爷变红，可能又会导致出现两个红色节点相邻的情况，因为爷爷的父亲可能为红色。此时我们只需要把爷爷当作新插入的节点，重复上面的操作即可。

一直重复这样的操作，直到不违反红黑树的性质或者到根为止。注意 grandfather 到根的时候需要把根变为黑色。

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

当叔叔不存在或叔叔为黑色时，需要通过旋转来调整结构。

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

以 RL 型为例，如果此时插入节点的父亲节点在爷爷节点的右边 (right)，插入节点在父亲节点的左边 (left)，那么我们把这种情况成为 RL 型。如果是 RL 型，那么需要将以爷爷节点为根的子树进行右左双旋操作，旋转之后将 cur 和爷爷节点进行变色，插入结束。

这种情况与 LR 型完全对称，这里不再画图演示。

4. 旋转操作

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

左单旋

// 左单旋 2 1 newNode 连成线，单纯的右边高
void RotateL(Node* parent) {
    _rotateCount++; // 测试旋转次数
    if (parent == nullptr || parent->_right == nullptr) return;
    Node* curNode = parent->_right;
    Node* curLeft = curNode->_left; // curLeft 有可能为空

    // 先处理 curNode 的 left 结点，curLeft 有可能是空
    parent->_right = curLeft;
    if (curLeft) curLeft->_parent = parent;

    // 再处理 curNode 结点
    // parent 有可能是根节点，也有可能是子树的根节点
    if (parent == _root) {
        // 先立新根
        _root = curNode;
        curNode->_parent = nullptr;
        // 再挂旧根
        parent->_parent = curNode;
        curNode->_left = parent;
    } else {
        Node* ppNode = parent->_parent; // 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子
        if (parent == ppNode->_left) ppNode->_left = curNode;
        else ppNode->_right = curNode;
        curNode->_parent = ppNode;
        // 挂 parent
        parent->_parent = curNode;
        curNode->_left = parent;
    }
}

右单旋

// 右单旋 -2 -1 newNode 连成线，单纯的左边高
void RotateR(Node* parent) {
    _rotateCount++; // 测试旋转次数
    // parent 为空 或 curNode 为空的情况
    if (parent == nullptr || parent->_left == nullptr) return;
    Node* curNode = parent->_left;
    Node* curRight = curNode->_right; // 把 curNode 的 right 给给 parent 的 left

    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; // 找 parent 是 ppNode 的左还是右
        if (parent == ppNode->_left) ppNode->_left = curNode;
        else ppNode->_right = curNode;
        curNode->_parent = ppNode;
        // 挂 parent
        curNode->_right = parent;
        parent->_parent = curNode;
    }
}

5. 插入的完整代码

bool insert(const pair<K, V>& kv) {
    // 先走二叉搜索树的插入逻辑
    if (_root == nullptr) {
        _root = new Node(kv);
        _root->_col = Black; // 性质 根节点是黑色的
        return true;
    }

    // _root 不为空时，二叉搜索树的逻辑
    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;
        }
    }

    // while 循环结束后，代表找到了可以插入的位置
    // 找到位置了，但父节点不知道 新结点比自己大还是比自己小
    curNode = new Node(kv);
    if (curNode->_kv.first < parent->_kv.first)
        parent->_left = curNode;
    else
        parent->_right = curNode;
    curNode->_parent = parent;

    // 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
    // 以下是红黑树的性质控制，是对二叉搜索树 进行的 控制平衡 操作
    // 控制近似平衡 ...
    // while 循环控制 颜色继续往上更新
    // 新插入的结点为红色 因此 parent 存在且 parent 为红色时，才需要更新颜色
    while (parent && parent->_col == Red) {
        Node* grandFather = parent->_parent;

        // parent 在 grandFather 左的场景
        if (parent == grandFather->_left) {
            Node* uncle = grandFather->_right;
            // 情况一 cur 为红 parent 为红 grandFather 为黑，uncle 存在且为红
            if (uncle && uncle->_col == Red) {
                // p 和 u 变黑，g 变红，cur 变成 grandFather 继续往上更新
                // 变色
                parent->_col = uncle->_col = Black;
                grandFather->_col = Red;
                // 继续向上处理
                curNode = grandFather;
                parent = curNode->_parent;
                // 如果更新完后 grandFather 为红色：
                // 1. g 为根节点，那么 parent 为空
                // 2. g 上面还有结点
                // 如果是黑色的，无需处理，进不去循环
                // 如果是红色，继续处理
            }
            // u 不存在 或 u 存在且为黑
            else {
                // 左左 -> 右单旋
                if (curNode == parent->_left) {
                    // g
                    // p
                    // c
                    RotateR(grandFather);
                    parent->_col = Black;
                    grandFather->_col = Red;
                }
                // 左右 -> 左右双旋
                else {
                    // g
                    // p
                    // c
                    RotateL(parent);
                    RotateR(grandFather);
                    curNode->_col = Black;
                    grandFather->_col = Red;
                }
                break;
            }
        }
        // parent 在 grandFather 右的场景
        else {
            Node* uncle = grandFather->_left;
            // 情况一 cur 为红 parent 为红 grandFather 为黑，uncle 存在且为红
            if (uncle && uncle->_col == Red) {
                // p 和 u 变黑，g 变红，cur 变成 grandFather 继续往上更新
                // 变色
                parent->_col = uncle->_col = Black;
                grandFather->_col = Red;
                // 继续向上处理
                curNode = grandFather;
                parent = curNode->_parent;
                // 如果更新完后 grandFather 为红色：
                // 1. g 为根节点，那么 parent 为空
                // 2. g 上面还有结点
                // 如果是黑色的，无需处理，进不去循环
                // 如果是红色，继续处理
            }
            // u 不存在 或 u 存在且为黑
            else {
                // 右右 -> 左单旋
                if (curNode == parent->_right) {
                    // g
                    // p
                    // c
                    RotateL(grandFather);
                    parent->_col = Black;
                    grandFather->_col = Red;
                }
                // 右左 -> 右左双旋
                else {
                    // g
                    // p
                    // c
                    RotateR(parent);
                    RotateL(grandFather);
                    curNode->_col = Black;
                    grandFather->_col = Red;
                }
                break;
            }
        }
    }
    // 继续向上处理 parent = curNode->_parent 如果 parent == nullptr 会结束循环
    // parent == nullptr 结束循环时，curNode 为_root 结点，需要对 _root 节点变色
    _root->_col = Black;
    // 粗暴的处理，直接将根节点设为黑色，根节点为黑色总是正确的
    return true;
}

验证红黑树

求树的高度

求树的高度思路如下：

• 先分别求树的左右子树高度
• 最终返回左右子树中 高度更大的高度 + 1

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;
    // 根节点颜色不为黑，false
    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);
}

_isBalance 实现以下功能：

• 检查根节点的颜色是否为黑色
• 计算树中最左路径中，黑色结点的数量作为基准值，传给 CheckColour 函数，与其他路径的黑色节点数量进行比对

检查红黑树的颜色

递归检查红黑树的颜色。

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) {
        cout << root->_kv.first << "出现连续红色节点" << endl;
        return false;
    }
    return CheckColour(root->_left, blacknum, benchmark) && CheckColour(root->_right, blacknum, benchmark);
}

CheckColour 函数内部完成以下检查：

• 递归检查，检查树中是否有连续的红色结点：if (root->_col == Red && root->_parent && root->_parent->_col == Red)
  • 若当前节点和它的父节点都是红色，则出现了连续的红色节点，违反红黑树性质④，输出提示并返回 false。
• 递归检查，检查其他路径中黑色结点的数量与基准值是否相同
  • 如果当前节点是黑色，就增加路径上的黑节点计数。（每次进入新节点，统计路径上黑节点的数量）
  • 当遍历到 nullptr 时，说明到达叶子。此时：
    • blacknum 是从根到当前叶子的黑节点数量；
    • benchmark 是从根到某一条路径上统计得到的标准黑节点数（通常是第一次到达叶子时确定的值）。
    • 如果当前路径上的黑节点数与标准值不同，则不满足红黑树性质⑤，返回 false
• 对左右子树分别检查，只有两边都满足条件，整棵树才合法。注意：blacknum 是值传递，在每条递归路径中互不影响。

blacknum 使用'传值'：

形参传值会拷贝一份当前的 blacknum，在递归调用中独立变化。 也就是说：

• 每条递归路径拥有自己独立的黑节点计数，不会因为返回后互相干扰；
• 非常适合这种'每条路径独立计算'的场景。

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

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

测试代码

#include "Red_Black_Tree.h"
#include "AVL_Tree.h"
#include <vector>

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); // 插入随机数据
        //v.push_back(i); // 插入有序数据
    }

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

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

插入有序数据的结果

（此处应有测试结果图）

插入随机无序数据的结果

（此处应有测试结果图）

完整代码

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

enum Colour { Red, Black };

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

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

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

public:
    bool insert(const 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;
    }

    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) {
            cout << root->_kv.first << "出现连续红色节点" << endl;
            return false;
        }
        return CheckColour(root->_left, blacknum, benchmark) && CheckColour(root->_right, blacknum, benchmark);
    }

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

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

private:
    void RotateL(Node* parent) {
        _rotateCount++;
        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) {
        _rotateCount++;
        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;
        }
    }
};

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); // 插入随机数据
    }

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

结语

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

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

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

红黑树的实现也标志着我们正式跨入了 C++ STL 底层机制探索的第二阶段。下一步，我们将基于该结构实现 map、set 等容器，深入理解迭代器、模板参数与仿函数在标准库中的实际应用。