漫画:什么是红黑树?(整合版)(下)

简介: 二叉查找树(BST)具备什么特性呢?1.左子树上所有结点的值均小于或等于它的根结点的值。2.右子树上所有结点的值均大于或等于它的根结点的值。3.左、右子树也分别为二叉排序树。

 

如此一来,我们的红黑树变得重新符合规则。

640.png640.png640.png

 

 

二叉查找树是如何进行删除操作的呢?


可以分成三种情况。

情况1,待删除的结点没有子结点:

 640.png

 

上图中,待删除的结点12是叶子结点,没有孩子,因此直接删除即可:

 640.png

 

情况2,待删除的结点有一个孩子:

640.png

 

 

上图中,待删除的结点13只有左孩子,于是我们让左孩子结点11取代被删除的结点,结点11以下的结点关系无需变动:

640.png


情况3,待删除的结点有两个孩子:

640.png

上图中,待删除的结点5有两个孩子,这种情况比较复杂。此时,我们需要选择与待删除结点最接近的结点来取代它。

上面的例子中,结点3仅小于结点5,结点6仅大于结点5,两者都是合适的选择。但习惯上我们选择仅大于待删除结点的结点,也就是结点6来取代它。

于是我们复制结点6到原来结点5的位置:

 

640.png

 

被选中的结点6,仅大于结点5,因此一定没有左孩子。所以我们按照情况1或情况2的方式,删除多余的结点6:

 640.png

640.png640.png640.png

红黑树的特性(规则)如下:


 

1.结点是红色或黑色。

2.根结点是黑色。

3.每个叶子结点都是黑色的空结点(NIL结点)。

4.每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)

5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

 下面我们通过一个例子,来看一看删除红黑树的结点会对规则产生怎样的影响:

 

 640.png

 

上图的这颗红黑树,待删除的是黑色结点1,有一个右孩子。根据二叉查找树的删除流程,我们让右孩子结点6直接取代结点1

640.png


显然,这颗新的二叉树打破了两个规则:

规则4.每个红色结点的两个子结点都是黑色。

规则5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

640.png640.png640.png

第一步:如果待删除结点有两个非空的孩子结点,转化成待删除结点只有一个孩子(或没有孩子)的情况。

640.png

 

上面例子是一颗红黑树的局部,标数字的三角形代表任意形态的子树,假设结点8是待删除结点。

根据上文讲解的二叉查找树删除流程,由于结点8有两个孩子,我们选择仅大于8的结点10复制到8的位置,结点颜色变成待删除结点的颜色:

 640.png

接下来我们需要删除红色的结点10

640.png 

红色结点10能成为仅大于8的结点,必定没有左孩子结点,所以问题转换成了待删除结点只有一个右孩子(或没有孩子)的情况。接下来我们进入第二步。

第二步:根据待删除结点和其唯一子结点的颜色,分情况处理。

情况1,自身是红色,子结点是黑色:

 

 640.png

这种情况最简单,按照二叉查找树的删除操作,删除结点1即可:

 640.png 

情况2,自身是黑色,子结点是红色:

 

640.png

这种情况也很简单,首先按照二叉查找树的删除操作,删除结点1

 

640.png

此时,这条路径凭空减少了一个黑色结点,那么我们把结点2变成黑色即可:

 640.png

情况3,自身是黑色,子结点也是黑色,或者子结点是空叶子结点:

640.png

 

这种情况最复杂,涉及到很多变化。首先我们还是按照二叉查找树的删除操作,删除结点1

 640.png 

显然,这条路径上减少了一个黑色结点,而且结点2再怎么变色也解决不了。

这时候我们进入第三步,专门解决父子双黑的情况。

第三步:遇到双黑结点,在子结点顶替父结点之后,分成6种子情况处理。

子情况1,结点2是红黑树的根结点:

 

640.png

此时所有路径都减少了一个黑色结点,并未打破规则,不需要调整。

子情况2,结点2的父亲、兄弟、侄子结点都是黑色:

 

640.png

此时,我们直接把结点2的兄弟结点B改为红色:

640.png

 

这样一来,原本结点2所在的路径少了一个黑色结点,现在结点B所在的路径也少了一个黑色结点,两边“扯平”了。

可是,结点A以下的每一条路径都减少了一个黑色结点,与结点A之外的其他路径又造成了新的不平衡啊?

没关系,我们让结点A扮演原先结点2的角色,进行递归操作,重新判断各种情况。

子情况3,结点2的兄弟结点是红色:

 

640.png

首先以结点2的父结点A为轴,进行左旋:

 640.png

然后结点A变成红色、结点B变成黑色:

 

 640.png

这样的意义是什么呢?结点2所在的路径仍然少一个黑色结点呀?

别急,这样的变化有可能转换成子情况456中的任意一种,在子情况456当中会进一步解决。

子情况4,结点2的父结点是红色,兄弟和侄子结点是黑色:

 

 640.png

 

这种情况,我们直接让结点2的父结点A变成黑色,兄弟结点B变成红色:

 640.png 

