文档章节

二叉树之红黑树的原理(一) 删除

y
 yky20190625
发布于 07/22 11:54
字数 2926
阅读 7
收藏 0

红黑树是一种特殊的排序二叉树,在满足排序二叉树的条件之后,还要满足以下几个特点:

红黑树:      1 根结点是黑色.
                2 叶节点都是Nil结点,且为黑色  
                3  父子节点不能同时为红色 
                4 从任意结点出发,到其每个叶结点的路径上都包含相同的黑结点数目. 
其中, 3,4 两个特点是关键.

红黑树的删除操作

 

1:节点命名约定

    D表示要被删除的节点。即:取 Delete 的首字母;

    P 表示父节点。即:取 Parent 的首字母;

    S表示兄弟姐妹节点。即:取 Sibling的首字母; SL表示兄弟节点的左子树,即:左子节点;

    G表示祖父节点。即:取 Grandfather的首字母;

    L表示左树。即:取Left的首字母;
    R表示右树。即:取Right的首字母;
    DR表示要被删除的节点的右子树,即:右子节点;  以此类推.

    Nil表示叶子节点。即所谓的空节点;注意:红黑树中的叶子节点与其他树中所述说的叶子节点不是同一概念。而且红黑树中的叶子节点(即:Nil节点)永远是被定义为黑色的。

2:删除操作宏观分析

    在红黑树中,被删除的结点,  只有以下四种情况。

    情况一:删除的节点的左、右子树都非空;

    情况二:删除的节点的左子树为空树,右子树非空;

    情况三:删除的节点的右子树为空树,左子树非空;

    情况四:删除的节点的左、右子树都为空树;

    其中情况一,可以按与普通二叉搜索树的删除方式一样处理。具体方法为:找到D节点的直接后继节点(暂且称为X节点),然后将X的值转移到D节点,最后将X节点作为真正要被删除掉的节点。
    查找直接后继点X的方法是: 从D结点转向右,再左转,一直向左前进, 直到左分支的尽头即是X点,  因此 X点是没有左子树的, 与情况二或情况四形同

    我们得到一条非常重要的结论:  红黑树中真正要删除的结点,要么只有单子树,要么是个无子树的单结点.

    

3:红黑树删除后平衡处理

      下面是几个图示说明:

    根据红黑树的定义,被删除的节点D(即:上文所述的(Real)D节点)不论如何都一定有一个“右子树”,只是该右子树要不为非空树(即:真正存在的节点,不为Nil节点),要不就必为空树(即:D的两个子节点都为Nil)。下面称D的该右子节点(或称为右子树)为DR。

    a)       被删除的D节点为红色。这种情况,则与D相关的颜色以及结构关系必然只有如下一种情况(为什么只有这种情况,不明白的请看红黑树的性质):

    分析:因为D为红色,所以P必为黑色,同时DR不可能为红色(否则违反性质4)。同时由于性质5,则DR必为Nil,否则就D树来说,经过DR与不经过DR的路径的黑节点数必不相同。现在要删除D节点,只需要直接将D节点删除,并将DR作为P的左子节点即可。因此删除后,变成上图右侧所示。

 

    b)       被删除的D节点为黑色。此时情况会稍复杂些,具体又分析为:DR为Nil与DR不为Nil。根据性质5,如果DR不为Nil,则DR必为红色,且DR的两个子节点必为Nil。因此,此处先来分析DR不为Nil的情况(因为该情况比较简单)。而DR为Nil的情况,由后面的C)及其后内容再进行具体分析 。

如前所述,如果DR不为Nil,则D、DR必为如下情况:

    分析:由于删除的D为黑色,删除后P的左子树的黑节点数必少1,此时刚好DR为黑色,并且删除后DR可以占据D的位置(这样仍是一棵二叉搜索树,只是暂时还不是合格的红黑树罢了),然后再将DR的颜色改为黑色,刚好可以填补P左子树所减少的黑节点数。从而P树又平衡了。因此,平衡处理后,最终变成上图右侧的图示。

    c)       被删除的D为黑色,且DR为Nil

