《C++进阶之STL》【红黑树】

往期《C++初阶》回顾：

《C++初阶》目录导航

---

往期《C++进阶》回顾：
/------------ 继承多态 ------------/
【普通类/模板类的继承 + 父类&子类的转换 + 继承的作用域 + 子类的默认成员函数】
【final + 继承与友元 + 继承与静态成员 + 继承模型 + 继承和组合】
【多态：概念 + 实现 + 拓展 + 原理】
/------------ STL ------------/
【二叉搜索树】
【AVL树】

前言：

Hi~ 小伙伴们大家好呀！(ﾉ･ω･)ﾉﾞ
今天可是九月的第一天，既是全新月份的开端，对学生党来说更是新学期的起点～从现在到这学期结束，博主都会一直陪着大家一起学习、一起进步，绝不会 “失踪” 哦！୧(๑•̀◡•́๑)૭

新开始就得配点有分量的干货才够意思，不知道大家觉得 【红黑树】 这份内容，能不能撑起这份 “开学仪式感” 呢？(≧◡≦)
可能有小伙伴看到 “红黑树” 会觉得有点怵，心里犯嘀咕 “这东西是不是很难懂啊？”(｡•ˇ‸ˇ•｡)！
但真的希望大家能跟着我一起看完这份内容 —— 相信我，一步步拆解下来其实没那么复杂，咱们一起啃下这块硬骨头！哈哈哈，不多说了，大家加油冲！٩(๑•̀ω•́๑)و

------------概念介绍------------

1. 什么是红黑树？

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

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

2. 红黑树的基本特性是什么？

红黑树的基本特性：

• 节点颜色属性：红黑树的每个节点都有一个颜色属性，颜色只能是红色或者黑色。
• 根节点与叶子节点：
  • 根节点是黑色的
  • 叶子节点（NIL 节点，这里可以理解为指向空的指针，并不是我们通常意义上的叶子节点）每个都是黑色的
• 红节点规则：如果一个节点是红色的，那么它的两个子节点都是黑色的，也就是说不存在连续的红色节点。
• 黑色高度：对每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点 。
  • 这个相同的黑色节点数目被称为该节点的 “黑色高度”，整棵红黑树的黑色高度就是根节点的黑色高度。

3. 红黑树的效率怎么样？

红黑树的优点：

1.对于二叉搜索树而言：

• 时间效率高：红黑树能保证在最坏情况下，基本的查找、插入、删除操作的时间复杂度都是 $O(logN)$ ，其中 $N$ 是树中节点的数量。
  • 假设红黑树中结点数量为 $N$，最短路径长度为 $h$，则满足 $2^h-1\le N<2^{2h}-1$。由此可推出 $h\approx \log N$ ，这意味着红黑树增删查改操作的最坏情况，是走最长路径 $2\times \log N$，所以时间复杂度仍为 $O(\log N)$
  • 相比普通的二叉搜索树，普通二叉搜索树在极端情况下（如：插入节点有序时）会退化为链表，导致操作时间复杂度变为$O(n)$ ，而红黑树通过平衡机制避免了这种情况

2.对于AVL树而言：

• 稳定性较好：红黑树的平衡调整操作相对比较稳定，虽然在插入和删除节点时会进行旋转和变色，但这些操作的代价相对较小，不会引起树结构的剧烈变化。

---

总结： 红黑树的概念表达相对 AVL 树更抽象。

• AVL 树通过高度差直观控制平衡
• 红黑树则借助 4 条颜色约束规则，间接实现近似平衡

二者效率处于同一档次，但相对而言，插入相同数量结点时，红黑树的旋转次数更少，因为它对平衡的控制没那么严格。

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

红黑树路径规则推导：

• 最短路径（全黑路径）：
  由红黑树规则 4（从根到 NIL结点的每条路径，黑色结点数量相同 ）可知，极端场景下，最短路径就是全由黑色结点组成的路径。 我们把这条最短路径的长度记为 bh（black height，黑色高度 ）
• 最长路径（黑红间隔路径）：
  结合规则 2（根结点是黑色 ）和规则 3（红色结点的子结点必为黑色，路径中不会出现连续红色结点 ）。极端场景下，最长路径会呈现一黑一红交替的结构，因此最长路径长度为 2*bh（黑色结点数量为 bh，红色结点数量最多也为 bh ）
• 路径长度范围：
  实际红黑树中，“全黑最短路径” 和 “黑红交替最长路径” 并非一定同时存在。但通过 4 条规则可推导：任意从根到 NIL结点的路径长度 h，都满足 bh ≤ h ≤ 2*bh ，这保证了红黑树的近似平衡特性

------------基本操作------------

一、查找操作

查找操作总结：

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

它们都依托二叉搜索树的 “左小右大” 基本规则，从根节点出发，通过键值的比较，不断向左右子树递归或迭代查找，本质都是利用树的有序性缩小查找范围。

• 差异主要体现在平衡维护（AVL 树的严格平衡、红黑树的近似平衡）

• 但查找操作的 “二分比较” 形式，始终保持着一脉相承的简洁与高效

二、插入操作

1. 本质

插入操作本质：

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

2. 步骤

---

场景说明：

在红黑树插入调整逻辑里，我们统一做如下标识：

• 新插入的节点记为 c（current，代表当前触发调整的节点）
• c 的父节点记为 p（parent ）
• p 的父节点（即：祖父节点）记为 g（grandfather）
• p 的兄弟节点（即：叔叔节点）记为 u（uncle）

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

情况1：变色

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

1. 颜色调整：将 p 和 u 染为黑色，g 染为红色
2. 向上回溯：把 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 的右孩子（左右型）

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

---

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

• 操作：
  1. 以 p 为旋转中心，右单旋（将 c 提升为 p 的父节点 ）
  2. 以 g 为旋转中心，左单旋（将 c 提升为 g 的父节点 ）
  3. 变色：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; /*  注意事项：怎么理解上面的三个指针的类型为什么要这么写成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> ---> Nodetypedef 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> ---> Nodetypedef 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.返回较高子树的高度+1return 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> ---> Nodetypedef 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：新插入节点是左子节点 ---> 父节点的平衡因子 -1if (current == parent->_left){parent->_bf--; // 插入到左子树，左子树高度+1，平衡因子-1}//位置2：新插入节点是右子节点 ---> 父节点的平衡因子 +1else{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的平衡因子均为0subL->_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的平衡因子均为0subR->_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” (￣▽￣)

二、比赛开始

测试的源文件：Te.hst

//任务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;
}

三、评委打分

运行结果截图