C++ 红黑树详解：原理、操作与代码实现

基本操作

一、查找操作

查找操作总结：

从二叉搜索树，到 AVL 树，再到红黑树，随着学习逐步深入，我们会发现：这三种树的查找操作，在核心逻辑上高度一致。

它们都依托二叉搜索树的'左小右大'基本规则，从根节点出发，通过键值的比较，不断向左右子树递归或迭代查找，本质都是利用树的有序性缩小查找范围。差异主要体现在平衡维护（AVL 树的严格平衡、红黑树的近似平衡），但查找操作的'二分比较'形式，始终保持着一脉相承的简洁与高效。

二、插入操作

1. 本质

插入操作本质：

红黑树的插入操作是在二叉搜索树的基础上，通过颜色调整和旋转操作来维持树的近似平衡特性。

2. 步骤

场景说明：

在红黑树插入调整逻辑里，我们统一做如下标识：新插入的节点记为 c（current，代表当前触发调整的节点）；c 的父节点记为 p（parent）；p 的父节点（即：祖父节点）记为 g（grandfather）；p 的兄弟节点（即：叔叔节点）记为 u（uncle）

后续将基于这些标识，分析不同场景下的红黑树平衡调整规则。

情况 1：变色

情况 1：当新插入节点 c 为红色、父节点 p 为红色（此时因红黑树性质，祖父节点 g 必为黑色），且叔叔节点 u 存在且为红色时：

• 颜色调整：将 p 和 u 染为黑色，g 染为红色。
• 向上回溯：把 g 视为新的'当前节点'，继续向上检查调整。

原理分析：

• 黑色高度守恒：原本 p（红）、u（红）、g（黑）的结构里，g 子树的黑色节点数由 g 维持。调整后 p、u 变黑（为子树各加一个黑节点），g 变红（抵消自身原本的黑色贡献），整体黑色高度不变。
• 解决连续红节点：c 与 p 的连续红色问题，因 p 变黑得以解决。
• 继续回溯的必要性：g 变红后，若它的父节点是红色，会形成新的'连续红节点'违规，需继续向上处理；若父节点是黑色，当前路径恢复合规，无需调整；若 g 已是整棵树的根，为满足'根节点必黑'规则，要再把 g 染回黑色收尾。

**红黑树平衡处理的图示说明：类似 AVL 树的场景化分析思路，上面图片展示的是红黑树的插入情况 1：变色的是一种具体案例，但实际红黑树需要处理的平衡场景远不止这一种。下面的图片中我们将对这类平衡逻辑做了抽象归纳：用 d/e/f 代表'路径含 hb 个黑色节点的子树'；a/b 代表'路径含 hb-1 个黑色节点且根为红色的子树'（其中 hb ≥ 0，是对黑色节点数量的抽象度量）。

下面的三种图片则分别对应 hb = 0、hb = 1、hb = 2 时的具体场景组合分析。尤其当 hb = 2 时，理论上的组合情况可达上百亿种，但核心逻辑始终一致：无论场景多复杂，均通过 变色 + 向上回溯调整 即可解决。因此：我们无需逐一分析极端案例，理解上图的抽象模型，就能掌握这类平衡问题的通用解法。

图示 1：红黑树的插入情况 1：变色 ---> '插入前 a/b/d/e/f 的黑色高度 bh==0'

图示 2：红黑树的插入情况 1：变色 ---> '插入前 a/b/d/e/f 的黑色高度 bh==1'

图示 3：红黑树的插入情况 1：变色 ---> '插入前 a/b/d/e/f 的黑色高度 bh==2'

情况 2：变色 + 单旋

情况 2：当新节点 c 为红色、父节点 p 为红色（此时祖父 g 必为黑色），且叔叔节点 u 不存在，或 u 存在但为黑色时：

• 若叔叔节点 u 不存在 → c 一定是本次新增的节点（因原树满足红黑性质，无连续红节点）。
• 若叔叔节点 u 存在且为黑色 → c不是新增节点（它原本是黑色，因子树插入触发调整，从黑色变为红色后'上升'到当前位置）。

核心矛盾：此时仅靠变色无法解决连续红节点问题（p 为红，若不变黑仍会违规），需结合旋转 + 变色调整。

◼ 场景 A：p 是 g 的左孩子，c 是 p 的左孩子（左左型）

• 操作：以 g 为旋转中心右单旋。旋转后，p 染黑，g 染红。
• 效果：p 成为新子树的根，黑色节点数量不变（满足'路径黑色高度一致'），消除 c 与 p 的连续红节点问题（p 变黑）。无需继续向上调整：因 p 的父节点（原 g 的父节点）无论颜色如何，都不会触发新的连续红违规。

◼ 场景 B：p 是 g 的右孩子，c 是 p 的右孩子（右右型）

• 操作：以 g 为旋转中心左单旋。旋转后，p 染黑，g 染红。
• 效果：p 成为新子树的根，黑色节点数量不变，消除 c 与 p 的连续红节点问题。无需继续向上调整：同理，p 新的父节点不触发违规。

图示 1：红黑树的插入情况 2：变色 + 单旋 ---> '具体情况'

图示 2：红黑树的插入情况 2：变色 + 单旋 ---> '抽象情况'

图示 3：红黑树的插入情况 2：变色 + 单旋 ---> '插入前 a/b/d/e/f 的黑色高度 bh==1'

情况 3：变色 + 双旋

当新节点 c 为红色、父节点 p 为红色（祖父 g 必为黑色），且叔叔节点 u 不存在，或 u 存在但为黑色时：

• 若叔叔节点 u 不存在 → c 是本次新增节点（原树无连续红节点，符合插入规则）。
• 若叔叔节点 u 存在且为黑色 → c不是新增节点（它原本为黑色，因下层子树插入触发调整，颜色变为红色后'上升'到当前层级）。

核心矛盾：此时仅靠变色无法修复连续红节点问题（p 为红色，必须变黑才能解决违规），但因 u 为黑色 / 不存在，直接变色会破坏'黑色高度一致'规则，需通过双旋转 + 变色调整。

◼ 场景 1：p 是 g 的左孩子，c 是 p 的右孩子（左右型）

• 操作：以 p 为旋转中心，左单旋（将 c 提升为 p 的父节点）；以 g 为旋转中心，右单旋（将 c 提升为 g 的父节点）；变色：c 染黑，g 染红。
• 效果：c 成为新子树的根，黑色节点数量不变（满足'路径黑色高度一致'），消除连续红节点问题（p 与 g 不再连续为红）。无需继续向上调整：因 c 的父节点（原 g 的父节点）无论颜色如何，都不会触发新的连续红违规。

◼ 场景 2：p 是 g 的右孩子，c 是 p 的左孩子（右左型）

• 操作：以 p 为旋转中心，右单旋（将 c 提升为 p 的父节点）；以 g 为旋转中心，左单旋（将 c 提升为 g 的父节点）；变色：c 染黑，g 染红。
• 效果：c 成为新子树的根，黑色节点数量不变，消除连续红节点问题。无需继续向上调整：同理，c 新的父节点不触发违规。

