【算法】最容易懂得的红黑树

这篇具有很好参考价值的文章主要介绍了【算法】最容易懂得的红黑树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

红黑树是一个平衡的二叉树,但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束,但是这样在动态插入中保持树的完美平衡代价太高,所以,我们稍微放松逛一下限制,希望找到一个能在对数时间内完成查找的数据结构。这个时候,红黑树站了出来。 
阅读以下需要了解普通二叉树的插入以及删除操作。 
红黑树是在普通二叉树上,对没个节点添加一个颜色属性形成的,同时整个红黑二叉树需要同时满足一下五条性质 
红黑树需要满足的五条性质: 
性质一:节点是红色或者是黑色; 
在树里面的节点不是红色的就是黑色的,没有其他颜色,要不怎么叫红黑树呢,是吧。 
性质二:根节点是黑色; 
根节点总是黑色的。它不能为红。 
性质三:每个叶节点(NIL或空节点)是黑色; 
这个可能有点理解困难,可以看图:

【算法】最容易懂得的红黑树

这个图片就是一个红黑树,NIL节点是个空节点,并且是黑色的。 
性质四:每个红色节点的两个子节点都是黑色的(也就是说不存在两个连续的红色节点); 
就是连续的两个节点不能是连续的红色,连续的两个节点的意思就是父节点与子节点不能是连续的红色。

**性质五:从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点;**
还是看图:

【算法】最容易懂得的红黑树

从根节点到每一个NIL节点的路径中,都包含了相同数量的黑色节点。 
这五条性质约束了红黑树,可以通过数学证明来证明,满足这五条性质的二叉树可以将查找删除维持在对数时间内。 
当我们进行插入或者删除操作时所作的一切操作都是为了调整树使之符合这五条性质。 
下面我们先介绍两个基本操作,旋转。 
旋转的目的是将节点多的一支出让节点给另一个节点少的一支,旋转操作在插入和删除操作中经常会用到,所以要熟记。

下面是左旋和右旋:
左旋:

【算法】最容易懂得的红黑树

右旋: 

【算法】最容易懂得的红黑树

下面讲讲插入

我们先明确一下各节点的叫法

【算法】最容易懂得的红黑树

因为要满足红黑树的这五条性质,如果我们插入的是黑色节点,那就违反了性质五,需要进行大规模调整,如果我们插入的是红色节点,那就只有在要插入节点的父节点也是红色的时候违反性质四或者是当插入的节点是根节点时,违反性质二,所以,我们把要插入的节点的颜色变成红色。

下面是可能遇到的插入的几种状况: 
1、当插入的节点是根节点时,直接涂黑即可; 
2、当要插入的节点的父节点是黑色的时候。

【算法】最容易懂得的红黑树

这个时候插入一个红色的节点并没有对这五个性质产生破坏。所以直接插入不用在进行调整操作。

3、如果要插入的节点的父节点是红色且父节点是祖父节点的左支的时候。 
这个要分两种情况,一种是叔叔节点为黑的情况,一种是叔叔节点为红的情况。 
当叔叔为黑时,也分为两种情况,一种是要插入的节点是父节点的左支,另一种是要插入的节点是父亲的右支。 
我们先看一下当要插入的节点是父节点的左支的情况:

这个时候违反了性质四,我们就需要进行调整操作,使之符合性质四,我们可以通过对祖父节点进行右旋同时将祖父节点和父节点的颜色进行互换,这样就变成了:

【算法】最容易懂得的红黑树

经过这样的调整可以符合性质四并且不对其他性质产生破坏。 
当插入的节点是父节点的右支的时候:

【算法】最容易懂得的红黑树

当要插入的节点是父节点的右支的时候,我们可以先对父节点进行左旋,变成如下:

【算法】最容易懂得的红黑树

如果我们把原先的父节点看做是新的要插入的节点,把原先要插入的节点看做是新的父节点,那就变成了当要插入的节点在父节点的左支的情况,对,是的,就是按照当要插入的节点在父节点的左支的情况进行旋转,旋转完之后变成如下:

【算法】最容易懂得的红黑树

4、如果要插入的节点的父节点是红色且父节点是祖父节点的右支的时候; 
这个时候的情况跟情况3所表述的情况是一个镜像,将情况3的左和右互换一下就可以了。 
5、如果要插入的节点的父节点是红色并且叔叔节点也为红色,如下:

【算法】最容易懂得的红黑树

这个时候,只需将父亲节点和叔叔节点涂黑,将祖父节点涂红。

以上就是插入的全部过程。 
下面我们再讲讲删除的操作:

首先你要了解普通二叉树的删除操作: 
1.如果删除的是叶节点,可以直接删除; 
2.如果被删除的元素有一个子节点,可以将子节点直接移到被删除元素的位置; 
3.如果有两个子节点,这时候就可以把被删除元素的右支的最小节点(被删除元素右支的最左边的节点)和被删除元素互换,我们把被删除元素右支的最左边的节点称之为后继节点(后继元素),然后在根据情况1或者情况2进行操作。如图:

