C++ 红黑树详解与实现

红黑树详解与实现

0. 前言

在上一篇文章中，我们从零实现了 AVL 树，深入理解了二叉搜索树的平衡思想。然而，AVL 树虽然严格平衡，但插入和删除操作频繁时，频繁的旋转会带来较大的性能损耗。

为了在'平衡性'和'性能'之间取得更好的折中，红黑树（Red-Black Tree）应运而生。它通过为每个结点引入'颜色属性'，并对节点间的颜色分布施加约束，使得树在近似平衡的状态下仍能保持高效的查找、插入与删除性能。

红黑树并不追求绝对平衡，而是通过「颜色规则 + 局部旋转」实现'动态平衡'。

这种思想也正是 C++ STL 容器 map / set 的底层核心机制。

本文将从最基本的概念出发，逐步剖析红黑树的性质、插入规则、旋转逻辑，并最终完成一个完整可运行的红黑树实现。 我们还将通过与 AVL 树的性能对比，深入理解红黑树在实际工程场景中的优势与应用价值。

---

1. 什么是红黑树

概念与定义

我们之前学习过了二叉搜索树和 AVL 树，红黑树和 AVL 树一样，也是一棵自平衡的二叉搜索树。AVL 树通过控制左右子树的高度差不超过 1 来保持平衡，而红黑树则是为每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束。

红黑树：一种自平衡二叉搜索树，由德国计算机科学家 Rudolf Bayer 在 1972 年发明，当时被称为对称二叉 B 树，后来被 Leo J. Guibas 和 Robert Sedgewick 改进并命名为红黑树。

• 它在很多编程语言的库和实际应用场景中都有广泛使用
  • C++ 的 STL 库中的 map 和 set 底层实现
  • Java 的 TreeMap 等库的实现
• 它通过额外的颜色标记和旋转操作来维持树的平衡，确保最坏情况下的基本操作（插入、删除、查找）时间复杂度为 O(logN)
• 它在每个节点上增加了一个存储位来表示节点的颜色，这个颜色可以是红色或黑色。
  • 通过对从根节点到任意叶子节点路径上的节点颜色进行约束来保持树的左右两边的相对平衡，红黑树确保没有一条路径会比其他路径长出 2 倍，即 2 * 最短路径 >= 最长路径，因而它是一种近似平衡的二叉搜索树

红黑树示例

---

2. 红黑树的性质

红黑树的性质：

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

红黑树的性质解读

性质解读：

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的：
   • 由性质 3 我们可以推断出：红黑树的任何路径没有连续的红色结点
4. 对于每个结点，从该结点到其所有后代叶结点（NIL）的简单路径上，均包含相同数目的黑色结点
   • 由性质 4 我们可以推断出：从根节点开始，每条路径上，都有相同数量的黑色结点
5. 每个叶子结点（NIL 结点）都是黑色的 (此处的叶子结点指的是空结点)
   • 说明：《算法导论》等书籍上补充了一条每个叶子结点 (NIL) 都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把 NIL 叫做外部结点。NIL 是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了 NIL 结点，所以我们知道一下这个概念即可。
   • 黑色的 NIL 结点即为红黑树的空结点

性质总结：

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

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

树的路径再认识

树路径的计算：

• 计算路径：从根节点到空结点，为一条路径，因此以上树有 11 条路径

如果树路径的计算不包含空节点，那么以下这棵树会被解读成红黑树，但其实这棵树不是红黑树 (违反性质 4)

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

红黑树路径规则推导：

• 最短路径（全黑路径）：
  • 由红黑树性质 4（从根到 NIL 结点的每条路径，黑色结点数量相同）可知，极端场景下，最短路径就是全由黑色结点组成的路径。我们把这条最短路径的长度记为 bh（black height，黑色高度）
• 最长路径（黑红间隔路径）：
  • 结合规则 2（根结点是黑色）和规则 3（红色结点的子结点必为黑色，路径中不会出现连续红色结点）。极端场景下，最长路径会呈现一黑一红交替的结构，因此最长路径长度为 2*bh（单条路径黑色结点数量最多为 bh，红色结点数量最多也为 bh）
• 路径长度范围：
  • 实际红黑树中，'全黑最短路径'和'黑红交替最长路径'不一定同时存在。但通过 4 条规则可推导：任意从根到 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;
    // 红黑树需要旋转，因此设计为三叉链，保存父节点的地址
    pair<K, V> _kv; // 键值对
    Colour _col;    // 表示结点的颜色

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

• 搜索树常用于存储键值，方便查找关键字，这里我们使用 std::pair<K, V> 来存储我们的键值对数据
• 结点中的成员变量：采用三叉链的方式实现
  • RBTreeNode<K, V>* _left：指向左孩子的指针
  • RBTreeNode<K, V>* _right：指向右孩子的指针
  • RBTreeNode<K, V>* _parent：指向父节点的指针
• 默认构造函数 RBTreeNode(const pair<K, V>& kv)：
  • 将三个指针初始化为 nullptr，初始化结点颜色为 Red
  • 使用 kv 初始化类内的 _kv 成员
• 结点采用 struct 设计，默认权限为 public，方便下文的 RBTree 类访问成员

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

红黑树设计

• 红黑树为模版实现

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

• typedef RBTreeNode<K, V> Node;：结点类型重定义，简化书写
• RBTree<K, V>* _root = nullptr：初始时根节点为空

---

红黑树的插入实现

1. 空树的插入

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

（下面所讨论的插入操作都是建立在树非空的情况之上）

---

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

新结点的颜色

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

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

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

---

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

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

我们插入的节点为红色，

• 此时如果它的父亲也为红色，那么就会违反不红红的性质。那么此时让父亲变为黑色
• 但这也意味着父亲这条路径上多了一个黑色节点，违反了黑路同，我们需要调节黑色节点的数量。
• 此时可以让父亲的父亲 (grandfather) 变为红色 (由于变色前父亲为红，所以爷爷变色之前必然为黑)，再让叔叔节点变为黑色，这样一来，我们就可以同时满足不红红和黑路同两个性质了。

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

• 一直重复这样的操作，直到不违反红黑树的性质或者到根为止。注意 grandfather 到根的时候需要把根变为黑色
• 下面是继续向上调整的红黑树抽象图

---

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

① LL 型：右单旋 + 变色

• uncle 不存在时：

• uncle 为黑色时：

② RR 型：左单旋 + 变色

• uncle 不存在时：

• uncle 为黑色时：

③ LR 型：左右双旋 + 变色

• uncle 为不存在时：

• uncle 为黑色时：

④ RL 型：右左双旋 + 变色

• uncle 为不存在时：

• uncle 为黑色时：

如果此时插入节点的父亲节点在爷爷节点的右边 (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;
}

---

5. 验证红黑树

求树的高度

求树的高度思路如下：

• 先分别求树的左右子树高度
• 最终返回左右子树中 高度更大的高度 + 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，在递归调用中独立变化。

也就是说：

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

---

6. 红黑树与 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;
}

插入有序数据的结果

---

插入随机无序数据的结果

---

7. 完整代码

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

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

    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:
    // 左单旋 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;
        }
    }
};

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

---

8. 结语

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

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

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

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