图示 1：红黑树的插入情况 3：变色 + 双旋 ---> '具体情况'

图示 2：红黑树的插入情况 3：变色 + 双旋 ---> '抽象情况'

图示 3：红黑树的插入情况 3：变色 + 双旋 ---> '插入前 a/b/d 的黑色高度 bh==1'

三、验证操作

红黑树规则校验的正确思路：

直接通过最长路径与最短路径的倍数关系（如：最长路径≤最短路径的 2 倍）来验证红黑树是不可行的。因为即使满足该条件，树的颜色规则也可能违规，且当前无问题的树，后续插入新节点时仍可能因颜色规则破坏而失衡。

因此：正确的做法是直接校验红黑树的 4 条核心规则 —— 只要满足这 4 条，自然能保证'最长路径≤最短路径的 2 倍'。

具体校验逻辑如下：

规则 1：颜色合法性 通过枚举定义颜色类型（仅黑色、红色），天然保证节点颜色合法，无需额外校验。

规则 2：根节点颜色 直接检查根节点是否为黑色即可，逻辑简单。

规则 3：红色节点的子节点合法性

• 直接思路：若直接遍历检查'红色节点的子节点是否为黑色'，需处理子节点不存在的情况，较为繁琐。
• 优化思路：反向校验 —— 遍历节点时，检查当前节点的父节点颜色。若父节点为红色且当前节点也为红色，即违反'红色节点的子节点必为黑色'规则。

规则 4：路径黑色节点数量一致性

• 通过前序遍历 + 传递黑色节点计数实现：遍历过程中，用参数 blackNum 记录'从根到当前节点的黑色节点数量'。遇到黑色节点时，blackNum++；遇到空节点（路径终点）时，记录当前路径的黑色节点总数。以第一条路径的黑色节点数量为'参考值'，后续遍历其他路径时逐一对比。若所有路径的黑色节点数量与参考值一致，则满足规则 4。

逻辑总结：

校验红黑树时，直接通过'最长/最短 路径倍数'判断不可靠，需严格校验 4 条核心规则：

• 规则 1：靠枚举天然保证
• 规则 2：直接检查根
• 规则 3：反向校验父节点颜色更高效
• 规则 4：通过前序遍历 + 计数对比实现

满足这 4 条规则，红黑树的'最长路径≤最短路径 2 倍'特性会被自动保证，无需额外验证。

图示：'验证一棵树是不是红黑树'

// 实现：'判断一棵树是不是红黑树'
bool IsRBTree() {
    /*------------处理'特殊情况 + 递归出口'------------*/
    // 特殊情况 1：'空树'
    if (_root == nullptr) {
        return true; // 空树也是红黑树
    }
    // 特殊情况 2：'只有一个节点并且为红色'
    if (_root->_col == RED) {
        return false; // 不满足红黑树的规则
    }
    /*------------处理'正常情况'------------*/
    /*------- 第一步：计算最左路径上节点的数量-------*/
    // 1. 记录该路径上黑色节点的数量
    int refNum = 0;
    // 2. 定义一个指向当前节点的指针
    Node* current = _root;
    // 3. 使用 while 循环统计该路径上黑色节点的数量
    while (current) {
        // 3.1：统计
        if (current->_col == BLACK) {
            ++refNum;
        }
        // 3.2：移动
        current = current->_left;
    }
    /*-------第二步：递归检查其他路径上面的黑色节点的数量-------*/
    return Check(_root, 0, refNum);
}

bool Check(Node* root, int blackNum, const int refNum) {
    /*------------处理'特殊情况 + 递归出口'------------*/
    if (root == nullptr) {
        // 情况 1：新遍历的这条路径上的黑色节点的数量'不等于'最左侧路径上的黑色节点的数量
        if (refNum != blackNum) {
            cout << "存在黑色结点的数量不相等的路径" << endl;
            return false;
        }
        // 情况 2：新路径'等于'旧路径
        return true;
    }
    /*------------处理'正常情况'------------*/
    // 1. 检查'连续红节点的情况'
    if (root->_col == RED && root->_parent->_col == RED) // 注意这里的细节，如果我们正向思维的话
    {
        cout << root->_kv.first << " 存在连续的红色结点" << endl;
        return false;
    }
    /* 注意实现：如果解决上面的这个问题我们使用正向思维的话：'对于当前红色节点要判断它的孩子是也是红色节点' *
     * 1. 我们不禁要判断 root 节点的左孩子还要判断右孩子是不是'红色' *
     * 2. 并且有可能正在遍历的这个节点还有可能根本不存在 *
     */
    // 2. 检查'记录黑色节点的数量'
    if (root->_col == BLACK) {
        blackNum++;
    }
    // 3. 递归检查左右子树
    return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}

代码实现

红黑树的存储结构是什么样的？

一、节点的存储结构

// 任务 2：定义红黑树节点的'颜色枚举'
enum Colour {
    RED,   // 红色节点
    BLACK  // 黑色节点
};

// 任务 3：定义红黑树节点的'结构体模板'
template<class K, class V>
struct RBTreeNode {
    /*--------------------------成员变量--------------------------*/
    // 1. 节点存储的键值对
    // 2. 左孩子指针
    // 3. 右孩子指针
    // 4. 父节点指针
    // 4. 节点的颜色
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    Colour _col;

    /*--------------------------成员函数--------------------------*/
    // 1. 定义：'红黑树节点的构造函数'
    RBTreeNode(const pair<K, V>& kv) // 注意：参数是'红黑树节点存储的键值对'
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};

二、树的存储结构

// 任务 4：定义红黑树的'类模板'
template<class K, class V>
class RBTree {
private:
    /*--------------------------成员变量--------------------------*/
    RBTreeNode<K, V>* _root = nullptr;

    /*--------------------------类型别名--------------------------*/
    // 1. 重新定义红黑树节点的类型：RBTreeNode<K,V> ---> Node
    typedef RBTreeNode<K, V> Node;

public:
    /*--------------------------成员函数（公有）--------------------------*/
    // …………
};

实现文件：RBTree.h

#pragma once

// 任务 1：包含需要使用的头文件
#include <iostream>
using namespace std;

// 任务 2：定义红黑树节点的'颜色枚举'
enum Colour {
    RED,   // 红色节点
    BLACK  // 黑色节点
};

// 任务 3：定义红黑树节点的'结构体模板'
template<class K, class V>
struct RBTreeNode {
    /*--------------------------成员变量--------------------------*/
    // 1. 节点存储的键值对
    // 2. 左孩子指针
    // 3. 右孩子指针
    // 4. 父节点指针
    // 4. 节点的颜色
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;

