您现在的位置是：首页 >技术杂谈 >Learning C++ No.20 【红黑树实战】网站首页技术杂谈
Learning C++ No.20 【红黑树实战】
引言：
北京时间：2023/5/12/20:30，今天周五，周五不摆烂从我做起，虽然刚睡醒，但是今天如果论学习时长，那可能是许久以来最长的一天，从早上6:40晨跑回来坐在凳子上，一坐久坐到了下午13:40，然后睡了10分钟去上了一节心理课，心理课结束去吃了个饭，回到宿舍16:20，帮同学下载了一个软件，可能是很久没下了，搞了半天才搞好，最终在17:10分进入学习状态，直到19:00左右，把自己目前手头上的任务搞定的差不多，然后洗了个澡，洗澡出来好像是19:08，最终调好闹钟，刚刚起床，在这个时间点，首先是我的舍友快从我没有的选修课上回来了，其次是我准备把博客给总结一下，该篇博客我们就来学习一下有关红黑树的相关知识，当然最重要的是红黑树相关接口的实现，有助于我们了解高阶数据结构是如何进行平衡控制，从而达到O(log N)的高速遍历效率，最终广泛用于各种现实场景之中
红黑树非代码实现有关知识
什么是红黑树
上篇博客，我们学习了有关搜索二叉树的有关知识，发现搜索二叉树是一种查找效率非常高的数据结构，但是在某些场景中，可能会导致左右子树失衡，进而导致搜索树退化成链表，查找效率大大降低，所以不难推出，今天我们学习红黑树的目的，就是为了解决这一问题，让左右子树之间可以保持相对平衡，进而让搜索效率一直保持在O(log N)左右，并且明白，单单从保持平衡这一方面去看，同理和红黑树类似的AVL树，它才是搜索树最好的平衡，因为它已经可以将左右子树的高度差控制在正负一，但也是由于这种严格的控制要求，导致AVL树在插入数据时，需要不断的通过旋转来控制平衡，导致在有的场景下，效率较低，所以人们在AVL树的基础上又创建出了一个全新的控制平衡的方法，也就是我们今天要学的红黑树，所以红黑树出现的本质就是为了解决AVL树频繁旋转的问题
红黑树如何弥补AVL树的不足
想要搞懂这个问题，此时我们应该先来看一看红黑树的具体概念：
红黑树首先是一棵搜索二叉树，但此时因为它通过在结点中添加了一个颜色对象，红色（RED）或者黑色(BLACK)，进而将该搜索二叉树的平衡给控制住了，所以红黑树也是一棵平衡搜索二叉树， 具体就是通过对任何一条根到叶子路径上的各个结点着色方式的限制，来保证没有一条路径会比其他路径长出两倍，进而将高度控制在 [logN，2logN] 的区间中，最终减少旋转的次数
搞懂了红黑树的基本概念，那此时进入正题，也就是红黑树的规则，这个规则的制定人不用多说，肯定是一个高手中的高手，当然待会我们如果想要自己实现红黑树的部分接口，首先一定要遵守这些规则，不然我们实现的搜索树就不叫做红黑树，所以这些规则一定要十分的清楚，如下：
1.每个结点不是红色就是黑色
2. 根节点一定是黑色
3. 如果一个结点是红色的，则它的两个孩子结点只能是黑色
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
当我们第一遍读完这些规则，人肯定是很懵逼的，因为你平时也没见过什么是红黑树，所以此时我们就需要有一幅图作为参考，如下图所示：
有了这幅图，就可以为我们理解红黑树性质的学习难度降低很多啦！所以此时就让我们通过上图和上述红黑树规则的描述，来看一看红黑树具体是怎样的吧！首先是性质1，通过上图一览无余，其次是性质2，通过上图，我们也可以发现，此时的13结点作为根结点，果然是黑色的，然后是性质3，同理，通过图示，发现，红色结点的孩子结点都是黑色的，再然后是性质4，数一数发现上图红黑树中一共有11条路径，并且每一条路径无论长短，它们的黑色结点个数都是2，最后是性质5，在红黑树中空结点被称为叶子结点，并且每一个空结点都是黑色，也就是上图所示的NIL结点
红黑树代码实现有关知识
红黑树结点的创建
在数据结构中结点的重要性我就不多说了，就这么说，之所以有各种各样的数据结构类型，本质上就是因为每种数据结构的结点不相同，一个结点等于决定了一个数据结构的类型，也就是说，通过一个结点中的对象，我们就可以知道该结点是提供给那种数据结构类型使用，也就是说，每一种数据类型都有一个独一无二的结点，所以红黑树的结点构造如下图代码所示：
别的不废话，首先是红黑树的经典实现方法三叉链，所以此时在二叉树左右孩子指针的基础上，加了一个父亲结点的指针，其次是pair<K,V> _kv，Color _color;其中 pair 表示的就是一个具有两个数据类型的模板对象，通过模板的方式可以构建出任意类型的两个数据类型，在红黑树中使用的目的和搜索二叉树中是一样的，本质就是key类型和key/value类型，具体详情可以去上篇博客中查看，其次_color对象是一个枚举类型，当然你也可以通过#define去定义，具体枚举结构如下代码所示：
enum Color
{
RED,
BLACK
};
最后也是一个最重要的知识点，也就是构造函数中对_color对象默认初始化为RED的理解，什么意思呢？如果你还没有意识到这个问题的严重性，那么只能说明你对搜索二叉树的知识还不是很了解，表示的意思就是在我们插入结点的时候，也就是在堆区上申请空间的时候，此时你就将每一个在堆区上创建出来的结点的颜色默认为红色，浅显理解就是，如果你在插入结点的时候，你不通过红黑树的规则去限制和更改对应的颜色，那么此时你构建出来的搜索二叉树就不是红黑树了，而是一棵红到发紫的红红树，吃太饱的我，把图片给你放在下面了，如下图：
但是此时会发现一个问题，就是为什么一定要默认构造成红色呢？黑色不行吗？哈哈哈，如果你有这个疑问，那我就只能说，烦人，搞得我又要码好多的字，哈哈哈，不开玩笑，如果你有这个疑问，那只能说明你是一个好奇的宝宝，并且拥有高于常人的智慧，想要解释该问题，此时理所当然的就会涉及到红黑树的规则，具体是那条规则，先不要着急，我们徐徐道来，回顾红黑树3、4两条规则，规则3说，红色结点的孩子结点必须是黑色，规则4说任意一条从根结点到叶子结点路径的黑色结点的个数都相同，细细读两遍，发现如果违反规则3，那么此时造成的后果是局部性的（某一个子树），而违反规则4，那么此时造成的后果却是全局性的（所有路径），什么意思呢？简单理解就是，如果违反了规则4，也就是默认插入结点的时候，插入的是黑色的结点，就等于在某条路径上的黑色结点多了一个，但是红黑树中其余路径的黑色结点都没有改变，所以问题很严重，也可以理解成，按照这个规则，随机在任意路径插入黑色结点，且我们知道对应的路径，但是我们却很难将每一条路径的黑色结点都给控制住，代码实现上也许可以，但是更加复杂，难度更大，场景更多，所以我们默认不能违反规则4，而是违反规则3，所以默认插入结点的时候，就是插入红色，而不可以是黑色，所以在构造函数中，我们使用的就是红色。
红黑树插入接口实现
承接着上述对红黑树结点中构造函数_color默认构造红色的理解，此时我们正式进入该篇博客的主题，当然也是我最痛苦的时候，当一个数据经过结点构造函数构造完毕之后，此时它就要被插入到红黑树中，类似于一只待宰的羔羊一般，当这只羊被处理好之后（拔毛，蒸煮），此时就等着被端上桌，最终被瓜分而食，同理，此时我们就需要把该红色结点插入到它应该在的地方，也就是合适的地方，但，如果你想完成这件任务，首先你就会遇到两种情况：1.该红色结点成为了某一个黑色结点的孩子结点 2.该红色结点成为了某一个红色结点的孩子结点，当然如果你是神仙，你可以想象出第三种情况，如果不是，那就是我上述所说的两种情况啦！哈哈哈！
如图所示：
此时如上图所示，可以清晰看出，如果将一个红色结点链接在了红色结点之后（左图），此时整棵红黑树大体是正常的，只有插入了红色结点的那一小棵子树出现了问题，因为违反了规则3，红色结点的孩子结点只能是黑色，而如果将一个红色结点链接在了黑色结点之后（右图），此时整棵红黑树都是正常的，符合所有规则，所以在插入数据时，我们只要把那些最终插入在了红色结点之后的红色结点给控制住，此时整棵红黑树我们就控制住了，具体如何控制，先不着急，控制规则很简单，但是写博客的我需要画图，就很难受了，痛苦两秒
同理如下代码：根据搜索树的特性（数值大的插入在右子树，数值小的插入在左子树），找到合适的空位置插入数据
搞定上述知识，此时进入该篇博客重点中的重点，当然也就是红黑树实现的关键地方，也就是红黑树如何控制平衡和高度的秘密，对于你来说可能还是个秘密，但是当搞定该篇博客，那么一切都将不是秘密，红黑树对于你来说就是一个赤裸身子的美女，你充满了不懈，所以接下来，我们将分为三个场景来搞定当我们把一个红色结点插入在了红色结点的孩子结点，也就是违反规则3的问题，如下：
简单对比，引出场景
A:
B:
此时通过对上述A与B的对比，可以发现，在该场景下，红色插入结点一定是被插入在红色结点的孩子结点，所以可以判断出，当出现问题（两个红色结点连续），此时孩子结点的父结点一定是红色，并且爷爷结点一定是黑色，因为插入该红色结点之前，该树是一棵红黑树，满足红黑树的所有规则， 所以了解到，只要是红色结点连续的场景，那么父亲结点和爷爷结点的颜色已经是被固定了，所以如果想要对不同的场景进行区分和处理，那么此时就需要依赖于 uncle(叔叔)结点，从图中也可以得到证实，两个不同的场景，确实是因为 uncle 结点不同，一个是存在且为红色，一个是不存在，明白了这点之后，我们正式进入不同场景的划分，如下：
场景一： uncle结点存在且为红色
注意：a/b/c/d/e代表的是黑结点为n的子树，并且该树可能是一棵完整的树，也可能是一棵子树，如果是完整的树，那么最后需要把根结点置成黑色，如果是一棵子树，那么如果该子树的根结点是红色，那就需要继续判断该根结点的父结点的颜色，如果是红色就继续变色（前提是uncle存在且为红），如果是黑色则break，表示插入成功，所以在上述场景下，如果爷爷结点的父结点也是红色，那么此时就需要继续向上变色（前提是uncle存在且为红色），直到为黑，才结束对应的循环，否则就需要一直通过迭代的方式去判断，如下图就是一个二次更新变色的场景：
总：无论是从上图，还是注意点，此时我们都可以发现，在插入红色结点，导致两个红色结点连续时，解决方法是让parent结点和uncle结点变成红色，pparent结点变成黑色，本质就是在使用pparent的红色替代parent的黑色，使得每一条路径的黑色结点依然保持相等，符合红黑树的要求
场景二： uncle结点不存或者存在但为黑色（同侧）
1.uncle结点不存在：
如上图，可以发现，当uncle结点不存在时，此时插入结点就会导致该红黑树的左子树或者右子树明显高于另一子树，不符合最长路径不超过最短路径的两倍，如上图所示，最短路径为1，最长路径为3，所以此时在违反规则3，红色结点的孩子结点只能是黑色的同时，间接就触碰到了红黑树的底线原则，最长路径不超过最短路径的两倍，所以此时的解决方法就是使用 旋转+变色 ，具体的旋转方法如AVL树中实现的一样，分为四种（左单旋、右单旋、左右双旋、右左双旋），待会给大家逐一介绍，然后是变色，值得注意的是：此时的变色方法并不同于之前uncle结点存在且为红的变色方法，具体变色方法需要根据场景来确定，但是唯一可以肯定就是，当旋转完之后，爷爷结点的颜色一定需要变成红色，其余结点的颜色在不作为根结点的情况下，都是不发生改变的， 如上图所示，parent结点之所以变成黑色是因为单旋之后，它作为了根结点，所以它要变成黑色，如下述场景三，你可以看到，并不是每一次它都需要变成黑色，变成黑色不是由结点的身份决定的，而是由结点所处的位置决定的
2.uncle结点存在但为黑色
同理，uncle结点存在但为黑色的处理方法和uncle结点不存在是一样的，旋转+变色，具体变色情况，让我们把第三个双旋场景搞定，我们就可以得出结论啦！
场景三： uncle结点不存或者存在但为黑色（不同侧）
如上图可以发现，并不是每一次红色结点和红色结点不同侧就一定要发生旋转，关键还是要取决于uncle结点的情况，如果是存在且为红，那么同理直接让parent和uncle结点变黑，pparent变红就行，只有如下图所示，当红色结点和红色结点不同侧，并且uncle结点存在但为黑色的情况时，才会发生双旋场景
如上图可以发现，当满足双旋场景时，在旋转过程中并不伴随着颜色的改变，只要当旋转全部完成，此时才可以进行颜色的变化，将爷爷结点变成红色（固定），将cur结点变成黑色（双旋场景固定，但旋转场景不固定），所以这也就是为什么在上述单旋场景中，我们说，只有爷爷结点的颜色变化是旋转场景中固有的，而其它结点的颜色变化需要取决于位置，本质就是因为，如果发生的是单旋，那么此时就是父结点去做根结点，如果是双旋，此时是cur结点去做根结点
总：在满足uncle存在但为黑或者不存在的场景下，此时红色结点和红色结点连续存在时的解决方法就是旋转，具体是单旋还是双旋，取决于cur的位置在红色父亲结点的同侧还是不同侧，同侧一次单旋就完成平衡，反之双旋，并且明白，单旋的颜色变化是爷爷结点变红（固）+父亲结点变黑（根），双旋的颜色变化是爷爷结点变红（固）+当前结点变黑（根）
插入接口具体代码实现
明白了上述的所有知识，那么此时你对红黑树的规则和具体不同的插入场景可以说是水到渠成了，现在只要再让你看看具体代码是如何实现的，那么此时红黑树的插入接口，你就全部搞定了，并且搞定程度起码达到90%，具体代码如下：
红黑树旋转过程以及代码详解
如何检测该搜索树是否是一棵红黑树
搞定了上述知识，有关红黑树的所有知识，无论是场景分析还是代码实现，我们就都搞定了，剩下最后一步就是检测我们实现的搜索树是否是一棵红黑树，最简单的方法就是按照红黑树的规则去判定我们实现的这棵红黑树是否是搜索树，就跟高考改卷一般，判断一个题目是否正确的方法就是用标准答案去对比，所以基本检测思路如下：
1.判断根结点是否为黑色
2.判断是否有连续的红色结点
3.判断每条路径黑色结点的个数是否相同
代码如下：
红黑树基础实现完整代码（循环）
删除接口以外的基础接口实现：
#include<iostream>
#include<map>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<cassert>
#include<time.h>
using namespace std;
enum Color
{
RED,
BLACK
};
template<class K,class V>
class RBTreeNode
{
public:
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;//直接使用pair结构体就行，但是要记得把模板参数传过去初始化数据类型
Color _color;
RBTreeNode(const pair<K,V>& kv)//注意：pair是一个结构体，所以如果想要使用这个结构体就一定也要给模板参数，不然不能确定pair两个数据的类型
:_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(RED)
{}
};
//明白红黑树相当于AVL树的本质就是因为它旋转的更少
template<class K,class V>//注意：此时模板之间是以类对应的那个分号来分割开
class RBTree
{
typedef RBTreeNode<K,V> Node;
public:
RBTree()
:_root(nullptr)
{}
~RBTree()
{
_Destory(_root);
_root = nullptr;//好习惯
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur != nullptr)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_color = BLACK;//满足规则，_root结点插入，该结点对应的颜色一定是黑色
return true;
}
// 并且明白，当不是root根结点时，新增一个结点应该给红色还是黑色
// 如果新增黑色，那么面临的第一个问题就是，由于每一条路径的黑色结点数要相同，此时每一条路径都需要新增一个黑色结点
// 而如果是新增红色，那么此时面临的问题就是，红色结点的孩子结点还是红色
//所以默认规定，此时每次插入默认都是插入红色结点，因为这样造成的错误比较容易解决
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);//此时默认初始化的时候，创建的就是一个红色结点
//cur->_color = RED;
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//此时代码来到这里，红色结点就被我们成功的插入到某个结点下了（可能是红色的，也可能是黑色的，具体看情况）
//如果是红色，那么此时就违反了红黑树的规则，此时需要通过判断进行控制住
//具体原理，看同文件的那幅图处理就行
//看图（去找一下就行了）
while (parent != nullptr && parent->_color == RED)//因为变色可能会一直向上，直到遇到root结点，所以需要判断到root结点，也就是parent=nullptr的时候
{
//根据原理：1.将父结点和叔叔结点变成黑色，爷爷结点变成黑色（前提是uncle不为空）
Node* pparent = parent->_parent;
if (pparent->_left == parent)//叔叔结点需要判断左右
{
Node* uncle = pparent->_right;
//此时就找到叔叔结点了，根据原理，此时就需要进行判断
if (uncle != nullptr && uncle->_color == RED)
{
//（uncle存在且为红）满足该条件，就走自己的变色规则（parent和uncle变红，pparent变黑）就行
parent->_color = BLACK;
uncle->_color = BLACK;
pparent->_color = RED;
//搞定完之后，再根据原理，需要判断爷爷结点的父结点是红色还是黑色（迭代循环走走）
cur = pparent;
parent = cur->_parent;
//parent = pparent->_parent;//这种写法虽然更快，但是没有真正按照迭代的原理来，每一步都要按照原理来最好，容易看懂
}
//注意：此时上述代码判断的只是uncle结点的一种情况，此时uncle还可能有另外两种情况
//1.不存在，为空
//2.存在，但是为黑色
//从图中可以得出结论，如果满足这两种情况，那么此时就是旋转+变色，如果是单旋的话，就让parent变黑，pparent变红，如果是双旋的话，就让cur变黑，pparent变红
//并且注意：单旋和双旋是由cur的位置决定，同侧单旋，反之双旋
else
{
//情况2+3（也就是单旋或者双旋场景）+变色（旋转不同，变色不同）
// g
// p u
// c 或 c
if (parent->_left == cur)
{
//满足该条件就是一个单旋
RotateR(pparent);
parent->_color = BLACK;
pparent->_color = RED;
}
else
{
//双旋
RotateL(parent);
RotateR(pparent);
cur->_color = BLACK;//双旋会导致cur去做根，所以cur变黑，单旋由于parent做根，所以parent变黑
pparent->_color = RED;
//上面两步就是双旋变色的关键，下面这个变色可有可无
parent->_color = RED;//这个只是为了保持红色而已，本质上没有变，最终让代码还可以进入循环进行判断，防止有的场景问题
}
break;//单旋或者双旋完，此时该子树的颜色就正常了，就可以退出该循环了
}
}
else
{
// g
// u p
// c c
Node* uncle = pparent->_left;
if (uncle != nullptr && uncle->_color == RED)//同理
{
//符合变色规则，就开始变色
parent->_color = BLACK;
uncle->_color = BLACK;
pparent->_color = RED;
cur = pparent;
parent = cur->_parent;
//parent = pparent->_parent;//最好不要这样写，因为这样写，会导致cur的位置没有改变，迭代不了cur，只迭代了parent
}
else
{//两个场景是类似的，可以当作一个场景看
if (parent->_right == cur)
{
RotateL(pparent);
parent->_color = BLACK;
pparent->_color = RED;
}
else
{
RotateR(parent);
RotateL(pparent);
cur->_color = BLACK;
pparent->_color = RED;
}
break;
}
}
}
//代码来到这里，表示出循环了，但是root结点可能会因为迭代被置成红色，所以此时需要来一步保底置黑
_root->_color = BLACK;//此时就可以不需要判断，某个根结点的父结点是否为空，因为如果爷爷结点的父结点为黑色了，这个循环就会被终止，这步就是多余的，但是如果是真的走到了root结点，root结点被置红了，那么循环终止的这个代码就尤为重要
return true;
}
private:
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pparent = parent->_parent;
parent->_right = subRL;
if (subRL != nullptr)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (pparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pparent = parent->_parent;
parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (pparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
}
public:
void _Destory(Node* root)
{
if (root == nullptr)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
void InOrder()//中序打印AVL树
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
else
{
_InOrder(root->_left);//这边递归不要传参，你真的是人才啊
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
}
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(Node* root)
{
//1.检查根结点
if (root != nullptr && root->_color == RED)//根结点等于黑色不能判断该树是一个红黑树，但是如果根结点是红色，那么这棵树肯定不是红黑树
{
cout << "_root结点不是黑色" << endl;
return false;
}
//2.检查是否有连续的红色结点
//原理就是找打红色结点，然后判断该结点的孩子结点或者父亲结点是否也是红色，是则违规，不是则该树可能是红黑树
int reference = 0;
Node* cur = root;
while (cur != nullptr)
{
if (cur->_color == BLACK)
{
++reference;
}
cur = cur->_left;//表示我们找的基础值就是最左路径黑色结点的个数
}
return _Check(_root, 0, reference);
}//3.计算黑色结点的数量
bool _Check(Node* root,int black_num,int reference)//此时注意：这里没有使用引用，因为我们要的就是形参，让各个递归函数间的形参不会互相干扰导致累加，这样就可以获取到最终黑色结点的个数了
{ //第三个参数表示的是某一条路径的黑色结点个数
if (root == nullptr)
{
//cout << black_num << endl;//此时表示的就是访问到叶子结点了，注意：此时不是平时返回，而是直接打印此时的black_num这个形参，并且由于递归传递的是形参，一个递归函数中的形参不会改变另一个递归函数的形参，所以最终这个递归函数访问到的就是黑色结点的个数
if (reference != black_num)
{
cout << "某条路径的黑色结点数量不同" << endl;
return false;
}
return true; //并且明白，只有在访问到到叶子结点为空的时候，才能看到个数，否则这个个数就消失了（具体可以画递归展开图）
}
if (root->_color == RED && root->_parent->_color == RED)//如果该结点是红色的，那么此时就去判断它的孩子结点是否为红色，但是此时这种方法不好，因为孩子结点可能不存在，所以我们就去判断它的父亲结点就行了
{
cout << "存在连续的红色结点" << endl;
return false;
}
if (root->_color == BLACK)
{
black_num++;
}
return _Check(root->_left, black_num,reference) && _Check(root->_right, black_num, reference);//递归遍历去寻找连续的红色结点
}//注意，每一层递归都有不同的栈帧，所以此时这个black_num是不会被继承的，假如此时是1，那么递归的下一个函数的black_num还是0
int Helight()
{
return _Height(_root);
}
int _Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
private:
Node* _root;
};
void testRedBlackTree1()
{
RBTree<int, int> t1;
int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15, 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };
for (auto e : arr)
{
t1.Insert(make_pair(e, e));
}//同理，不能说明什么问题，需要按照红黑树的规则去测试此时的这棵树是否符合
t1.InOrder();
t1.IsBalance();
}
void testRedBlackTree2()
{
srand(time(0));
const size_t N = 100000;
RBTree<int, int> t;
for (size_t i = 0; i < N; ++i)
{
size_t x = rand();
t.Insert(make_pair(x, x));
}
//t.InOrder();
cout << t.Helight() << endl;
cout << t.IsBalance() << endl;
}
int main()
{
//testRedBlackTree1();
testRedBlackTree2();
}
总结：无论是AVL树还是红黑树，亦或者是之前学习的初阶数据结构，代码都不重要，重要的永远都是思路而已，并且明白，我们自己实现的数据结构类型，在没有经过检测之前，都是不靠谱的哦！
站长推荐
- SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述