文档章节

数据结构-红黑树详解

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 2754
阅读 7
收藏 1

「深度学习福利」大神带你进阶工程师,立即查看>>>

介绍:

红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。

它是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。

它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

用途:

它的统计性能要好于平衡二叉树,红黑树在很多地方都有应用。java中的TreeSet和TreeMap数据结构。在C++ STL中,很多部分(包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。其他平衡树还有:AVL,SBT,伸展树,TREAP 等等。

性质:

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3 每个叶节点(NIL节点,空节点)是黑色的。

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

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

总结:

这些约束强制了红黑树的关键性质:

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

要知道为什么这些特性确保了这个结果

,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

一颗二叉树:

这里写图片描述

图解二叉树的操作:

1.左旋

这里写图片描述

2.右旋:

这里写图片描述

插入操作:

在对红黑树进行插入操作时,我们一般总是插入红色的节点,因为这样可以在插入过程中尽量避免对树的调整。 那么,我们插入一个节点后,可能会使原树的哪些性质改变列? 由于,我们是按照二叉树的方式进行插入,因此元素的搜索性质不会改变。

如果插入的节点是根节点,性质2会被破坏,如果插入节点的父节点是红色,则会破坏性质4。 因此,总而言之,插入一个红色节点只会破坏性质2或性质4。 我们的恢复策略很简单,

1.把出现违背红黑树性质的节点向上移,如果能移到根节点,那么很容易就能通过直接修改根节点来恢复红黑树的性质。直接通过修改根节点来恢复红黑树应满足的性质。

2.穷举所有的可能性,之后把能归于同一类方法处理的归为同一类,不能直接处理的化归到下面的几种情况

插入修复具体操作情况:

1) 情况1:插入的是根节点。

原树是空树,此情况只会违反性质2。

对策:直接把此节点涂为黑色。

2) 情况2:插入的节点的父节点是黑色。

此不会违反性质2和性质4,红黑树没有被破坏。

对策:什么也不做。

3) 情况3:当前节点的父节点是红色且祖父节点的另一个子节点(叔叔节点)是红色。

此时父节点的父节点一定存在,否则插入前就已不是红黑树。与此同时,又分为父节点是祖父节点的左子还是右子,对于对称性,我们只要解开一个方向就可以了。 在此,我们只考虑父节点为祖父左子的情况。 同时,还可以分为当前节点是其父节点的左子还是右子,但是处理方式是一样的。我们将此归为同一类。

对策:将当前节点的父节点和叔叔节点涂黑,祖父节点涂红,把当前节点指向祖父节点,从新的当前节点重新开始算法。

针对情况3,变化前[当前节点为4节点]:
这里写图片描述

变化后:

这里写图片描述

4) 情况4:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子

对策:当前节点的父节点做为新的当前节点,以新当前节点为支点左旋。

如下图所示,变化前[当前节点为7节点]:
这里写图片描述

变化后:

这里写图片描述

5) 情况5:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的左子

解法:父节点变为黑色,祖父节点变为红色,在祖父节点为支点右旋

如下图所示[当前节点为2节点]
这里写图片描述

变化后:

这里写图片描述

总结:

经过上面情况3、情况4、情况5等3种插入修复情况的操作示意图,读者自会发现,后面的情况4、情况5都是针对情况3插入节点4以后,进行的一系列插入修复情况操作,不过,指向当前节点N指针一直在变化。所以,你可以想当然的认为:整个下来,情况3、4、5就是一个完整的插入修复情况的操作流程。

删除操作:

普通的搜索树删除操作

1.没有儿子,即为叶节点。直接把父节点的对应儿子指针设为NULL,删除儿子节点就OK了。

2.有一个儿子。那么把父节点的相应儿子指针指向儿子的独生子,删除儿子节点也OK了。

3.有两个儿子。这是最麻烦的情况,因为你删除节点之后,还要保证满足搜索二叉树的结构。其实也比较容易,我们可以选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置,就可以保证结构的不变。当然,你要记得调整子树,毕竟又出现了节点删除。习惯上大家选择左儿子中的最大元素,其实选择右儿子的最小元素也一样,没有任何差别,只是人们习惯从左向右。这里咱们也选择左儿子的最大元素,将它放到待删节点的位置。左儿子的最大元素其实很好找,只要顺着左儿子不断的去搜索右子树就可以了,直到找到一个没有右子树的节点。那就是最大的了。

红黑树的删除:

上面的修复情况看起来有些复杂,下面我们用一个分析技巧:我们从被删节点后来顶替它的那个节点开始调整,并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢,我们不是把红黑树的节点加上除红与黑的另一种颜色,这里只是一种假设,我们认为我们当前指向它,因此空有额外一种黑色,可以认为它的黑色是从它的父节点被删除后继承给它的,它现在可以容纳两种颜色,如果它原来是红色,那么现在是红+黑,如果原来是黑色,那么它现在的颜色是黑+黑。有了这重额外的黑色,原红黑树性质5就能保持不变。现在只要花时是恢复其它性质就可以了,做法还是尽量向根移动和穷举所有可能性。