    /* 注意事项：怎么理解上面的三个指针的类型为什么要这么写成 BBTNode<K,V>*的形式？ *
     * 1. 首先：它们都是指针，所以要添加指针的符号'*' *
     * 2. 其次：它们都指向的都是红黑树的节点，所以要添加节点的类型'RBTNode' *
     * 3. 最后：红黑树的节点是'结构体'并且是'结构体模板'，所以要添加模板参数'<K,V>' *
     */
    Colour _col;

    /*--------------------------成员函数--------------------------*/
    // 1. 定义：'红黑树节点的构造函数'
    RBTreeNode(const pair<K, V>& kv) // 注意：参数是'红黑树节点存储的键值对'
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};

// 任务 4：定义红黑树的'类模板'
template<class K, class V>
class RBTree {
private:
    /*--------------------------成员变量--------------------------*/
    RBTreeNode<K, V>* _root = nullptr;

    /*--------------------------类型别名--------------------------*/
    // 1. 重新定义红黑树节点的类型：RBTreeNode<K,V> ---> Node
    typedef RBTreeNode<K, V> Node;

    /*--------------------------成员函数（私有）--------------------------*/
    // 1. 实现：'中序遍历'
    void _InOrder(Node* root) {
        /*------------处理'特殊情况 + 递归出口'------------*/
        if (root == nullptr) {
            return;
        }
        /*------------处理'正常情况'------------*/
        // 1. 递归遍历左子树
        _InOrder(root->_left);
        // 2. 输出当前节点的键值对
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        // 3. 递归遍历右子树
        _InOrder(root->_right);
    }