【算法】最容易懂得的红黑树

将被删除元素与其右支的最小元素互换,变成如下图所示:

【算法】最容易懂得的红黑树

然后再将被删除元素删除:

【算法】最容易懂得的红黑树

我们下面所称的被删除元素,皆是指已经互换之后的被删除元素。 
加入颜色之后,被删除元素和后继元素互换只是值得互换,并不互换颜色,这个要注意。

下面开始讲一下红黑树删除的规则: 
1.当被删除元素为红时,对五条性质没有什么影响,直接删除。 
2.当被删除元素为黑且为根节点时,直接删除。 
3.当被删除元素为黑,且有一个右子节点为红时,将右子节点涂黑放到被删除元素的位置,如图: 

【算法】最容易懂得的红黑树

变成

【算法】最容易懂得的红黑树

4.当被删除元素为黑,且兄弟节点为黑,兄弟节点两个孩子也为黑,父节点为红,此时,交换兄弟节点与父节点的颜色;NIL元素是指每个叶节点都有两个空的,颜色为黑的NIL元素,需要他的时候就可以把它看成两个黑元素,不需要的时候可以忽视他。 
如图: 

【算法】最容易懂得的红黑树

变成:

【算法】最容易懂得的红黑树

5.当被删除元素为黑、并且为父节点的左支,且兄弟颜色为黑,兄弟的右支为红色,这个时候需要交换兄弟与父亲的颜色,并把父亲涂黑、兄弟的右支涂黑,并以父节点为中心左转。如图: 
由:

【算法】最容易懂得的红黑树

变成:

【算法】最容易懂得的红黑树

6.当被删除元素为黑、并且为父节点的左支,且兄弟颜色为黑,兄弟的左支为红色,这个时候需要先把兄弟与兄弟的左子节点颜色互换,进行右转,然后就变成了规则5一样了,在按照规则5进行旋转。如图: 

【算法】最容易懂得的红黑树

先兄弟与兄弟的左子节点颜色互换,进行右转,变成:

【算法】最容易懂得的红黑树

然后在按照规则5进行旋转,变成:

【算法】最容易懂得的红黑树

7.当被删除元素为黑且为父元素的右支时,跟情况5.情况6 互为镜像。 
8.被删除元素为黑且兄弟节点为黑,兄弟节点的孩子为黑,父亲为黑,这个时候需要将兄弟节点变为红,再把父亲看做那个被删除的元素(只是看做,实际上不删除),看看父亲符和哪一条删除规则,进行处理变化如图: 
由:

【算法】最容易懂得的红黑树

变成:

【算法】最容易懂得的红黑树

8.当被删除的元素为黑,且为父元素的左支,兄弟节点为红色的时候,需要交换兄弟节点与父亲结点的颜色,以父亲结点进行左旋,就变成了情况4,在按照情况四进行操作即可,变化如下: 
由:

【算法】最容易懂得的红黑树

交换兄弟节点与父亲结点的颜色,以父亲结点进行左旋 变成:

【算法】最容易懂得的红黑树

在按照情况四进行操作,变成:

【算法】最容易懂得的红黑树

 

好了,删除的步骤也讲完,没有讲到的一点就是,在添加删除的时候,时刻要记得更改根元素的颜色为黑。 
这里并没有语言实现,只是讲了一下红黑树的插入删除步骤,你可以根据步骤自己把红黑树实现。

点击这里,照着规则一步一步的构建一个红黑树吧。

最后: 
1.红黑树的实现其实是一个2、3、4树,只是将双节点或者三节点用红色进行了标示,如果你将红色节点放到和它父元素相同的高度,并把它和父元素看做是一个元素,你就会发现,变成了一个高度为lgN的二叉树,这个2.3.4树对红黑树很有启发意义。 
2.上面的步骤其实可以不用死记硬背,是可以推导出来的,因为我们是把一个平衡但通过插入或者删除破坏了平衡的红黑树再次平衡,同过旋转让位,改变红黑颜 色,使之符合那五条基本性质。比如遇到删除操作情况四的时候,我们可以把那个删除元素去除,发现左边比右边少一个黑元素,这个时候,怎么办,我们发现兄弟 节点的子元素有一个红元素,操作这个不会影响那五条性质,所以我们通过变换颜色,旋转,即可让左右两边的的黑色数目一样。 
3.旋转操作的目的是出让一个元素到另外的地方并且符合二叉树左小右大的性质,交换颜色的目的是为了保持红黑树的那五条性质。 
4.要时刻记得 ,一切的操作都是为了保持那五条性质。