注:以下的情况3、4、5、6,与上述算法导论之代码RB-DELETE-FIXUP(T, x) 恢复与保持 中case1,case2,case3,case4相对应。

情况1:当前节点是红+黑色

解法,直接把当前节点染成黑色,结束。此时红黑树性质全部恢复。

情况2:当前节点是黑+黑且是根节点

解法:什么都不做,结束

情况3:当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。

解法:把父节点染成红色,把兄弟节点染成黑色,之后重新进入算法(我们只讨论当前节点是其父节点左孩子时的情况)。此变换后原红黑树性质5不变,而把问题转化为兄弟节点为黑色的情况(注:变化前,原本就未违反性质5,只是为了把问题转化为兄弟节点为黑色的情况)。

情况4:当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色。

解法:把当前节点和兄弟节点中抽取一重黑色追加到父节点上,把父节点当成新的当前节点,重新进入算法。(此变换后性质5不变)

情况5:当前节点颜色是黑+黑,兄弟节点是黑色,兄弟的左子是红色,右子是黑色。。

解法:把兄弟节点染红,兄弟左子节点染黑,之后再在兄弟节点为支点解右旋,之后重新进入算法。此是把当前的情况转化为情况6,而性质5得以保持。

解法:把兄弟节点染成当前节点父节点的颜色,把当前节点父节点染成黑色,兄弟节点右子染成黑色,之后以当前节点的父节点为支点进行左旋,此时算法结束,红黑树所有性质调整正确。

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述
参考:
http://baike.baidu.com/view/133754.htm
https://segmentfault.com/a/1190000000472153

fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
加载中
请先登录后再评论。
beego API开发以及自动化文档

beego API开发以及自动化文档 beego1.3版本已经在上个星期发布了,但是还是有很多人不了解如何来进行开发,也是在一步一步的测试中开发,期间QQ群里面很多人都问我如何开发,我的业余时间实在...

astaxie
2014/06/25
2.7W
22
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
C++模板库--C++ B-tree

这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

匿名
2013/02/05
3.4K
1
开源数据访问组件--Smark.Data

Smark.Data是基于Ado.net实现的数据访问组件,提供基于强类型的查询表达式进行灵活的数据查询,统计,修改和删除等操作;采用基于条件驱动的操作模式,使数据操作更简单轻松;内部通过标准SQL...

泥水佬
2013/03/12
2.6K
0
数据中心生命周期管理--Foreman

Foreman是一个集成的数据中心生命周期管理工具,提供了服务开通,配置管理以及报告 功能,和Puppet Dahboard一样,Foreman也是一个Ruby on Rails程序.Foreman和 Dashboard不同的地方是在于,Fore...

匿名
2012/10/24
1.5W
0

没有更多内容

加载失败,请刷新页面

加载更多

Java圈里,什么样的人,会越来越穷?

“我不想做 Java 了,想去做大数据!但我一个双非本科,能行么?“ 我还挺费解,为什么疫情之后,很多粉丝都想去做大数据, 但仔细想想原因太简单。 因为做大数据值钱、岗位还多。(是的,成...

倪升武
今天
2
0
Java 8 - Stream 集合操作快速上手

点击上方Java学习指南关注公众号 每天阅读Java干货文章 链接:www.jianshu.com/p/9fe8632d0bc2 目录 Stream 简介 为什么要使用 Stream 实例数据源 Filter Map FlatMap Reduce Collect Option...

xqnode
前天
19
0
工作流引擎的工作原理与功能

协同工作流引擎(Synchro flow)基于企业流程自动化基础的平台的产品同时也是企业流程再造的核心产品,并且提供以业务建模、流程设计、流程仿真、界面设计、业务整合、部署执行、系统管理、业...

osc_3nr0mda4
58分钟前
0
0
第三本 PDF !!!程序员必知核心基础知识

我们可以感觉出来,计算机专业的门槛正在逐渐增高,人与人之间的差距在逐渐拉大,今天和 一位阿里的大龄程序员聊天后发现,他也觉得自己底层知识很薄弱,正在找时间恶补,也在感叹时间管理的...

osc_htns3spg
59分钟前
9
0
【CSS】679- rem,em,px的区别和使用场景

作者:大前端小菜鸟 来源: cnblogs.com/hyns/p/12380944.html 作rem布局原理深度理解(以及em/vw/vh) 一、前言 我们h5项目终端适配采用的是淘宝那套《Flexible实现手淘H5页面的终端适配》方...

前端自习课
前天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部