网站建设电子书,采集发布wordpress,大连高新园区范围,推广赚钱拿佣金的软件文章目录 前言1. 红黑树的概念及性质1.1 红黑树的概念1.2 红黑树的性质1.3 已经学了AVL树#xff0c;为啥还要学红黑树 2. 红黑树结构的定义3. 插入#xff08;仅仅是插入过程#xff09;4. 插入结点之后根据情况进行相应调整4.1 cur为红#xff0c;p为红#xff0c;g为黑… 文章目录 前言1. 红黑树的概念及性质1.1 红黑树的概念1.2 红黑树的性质1.3 已经学了AVL树为啥还要学红黑树 2. 红黑树结构的定义3. 插入仅仅是插入过程4. 插入结点之后根据情况进行相应调整4.1 cur为红p为红g为黑u存在且为红无需旋转变色即可情况分析及处理代码实现 4.2 cur为红p为红g为黑u不存在/u存在且为黑单旋变色情况分析及处理代码实现 4.3 cur为红p为红g为黑u不存在/u存在且为黑双旋变色情况分析及处理 4.4 单/双旋转变色 代码统一实现 5. 红黑树的测试5.1 验证其为搜索二叉树5.2 验证其是否平衡且满足红黑树性质5.3 大量随机数构建红黑树进行测试5.4 插入相同数量随机数比较AVL树和红黑树的高度 6. 红黑树的删除7. 红黑树的查找8. 红黑树与AVL树的比较9. 红黑树的应用10. 源码分享10.1 RBTree.h10.2 Test.cpp 前言 这篇文章我们再来学习一种平衡搜索二叉树——红黑树 红黑树和AVL树都是常见的自平衡二叉搜索树它们都可以用于高效地支持插入、删除和查找等操作。虽然它们都能够保持树的平衡性但在不同的应用场景下红黑树和AVL树有各自的优势和适用性。 1. 红黑树的概念及性质
1.1 红黑树的概念 红黑树Red-Black Tree也是是一种自平衡的二叉搜索树与AVL树不同的是它在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍最长路径也不会超出最短路径的两倍因此红黑树的平衡性要求相对宽松没有AVL树那样严格从而使搜索树达到一种相对平衡的状态。 1.2 红黑树的性质
红黑树具有以下特点 每个结点不是黑色就是红色根结点必须是黑色的红色结点的两个子结点必须都是黑色的这保证了没有两个连续的红色节点相连 每个叶子结点都是黑色的(此处的叶子结点指的是空结点也被称为NIL节点)任意结点到其每个叶子结点的简单路径上黑色节点的数量相同确保了树的黑平衡性即红黑树中每条路径上黑色结点的数量一致。 大家可以对照着看一下上面的图看它是否满足这些性质。
思考为什么满足上面的性质红黑树就能保证其最长路径中结点个数不会超过最短路径结点个数的两倍其实不带第4条就可以加不加第4条都不会影响每条路径黑色结点数量是否相等 那通过上面的性质我们可以得知红黑树中的结点要么是黑色要么是红色这没什么可说的然后要求根结点一定是黑色的红色结点不能连续出现如果出现了红色结点那它的子结点必须是黑色的然后还要求每条路径黑色结点的数量必须相等。 那这样其实就可以保证一棵红黑树中最长路径不超高最短路径的两倍。 当然实际中不同的红黑树情况是不一样的所以我们这里来分析一种极端的情况 大家想如果一棵红黑树有红有黑它里面如果有一条全黑的路径那这条全黑的路径一定就是最短路径 如果有一条是一黑一红一黑一红…这样黑红相间的那他就是最长的路径。 然后它们里面的黑色结点个数又是相同的的所以最长路径最多是最短路径的两倍不可能超过最短路径两倍。 所以这样红黑树的高度就能够保持在一个相对平衡的范围内当然他就没有AVL树那么严格。 比如这样的 那另外: 其实分析上面的性质红黑树是可以全黑的全部黑色结点只要满足上面的性质即可。 然后大家思考一个问题上面第四条性质——每个叶子结点都是黑色的(此处的叶子结点指的是空结点也被称为NIL节点)有什么用 那大家先算一下这个红黑树有多少条路径 如果不带空的话我们可能会认为有5条但是这里计算路径其实应该走到空NIL所以正确的应该是有11条路径。 所有我们可以认为这条规则就是为了更好的帮我们区分不同路径的。 然后再补充一个概念 结点的黑高黑色高度从某结点出发不含该结点到达任一空叶结点的路径上经过的黑结点总数 1.3 已经学了AVL树为啥还要学红黑树
然后我们再来分析一个问题 大家想对于一棵红黑树来说如果它里面全部的黑色结点一共有N个的话那它的最短路径长度就差不多是 l o g 2 ( N ) log_2 (N) log2(N)。 然后整棵树的节点数量就是在【N2N】之间。 所以最长路径长度就可以认为差不多是2 l o g 2 ( N ) log_2 (N) log2(N) 所以红黑树的查找最少是 l o g 2 ( N ) log_2 (N) log2(N)次最多是2 l o g 2 ( N ) log_2 (N) log2(N)次所以红黑树查找的时间复杂度是O( l o g 2 N log_2 N log2N)计算时间复杂度前面的常数项可以省略嘛。 而AVL树也是O( l o g 2 N log_2 N log2N但AVL树是比较严格的O( l o g 2 N log_2 N log2N而红黑树是省略了常数项。 所以严格来说红黑树的查找效率是比不上AVL树的但对于计算机来说是没什么差别的但是它们是同一个数量级的都是O( l o g 2 N log_2 N log2N。 那既然好像都差不多为什么我们已经学了AVL树了还要学红黑树呢红黑树有什么优势吗 由于AVL树要求更加严格的平衡所以在进行插入和删除操作时可能需要更频繁地进行旋转操作来调整树的结构以保持平衡。相比之下红黑树的插入和删除操作需要旋转的次数相对较少因此在插入和删除操作频繁的情况下红黑树可能更加高效。 这个如果大家学完这篇文章或许能更好的理解。 所以综合而言 红黑树其实更胜一筹红黑树在实际应用中更为常用STL中的map和set底层就是用的红黑树我们后面也会用红黑树进行模拟实现。 当然红黑树和AVL树在不同的应用场景下有各自的优势和适用性所以我们都有必要学习学习。 2. 红黑树结构的定义
那我们先来定义一下红黑树的结构 这里结点的颜色我们可以用一个枚举 这些代码很简单相信就不用给大家解释了。 然后大家看这里结点的颜色我们给的是红色为什么要选择红色呢黑色不可以吗 我们来分析一下如果我们插入一个新结点给的是黑色那它一定会违反上面提到的红黑树的第5条性质——每条路径上黑色结点的数量一致。 因为原来每条路径黑色结点数量是相同的现在新插入一个黑色结点的话那插入的这条路径会增加一个黑色结点但是其它路径数量不变所以其它所有的路径黑色结点数量都和这一条不相等这样就比较麻烦了。 那如果我们插入结点默认给红色呢会违反规则吗 那红色的话其实要看具体情况了 如果插入一个红色结点但是它的父亲也是红色那就出事了因为红黑树里面不能出现连续的红色结点那这种情况就需要调整了。 但如果它的父亲是黑色那就没问题不需要进行什么处理。 所以我们新插入的结点给成红色当然如果是第一次插入根结点我们可以直接给黑色因为红黑树要求根结点必须是黑色嘛。
3. 插入仅仅是插入过程
由于红黑树也是一种搜索二叉树是在二叉搜索树的基础上加上其平衡限制条件来实现平衡。
所以红黑树插入的逻辑也根搜索二叉树一样 那插入一下就完事了吗 当然不是和AVL树一样插入新结点之后我们要去判断此时这棵树是否还满足是一棵红黑树如果不满足就要进行相应的调整。 那红黑树又是如何进行调整的呢
4. 插入结点之后根据情况进行相应调整
对于红黑树来说插入新结点之后我们要检查红黑树的性质是否遭到破坏如果遭到破坏的话就需要进行相应的调整。
因为新节点的默认颜色是红色因此 如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整 但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连续红色结点出现此时需要对红黑树分情况来讨论 约定 当我们在红黑树中插入一个新结点的时候cur为当前新插入结点pparent为父结点ggrandfather为祖父结点uuncle为叔叔节点 比如 我们下面分成了三种情况但是有些地方分的比较细的话会分为五种 第一种就是第一次插入作为根结点直接将它染成黑色就完了那这种我们上面已经处理过了。 第二种就是插入的时候它的父亲是黑色的新插入的结点是红色的这种就不需要调整插入完直接结束。 那第二种的话我们也不需要单去处理因为第二种不进入我们下面讲的三种情况所以就不会对他进行任何处理最后直接结束。 最后全部写完大家可以自己捋一遍。
下面讲解剩下的三种情况
4.1 cur为红p为红g为黑u存在且为红无需旋转变色即可
情况分析及处理
那这个我们就认为是情况三。
那首先我们还是来看一下该情况对应的一个抽象图 这就是我们当前要讨论的情况那大家看到这里我没有像AVL树那里的画成高度为h的树因为红黑树这里就不太关注高度了而是重点关注结点的颜色。 那这里a/b/c/d/e高度都为0的话其实就是cur就是新增的结点如果不为0代表的情况其实就是下面插入之后调整更新上面变成这种情况那他们的处理方法是统一的。 现在我们插入一个红色结点那这里就出现了连续红色结点的情况这是不行的。 那我们可以直接把p改成黑色吗这样不就没有连续红色结点了 不可以直接把p改成黑色的话这条路径就增加了一个黑色结点但是其它路径数量不变那就不满足所有路径黑色结点数量相同的性质了。 那对于这种情况我们要如何去处理呢 首先第一步将p,u改为黑g改为红 那这样处理过后就不存在连续红色结点的情况了而且每条路径黑色结点的数量依然相等。 那这样就完了吗 还没有。 如果g是根节点调整完成后需要将g改为黑色。 这样它才满足是一棵红黑树。 那上面是g是根结点的情况那如果g是一棵子树呢 比如这样 当然这里不止在cur这个位置插入会引发这种情况上面那个也是p的两个孩子位置u的两个孩子位置在这4个位置新插入结点是不是都是这种情况啊。 那这种情况又如何处理呢 如果g是子树那前面的步骤还是一样——将p,u改为黑g改为红 然后呢如果g的父亲是黑色就可以结束了但现在g的父亲也是红色所以 继续向上调整把g当成cur重新确定p、u、g进行同样的操作一直往上走 直至某一次调整完遇到9的父亲为黑或者走到根停止 代码实现
那我们来写一下代码 上面画图没有画父亲是祖父右孩子的情况单处理方式是一样的这里代码直接加上了。 代码我就不过多解释了相信结合图和上面的分析大家很容易能看懂。 4.2 cur为红p为红g为黑u不存在/u存在且为黑单旋变色
情况四
情况分析及处理
那上面讨论的是u存在且为红的情况那如果u不存在或者u存在且为黑呢
先来看u不存在的情况 像这样 cur是新插入的结点它的叔叔u不存在。 怎么处理呢 其实跟下面讨论的u存在且为黑的处理方法一样下面统一说明。 来看u存在且为黑的情况 如果出现u存在且为黑的情况一定是由上面的4.1情况3调整得到的。 为什么呢 大家看如果插入的时候就是这种情况 是不可能出现的因为这样的话插入之前红黑树中不同路径的黑色结点数量就不相等了他就不符合是一颗红黑树了。 所以出现这种情况一定是情况一转变得来的 就是这样子这种情况的话c里面一定要有一个黑色结点d/e要么为空要么是一个红色结点这样才满足是红黑树在插入之前我们就不具体画了情况比较多。 那如何处理呢 那对于这种情况我们要进行的旋转变色对于上面u不存在也是一样 为什么要旋转因为这种情况的话最长路径有可能已经超过最短路径的两倍了比如上面这个图如果如果d/e是空的话就已经超过了。 所以要先旋转降高度再去调整颜色使它符合红黑树。 进行什么旋转呢 那就要看具体情况了其实还是我们AVL树那里学习的四种情况。 当前我们是在较高左子树的左侧插入所以要进行的旋转是右单旋 先旋转对g这棵树的目的就是让它变平衡。然后变色怎么变呢 变色的话不论那种旋转是统一的p、g变色–p变黑g变红 然后大家看就重新符合红黑树了上面说了c里面一定要有一个黑色结点d/e要么为空要么是一个红色结点。 那上面说了u为空也是一样的处理我们可以来画一下 首先这种情况也应该是右旋较高左子树左侧插入 是不是一样的处理啊。 这里变色的情况是一样的关键在于判断并进行不同的旋转。 我们上面分析的情况是在较高左子树的左侧插入所以先要进行右单旋然后变色。 如果我们是在右侧插入较高右子树的右侧的话那就是先进性左单旋然后变色这里变色是一样的。 比如这样 代码实现 这里的代码我们等到后面和双旋的一起写 那上面我们说细分的话有5种情况上面已经说了4种那最后一种其实也是u不存在/u存在且为黑与上一种情况的区别就是第5中是双旋变色
4.3 cur为红p为红g为黑u不存在/u存在且为黑双旋变色
上面我们分析的是需要进行单旋然后变色的情况那当然就有需要进行双旋调整高度然后再变色的情况。 当然本质是因为插入的情况不同所以需要不同的旋转来降高度。
情况分析及处理
那我们就来分析一下需要双旋变色的情况 首先前提条件根上面一样还是cur为红p为红g为黑u不存在/u存在且为黑 这里画图我就不分那么细了因为跟上面其实差不多只是要进行的旋转不同 我们来画一种左右双旋变色的情况 那如果u不存在那就是这样 那先进行一个左右双旋 这样高度就降下去了然后怎么变色呢 cur变黑g变红不论哪种双旋变色是一样的 这样就重新调整为红黑树了。 再给大家画一下u存在且为黑的情况吧 同样的如果这里出现u存在且为黑的情况也一定是有4.1情况3调整更新得到的 比如这样 那然后其实和u为空一样先进行一个左右双旋因为我们这里画的还是较高左子树右侧插入的情况 然后变色还跟上面一样cur变黑g变红 4.4 单/双旋转变色 代码统一实现
那接下来我们来写一下需要旋转变色调整的几种情况的代码
首先我们来看左侧插入的情况右单旋/左右单旋 那我们来写一下 这就是左侧插入的两种需要旋转的情况处理 那我们再来写一下右侧插入的 叔叔为红我们上面写过了这里还是写叔叔不存在或者存在且为黑的情况 就写好了。 左旋右旋的代码直接拷贝AVL树的就行记得把平衡因子的更新删掉。 5. 红黑树的测试
5.1 验证其为搜索二叉树
首先我们还是先来验证他是否是二叉搜索树看它中序是否有序就行了 测试一下 是平衡的没问题。 再换一组数据 没什么问题 ps我在这个地方测试的时候修改了几处错误都是判断的写成了我都改了过来上面代码的截图有错误的地方我也做了修改。 如果有遗漏的地方大家发现了上面代码片段的截图有地方有错误的话可以看我最后分享的源码。不过应该都被我修改过了 5.2 验证其是否平衡且满足红黑树性质
那如何判断它是否满足是一棵红黑树呢
其实就是去检查那几条规则性质 首先结点颜色要么是黑色要么是红色这没什么好检查的。 然后根结点必须是黑色这个可以检查一下如果根结点不是黑色是红色直接就不符合了 然后如果出现连续的红色结点那也不符合。 那怎么检查有没有出现连续红色结点呢 我们可以去遍历这棵树然后遇到红色结点判断它的孩子是不是红色结点如果存在红色结点它的孩子也是红色那就不符合。 这样确实可以但是不太好因为孩子的话要检查两个而且结点的孩子有还有可能不存在为空那还得再加一个判断。 所以我们可以这样做遍历遇到红色结点我们去看它的父亲如果它的父亲也为红色那就不行。 而判断父亲的话只有根结点没有父亲但是根结点是黑色的也不会去检查它。 所以这样写会好一点 然后还剩一个我们要检查每条路径黑色结点数量是否相等存在不相等的情况就不符合。 那这个要如何检查呢 我们可以先求出一条路径的黑色结点数量把它作为基准值然后再递归求出每条路径的黑色结点数量和它比较如果存在不相等的情况就不符合。 那就写好了 然后我们来验证一下 5.3 大量随机数构建红黑树进行测试
下面我们来生成一些随机数构建一棵红黑树测试一下 先来10万个 没有出现问题 来100万 没有问题。 5.4 插入相同数量随机数比较AVL树和红黑树的高度
然后我们AVL树写的求高度的函数拷贝过来在AVL树和红黑树中插入相同数量的随机数看看它们的高度会差多少 我们看到插入相同数量随机数它们的高度是可以达到一样高的当然这里产生的随机数可能会有很多重复值所以实际不会插入那么多。 还是10万个这次对产生的随机数都加个i那产生的随机数不同的数量就多了我们看到就有一些差异了 那让他们插入的值不相同呢 大家看这次差异就大了还是红黑树要高一点 那增加到100万个数据呢 这次差的就多了。 那这个结果其实也证实了我们上面说的就是AVL树对平衡的控制是比较严格的而红黑树是相对宽松的。 6. 红黑树的删除
红黑树的删除呢我们这里不做详细讲解 红黑树的删除比较复杂要比插入还复杂好多。 但关键的是红黑树的删除在考研包括我们找工作笔试面试的时候一般是不会考察的所以我们也没必要去学。 大家有兴趣的可以自己查找相关资料进行学习可以参考《算法导论》或者《STL源码剖析》 7. 红黑树的查找
那红黑树的查找就也和搜索二叉树的查找一样之前讲过这里就不再说了。
8. 红黑树与AVL树的比较 红黑树和AVL树都是高效的自平衡搜索二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)。 红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍所以AVL树的插入和删除操作比红黑树更耗时。 因为AVL树在插入和删除节点后会进行更多的旋转操作以维持一个较为严格的平衡所以插入和删除操作的时间复杂度更高。 相对而言红黑树对平衡的控制比较宽松降低了插入删除时需要旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 在实际应用中红黑树的使用更广泛。许多编程语言和库都使用红黑树作为基础数据结构例如C STL中的std::map和std::set就是基于 红黑树实现的。 9. 红黑树的应用 1. C STL库 – map/set、mutil_map/mutil_set 2. Java 库 3. linux内核 4. 其他一些库 10. 源码分享
10.1 RBTree.h
#pragma onceenum Colour
{RED,BLACK,
};template class T
struct RBTreeNode
{RBTreeNodeT* _parent;RBTreeNodeT* _left;RBTreeNodeT* _right;T _data;Colour _col;RBTreeNode(const T data):_parent(nullptr), _left(nullptr), _right(nullptr), _data(data), _col(RED){}};template class T
class RBTree
{typedef RBTreeNodeT Node;
public:bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (data cur-_data){parent cur;cur cur-_left;}else if (data cur-_data){parent cur;cur cur-_right;}else{return false;}}//走到这里cur为空就是key应该插入的位置cur new Node(data);//链接if (data parent-_data)parent-_left cur;if (data parent-_data)parent-_right cur;//链接父亲指针cur-_parent parent;//如果插入之后它的parent是红的就需要进行调整while (parent parent-_col RED){Node* grandfather parent-_parent;//如果父亲是祖父的左孩子那右孩子就是叔叔if (parent grandfather-_left){Node* uncle grandfather-_right;//这里处理的情况是叔叔存在且为红变色向上继续处理if (uncle uncle-_col RED){//将p,u改为黑g改为红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//更新cur为grandfather判断它的父亲是什么情况//1.如果不存在或者为黑就需要继续处理了也不会进行循环了//2.如果它的父亲存在且为红重新循环进行调整cur grandfather;parent cur-_parent;}else//叔叔不存在/叔叔存在且为黑的情况{// g// p u// c if (cur parent-_left)//左左——右单旋变色{RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//左右——左右双旋变色{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}//这里调整完就可以break了因为颜色都变的合适了而相关的链接关系旋转会帮我们处理break;}}//如果父亲是祖父的右孩子那左孩子就是叔叔else //parent grandfather-_right{Node* uncle grandfather-_left;//这里处理的情况是叔叔存在且为红if (uncle uncle-_col RED){//将p,u改为黑g改为红parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//更新cur为grandfather判断它的父亲是什么情况//1.如果不存在或者为黑就需要继续处理了也不会进行循环了//2.如果它的父亲存在且为红重新循环进行调整cur grandfather;parent cur-_parent;}else{if (cur parent-_right)//右右——左单旋变色{// g// u p// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else//右左——右左双旋变色{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}//上面处理过程中有可能会把根变成红色这里统一处理一下把根置成黑_root-_col BLACK;return true;}void InOrder(){_InOrder(_root);cout endl;}bool IsBlance(){if (_root _root-_col RED){cout 根结点是红色 endl;return false;}//先求出一条路径黑色结点数量int mark 0;Node* cur _root;while (cur){if (cur-_col BLACK)mark;cur cur-_left;}//检查是否出现连续红色结点及所有路径黑色结点数量是否相等return _Check(_root, 0, mark);}int TreeHeight(){return _TreeHeight(_root);}
private:int _TreeHeight(Node* root){if (root nullptr)return 0;int RightH _TreeHeight(root-_left);int leftH _TreeHeight(root-_right);return RightH leftH ? RightH 1 : leftH 1;}bool _Check(Node* root, int blackNum, int mark){if (root nullptr){//走到空就是一条路径走完了比较一下是否相等if (blackNum ! mark){cout 存在黑色结点数量不相等 endl;return false;}return true;}if (root-_col BLACK)blackNum;if (root-_col RED root-_parent-_col RED){cout 出现连续红色结点 endl;return false;}return _Check(root-_left, blackNum, mark) _Check(root-_left, blackNum, mark);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_data ;_InOrder(root-_right);}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//旋转并更新_parent指针parent-_right subRL;if (subRL)subRL-_parent parent;//先保存一下parent-_parent因为下面会改它Node* pparent parent-_parent;//旋转并更新_parent指针subR-_left parent;parent-_parent subR;//若pparent为空则证明旋转的是一整棵树因为根结点的_parent为空if (pparent nullptr){//subR是新的根_root subR;_root-_parent nullptr;}//若pparent不为空则证明旋转的是子树parent上面还有结点else{//让pparent指向子树旋转之后新的根if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}//同时也让新的根指向pparentsubR-_parent pparent;}}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;//旋转并更新_parent指针parent-_left subLR;if (subLR)subLR-_parent parent;//先保存一下parent-_parent因为下面会改它Node* pparent parent-_parent;//旋转并更新_parent指针subL-_right parent;parent-_parent subL;//若parent等于_root则证明旋转的是一整棵树这也是一种判断方法if (parent _root){_root subL;_root-_parent nullptr;}else{//让pparent指向子树旋转之后新的根if (parent pparent-_left){pparent-_left subL;}else{pparent-_right subL;}//同时也让新的根指向pparentsubL-_parent pparent;}}private:Node* _root nullptr;
};10.2 Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include iostream
using namespace std;
#include time.h
#include RBTree.h
void RBTest1()
{//int arr[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//int arr[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int arr[] { 95,47,32,29,7,7,2,50,74,30 };RBTreeint t1;for (auto e : arr){t1.Insert(e);}t1.InOrder();cout t1.IsBlance() endl;}void RBTest2()
{srand((unsigned int)time(nullptr));const int N 100000;RBTreeint t;for (int i 0; i N; i){int x rand() i;t.Insert(x);}cout t.TreeHeight() endl;AVLTreeint, int t2;for (int i 0; i N; i){int x rand() i;t2.Insert(make_pair(x, x));}cout t2.TreeHeight() endl;}
int main()
{RBTest2();return 0;
}