    // 2. 实现：'获取树的高度'
    int _Height(Node* root) {
        /*------------处理'特殊情况 + 递归出口'------------*/
        if (root == nullptr) {
            return 0;
        }
        /*------------处理'正常情况'------------*/
        // 1. 递归计算左子树的高度
        int leftHeight = _Height(root->_left);
        // 2. 递归计算右子树的高度
        int rightHeight = _Height(root->_right);
        // 3. 返回较高子树的高度 +1
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    // 3. 实现：'获取树中节点的数量'
    int _Size(Node* root) {
        /*------------处理'特殊情况 + 递归出口'------------*/
        if (root == nullptr) {
            return 0;
        }
        /*------------处理'正常情况'------------*/
        // 1. 递归计算树中节点的总数量 ---> 节点数 = 左子树节点数 + 右子树节点数 + 1（当前节点）
        return _Size(root->_left) + _Size(root->_right) + 1;
    }

    // 4. 实现：'判断一棵树是不是红黑树'
    bool Check(Node* root, int blackNum, const int refNum) {
        /*------------处理'特殊情况 + 递归出口'------------*/
        if (root == nullptr) {
            // 情况 1：新遍历的这条路径上的黑色节点的数量'不等于'最左侧路径上的黑色节点的数量
            if (refNum != blackNum) {
                cout << "存在黑色结点的数量不相等的路径" << endl;
                return false;
            }
            // 情况 2：新路径'等于'旧路径
            return true;
        }
        /*------------处理'正常情况'------------*/
        // 1. 检查'连续红节点的情况'
        if (root->_col == RED && root->_parent->_col == RED) // 注意这里的细节，如果我们正向思维的话
        {
            cout << root->_kv.first << " 存在连续的红色结点" << endl;
            return false;
        }
        /* 注意实现：如果解决上面的这个问题我们使用正向思维的话：'对于当前红色节点要判断它的孩子是也是红色节点' *
         * 1. 我们不禁要判断 root 节点的左孩子还要判断右孩子是不是'红色' *
         * 2. 并且有可能正在遍历的这个节点还有可能根本不存在 *
         */
        // 2. 检查'记录黑色节点的数量'
        if (root->_col == BLACK) {
            blackNum++;
        }
        // 3. 递归检查左右子树
        return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
    }

public:
    /*--------------------------成员函数（公有）--------------------------*/
    // 1. 实现：'红黑树的查找'的操作
    Node* Find(const K& key) // 注意：根据键 key 进行查找，类似二叉搜索树中查找操作
    {
        // 1. 定义进行遍历节点的指针
        Node* curr = _root;
        // 2. 使用 while 循环查找对应节点
        while (curr) {
            // 情况 1：当前遍历到的节点的键 < 要查找的键 ---> '继续向当前节点的右子树中查找'
            if (curr->_kv.first < key) {
                curr = curr->_right;
            }
            // 情况 2：当前遍历到的节点的键 > 要查找的键 ---> '继续向当前节点的左子树中查找'
            else if (curr->_kv.first > key) {
                curr = curr->_left;
            }
            // 情况 3：当前遍历到的节点的键 = 要查找的键 ---> '找到了要查找的键'
            else {
                return curr;
            }
        }
        // 3. 跳出了循环，说明没有找到的键为 key 的节点
        return nullptr;
    }

    // 2. 实现：'红黑树的插入'的操作
    bool Insert(const pair<K, V>& kv) // 注意：对于 set 而言插入的是键 K key，对于 map 而言插入的是键值对 pair<K,V> kv
    {
        /*--------处理'特殊情况 + 递归出口'--------*/
        if (_root == nullptr) {
            // 1. 创建新节点
            _root = new Node(kv);
            // 2. 将新节点染色为黑色 (*相比 AVL 树多了这一步骤*)
            _root->_col = BLACK;
            // 3. 返回 true 即可
            return true;
        }
        /*--------处理'正常情况'--------*/
        /*----------------第一阶段：准备阶段----------------*/
        // 1. 创建一个指向当前节点的指针
        Node* current = _root;
        // 2. 创建一个指向当前节点的父节点的指针
        Node* parent = nullptr;

        /*----------------第二阶段：查找阶段----------------*/
        while (current) // 循环查找插入位置
        {
            // 情况 1：当前遍历到的节点的键 < 要插入的键 ---> '继续寻找'
            if (current->_kv.first < kv.first) // 注意：没学 pair 之前我们是这样写的：if (current->_key < key)
            {
                // 1. 更新当前遍历节点的父节点
                parent = current;
                // 不同之处 1：这里的需要更新 parent 指针的位置
                // 原因：下面我们要在 curr 指针指向的位置进行插入操作，所以我们需要记录当前遍历到节点的父节点
                // 2. 继续去右子树中寻找
                current = current->_right;
            }
            // 情况 2：当前遍历到的节点的键 > 要插入的键 ---> '继续寻找'
            else if (current->_kv.first > kv.first) // 注意：没学 pair 之前我们是这样写的：else if (current->_key > key)
            {
                parent = current;
                current = current->_left; // 继续去左子树中寻找
            }
            // 情况 3：当前遍历到的节点的键 = 要插入的键 ---> '键已存在'---> 查找插入位置失败
            else {
                return false; // 不同之处 2：这里放回的是 false
                // 原因：我们实现的二叉搜索树不支持存储'键相等的节点'
            }
        }
        // 注意：能执行到此处，说明在第二阶段成功跳出了 while 循环，并非因 return false 终止程序，
        // 这意味着已找到插入节点的位置，那下面就让我们插入节点吧

        /*----------------第三阶段：插入阶段----------------*/
        // 1. 创建要插入的节点
        current = new Node(kv); // 注意：没学 pair 之前我们是这样写的：current = new Node(key, value);
        // 2. 将新节点染为红色 (*相比 AVL 树多了这一步骤*)
        current->_col = RED;
        // 3. 将新节点连接到二叉搜索树中 ---> 注意并不能简单的进行插入操作要先判断：
        // '新节点和父节点的键之间的大小关系，从而判断出新节点是应该插入到父节点的左子节点还是右子节点'
        // 情况 1：新节点的键 < 父节点的键
        if (kv.first < parent->_kv.first) // 注意：没学 pair 之前我们是这样写的：if (key < parent->_key)
        {
            parent->_left = current;
        }
        // 情况 2：新节点的键 > 父节点的键
        else // 注意：这里使用 else 表面上看是：满足 key >= parent->_key 条件的情况都可以执行下面的代码
        { // 但其实 key = parent->_key 这种情况在上面的第二阶段中已经被的 return false 排除掉了
            parent->_right = current;
        }

        /*------------------声明：如果是普通的二叉搜索树，到这里插入操作就已经算作是结束了，但是对于平衡二叉搜索树还有步骤------------------*/
        /*----------------第四阶段：连接阶段----------------*/
        // 1. 更新新插入节点的父节点
        current->_parent = parent; // 这里之所以要进行更新是因为，红黑树节点的存储了三个指针，也就是其底层是用'三叉链'的结构进行存储的

        /*----------------第五阶段：调整阶段----------------*/
        while (parent && parent->_col == RED) // 不断地进行调整，直至：'parent 为空节点'或'parent 节点颜色为黑色'
        {
            // 1. 获取祖父节点（父节点的父节点）
            Node* grandfather = parent->_parent;
            // 2. 处理需要进行调整的场景
            // 场景一：父节点是祖父节点的左孩子节点
            if (parent == grandfather->_left) {
                // 情况 1：叔叔节点'存在'且为'红色' ---> '变色处理'
                Node* uncle = grandfather->_right;
                if (uncle && uncle->_col == RED) {
                    /*-------第一步：变色处理-------*/
                    // 1. 将'父节点'染为'黑色'
                    // 2. 将'叔叔节点'染为'黑色'
                    // 3. 将'祖父节点'染为'红色'
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 注意：处理完上面这一种仅仅需要变色的情况之后，调整还没结束还需要向上继续进行检查
                    /*-------第二步：向上检查-------*/
                    // 1.'祖父节点'变为'当前节点'
                    current = grandfather;
                    // 2.'父节点'变为'祖父节点的父节点'
                    parent = grandfather->_parent; // 或者写成：parent = current->_parent;
                }
                // 情况 2：叔叔节点'不存在'或为'黑色' ---> '旋转处理'
                else {
                    // 情况 2.1：当前节点是父节点的左孩子 ---> '右单旋'
                    if (current == parent->_left) {
                        /*-------第一步：旋转处理-------*/
                        // 1. 右单旋'祖父节点'
                        RotateR(grandfather);
                        /*-------第一步：变色处理-------*/
                        // 1. 将'父节点'染为'黑色'
                        // 2. 将'祖父节点'染为'红色'
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    // 情况 2.2：当前节点是父节点的右孩子 ---> '左右双旋'
                    else {
                        /*-------第一步：旋转处理-------*/
                        // 1. 先左单旋'父节点'
                        RotateL(parent);
                        // 2. 再右单旋'祖父节点'
                        RotateR(grandfather);
                        /*-------第二步：变色处理-------*/
                        // 1. 将'当前节点'染为'黑色'
                        // 2. 将'祖父节点'染为'红色'
                        current->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    // 处理完上面的两种需要进行旋转的情况之后，就可以跳出 while 循环了
                    break;
                }
            }
            // 场景二：父节点是祖父节点的右孩子节点 (注意：场景二其实和场景一的本质是一样的，区别在于两者由于镜像的关系所以两者的旋转操作的是相反的)
            else {
                // 情况 1：叔叔节点'存在'且为'红色' ---> '变色处理'
                Node* uncle = grandfather->_left;
                if (uncle && uncle->_col == RED) {
                    /*-------第一步：变色处理-------*/
                    // 1. 将'父节点'染为'黑色'
                    // 2. 将'叔叔节点'染为'黑色'
                    // 3. 将'祖父节点'染为'红色'
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 注意：处理完上面这一种仅仅需要变色的情况之后，调整还没结束还需要向上继续进行检查
                    /*-------第二步：向上检查-------*/
                    // 1.'祖父节点'变为'当前节点'
                    current = grandfather;
                    // 2.'父节点'变为'祖父节点的父节点'
                    parent = grandfather->_parent; // 或者写成：parent = current->_parent;
                }
                // 情况 2：叔叔节点'不存在'或为'黑色' ---> '旋转处理'
                else {
                    // 情况 2.1：当前节点是父节点的右孩子 ---> '左单旋'
                    if (current == parent->_right) {
                        /*-------第一步：旋转处理-------*/
                        // 1. 左单旋'祖父节点'
                        RotateL(grandfather);
                        /*-------第一步：变色处理-------*/
                        // 1. 将'父节点'染为'黑色'
                        // 2. 将'祖父节点'染为'红色'
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    // 情况 2.2：当前节点是父节点的左孩子 ---> '右左双旋'
                    else {
                        /*-------第一步：旋转处理-------*/
                        // 1. 先右单旋'父节点'
                        RotateR(parent);
                        // 2. 再左单旋'祖父节点'
                        RotateL(grandfather);
                        /*-------第二步：变色处理-------*/
                        // 1. 将'当前节点'染为'黑色'
                        // 2. 将'祖父节点'染为'红色'
                        current->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    // 处理完上面的两种需要进行旋转的情况之后，就可以跳出 while 循环了
                    break;
                }
            }
            // 场景二结束
        }
        // 调整阶段结束
        // 1. 根节点强制染黑
        _root->_col = BLACK;
        // 2. 返回 true 即可
        return true;
    }

    // Insert 函数结束

    // 3. 实现：'右单旋'操作（以 parent 为中心右旋）
    void RotateR(Node* parent) {
        /*---------------第一阶段：准备阶段---------------*/
        // 1. 记录 parent 的左子节点的'指针'
        // 2. 记录 parent 的左子节点的右子节点的'指针'
        // 3. 记录 parent 的父节点的'指针'
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right; // 或者写成：Node* subLR = subL->_right;
        Node* pParent = parent->_parent;

        /*---------------第二阶段：调整阶段---------------*/
        // 1. 调整 parent 和 subLR 的关系
        parent->_left = subLR;
        if (subLR) // 注意细节：subLR 不一定存在，所以这里为了判断防止对空指针进行解引用，先使用 if 对 subLR 指针进行一个判断
        {
            subLR->_parent = parent;
        }
        // 2. 调整 parent 和 subL 的关系
        parent->_parent = subL;
        subL->_right = parent;
        // 3. 调整根节点或祖父节点的子树指向
        // 情况 1：parent 节点是根节点 ---> 调整根节点
        if (parent == _root) {
            // 1. 调整根节点
            _root = subL; // 注意：这里的调整根节点要写成：_root = subL，千万不要写成了 subL = _root;
            // 2. 更新 subL 的父节点
            subL->_parent = nullptr; // 或者写成：_root->_parent =nullptr;
        }
        // 情况 2：parent 节点不是根节点 ---> 调整祖父节点的子树指向
        else {
            // 1. 调整祖父节点的子树指向
            if (parent == pParent->_left) {
                pParent->_left = subL;
            } else {
                pParent->_right = subL;
            }
            // 2. 更新 subL 的父节点
            subL->_parent = pParent;
        }
        //// 4. 更新平衡因子 ---> 右单旋后 subL 和 parent 的平衡因子均为 0
        // subL->_bf = 0;
        // parent->_bf = 0;
        // 注意：对于红黑树由于没有使用'平衡因子'所以旋转结束后并不需要更新平衡因子
    }

    // 4. 实现：'左单旋'操作（处理右右失衡的情况）
    void RotateL(Node* parent) {
        /*---------------第一阶段：准备阶段---------------*/
        // 1. 记录 parent 的右子节点的'指针'
        // 2. 记录 parent 的右子节点的左子节点的'指针'
        // 3. 记录 parent 的父节点的'指针'
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left; // 或者写成：Node* subLR = subL->_left;
        Node* pParent = parent->_parent;

        /*---------------第二阶段：调整阶段---------------*/
        // 1. 调整 parent 和 subRL 的关系
        parent->_right = subRL;
        if (subRL) {
            subRL->_parent = parent;
        }
        // 2. 调整 parent 和 subR 的关系
        parent->_parent = subR;
        subR->_left = parent;
        // 3. 调整根节点或祖父节点的子树指向
        // 情况 1：parent 节点是根节点 ---> 调整根节点
        if (pParent == nullptr) // 或者写成：parent == _root
        {
            // 1. 调整根节点
            _root = subR;
            // 2. 更新 subL 的父节点
            subR->_parent = nullptr; // 或者写成：_root->_parent = nullptr;
        }
        // 情况 2：parent 节点不是根节点 ---> 调整祖父节点的子树指向
        else {
            // 1. 调整祖父节点的子树指向
            if (parent == pParent->_left) {
                pParent->_left = subR;
            } else {
                pParent->_right = subR;
            }
            // 2. 更新 subL 的父节点
            subR->_parent = pParent;
        }
        //// 4. 更新平衡因子 ---> 左单旋后 subR 和 parent 的平衡因子均为 0
        // subR->_bf = 0;
        // parent->_bf = 0;
    }

    // 5. 实现：'中序遍历'
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

    // 6. 实现：'获取树的高度'
    int Height() {
        return _Height(_root);
    }

    // 7. 实现：'获取节点的数量'
    int Size() {
        return _Size(_root);
    }

    // 8. 实现：'判断一棵树是不是红黑树'
    bool IsRBTree() {
        /*------------处理'特殊情况 + 递归出口'------------*/
        // 特殊情况 1：'空树'
        if (_root == nullptr) {
            return true; // 空树也是红黑树
        }
        // 特殊情况 2：'只有一个节点并且为红色'
        if (_root->_col == RED) {
            return false; // 不满足红黑树的规则
        }
        /*------------处理'正常情况'------------*/
        /*------- 第一步：计算最左路径上节点的数量-------*/
        // 1. 记录该路径上黑色节点的数量
        int refNum = 0;
        // 2. 定义一个指向当前节点的指针
        Node* current = _root;
        // 3. 使用 while 循环统计该路径上黑色节点的数量
        while (current) {
            // 3.1：统计
            if (current->_col == BLACK) {
                ++refNum;
            }
            // 3.2：移动
            current = current->_left;
        }
        /*-------第二步：递归检查其他路径上面的黑色节点的数量-------*/
        return Check(_root, 0, refNum);
    }
};

测试文件：Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "RBTree.h"

void TestRBTree() {
    RBTree<int, int> rbTree;

    /*-------------------测试 1：测试插入操作-------------------*/
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a) {
        rbTree.Insert({ e, e });
    }

    /*-------------------测试 2：测试中序遍历-------------------*/
    std::cout << "中序遍历结果：" << std::endl;
    rbTree.InOrder();

    /*-------------------测试 3：测试红黑树平衡性-------------------*/
    std::cout << "红黑树平衡性验证结果：" << (rbTree.IsRBTree() ? "平衡（1）" : "不平衡（0）") << std::endl;

    /*-------------------测试 4：测试查找操作-------------------*/
    int keyToFind = 7;
    auto foundNode = rbTree.Find(keyToFind);
    if (foundNode) {
        std::cout << "找到节点：" << foundNode->_kv.first << ":" << foundNode->_kv.second << std::endl;
    } else {
        std::cout << "未找到节点：" << keyToFind << std::endl;
    }

    /*-------------------测试 4：测试树的高度和节点数量-------------------*/
    std::cout << "树的高度：" << rbTree.Height() << std::endl;
    std::cout << "节点数量：" << rbTree.Size() << std::endl;
}

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

运行结果：

终极对决

一、选手登场

AVL 树的源代码

#pragma once

// 任务 1：包含需要使用头文件
#include <iostream>
#include <assert.h>
using namespace std;

// 任务 2：定义 AVL 树节点的结构模板
template<class K, class V>
struct AVLTreeNode {
    /*----------------第一部分：成员变量----------------*/
    // 1. 节点存储的键值对
    // 2. 左右子节点的指针
    // 3. 父节点的指针
    // 4. 平衡因子
    pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf;

    /*----------------第二部分：成员函数----------------*/
    // 1.AVL 树节点的构造函数
    AVLTreeNode(const pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};

// 任务 3：定义 AVL 树的类模板
template<class K, class V>
class AVLTree {
private:
    /*----------------第一部分：成员变量----------------*/
    AVLTreeNode<K, V>* _root = nullptr;

    /*----------------第二部分：类型别名----------------*/
    // 1. 重新定义 AVL 树节点的类型：pair<K,V> ---> Node
    typedef AVLTreeNode<K, V> Node;

    /*----------------第三部分：成员函数（私有）----------------*/
    // 1. 实现：'中序遍历'的操作
    void _InOrder(Node* root) {
        // 处理'特殊情况'+ '递归出口'
        if (root == nullptr) {
            return;
        }
        // 处理'正常情况'
        // 1. 首先递归遍历'左子树'
        _InOrder(root->_left);
        // 2. 然后输出遍历到的当前的节点
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        // 3. 最后递归遍历'右子树'
        _InOrder(root->_right);
    }

    // 2. 实现：'获取树的高度'的操作
    int _Height(Node* root) {
        // 处理'特殊情况'+ '递归出口'
        if (root == nullptr) {
            return 0;
        }
        // 处理'正常情况'
        // 1. 递归计算左子树的高度
        int leftHeight = _Height(root->_left);
        // 2. 递归计算右子树的高度
        int rightHeight = _Height(root->_right);
        // 3. 返回左右子树中高度最高的那一个
        return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    }

    // 3. 实现：'获取节点的数量'的操作
    int _Size(Node* root) {
        // 处理'特殊情况'+ '递归出口'
        if (root == nullptr) {
            return 0;
        }
        // 处理'正常情况'
        // 1. 直接返回递归计算的左子树和右子树的节点的数量之和
        return _Size(root->_left) + _Size(root->_right) + 1;
    }

    // 4. 实现：'判断一棵树是不是 AVL 树'
    bool _IsAVLTree(Node* root) {
        // 处理'特殊情况'+ '递归出口'
        if (root == nullptr) {
            return true; // 空树是 AVL 树
        }
        // 处理'正常情况'
        /*-------------------第一步：计算平衡因子-------------------*/
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        int bf = rightHeight - leftHeight;

        /*-------------------第一步：检查平衡因子-------------------*/
        // 1. 检查平衡因子'是否合法'
        if (abs(bf) >= 2) {
            cout << root->_kv.first << "平衡因子不合法" << endl;
            return false;
        }
        // 2. 检查平衡因子'是否异常'
        if (root->_bf != bf) {
            cout << root->_kv.first << "平衡因子异常" << endl;
            return false;
        }
        /*-------------------第三步：递归验证-------------------*/
        return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
    }

public:
    /*----------------第三部分：成员函数（公有）----------------*/
    // 1. 实现：'查找键对应节点'
    Node* Find(const K& key) {
        // 1. 定义进行遍历节点的指针
        Node* curr = _root;
        // 2. 使用 while 循环查找对应节点
        while (curr) {
            // 情况 1：当前遍历到的节点的键 < 要查找的键 ---> '继续向当前节点的右子树中查找'
            if (curr->_kv.first < key) {
                curr = curr->_right;
            }
            // 情况 2：当前遍历到的节点的键 > 要查找的键 ---> '继续向当前节点的左子树中查找'
            else if (curr->_kv.first > key) {
                curr = curr->_left;
            }
            // 情况 3：当前遍历到的节点的键 = 要查找的键 ---> '找到了要查找的键'
            else {
                return curr;
            }
        }
        // 3. 跳出了循环，说明没有找到的键为 key 的节点
        return nullptr;
    }

    // 2. 实现：'插入操作'
    bool Insert(const pair<K, V>& kv) // 注意：没学 pair 之前我们是这样写的：bool Insert(const K& key, const V& value)
    {
        // 特殊情况：要插入的节点的树是'空树'
        if (_root == nullptr) {
            // 1. 直接创建一个节点为跟节点
            _root = new Node(kv); // 注意：没学 pair 之前我们是这样写的：_root = new Node(key, value);
            // 2. 返回 true 即可
            return true;
        }
        // 正常情况：要插入的节点的树是'非空树'
        /*----------------第一阶段：准备阶段----------------*/
        // 1. 创建一个遍历树的当前节点指针
        Node* current = _root;
        // 2. 创建当前遍历节点的父节点的指针
        Node* parent = nullptr;

        /*----------------第二阶段：查找阶段----------------*/
        while (current) // 循环查找插入位置
        {
            // 情况 1：当前遍历到的节点的键 < 要插入的键 ---> '继续寻找'
            if (current->_kv.first < kv.first) // 注意：没学 pair 之前我们是这样写的：if (current->_key < key)
            {
                // 1. 更新当前遍历节点的父节点
                parent = current;
                // 不同之处 1：这里的需要更新 parent 指针的位置
                // 原因：下面我们要在 curr 指针指向的位置进行插入操作，所以我们需要记录当前遍历到节点的父节点
                // 2. 继续去右子树中寻找
                current = current->_right;
            }
            // 情况 2：当前遍历到的节点的键 > 要插入的键 ---> '继续寻找'
            else if (current->_kv.first > kv.first) // 注意：没学 pair 之前我们是这样写的：else if (current->_key > key)
            {
                parent = current;
                current = current->_left; // 继续去左子树中寻找
            }
            // 情况 3：当前遍历到的节点的键 = 要插入的键 ---> '键已存在'---> 查找插入位置失败
            else {
                return false; // 不同之处 2：这里放回的是 false
                // 原因：我们实现的二叉搜索树不支持存储'键相等的节点'
            }
        }

        /*----------------第三阶段：插入阶段----------------*/
        // 1. 创建要插入的节点
        current = new Node(kv); // 注意：没学 pair 之前我们是这样写的：current = new Node(key, value);
        // 2. 将新节点连接到二叉搜索树中 ---> 注意并不能简单的进行插入操作要先判断：
        // '新节点和父节点的键之间的大小关系，从而判断出新节点是应该插入到父节点的左子节点还是右子节点'
        // 情况 1：新节点的键 < 父节点的键
        if (kv.first < parent->_kv.first) // 注意：没学 pair 之前我们是这样写的：if (key < parent->_key)
        {
            parent->_left = current;
        }
        // 情况 2：新节点的键 > 父节点的键
        else // 注意：这里使用 else 表面上看是：满足 key >= parent->_key 条件的情况都可以执行下面的代码
        { // 但其实 key = parent->_key 这种情况在上面的第二阶段中已经被的 return false 排除掉了
            parent->_right = current;
        }

        /*------------------声明：如果是普通的二叉搜索树，到这里插入操作就已经算作是结束了，但是对于平衡二叉搜索树还有步骤------------------*/
        /*----------------第四阶段：连接阶段----------------*/
        // 1. 更新新插入节点的父节点
        current->_parent = parent; // 这里之所以要进行更新是因为，AVL 树节点的存储了三个指针，也就是其底层是用'三叉链'的结构进行存储的

        /*----------------第五阶段：调整阶段----------------*/
        while (parent) // 循环进行平衡二叉搜索树的高度
        {
            /*-------------第一步：更新新插入节点的父节点的平衡因子-------------*/
            // 位置 1：新插入节点是左子节点 ---> 父节点的平衡因子 -1
            if (current == parent->_left) {
                parent->_bf--; // 插入到左子树，左子树高度 +1，平衡因子 -1
            }
            // 位置 2：新插入节点是右子节点 ---> 父节点的平衡因子 +1
            else {
                parent->_bf++; // 插入到右子树，右子树高度 +1，平衡因子 +1
            }

            /*-------------第二步：根据父节点的平衡因子做进一步的更新-------------*/
            // 情况 1：父节点的平衡因子为 0 ---> 高度变化未影响上层，结束更新
            if (parent->_bf == 0) {
                break;
            }
            // 情况 2：父节点的平衡因子为±1 ---> 高度变化需向上传递，继续更新上层节点
            else if (parent->_bf == -1 || parent->_bf == 1) {
                // 1. 新节点 ---> 父节点
                current = current->_parent; // 或者写成：current = parent;
                // 2. 父节点 ---> 爷爷节点
                parent = parent->_parent; // 注意：这里也就体现了，为什么我们要对二叉搜索树底层结构中再设计一个指针_parent 了，
                // 因为：调整阶段我们需要更新上层的节点，多引入一个_parent 指针可以让我们更方便的找到上层的节点
            }
            // 情况 3：父节点的平衡因子为±2 ---> 树失衡，需要旋转调整
            else if (parent->_bf == -2 || parent->_bf == 2) // 注意：按理说这里我们因该使用一个 else 即可，因为平衡因子只可能是：0，±1，±2
            { // 但是不怕一万就怕万一，这里我们使用防御性编程，再另设一个情况 4（特殊情况）
                // 失衡 1：左左失衡（父子平衡因子都为'负'） ---> 右单旋
                if (parent->_bf == -2 && current->_bf == -1) {
                    RotateR(parent);
                }
                // 失衡 2：右右失衡（父子平衡因子都为'正'） ---> 左单旋
                else if (parent->_bf == 2 && current->_bf == 1) {
                    RotateL(parent);
                }
                // 失衡 3：左右失衡（父为'负'，子为'正'） ---> 左右双旋
                else if (parent->_bf == -2 && current->_bf == 1) {
                    RotateLR(parent);
                }
                // 失衡 4：右左失衡（父为'正'，子为'负'） ----> 右左双旋
                else if (parent->_bf == 2 && current->_bf == -1) {
                    RotateRL(parent);
                }
                // 特殊情况：非法平衡因子 ---> 断言失败
                else {
                    assert(false);
                }
                break; // 注意：这里一定要添加一个 break，因为这个 break 是调整成功出 while 循环的唯一方式
            }
            // 情况 4：非法平衡因子 ---> 断言失败
            else {
                assert(false);
            }
        }
        return true; // 跳出了调整阶段 while 循环，说明已经调整成功了，返回 true
    }

    // 3. 实现：'右单旋'操作（处理左左失衡的情况）
    void RotateR(Node* parent) {
        /*---------------第一阶段：准备阶段---------------*/
        // 1. 记录 parent 的左子节点的'指针'
        // 2. 记录 parent 的左子节点的右子节点的'指针'
        // 3. 记录 parent 的父节点的'指针'
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right; // 或者写成：Node* subLR = subL->_right;
        Node* pParent = parent->_parent;

        /*---------------第二阶段：调整阶段---------------*/
        // 1. 调整 parent 和 subLR 的关系
        parent->_left = subLR;
        if (subLR) // 注意细节：subLR 不一定存在，所以这里为了判断防止对空指针进行解引用，先使用 if 对 subLR 指针进行一个判断
        {
            subLR->_parent = parent;
        }
        // 2. 调整 parent 和 subL 的关系
        parent->_parent = subL;
        subL->_right = parent;
        // 3. 调整根节点或祖父节点的子树指向
        // 情况 1：parent 节点是根节点 ---> 调整根节点
        if (parent == _root) {
            // 1. 调整根节点
            _root = subL; // 注意：这里的调整根节点要写成：_root = subL，千万不要写成了 subL = _root;
            // 2. 更新 subL 的父节点
            subL->_parent = nullptr; // 或者写成：_root->_parent =nullptr;
        }
        // 情况 2：parent 节点不是根节点 ---> 调整祖父节点的子树指向
        else {
            // 1. 调整祖父节点的子树指向
            if (parent == pParent->_left) {
                pParent->_left = subL;
            } else {
                pParent->_right = subL;
            }
            // 2. 更新 subL 的父节点
            subL->_parent = pParent;
        }
        // 4. 更新平衡因子 ---> 右单旋后 subL 和 parent 的平衡因子均为 0
        subL->_bf = 0;
        parent->_bf = 0;
    }

    // 4. 实现：'左单旋'操作（处理右右失衡的情况）
    void RotateL(Node* parent) {
        /*---------------第一阶段：准备阶段---------------*/
        // 1. 记录 parent 的右子节点的'指针'
        // 2. 记录 parent 的右子节点的左子节点的'指针'
        // 3. 记录 parent 的父节点的'指针'
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left; // 或者写成：Node* subLR = subL->_left;
        Node* pParent = parent->_parent;

        /*---------------第二阶段：调整阶段---------------*/
        // 1. 调整 parent 和 subRL 的关系
        parent->_right = subRL;
        if (subRL) {
            subRL->_parent = parent;
        }
        // 2. 调整 parent 和 subR 的关系
        parent->_parent = subR;
        subR->_left = parent;
        // 3. 调整根节点或祖父节点的子树指向
        // 情况 1：parent 节点是根节点 ---> 调整根节点
        if (pParent == nullptr) // 或者写成：parent == _root
        {
            // 1. 调整根节点
            _root = subR;
            // 2. 更新 subL 的父节点
            subR->_parent = nullptr; // 或者写成：_root->_parent = nullptr;
        }
        // 情况 2：parent 节点不是根节点 ---> 调整祖父节点的子树指向
        else {
            // 1. 调整祖父节点的子树指向
            if (parent == pParent->_left) {
                pParent->_left = subR;
            } else {
                pParent->_right = subR;
            }
            // 2. 更新 subL 的父节点
            subR->_parent = pParent;
        }
        // 4. 更新平衡因子 ---> 左单旋后 subR 和 parent 的平衡因子均为 0
        subR->_bf = 0;
        parent->_bf = 0;
    }

    // 5. 实现：'左右双旋'操作（处理左右失衡的情况）
    void RotateLR(Node* parent) {
        /*---------------第一阶段：准备阶段---------------*/
        // 1. 记录 parent 的左子节点的'指针'
        // 2. 记录 parent 的左子节点的右子节点的'指针'
        // 3. 记录 parent 的左子节点的右子节点的'平衡因子'
        Node* subL = parent->_left;
        Node* subLR = parent->_left->_right; // 或者写成：Node* subLR = subL->_right;
        int bf = subLR->_bf; // 注意：双选可以使用两个单旋复用实现，所以我们不需要重新实现节点之间的关系的更新了，但是双旋还有一个难点：'节点的平衡因子的更新'
        // 所以：这里我们需要定义一个变量记录 subLR 的平衡因子
        // 因为：经过双旋之后，节点平衡因子的更新依赖于'subLR 节点原始的平衡因子'

        /*---------------第二阶段：旋转阶段---------------*/
        // 1. 首先对当前的节点的左子树进行'左单旋'
        RotateL(parent->_left);
        // 2. 然后对当前的节点进行'右单旋'
        RotateR(parent);

        /*---------------第三阶段：更新阶段---------------*/
        // 情况 1：subLR 节点原始的平衡因子为'-1'
        if (bf == -1) {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        }
        // 情况 2：subLR 节点原始的平衡因子为'1'
        else if (bf == 1) {
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_bf = 0;
        }
        // 情况 3：subLR 节点原始的平衡因子为'0'
        else if (bf == 0) // 注意：同样的按理说：subLR 的平衡因子只可能是：0，1，-1 这三中情况，也就是说这里我们因该使用 else 即可，所以我们还使用防御性编程，以防万一
        {
            subLR->_bf = 0; // 注意：这里表面看上去并不需要进行更新，这里只是为了以防万一
            subL->_bf = 0;
            parent->_bf = 0;
        }
        // 情况 4：非法平衡因子，断言失败
        else {
            assert(false);
        }
    }

    // 6. 实现：'右左双旋'操作（处理右左失衡的情况）
    void RotateRL(Node* parent) {
        /*---------------第一阶段：准备阶段---------------*/
        // 1. 记录 parent 的右子节点的'指针'
        // 2. 记录 parent 的右子节点的左子节点的'指针'
        // 3. 记录 parent 的右子节点的左子节点的'平衡因子'
        Node* subR = parent->_right;
        Node* subRL = parent->_right->_left; // 或者写成：Node* subRL = subR->_left;
        int bf = subRL->_bf; // 注意：双选可以使用两个单旋复用实现，所以我们不需要重新实现节点之间的关系的更新了，但是双旋还有一个难点：'节点的平衡因子的更新'
        // 所以：这里我们需要定义一个变量记录 subRL 的平衡因子
        // 因为：经过双旋之后，节点平衡因子的更新依赖于'subRL 节点原始的平衡因子'

        /*---------------第二阶段：旋转阶段---------------*/
        // 1. 首先对当前的节点的右子树进行'右单旋'
        RotateR(parent->_right);
        // 2. 然后对当前的节点进行'左单旋'
        RotateL(parent);

        /*---------------第三阶段：更新阶段---------------*/
        // 情况 1：subRL 节点原始的平衡因子为'-1'
        if (bf == -1) {
            subRL->_bf = 0;
            subR->_bf = 1;
            parent->_bf = 0;
        }
        // 情况 2：subRL 节点原始的平衡因子为'1'
        else if (bf == 1) {
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = -1;
        }
        // 情况 3：subRL 节点原始的平衡因子为'0'
        else if (bf == 0) {
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = 0;
        }
        // 情况 4：非法平衡因子，断言失败
        else {
            assert(false);
        }
    }

    // 7. 实现：'中序遍历'操作
    void InOrder() {
        _InOrder(_root); // 注意：这里我们实际上是调用 private 权限下的_InOrder() 接口函数实现中序遍历
        cout << endl;
    }

    // 8. 实现：'获取树的高度'操作
    int Height() {
        return _Height(_root); // 和上面的一样我们还调用其他接口实现
    }

    // 9. 实现：'获取节点的数量'操作
    int Size() {
        return _Size(_root);
    }

    // 10. 实现：'判断一棵树是不是 AVL 树'
    bool IsAVLTree() {
        return _IsAVLTree(_root);
    }
};

红黑树的源代码

// 这里就不再粘贴复制了 (●ˇ∀ˇ●)，这里的源码同'实现文件 RBTree.h' (￣▽￣)

二、比赛开始

测试的源文件：Test.cpp

// 任务 1：包含需要使用头文件
#include "AVLTree.h"
#include "RBTree.h"
#include <vector>
#include <ctime>
using namespace std;

/*-------------------对比 AVL 树和红黑树的性能指标-------------------*/
void TestBST() {
    cout << "测试一百万的数据规模下 AVL 树和红黑树的性能差距 \n" << endl;

    /*--------------------第一阶段：准备阶段--------------------*/
    // 1. 指定测试数据的规模
    const int N = 1000000;
    // 2. 创建一个 vector 容器
    vector<int> v;
    // 3. 预先分配内存（避免插入时频繁扩容）
    v.reserve(N);
    // 4. 设置随机数种子 (让每次随机数不同，依赖系统时间)
    srand(time(0));
    // 5. 将 N 个随机数添加到 vector 容器中
    for (size_t i = 0; i < N; i++) {
        v.push_back(rand() + i); // 构造随机数据，rand() + i 降低重复概率
    }

    /*--------------------第二阶段：测试阶段--------------------*/
    // ------ AVL 树插入性能测试 ------
    AVLTree<int, int> avl;
    // 1. 记录开始时间
    size_t begin1 = clock();
    // 2. 将 vector 容器中的数据添加到 AVL 树中
    for (auto it : v) {
        avl.Insert(make_pair(it, it));
    }
    // 3. 记录结束时间
    size_t end1 = clock();

    // ------ 红黑树插入性能测试 ------
    RBTree<int, int> rb;
    // 1. 记录开始时间
    size_t begin2 = clock();
    // 2. 将 vector 容器中的数据添加到红黑树中
    for (auto it : v) {
        rb.Insert(make_pair(it, it));
    }
    // 3. 记录结束时间
    size_t end2 = clock();

    // ------ AVL 树查找性能测试 ------
    size_t begin3 = clock();
    for (auto it : v) {
        avl.Find(it);
    }
    size_t end3 = clock();

    // ------ 红黑树查找性能测试 ------
    size_t begin4 = clock();
    for (auto it : v) {
        rb.Find(it);
    }
    size_t end4 = clock();

    /*--------------------第二阶段：输出阶段--------------------*/
    // 1. 输出 AVL 树和红黑树插入操作的耗时
    cout << "-----------插入操作的耗时-----------" << endl;
    cout << "AVL Insert:" << end1 - begin1 << endl;
    cout << "RB Insert:" << end2 - begin2 << endl;

    // 2. 输出 AVL 树和红黑树查找操作的耗时
    cout << "\n-----------查找操作的耗时-----------" << endl;
    cout << "AVL Find:" << end3 - begin3 << endl;
    cout << "RB Find:" << end4 - begin4 << endl;

    // 2. 检查并输出两棵树是否平衡
    cout << "\n-----------是否平衡-----------" << endl;
    cout << "AVL IsBalance:" << avl.IsAVLTree() << endl;
    cout << "RB IsBalance:" << rb.IsRBTree() << endl;

    // 3. 输出两棵树的高度
    cout << "\n-----------树的高度-----------" << endl;
    cout << "AVL Height:" << avl.Height() << endl;
    cout << "RB Height:" << rb.Height() << endl;

    // 4. 输出两棵树的节点的数量
    cout << "\n-----------插入节点的数量-----------" << endl;
    cout << "AVL Size:" << avl.Size() << endl;
    cout << "RB Size:" << rb.Size() << endl;
}

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

三、评委打分

运行结果截图