如果DR为Nil,则删除D后,P的左子树黑节点数必定少1,纯粹想在P的左子树做文章来平衡P树是绝无可能的了。因此,必定需要其他分支的辅助来最终完成平衡调整。根据红黑树的定义,P会有一个右子节点,称为S子节点。此处又可细节分两种情况:黑S与红S。此处先讨论红S的情况。

    说明:如果S为黑,则它必不会为Nil。(不明白的人,再好好想想为什么)。同时根据红黑树的性质,D、S、P、SL、SL的颜色关系必只有如下一种情况(因为此处探讨的是S为红的情况)。

    分析:删除前P树的左、右子树的黑节点数平衡,删除后(即:上图右侧所示),经过DR分支的黑节点数将比通过S分支的黑节点数少1。此时,做如下操作:

    将P左旋转,再将P由黑色改为红色,将S由红色改为黑色,演变过程如下图示:

    经过以上演变后,经过P的路径,左分支黑节点数仍是少1,其他分支的黑节点数做仍然保持不变。此时的情况却变成DR的兄弟节点为黑色(不再是红色的情况了),因此转入此处c)点一开始所说的另一种情况(S为黑色的情况)的处理。

    注意:可能有人会一时想不明白什么要这样转换。因为这样转换后,虽然对于P树的左子树的黑节点数仍然会比右子树的黑节点数少1,但此时DR的兄弟(以前的S节点)现在已经变为SL,即已经由红色变为黑色,并且非常重要的此时的DR的兄弟节点SL的子结点(即:DR的两个侄子节点),要不就是红色节点要不就必为Nil节点,而这种情况正是D为黑色、S也黑色的情况。(注意看注意看注意看一定注意看这点:对于被删除节点D的父节点来说,D黑S黑的情况下,无论如何D的兄弟节点S的两个儿子节点SL与SR都不可能是非Nil的黑节点。不明白的好好想想为什么)。因此我们有了进一步分析的余地。

    d)       被删除的D为黑色,S也为黑色的情况。根据D、P、S、SL、SR的颜色组合情况,本来是有非常多种变换的。但事实上,我们只需要按如下4种情况做进一步的处理,即可全部涵盖所有的颜色组合情况。

    d.1> SL为红,SR颜色任意;(对于该情况的处理,其实我们不关心P的颜色)

    d.2> SR为红,SL颜色任意;(对于该情况的处理,其实我们不关心P的颜色)

    d.3> SL、SR都为黑;P为红。(注意:根据前面c)点的红色文字部分的分析,此时SL与SR必定必定都为Nil节点);

    d.4> SL、SR都为黑;P为黑。(注意:根据前面c)点的红色文字部分的分析,此时SL与SR必定必定都为Nil节点);

 

    d.1> SL为红,SR颜色任意情况

    分析:P树的左子树黑节点数减少1,因此,要想平衡,必需想办法让左子树的黑结节数增加1,而且同时P的右子树的黑节点数要保持不变。因此,想办法将SL这个红色节点利用起来,让它来填补P的左子树所缺少的黑节点个数。因此,立马想到旋转,只要有办法转到P的左子树或P位置上,则就有可能填平P左子树的高度。所以具体操作步骤为:

    将S右旋转;接着将SL改为P的颜色,P的颜色改为黑色(用这个黑色来填补DR分支的黑节点数);将P左旋转。

 

    d.2> SR为红色,SL颜色任意的情况

    分析:思路同d.1>情况类似,都是想办法用红色的SR节点来填补P的左子树的减少的黑节点数。具体步骤为:

    将S由黑色改为P的颜色;

    将SR由红色改为黑色;

    将P的颜色改为黑色(用该黑色来填补DR分支缺失的黑节点数);

    将P节点左旋转;

 

    d.3> SL、SR都为黑色(其实都为Nil节点),P为红色的情况

    分析:此情况较为简单,直接将红色的P改为黑色,以此为填补DR缺少的黑节点个数。此时P右子树黑节点数却增多,因此,再将S改为红色即可平衡。

 

    d.4> SL、SR都为黑色(其实都为Nil节点),P为黑色的情况

    分析:因为DR、P、S、SL、SR全都为黑色,则不论如何变换,都永远不可能使用P的左右子树的黑节点数达到平衡。而P不平衡的原因是因为P的右子树黑节点数会比左子树多1个。因此,干脆将S由黑色改为红色,如此一来,P的左、右子树的黑节点个数是平衡的。但是,此时经过P的路径的黑节点个数将会比不经过它的路径少一个。因此,我们将P作为待平衡的节点(即:此时的P相当于DR的角色)往上继续上溯,直到P为根节点为止。

 

    到此,红黑树的删除操作已全部说明完。从以上的分析来看,红黑树的删除操作将是最为费时的,至少会比插入操作复杂,更耗时的可能性肯定会更大。但事实上,红黑树的插入、删除、效率都是非常高的。插入比较简单就不说了。删除操作事实上,就算遇到最坏情况:DR、P、S、SL、SR全为黑的情况下,在上溯过程中,一般情况下也是会很快就遇到红色的P节点的。除非整棵红黑树的右子树基本上都是黑节点(试想下,这可能性几乎不可能,因为我们插入时,总是以红色插入的,再加上红黑树的几条性质约束一下),或者本来身红黑树的整体高度就非常浅。

© 著作权归作者所有

y
粉丝 0
博文 10
码字总数 13524
作品 0
荆州
私信 提问
关于红黑树(R-B tree)原理,看这篇如何

学过数据数据结构都知道二叉树的概念,而又有多种比较常见的二叉树类型,比如完全二叉树、满二叉树、二叉搜索树、均衡二叉树、完美二叉树等;今天我们要说的红黑树就是就是一颗非严格均衡的二...

工匠初心
07/17
0
0
树型结构之红黑树

一.红黑树的介绍 红黑树是一种自平衡二叉树,红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作...

大覇
2016/03/28
173
0
java集合框架(四):TreeMap

TreeMap的数据结构与HashMap、LinkedHashMap不同,其整个结构就是一颗红黑树,所以我们要研究TreeMap就得先从红黑树开始。对于红黑树的算法,我在本文章不详细展开,有兴趣的同学可以点击这里...

chenzanjin
2017/11/07
56
1
Java关于数据结构的实现:树

关于作者 郭孝星,程序员,吉他手,主要从事Android平台基础架构方面的工作,欢迎交流技术方面的问题,可以去我的Github提issue或者发邮件至guoxiaoxingse@163.com与我交流。 文章目录` 一 ...

郭孝星
2017/09/28
0
0
JDK TreeMap Red-Black Tree

介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和 Robert Sedgewi...

zuoer
2011/12/18
362
0

没有更多内容

加载失败,请刷新页面

加载更多

rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
5
0
简述TCP的流量控制与拥塞控制

1. TCP流量控制 流量控制就是让发送方的发送速率不要太快,要让接收方来的及接收。 原理是通过确认报文中窗口字段来控制发送方的发送速率,发送方的发送窗口大小不能超过接收方给出窗口大小。...

鏡花水月
今天
10
0
OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
1K
11
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部