专栏首页每天学Java红黑树(二):删除操作

红黑树(二):删除操作

上一篇文章根据红黑树的定义实现了红黑树的插入操作,在节点插入操作过程中,我们默认插入节点为红,然后判断是否需要进行平衡操作,那么今天就来看一下红黑树的删除操作需要考虑哪些情况。

红黑树的删除操作比插入操作要更为复杂,因为需要考虑的因素比节点插入要多。

分析

对于一个节点的删除,我们可以从如下两个方面去考虑:

一.删除节点的颜色

二.删除节点的构造

颜色上,节点有红黑两种可能,那么删除黑节点就会造成节点失衡。

构造上,节点会有三种可能:其一是删除节点的孩子都为Nil,其二是删除节点的一个孩子节点为Nil,其三是删除节点的两个孩子节点都不为Nil。而如果两个节点都不为Nil,那么我们就需要找替代节点(后继结点)来替代删除,而删除替代结点就会是情况一和情况二。

后继结点的判断可以使用下图的方式,将节点Key落入X轴中(实质是中序排序)其后一个结点就是后继节点。那么我们看一下后继节点替代删除的方案,比如删除-1,那么可以将0替换到-1的位置,然后删除0,这样就回到情况一, 再比如删除4,那么使用5来代替,然后删除5,这样就回到了情况二。

那么现在我们正式开始分析删除操作会出现的可能情况。

删除操作

情况一.删除节点存在一个孩子,那么此时,不需要考虑节点的颜色,因为该节点必然为黑色 (因为如果结点为红色,那么两个孩子结点只会都为Nil,或者都为黑色,否则无法保证平衡, 也就无法满足任意节点到叶子结点经过相同的黑色节点),且孩子节点必然为红(如果为黑,那么D节点就会有一方黑色节点比另一方多一)。如下:

这种情况处理较为简单,只需要将节点P的指针指向DL或者DR,然后将DL或者DR的颜色变更为黑色, 就保证了红黑树的平衡,如下(以右孩子为例):

上述情况需要注意当D是根节点时,删除操作之后,孩子节点会成为新的根节点

情况二.删除节点不存在孩子,那么此时就需要考虑节点的颜色。

如果为红色,那么直接删除即可, 但是如果为黑色,那么需要考虑的因素如下几种。

情况2.1:我们考虑为红色这种最简单的情况,这种情况,P节点断掉指向节点D的指针指向就好了

情况2.2:然后我们考虑黑色,这种情况较为复杂,因为黑色节点被删除之后,红黑树会失去平衡,此时需要调整平衡。那么可能的情况有如下几种(如果D为根节点,删除操作后,红黑树变为空树即可,下面以非根节点的情况为例来分析)

情况2.2.1:父节点为红色,兄弟节点不存在孩子(兄弟节点必然存在,且为黑色)。此时情况稍微好处理,因为将父节点变为黑色,兄弟节点变为红色,即可 保证红黑树平衡

情况2.2.2:父节点为红色,兄弟节点存在孩子,此时无法向情况2.2.1那么处理,因为兄弟节点存在的孩子必然为红色,那么此时就需要进行旋转

情况2.2.3:父节点为黑色,那么此时删除节点D,无法通过修改父节点颜色来调整红黑树平衡,就需要 我们进行旋转操作,来调整平衡,那么此时共有如下几种可能(以删除结点在左侧为例):

1> 兄弟结点存在孩子结点

1.1> 左孩子存在(不为Nil),需要两次调整实现红黑树平衡

1.2> 左孩子为Nil,右孩子不为Nil,此时通过一次旋转即可平衡

2> 兄弟结点不存在孩子结点,此时无法通过旋转来实现平衡,即P节点无法继续调整,那么就D设置为 红色,保证P这个子树平衡,然后通过P节点,向上递归,然后就会回归到情况二, 即如果P的父结点为红色就是(情况二的第一种情况),如果为黑(情况二的第二种情况)。

到这里删除节点的操作就完成了,对于文章有疑问,可通过公众号回复加群来一起探讨。

完整源码查看:

红黑树源码

本文分享自微信公众号 - 每天学Java(gh_fddfb9d03324),作者:每天学Java

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日面试题推送及讲解-20190410

    第一题是对Hash表的考察,哈希表的特点:关键字和它在表中存储位置之间存在一种函数关系。这个函数我们称为为哈希函数。而键(key)经过hash函数得到的结果作为...

    每天学Java
  • 彻底搞懂ArrayList

    同样是空的数组对象,和EMPTY_ELEMENTDATA区别在于,无参构造函数的空数组会用DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值...

    每天学Java
  • Java设计模式(十)组合模式

    组合模式,就是在一个对象中包含其他对象,这些被包含的对象可能是终点对象(不再包含别的对象),也有可能是非终点对象(其内部还包含其他对象,或叫组对象),我们将对象...

    每天学Java
  • 一文搞定 Redis 复制(全会的举个手看看)

    Step 2:从节点只是保存了 slaveof 命令中主节点的信息,并没有立即发起复制。

    良月柒
  • 数据结构之二叉树解析

    可是,排序有快速排序,归并排序,查找有二分法,甚至直接遍历查找,我干啥要使用二叉树呢?

    Kevin_Zhang
  • Rafy 领域实体框架 - 树型实体功能(自关联表)

    在 Rafy 领域实体框架中,对自关联的实体结构做了特殊的处理,下面对这一功能进行讲解。 场景 在开发数据库应用程序时,往往会遇到自关联表的场景。例如,分类信息...

    用户1172223
  • GR运维手册 - 第一册 苦海岸边,GR的基础知识

    作者简介: ? 刘伟 云和恩墨开源解决方案事业部首席架构师 多年一线互联网企业DBA经历,对MySQL、NoSQL,PostgreSQL等各类开源数据库均有涉猎...

    数据和云
  • python学习之selenium的xpath轴的用法,附案例

    在 XPath 中,有七种类型的节点:元素、属性、文本、命名空间、处理指令、注释以及文档节点(或称为根节点)。

    吾爱乐享
  • 神经网络图的简介(基本概念,DeepWalk以及GraphSage算法)

    近来,图神经网络(GNN)在各个领域广受关注,比如社交网络,知识图谱,推荐系统以及生命科学。GNN在对图节点之间依赖关系进行建模的强大功能使得与图分析相关的研究...

    AI研习社
  • 算法面试能过几关:咱也不知道,咱也不敢问

    微信公众号“程序员小灰”的作者,具有多年软件行业从业经验,先后在京东金融、摩拜科技从事研发工作,对算法有一定的兴趣和经验。

    用户1682855

扫码关注云+社区

领取腾讯云代金券