【C++】红黑树模拟实现插入功能(包含旋转和变色)

这篇具有很好参考价值的文章主要介绍了【C++】红黑树模拟实现插入功能(包含旋转和变色)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

前言

本篇主要讲解红黑树的模拟实现,实现之后再封装成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。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

先来一棵树看看:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

看起来花里胡哨的,不要怕,纸老虎。

红黑树基本要求

红黑树实现的时候不是按照AVL树那样依靠平衡因子来实现的。而是通过控制节点是红色还是黑色来实现的,不然也就不叫红黑树了。

但是对于节点是红色还是黑色是有要求的:

  1. 每个节点非黑即红
  2. 根节点是黑色的
  3. 红色节点的两个子节点为黑色的,即树中没有连续的红色结点
  4. 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。即每条路径上黑色结点数相等。
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。

第五点其实没什么用,是指空节点是黑色节点,当树是空树的时候正好可以和第二条对应。树是空树,根节点就是空的,空节点是黑色节点,那么根节点也就是黑色结点了。

我再把上面那张图拿出来,各位对着前四点看看:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

每个结点满足上述条件后就能够保证最长路径不超过最短路径的二倍了。各位想想为什么。

上述条件中可没有说不能有连续的黑色节点,所以最短路径就可以是连续黑色结点所组成的路径,最长路径就是一黑一红一黑一红…组成的路径。那么当到达极限时,最长路径就正好是最短路径的二倍。

再问个问题:
上图中,一共有几条路径?

答案是:11条。
有的同学可能懵了,不要懵。
上面数路径是要数到空节点的,上面一共有11个空节点,所以也就是11条路径。
这里也是第五点的一个好处,方便我们数路径,可以看到图中空节点写的是NIL,红黑树这里把空节点叫做NIL节点。

废话不多说了,我们先把树大致框架搞出来。

大致框架

树节点

红黑树树节点中包含的东西如下:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

构造函数为:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构
颜色暂时不给,等会插入的时候会再说。

再来写树。

初始就一根:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

然后把二叉搜索树的基本的插入功能写出来:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

上面我把调整树结构的留下,这里细讲。

调整红黑树使其平衡

若插入新节点后的树结构不符合了前面说的那四条规则,此时就要调整。

但是插入节点要确定一下其颜色,如何确定呢?
看第三条和第四条规定。不能有连续的红色节点,所有路径黑色节点数量相同。

所以如果我们插入红色节点,影响的就只是当前插入节点所处的路径,因为红色节点不相连即可。如果我们插入黑色结点,影响的就是整棵树了,因为当前路径加一个黑的,其他路径就都要加一个黑的。显然,我们要选就选红色的插入,千万不敢选黑色的插,一选黑色就要调整棵树,选了红色只调当前路径就够了。

那么调整之前,我得先声明几个节点的名字

  1. cur节点,就是新插入的节点,等会在调整的过程中我以cur表示。
  2. . 父(father)节点 / 双亲(parent)节点, 等会在调整的过程中我以字母p表示。
  3. 叔叔(uncle)节点,就是父节点的兄弟,等会在调整的过程中我以字母u表示。
  4. 爷爷(grandfather)节点,就是父节点的父节点,等会在调整的过程中我以字母g表示。

先来个图看看:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

那么调整可分为两大种情况。

第一种:cur红,p红,g黑,u存在且为红

第二种:cur红,p红,g黑,u不存在或为黑

说一下为啥是上面两种。
首先我们插入的一定是红色节点。

  1. 树为空的时候,不需要调整,直接让根搞成黑色节点。
  2. 插入节点为红色,p为黑色,此时不需要调整,直接插入即可。因为前面也说了,极限长度是黑红黑红这样规律走下去的,当插入的是红色的时候,不会出现到达最长路径的情况。所以不需要调整。
  3. 插入节点为红色,p为红色,违反第三条规定,此时就需要调整。而且当p为红色的时候,g一定为黑色,因为原树要保证是红黑树,所以当p是红色的时候,不能有连续的红色节点,所以g就一定是黑色的。

然后将第三点的调整分为两大种,至于为什么,等会将调整的时候就知道了,这是前人总结出来的规律。

那么就开始将调整。
如果你对于AVL树插入时的旋转非常熟悉了,那么这里红黑树插入的调整自然也不在话下。

正式开始调整:

第一种:cur红,p红,g黑,u存在且为红

调整方式为:pu变黑g变红,cur指向g继续向上调整,遇到树根为止,将树根改为黑。
即只有变色。

先来两个例子:

调整一次:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

调整两次:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

不用往下画了,再往下就是调整三、四、五……等等次数了。是有规律的,上面两个都是具象图,下来我把抽象图给大家,各位参考参考:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

附上我手画的图:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构
比较潦草,主要是方便我看一下。

这里不管cur在p左边还是右边,调整方式都是一样的,记住最开始写的调整方式就行:

调整方式为:pu变黑g变红,cur指向g继续向上调整,遇到树根为止,将树根改为黑。
即只有变色。

第二种:cur红,p红,g黑,u不存在或为黑

