【红黑树】目录
往期《C++初阶》回顾：
往期《C++进阶》回顾：
/------------ 继承多态 ------------/
【普通类/模板类的继承 + 父类&子类的转换 + 继承的作用域 + 子类的默认成员函数】
【final + 继承与友元 + 继承与静态成员 + 继承模型 + 继承和组合】
【多态：概念 + 实现 + 拓展 + 原理】
/------------ STL ------------/
【二叉搜索树】
【AVL树】
前言：
Hi~ 小伙伴们大家好呀！(ﾉ･ω･)ﾉﾞ
今天可是九月的第一天，既是全新月份的开端，对学生党来说更是新学期的起点～从现在到这学期结束，博主都会一直陪着大家一起学习、一起进步，绝不会 “失踪” 哦！୧(๑•̀◡•́๑)૭
新开始就得配点有分量的干货才够意思，不知道大家觉得 【红黑树】 这份内容，能不能撑起这份 “开学仪式感” 呢？(≧◡≦)
可能有小伙伴看到 “红黑树” 会觉得有点怵，心里犯嘀咕 “这东西是不是很难懂啊？”(｡•ˇ‸ˇ•｡)！
但真的希望大家能跟着我一起看完这份内容 —— 相信我，一步步拆解下来其实没那么复杂，咱们一起啃下这块硬骨头！哈哈哈，不多说了，大家加油冲！٩(๑•̀ω•́๑)و
------------概念介绍------------
1. 什么是红黑树？
红黑树：是一种自平衡二叉搜索树，由德国计算机科学家 Rudolf Bayer 在 1972 年发明，当时被称为对称二叉B树，后来被 Leo J. Guibas 和 Robert Sedgewick 改进并命名为红黑树
- 它在很多编程语言的库和实际应用场景中都有广泛使用
- C++ 的 STL 库中的
map和set底层实现- Java 的
TreeMap等库的实现- 它通过额外的 颜色标记 和 旋转操作 来维持树的平衡，确保最坏情况下的基本操作（插入、删除、查找）时间复杂度为 O ( l o g n ) O(log n) O(logn)
- 它在每个节点上增加了一个存储位来表示节点的颜色，这个颜色可以是红色或者黑色。
- 通过对从根节点到任意叶子节点路径上的节点颜色进行约束，红黑树确保了没有一条路径的长度会比其他路径长出两倍，因此它是一种近似平衡的二叉搜索树
2. 红黑树的基本特性是什么？
红黑树的基本特性：
- 节点颜色属性：红黑树的每个节点都有一个颜色属性，颜色只能是红色或者黑色。
- 根节点与叶子节点：
- 根节点是黑色的
- 叶子节点（NIL 节点，这里可以理解为指向空的指针，并不是我们通常意义上的叶子节点）每个都是黑色的
- 红节点规则：如果一个节点是红色的，那么它的两个子节点都是黑色的，也就是说不存在连续的红色节点。
- 黑色高度：对每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点 。
- 这个相同的黑色节点数目被称为该节点的 “黑色高度”，整棵红黑树的黑色高度就是根节点的黑色高度。
3. 红黑树的效率怎么样？
红黑树的优点：
1.对于二叉搜索树而言：
- 时间效率高：红黑树能保证在最坏情况下，基本的查找、插入、删除操作的时间复杂度都是 O ( l o g N ) O(logN) O(logN) ，其中 N N N 是树中节点的数量。
- 假设红黑树中结点数量为 N N N，最短路径长度为 h h h，则满足 2 h − 1 ≤ N < 2 2 h − 1 2^h - 1 \leq N < 2^{2h} - 1 2h−1≤N<22h−1。由此可推出 h ≈ log N h \approx \log N h≈logN ，这意味着红黑树增删查改操作的最坏情况，是走最长路径 2 × log N 2 \times \log N 2×logN，所以时间复杂度仍为 O ( log N ) O(\log N) O(logN)
- 相比普通的二叉搜索树，普通二叉搜索树在极端情况下（如：插入节点有序时）会退化为链表，导致操作时间复杂度变为 O ( n ) O(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 存在且为红色时：
- 颜色调整：将
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;
/* 注意事项：怎么理解上面的三个指针的类型为什么要这么写成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;
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” (￣▽￣)
二、比赛开始
测试的源文件：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;
}
三、评委打分
运行结果截图