这样一来,结点2的路径补充了黑色结点,而结点B的路径并没有减少黑色结点,重新符合了红黑树的规则。

子情况5,结点2的父结点随意,兄弟结点B是黑色右孩子,左侄子结点是红色,右侄子结点是黑色:

 

 640.png

这种情况下,首先以结点2的兄弟结点B为轴进行右旋:

640.png

接下来结点B变为红色,结点C变为黑色:

640.png

这样的变化转换成了子情况6

子情况6,结点2的父结点随意,兄弟结点B是黑色右孩子,右侄子结点是红色:

640.png

 

首先以结点2的父结点A为轴左旋:

 

640.png 

接下来让结点A和结点B的颜色交换,并且结点D变为黑色:

 640.png

这样是否解决了问题呢?

经过结点2的路径由(随意+黑)变成了(随意++黑),补充了一个黑色结点;

经过结点D的路径由(随意++红)变成了(随意+黑),黑色结点并没有减少。

所以,这时候重新符合了红黑树的规则。

以上就是红黑树删除的全过程。

 640.png640.png

给定下面这颗红黑树,待删除的是结点17

 

640.png

 

第一步,由于结点17有两个孩子,子树当中仅大于17的结点是25,所以把结点25复制到17位置,保持黑色:

 640.png

 

接下来,我们需要删除原本的结点25

640.png


 

这个情况正好对应于第二步的情况三,即待删除结点是黑色,子结点是空叶子结点。

于是我们删除框框中结点25,进入第三步:

 

640.png

 

此时,框框中的结点虽然是空叶子结点,但仍然可以用于判断局面,当前局面符合子情况5的镜像:

640.png640.png

 

于是我们通过左旋和变色,把子树转换成情况6的镜像:

 640.png

再经过右旋、变色,子树最终成为了下面的样子:


 640.png640.png

这样一来,整颗二叉树又重新符合了红黑树的规则。

640.png640.png640.png640.png 

 


相关文章
|
6月前
|
关系型数据库 C++
【C++高阶(四)】红黑树深度剖析--手撕红黑树!
【C++高阶(四)】红黑树深度剖析--手撕红黑树!
|
存储 算法 程序员
C 非线性结构——树 万字详解(通俗易懂)
C 数据结构与算法入门——树 内容分享。
135 0
|
算法 关系型数据库 MySQL
手撕数据结构与算法——树(三指针描述一棵树)
手撕数据结构与算法——树(📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段,因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力>——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:king&南星 📖专栏链接:数据结构 🎉欢迎各位→点赞👏 + 收藏💞 + 留言🔔​ 💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🐾 ———————————————— 版权声明:本文为CSDN博主「热爱编程的小K」的原创文章,遵循CC 4.0 BY-S三指针描述一棵树)
整理得吐血了,二叉树、红黑树、B&B+树超齐全,快速搞定数据结构
没有必要过度关注本文中二叉树的增删改导致的结构改变,规则操作什么的了解一下就好,看不下去就跳过,本文过多的XX树操作图片纯粹是为了作为规则记录,该文章主要目的是增强下个人对各种常用XX树的设计及缘由的了解,也从中了解到常用的实现案例使用XX树实现的原因。
|
存储 机器学习/深度学习 算法
数据结构 | 有关树和二叉树的详解【内附考点精析】
树和二叉树的基本概念和性质,内附精致讲解图和推理过程
222 0
数据结构 | 有关树和二叉树的详解【内附考点精析】
|
存储 算法 安全
【高阶数据结构】手撕红黑树(超详细版本)
【高阶数据结构】手撕红黑树(超详细版本)
263 0
【高阶数据结构】手撕红黑树(超详细版本)
|
存储 算法 安全
数据结构与算法—一文多图搞懂双链表
前面讲过线性表中顺序表和链表的实现和性质。但是在数据结构与算法中,双向链表无论在考察还是运用中都占有很大的比例,笔者旨在通过本文与读者一起学习分享双链表相关知识。
136 0
数据结构与算法—一文多图搞懂双链表
|
算法
重温算法之二叉树中的列表
对于二叉树的题目很多就是涉及到遍历二叉树的,针对其一般使用的方法有枚举,深度优先搜索以及双向DFS,当然其难度系数就有点高了,遇到难得题目可以暂时跳过,不然一直解不出来也打击信心。
99 0
重温算法之二叉树中的列表
|
存储
还不知道层序遍历有多强?带你一口气打穿十道题(动图理解)(中)
还不知道层序遍历有多强?带你一口气打穿十道题(动图理解)
118 0
还不知道层序遍历有多强?带你一口气打穿十道题(动图理解)(中)
还不知道层序遍历有多强?带你一口气打穿十道题(动图理解)(上)
众所周知二叉树的遍历一般是前中后序遍历,但其实还有一种层序遍历。它是按照一层一层的顺序去遍历二叉树
176 0
还不知道层序遍历有多强?带你一口气打穿十道题(动图理解)(上)