淮南餐饮网站建设,赤峰市住房和城乡建设局官方网站,跨境电商最好卖的产品,php开源订单管理系统红黑树模拟实现并封装为map和set 前言正式开始红黑树概念红黑树基本要求大致框架树节点树 调整红黑树使其平衡第一种#xff1a;cur红#xff0c;p红#xff0c;g黑#xff0c;u存在且为红第二种#xff1a;cur红#xff0c;p红#xff0c;g黑#xff0c;u不存在或为黑… 红黑树模拟实现并封装为map和set 前言正式开始红黑树概念红黑树基本要求大致框架树节点树 调整红黑树使其平衡第一种cur红p红g黑u存在且为红第二种cur红p红g黑u不存在或为黑左左右右单旋 变色左右右左双旋 变色 前言
本篇主要讲解红黑树的模拟实现实现之后再封装成map和set。
红黑树中所用到的旋转功能均源自我的上一篇博客本篇中不会再详谈旋转若对于旋转不了解的同学可以先看看上一篇博客【C】AVL树模拟实现插入功能
正式开始
前一篇的AVL树是严格平衡的一棵二叉搜索树也就是每个节点的做右子树高度差不超过1。
红黑树在二叉搜索树的基础上多了一个条件最长路径不超过最短路径的2倍。没有AVL树那么严格但是也是近似平衡的。
同AVL树相比插入同样的数据AVL树旋转更多红黑树旋转更少红黑树的优势就在于此这一点比AVL树优很多毕竟每次旋转的时候还是要动不少指针的。
但同时红黑树也有一丁点的劣势查找效率比AVL树低一丢丢因为极端情况下也就是最长路径就是最短路径的2倍时当我们正好要查找最长路径的叶子节点时速度比AVL树慢了一半。但是虽说是一半那也只是 l o g 2 N log_2N log2N的一半如果存储10亿个数查找最边上的节点也就查找30次就能找到因为对于AVL树来说几乎是完全二分的那么红黑树的最坏情况就是60次喽但是这样二者相差可以说是忽略不计的。
所以考虑整体情况的话还是红黑树更胜一筹。不然STL中的map和set底层用的就不是红黑树了。
红黑树概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。
先来一棵树看看
看起来花里胡哨的不要怕纸老虎。
红黑树基本要求
红黑树实现的时候不是按照AVL树那样依靠平衡因子来实现的。而是通过控制节点是红色还是黑色来实现的不然也就不叫红黑树了。 但是对于节点是红色还是黑色是有要求的 每个节点非黑即红根节点是黑色的红色节点的两个子节点为黑色的即树中没有连续的红色结点对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点。即每条路径上黑色结点数相等。每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。
第五点其实没什么用是指空节点是黑色节点当树是空树的时候正好可以和第二条对应。树是空树根节点就是空的空节点是黑色节点那么根节点也就是黑色结点了。
我再把上面那张图拿出来各位对着前四点看看
每个结点满足上述条件后就能够保证最长路径不超过最短路径的二倍了。各位想想为什么。 上述条件中可没有说不能有连续的黑色节点所以最短路径就可以是连续黑色结点所组成的路径最长路径就是一黑一红一黑一红…组成的路径。那么当到达极限时最长路径就正好是最短路径的二倍。 再问个问题 上图中一共有几条路径 答案是11条。 有的同学可能懵了不要懵。 上面数路径是要数到空节点的上面一共有11个空节点所以也就是11条路径。 这里也是第五点的一个好处方便我们数路径可以看到图中空节点写的是NIL红黑树这里把空节点叫做NIL节点。 废话不多说了我们先把树大致框架搞出来。
大致框架
树节点
红黑树树节点中包含的东西如下
构造函数为 颜色暂时不给等会插入的时候会再说。
树
再来写树。
初始就一根
然后把二叉搜索树的基本的插入功能写出来
上面我把调整树结构的留下这里细讲。
调整红黑树使其平衡
若插入新节点后的树结构不符合了前面说的那四条规则此时就要调整。
但是插入节点要确定一下其颜色如何确定呢 看第三条和第四条规定。不能有连续的红色节点所有路径黑色节点数量相同。
所以如果我们插入红色节点影响的就只是当前插入节点所处的路径因为红色节点不相连即可。如果我们插入黑色结点影响的就是整棵树了因为当前路径加一个黑的其他路径就都要加一个黑的。显然我们要选就选红色的插入千万不敢选黑色的插一选黑色就要调整棵树选了红色只调当前路径就够了。
那么调整之前我得先声明几个节点的名字
cur节点就是新插入的节点等会在调整的过程中我以cur表示。. 父(father)节点 / 双亲(parent)节点 等会在调整的过程中我以字母p表示。叔叔(uncle)节点就是父节点的兄弟等会在调整的过程中我以字母u表示。爷爷(grandfather)节点就是父节点的父节点等会在调整的过程中我以字母g表示。
先来个图看看
那么调整可分为两大种情况。 第一种cur红p红g黑u存在且为红 第二种cur红p红g黑u不存在或为黑 说一下为啥是上面两种。 首先我们插入的一定是红色节点。
树为空的时候不需要调整直接让根搞成黑色节点。插入节点为红色p为黑色此时不需要调整直接插入即可。因为前面也说了极限长度是黑红黑红这样规律走下去的当插入的是红色的时候不会出现到达最长路径的情况。所以不需要调整。插入节点为红色p为红色违反第三条规定此时就需要调整。而且当p为红色的时候g一定为黑色因为原树要保证是红黑树所以当p是红色的时候不能有连续的红色节点所以g就一定是黑色的。
然后将第三点的调整分为两大种至于为什么等会将调整的时候就知道了这是前人总结出来的规律。
那么就开始将调整。 如果你对于AVL树插入时的旋转非常熟悉了那么这里红黑树插入的调整自然也不在话下。
正式开始调整
第一种cur红p红g黑u存在且为红 调整方式为pu变黑g变红cur指向g继续向上调整遇到树根为止将树根改为黑。 即只有变色。 先来两个例子 调整一次 调整两次 不用往下画了再往下就是调整三、四、五……等等次数了。是有规律的上面两个都是具象图下来我把抽象图给大家各位参考参考
附上我手画的图 比较潦草主要是方便我看一下。
这里不管cur在p左边还是右边调整方式都是一样的记住最开始写的调整方式就行 调整方式为pu变黑g变红cur指向g继续向上调整遇到树根为止将树根改为黑。 即只有变色。 第二种cur红p红g黑u不存在或为黑
第二大种就要用到旋转了但还要再分为两小种。 第一小种p在g左且cur在p左或者p在g右且cur在p右。此种情况下为单旋。 对应的图为 第二小种p在g左且cur在p右或者p在g右且cur在p左。此种情况下为双旋。 对应图为 然后再细谈
左左右右单旋 变色
单旋 变色。 和AVL树一样左左就右单旋右右就左单旋。
我就只画左左的还是先给两个实例的图再给抽象图。 抽象图
左右右左双旋 变色
单旋 变色。 和AVL树一样左右就左右双旋右左就右左双旋。
实例
抽象图
手画图
总结一下 红黑树调节平衡关键是看叔叔。 u存在且为红变色继续往上处理。 u不存在 或者 存在且为黑旋转变色。其中旋转又分单旋和双旋若p、cur在单侧就单旋若p、cur一左一右或一右一左就双旋。
上面的三种情况搞完就可以写代码了。
调节平衡的代码如下
其中我光用了单旋没有用双旋因为双旋就是两个单旋。 单旋代码
可以写一个中序遍历来简单打印一下结果 但是简单的中序遍历可不够来写一个专门用来检查是否平衡的函数。 到此结束。。。
