【红黑树】目录
往期《C++初阶》回顾：《C++初阶》目录导航 往期《C++进阶》回顾：【普通类/模板类的继承 + 父类&子类的转换 + 继承的作用域 + 子类的默认成员函数】 【final + 继承与友元 + 继承与静态成员 + 继承模型 + 继承和组合】 【多态：概念 + 实现 + 拓展 + 原理】 【二叉搜索树】 【AVL树】 前言： Hi~ 小伙伴们大家好呀！(ﾉ･ω･)ﾉﾞ 新开始就得配点有分量的干货才够意思，不知道大家觉得 【红黑树】 这份内容，能不能撑起这份 “开学仪式感” 呢？(≧◡≦) ------------概念介绍------------ 1. 什么是红黑树？ 红黑树 自平衡二叉搜索树 对称二叉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. 红黑树的效率怎么样？ 红黑树的优点： 时间效率高 ：红黑树能保证在最坏情况下，基本的查找、插入、删除操作的时间复杂度都是 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树而言： 稳定性较好 ：红黑树的平衡调整操作相对比较稳定，虽然在插入和删除节点时会进行旋转和变色，但这些操作的代价相对较小，不会引起树结构的剧烈变化。总结： 4. 红黑树如何确保最长路径不超过最短路径的2倍？ 红黑树路径规则推导： 最短路径（全黑路径） ：全由黑色结点组成 的路径。我们把这条最短路径的长度记为 bh（black height，黑色高度 ）最长路径（黑红间隔路径） ：一黑一红交替 的结构，因此最长路径长度为 2*bh（黑色结点数量为 bh，红色结点数量最多也为 bh ）路径长度范围 ：任意从根到 NIL结点的路径长度 h ，都满足bh ≤ h ≤ 2*bh------------基本操作------------ 一、查找操作 查找操作总结： 二、插入操作 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 染回黑色收尾红黑树平衡处理的图示说明： 红黑树的插入情况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逻辑总结： 自动保证 ，无需额外验证。图示 ：“验证一棵树是不是红黑树”//实现：“判断一棵树是不是红黑树”boolIsRBTree(){/*------------处理“特殊情况 + 递归出口”------------*///特殊情况1：“空树”if(_root ==nullptr){returntrue;//空树也是红黑树}//特殊情况2：“只有一个节点并且为红色”if(_root->_col == RED){returnfalse;//不满足红黑树的规则}/*------------处理“正常情况”------------*//*------- 第一步：计算最左路径上节点的数量-------*///1.记录该路径上黑色节点的数量int refNum =0;//2.定义一个指向当前节点的指针 Node* current = _root;//3.使用while循环统计该路径上黑色节点的数量while(current){//3.1：统计if(current->_col == BLACK){++refNum;}//3.2：移动 current = current->_left;}/*-------第二步：递归检查其他路径上面的黑色节点的数量-------*/returnCheck(_root,0, refNum);}boolCheck(Node* root,int blackNum,constint refNum){/*------------处理“特殊情况 + 递归出口”------------*/if(root ==nullptr){//情况1：新遍历的这条路径上的黑色节点的数量“不等于”最左侧路径上的黑色节点的数量if(refNum != blackNum){ cout <<"存在黑色结点的数量不相等的路径"<< endl;returnfalse;}//情况2：新路径“等于”旧路径returntrue;}/*------------处理“正常情况”------------*///1.检查“连续红节点的情况”if(root->_col == RED && root->_parent->_col == RED)//注意这里的细节，如果我们正向思维的话{ cout << root->_kv.first <<" 存在连续的红色结点"<< endl;returnfalse;}/* 注意实现：如果解决上面的这个问题我们使用正向思维的话：“对于当前红色节点要判断它的孩子是也是红色节点” * 1. 我们不禁要判断root节点的左孩子还要判断右孩子是不是“红色” * 2. 并且有可能正在遍历的这个节点还有可能根本不存在 *///2.检查“记录黑色节点的数量”if(root->_col == BLACK){ blackNum++;}//3.递归检查左右子树returnCheck(root->_left, blackNum, refNum)&&Check(root->_right, blackNum, refNum);}------------代码实现------------ 红黑树的存储结构是什么样的？ 一、节点的存储结构 //任务2：定义红黑树节点的“颜色枚举”enumColour{ RED,//红色节点 BLACK //黑色节点};//任务3：定义红黑树节点的“结构体模板”template<classK,classV>structRBTreeNode{/*--------------------------成员变量--------------------------*///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<classK,classV>classRBTree{private:/*--------------------------成员变量--------------------------*/ RBTreeNode<K, V>* _root =nullptr;/*--------------------------类型别名--------------------------*///1.重新定义红黑树节点的类型：RBTreeNode<K,V> ---> Nodetypedef RBTreeNode<K, V> Node;public:/*--------------------------成员函数（公有）--------------------------*///…………};实现文件：RBTree.h #pragmaonce//任务1：包含需要使用的头文件#include<iostream>usingnamespace std;//任务2：定义红黑树节点的“颜色枚举”enumColour{ RED,//红色节点 BLACK //黑色节点};//任务3：定义红黑树节点的“结构体模板”template<classK,classV>structRBTreeNode{/*--------------------------成员变量--------------------------*///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<classK,classV>classRBTree{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){return0;}/*------------处理“正常情况”------------*///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){return0;}/*------------处理“正常情况”------------*///1.递归计算树中节点的总数量 ---> 节点数 = 左子树节点数 + 右子树节点数 + 1（当前节点）return_Size(root->_left)+_Size(root->_right)+1;}//4.实现：“判断一棵树是不是红黑树”boolCheck(Node* root,int blackNum,constint refNum){/*------------处理“特殊情况 + 递归出口”------------*/if(root ==nullptr){//情况1：新遍历的这条路径上的黑色节点的数量“不等于”最左侧路径上的黑色节点的数量if(refNum != blackNum){ cout <<"存在黑色结点的数量不相等的路径"<< endl;returnfalse;}//情况2：新路径“等于”旧路径returntrue;}/*------------处理“正常情况”------------*///1.检查“连续红节点的情况”if(root->_col == RED && root->_parent->_col == RED)//注意这里的细节，如果我们正向思维的话{ cout << root->_kv.first <<" 存在连续的红色结点"<< endl;returnfalse;}/* 注意实现：如果解决上面的这个问题我们使用正向思维的话：“对于当前红色节点要判断它的孩子是也是红色节点” * 1. 我们不禁要判断root节点的左孩子还要判断右孩子是不是“红色” * 2. 并且有可能正在遍历的这个节点还有可能根本不存在 *///2.检查“记录黑色节点的数量”if(root->_col == BLACK){ blackNum++;}//3.递归检查左右子树returnCheck(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：当前遍历到的节点的键 > 要查找的键 ---> “继续向当前节点的左子树中查找”elseif(curr->_kv.first > key){ curr = curr->_left;}//情况3：当前遍历到的节点的键 = 要查找的键 ---> “找到了要查找的键”else{return curr;}}//3.跳出了循环，说明没有找到的键为key的节点returnnullptr;}//2.实现：“红黑树的插入”的操作boolInsert(const pair<K, V>& kv)//注意：对于set而言插入的是键K key，对于map而言插入的是键值对pair<K,V> kv{/*--------处理“特殊情况 + 递归出口”--------*/if(_root ==nullptr){//1.创建新节点 _root =newNode(kv);//2.将新节点染色为黑色 (*相比AVL树多了这一步骤*) _root->_col = BLACK;//3.返回true即可returntrue;}/*--------处理“正常情况”--------*//*----------------第一阶段：准备阶段----------------*///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：当前遍历到的节点的键 > 要插入的键 ---> “继续寻找”elseif(current->_kv.first > kv.first)//注意：没学pair之前我们是这样写的：else if (current->_key > key){ parent = current; current = current->_left;//继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 要插入的键 ---> “键已存在”---> 查找插入位置失败else{returnfalse;//不同之处2：这里放回的是false//原因：我们实现的二叉搜索树不支持存储“键相等的节点”}}//注意：能执行到此处，说明在第二阶段成功跳出了while循环，并非因return false终止程序，//这意味着已找到插入节点的位置，那下面就让我们插入节点吧/*----------------第三阶段：插入阶段----------------*///1.创建要插入的节点 current =newNode(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即可returntrue;}//Insert函数结束//3.实现：“右单旋”操作（以parent为中心右旋）voidRotateR(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.实现：“左单旋”操作（处理右右失衡的情况）voidRotateL(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.实现：“中序遍历”voidInOrder(){_InOrder(_root); cout << endl;}//6.实现：“获取树的高度”intHeight(){return_Height(_root);}//7.实现：“获取节点的数量”intSize(){return_Size(_root);}//8.实现：“判断一棵树是不是红黑树”boolIsRBTree(){/*------------处理“特殊情况 + 递归出口”------------*///特殊情况1：“空树”if(_root ==nullptr){returntrue;//空树也是红黑树}//特殊情况2：“只有一个节点并且为红色”if(_root->_col == RED){returnfalse;//不满足红黑树的规则}/*------------处理“正常情况”------------*//*------- 第一步：计算最左路径上节点的数量-------*///1.记录该路径上黑色节点的数量int refNum =0;//2.定义一个指向当前节点的指针 Node* current = _root;//3.使用while循环统计该路径上黑色节点的数量while(current){//3.1：统计if(current->_col == BLACK){++refNum;}//3.2：移动 current = current->_left;}/*-------第二步：递归检查其他路径上面的黑色节点的数量-------*/returnCheck(_root,0, refNum);}};测试文件：Test.cpp #define_CRT_SECURE_NO_WARNINGS1#include"RBTree.h"voidTestRBTree(){ 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;}intmain(){TestRBTree();return0;}运行结果： ------------终极对决------------ 一、选手登场 AVL树的源代码 #pragmaonce//任务1：包含需要使用头文件#include<iostream>#include<assert.h>usingnamespace std;//任务2：定义AVL树节点的结构模板template<classK,classV>structAVLTreeNode{/*----------------第一部分：成员变量----------------*///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<classK,classV>classAVLTree{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){return0;}//处理“正常情况”//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){return0;}//处理“正常情况”//1.直接返回递归计算的左子树和右子树的节点的数量之和return_Size(root->_left)+_Size(root->_right)+1;}//4.实现：“判断一棵树是不是AVL树”bool_IsAVLTree(Node* root){//处理“特殊情况”+ “递归出口”if(root ==nullptr){returntrue;//空树是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;returnfalse;}//2.检查平衡因子“是否异常”if(root->_bf != bf){ cout << root->_kv.first <<"平衡因子异常"<< endl;returnfalse;}/*-------------------第三步：递归验证-------------------*/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：当前遍历到的节点的键 > 要查找的键 ---> “继续向当前节点的左子树中查找”elseif(curr->_kv.first > key){ curr = curr->_left;}//情况3：当前遍历到的节点的键 = 要查找的键 ---> “找到了要查找的键”else{return curr;}}//3.跳出了循环，说明没有找到的键为key的节点returnnullptr;}//2.实现：“插入操作”boolInsert(const pair<K, V>& kv)//注意：没学pair之前我们是这样写的：bool Insert(const K& key, const V& value){//特殊情况：要插入的节点的树是“空树”if(_root ==nullptr){//1.直接创建一个节点为跟节点 _root =newNode(kv);//注意：没学pair之前我们是这样写的：_root = new Node(key, value); //2.返回true即可returntrue;}//正常情况：要插入的节点的树是“非空树”/*----------------第一阶段：准备阶段----------------*///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：当前遍历到的节点的键 > 要插入的键 ---> “继续寻找”elseif(current->_kv.first > kv.first)//注意：没学pair之前我们是这样写的：else if (current->_key > key){ parent = current; current = current->_left;//继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 要插入的键 ---> “键已存在”---> 查找插入位置失败else{returnfalse;//不同之处2：这里放回的是false//原因：我们实现的二叉搜索树不支持存储“键相等的节点”}}/*----------------第三阶段：插入阶段----------------*///1.创建要插入的节点 current =newNode(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 ---> 高度变化需向上传递，继续更新上层节点elseif(parent->_bf ==-1|| parent->_bf ==1){//1.新节点 ---> 父节点 current = current->_parent;//或者写成：current = parent; //2.父节点 ---> 爷爷节点 parent = parent->_parent;//注意：这里也就体现了，为什么我们要对二叉搜索树底层结构中再设计一个指针_parent了，//因为：调整阶段我们需要更新上层的节点，多引入一个_parent指针可以让我们更方便的找到上层的节点}//情况3：父节点的平衡因子为±2 ---> 树失衡，需要旋转调整elseif(parent->_bf ==-2|| parent->_bf ==2)//注意：按理说这里我们因该使用一个else即可，因为平衡因子只可能是：0，±1，±2 {//但是不怕一万就怕万一，这里我们使用防御性编程，再另设一个情况4（特殊情况）//失衡1：左左失衡（父子平衡因子都为“负”） ---> 右单旋if(parent->_bf ==-2&& current->_bf ==-1){RotateR(parent);}//失衡2：右右失衡（父子平衡因子都为“正”） ---> 左单旋elseif(parent->_bf ==2&& current->_bf ==1){RotateL(parent);}//失衡3：左右失衡（父为“负”，子为“正”） ---> 左右双旋elseif(parent->_bf ==-2&& current->_bf ==1){RotateLR(parent);}//失衡4：右左失衡（父为“正”，子为“负”） ----> 右左双旋elseif(parent->_bf ==2&& current->_bf ==-1){RotateRL(parent);}//特殊情况：非法平衡因子 ---> 断言失败else{assert(false);}break;//注意：这里一定要添加一个break，因为这个break是调整成功出while循环的唯一方式}//情况4：非法平衡因子 ---> 断言失败else{assert(false);}}returntrue;// 跳出了调整阶段while循环，说明已经调整成功了，返回true}//3.实现：“右单旋”操作（处理左左失衡的情况）voidRotateR(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.实现：“左单旋”操作（处理右右失衡的情况）voidRotateL(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.实现：“左右双旋”操作（处理左右失衡的情况）voidRotateLR(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”elseif(bf ==1){ subLR->_bf =0; subL->_bf =-1; parent->_bf =0;}//情况3：subLR节点原始的平衡因子为“0”elseif(bf ==0)//注意：同样的按理说：subLR的平衡因子只可能是：0，1，-1这三中情况，也就是说这里我们因该使用else即可，所以我们还使用防御性编程，以防万一{ subLR->_bf =0;//注意：这里表面看上去并不需要进行更新，这里只是为了以防万一 subL->_bf =0; parent->_bf =0;}//情况4：非法平衡因子，断言失败else{assert(false);}}//6.实现：“右左双旋”操作（处理右左失衡的情况）voidRotateRL(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”elseif(bf ==1){ subRL->_bf =0; subR->_bf =0; parent->_bf =-1;}//情况3：subRL节点原始的平衡因子为“0”elseif(bf ==0){ subRL->_bf =0; subR->_bf =0; parent->_bf =0;}//情况4：非法平衡因子，断言失败else{assert(false);}}//7.实现：“中序遍历”操作voidInOrder(){_InOrder(_root);//注意：这里我们实际上是调用private权限下的_InOrder()接口函数实现中序遍历 cout << endl;}//8.实现：“获取树的高度”操作intHeight(){return_Height(_root);//和上面的一样我们还调用其他接口实现}//9.实现：“获取节点的数量”操作intSize(){return_Size(_root);}//10.实现：“判断一棵树是不是AVL树”boolIsAVLTree(){return_IsAVLTree(_root);}};红黑树的源代码 // 这里就不再粘贴复制了(●ˇ∀ˇ●)，这里的源码同“实现文件RBTree.h” (￣▽￣)二、比赛开始 测试的源文件：Test.cpp //任务1：包含需要使用头文件#include"AVLTree.h"#include"RBTree.h"#include<vector>#include<ctime>usingnamespace std;/*-------------------对比 AVL 树和红黑树的性能指标-------------------*/voidTestBST(){ cout <<"测试一百万的数据规模下AVL树和红黑树的性能差距 \n"<< endl;/*--------------------第一阶段：准备阶段--------------------*///1.指定测试数据的规模constint 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;}intmain(){TestBST();return0;}三、评委打分 运行结果截图