最后的最后,其实还有一种更为简单的红黑二叉树,这个简单的红黑二叉树实际上是一个2.3树,他只允许左节点为红节点,但是性能上肯定是不如这个红黑树。这个简单的红黑二叉树在《算法》第四版有介绍,掌握完之后再看这个简单的红黑二叉树,就会觉着简单 easy。 
最后的最后的最后,一定要尝试着自己推导一下插入删除规则啊,不然经常忘,是睡一觉起来再看就有点懵逼的那种忘。

RBT 操作动画:https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

https://www.jianshu.com/p/e136ec79235c
 文章来源地址https://www.toymoban.com/news/detail-429754.html

到了这里,关于【算法】最容易懂得的红黑树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Linux面试必备的红黑树问题,这可能是zui全的一篇了!

    原文网址:https://zhuanlan.zhihu.com/p/471318214 首先上一个红黑树知识点结构图 1.stl中的set底层用的什么数据结构? 2.红黑树的数据结构怎么定义的? 3.红黑树有哪些性质? 4.红黑树的各种操作的时间复杂度是多少? 5.红黑树相比于BST和AVL树有什么优点? 6.红黑树相对于哈希表,在

    2024年02月08日
    浏览(44)
  • Python - 深夜数据结构与算法之 AVL 树 & 红黑树

    目录 一.引言 二.高级树的简介 1.树 2.二叉树 3.二叉搜索树 4.平衡二叉树 三.AVL 树 ◆ 插入节点 ◆ 左旋 ◆ 右旋 ◆ 左右旋 ◆ 右左旋 ◆ 一般形式 ◆ 实际操作 ◆ 总结 四.红黑树 ◆ 概念 ◆ 示例 ◆ 对比 五.总结 前面我们介绍了二叉树、二叉搜索树、多叉树等基础的树形结构,

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

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

    2024年02月09日
    浏览(49)
  • 数据结构与算法(三):树论(树形结构、二叉树、二叉搜索树、红黑树、Btree&B+Tree、赫夫曼树、堆树)

    树论(树形结构、二叉树、二叉搜索树、红黑树、Btree、B+Tree、赫夫曼树、堆树) 在树形结构里面重要的术语: 结点:树里面的元素。 父子关系:结点之间相连的边 子树:当结点大于1时,其余的结点分为的互不相交的集合称为子树 度:一个结点拥有的子树数量称为结点的

    2024年02月01日
    浏览(94)
  • 【C++高阶(四)】红黑树深度剖析--手撕红黑树!

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 如果说发明AVL树的人是天才,那么 发明红黑树的人可以称为天才中的 精英!为什么AVL树这么强大但是没啥 人用呢?就是因为红黑树比你还好

    2024年02月05日
    浏览(46)
  • AVL树,红黑树,红黑树封装map和set

    二叉搜索树虽可以缩短查找的效率,但如果 数据有序或接近有序二叉搜索树将退化为单支树 ,查找元素相当于在顺序表中搜索元素, 效率低下 。因此,咱们中国的邻居俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法: 当向二叉搜索树中插入

    2023年04月25日
    浏览(61)
  • 搜索二叉树 | 红黑树 | 验证是否为红黑树 | 代码实现

    黑红树是一颗特殊的搜索二叉树,本文在前文的基础上,图解红黑树插入:前文 链接,完整对部分关键代码展示,完整的代码在gitee仓库中: 链接 文章中有错误的地方,欢迎大家指正!如果有帮助到你,也请多多点赞支持! 1.红黑树的概述 平衡二叉树要求左右子树的高度差

    2024年02月21日
    浏览(41)
  • 【C++进阶06】红黑树图文详解及C++模拟实现红黑树

    1.1 红黑树的概念 AVL树用平衡因子让树达到高度平衡 红黑树可以认为是AVL树的改良 通过给每个节点标记颜色让树接近平衡 以减少树在插入节点的旋转 在每个结点新增一个存储位表示结点颜色 可以是Red或Black 通过对任何一条从根到叶子的路径上 各个结点着色方式的限制 红黑

    2024年01月21日
    浏览(49)
  • 红黑树是什么,为什么HashMap使用红黑树代替数组+链表?

            我们都知道在HashMap中,当数组长度大于64并且链表长度大于8时,HashMap会从数组+链表的结构转换成红黑树,那为什么要转换成红黑树呢,或者为什么不一开始就使用红黑树呢?接下来我们将去具体的去剖析一下!         红黑树是一种自平衡的二叉搜索树,它是

    2024年04月14日
    浏览(37)
  • 【C++进阶5-红黑树】噩梦般的存在?手提AVLTree暴揍红黑树!

    今天,带来无数人的噩梦——红黑树的讲解。文中不足错漏之处望请斧正! 如果还没看过AVLTree讲解的一定要去看看,看完才能更好理解红黑树! 红黑树是自平衡的二叉搜索树。 红黑树的规则: 每个结点非黑即红 根结点为黑 叶子结点为黑(此处的叶子结点指空结点) 不能有

    2024年02月07日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包