第二大种就要用到旋转了,但还要再分为两小种。

第一小种:p在g左且cur在p左,或者p在g右且cur在p右。此种情况下为单旋。
对应的图为:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

第二小种:p在g左且cur在p右,或者p在g右且cur在p左。此种情况下为双旋。
对应图为:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

然后再细谈:

左左,右右:单旋 + 变色

单旋 + 变色。
和AVL树一样,左左就右单旋,右右就左单旋。

我就只画左左的,还是先给两个实例的图,再给抽象图。

【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

抽象图:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

左右,右左:双旋 + 变色

单旋 + 变色。
和AVL树一样,左右就左右双旋,右左就右左双旋。

实例:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

抽象图:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

手画图:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

总结一下:
红黑树调节平衡关键是看叔叔。
u存在且为红,变色继续往上处理。
u不存在 或者 存在且为黑,旋转+变色。其中旋转又分单旋和双旋,若p、cur在单侧,就单旋,若p、cur一左一右或一右一左就双旋。

上面的三种情况搞完就可以写代码了。

调节平衡的代码如下:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

其中我光用了单旋,没有用双旋,因为双旋就是两个单旋。
单旋代码:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

可以写一个中序遍历来简单打印一下结果:
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构
【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

但是简单的中序遍历可不够,来写一个专门用来检查是否平衡的函数。

【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

【C++】红黑树模拟实现插入功能(包含旋转和变色),c++,红黑树,二叉搜索树,算法,数据结构

到此结束。。。文章来源地址https://www.toymoban.com/news/detail-646005.html

到了这里,关于【C++】红黑树模拟实现插入功能(包含旋转和变色)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】红黑树的概念与模拟实现

    红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 1.每个结点不是红色就是黑色 2.根节点是黑

    2024年02月09日
    浏览(42)
  • 【C++】红黑树插入删除

    喜欢的点赞,收藏,关注一下把! 红黑树 ,是一种 二叉搜索树 ,但 在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制 , 红黑树确保没有一条路径会比其他路径长出俩倍 ,因而是 接近平衡 的。

    2024年02月02日
    浏览(39)
  • 【C++】 使用红黑树模拟实现STL中的map与set

    前面的文章我们学习了红黑树,也提到了C++STL中的map和set的底层其实就是用的红黑树来实现的(而map和set的使用我们前面也学过了)。 既然红黑树我们也学习过了,那这篇文章我们就用红黑树来简单实现一下STL中的map和set,重点是学习它的框架。 上一篇文章我们实现了红黑

    2024年02月12日
    浏览(29)
  • 【C++】红黑树的插入分析及验证

    红黑树 是一种二叉搜索树, 但在每个节点上增加一个存储位表示节点的颜色,可以是red或black, 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其他路径长处两倍,所以是接近平衡的 1. 每个结点不是红色就是黑色 2. 根节点是黑

    2024年02月05日
    浏览(46)
  • 【C++】AVL树和红黑树的插入

    时间过的好快,我也修炼到红黑树了 人世这一遭,何其短暂而漫长啊…… 1. 虽然二叉搜索树的搜索效率很高,当搜索树接近满二叉树时,搜索效率可以达到logN,但是如果数据是有序的,则二叉搜索树会退化为单支树,搜索效率和普通的序列式容器相同了就,所以在搜索树的

    2023年04月08日
    浏览(42)
  • C++语法(20)---- 模拟红黑树

    C++语法(19)---- 模拟AVL树_哈里沃克的博客-CSDN博客 https://blog.csdn.net/m0_63488627/article/details/130229501?spm=1001.2014.3001.5501 目录 1.红黑树介绍 2.模拟实现 1.枚举红黑颜色 2.节点的定义 3.树类框架 4.插入 5.检查 3.代码实现 最长路径不超过最短路径的两倍,近似平衡 最短:全黑 最长:

    2024年02月01日
    浏览(35)
  • 【高阶数据结构】红黑树 {概念及性质;红黑树的结构;红黑树的实现;红黑树插入操作详细解释;红黑树的验证}

    红黑树(Red Black Tree) 是一种自平衡二叉查找树,在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 AVL树 VS 红黑树 红黑树是

    2024年02月09日
    浏览(46)
  • C++ 实现红黑树

    红黑树 ,是一种二叉搜索树,但 在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black 。 通过对 任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路 径会比其他路径长出俩倍 ,因而是 接近平衡 的。 红黑树的性质 每个结点不是红色就

    2024年02月05日
    浏览(39)
  • 【C++】实现红黑树

    红黑树是一个二叉搜索树,与AVL树相比,红黑树不再使用平衡因子来控制树的左右子树高度差,而是用颜色来控制平衡,颜色为红色或者黑色。控制任意一条从根到叶子节点的路径的节点颜色,就可以确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 红黑树的规

    2024年03月25日
    浏览(39)
  • 【数据结构】—红黑树(C++实现)

                                                            🎬 慕斯主页 : 修仙—别有洞天                                                  💜 本文前置知识:  AVL树                                                       ♈️ 今日夜电波 :

    2024年02月05日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包