文档章节

数据结构-红黑树详解

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
朝阳
程序员
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
0
0
HashMap详解(一). put方法详解

JAVA8 1.HashMap.put 方法实现了Map.put(K key,V value)的方法。直接调用内部方法 大致思路是这样的: 对key的hashCode()进行hash后计算数组下标index; 如果当前数组table为null,进行resiz...

努力学的程序员
2017/11/02
0
0
详解 Java 8 HashMap 实现原理

HashMap 是 Java 开发过程中常用的工具类之一,也是面试过程中常问的内容,此篇文件通过作者自己的理解和网上众多资料对其进行一个解析。作者本地的 JDK 版本为 64 位的 1.8.0_171。参考资料...

☆★傲天★☆
2018/08/17
0
0
Java8 HashMap详解

Java8 HashMap Java8 对 HashMap 进行了一些修改,最大的不同就是利用了红黑树,所以其由 数组+链表+红黑树 组成。 根据 Java7 HashMap 的介绍,我们知道,查找的时候,根据 hash 值我们能够...

sihailoveyan
2018/02/27
0
0
Skip List(跳跃表)原理详解

为什么选择跳跃表 目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等。想象一下,给你一张草稿纸,一只笔,一个编辑器,你能立即实现一颗红黑树,或者AVL树出来吗? ...

黎嘉诚
2016/12/16
498
1

没有更多内容

加载失败,请刷新页面

加载更多

20个使用 Java CompletableFuture的例子

https://colobu.com/2018/03/12/20-Examples-of-Using-Java%E2%80%99s-CompletableFuture/

lemos
34分钟前
1
0
Apache 流框架 Flink,Spark Streaming,Storm对比分析

1.Flink架构及特性分析 Flink是个相当早的项目,开始于2008年,但只在最近才得到注意。Flink是原生的流处理系统,提供high level的API。Flink也提供 API来像Spark一样进行批处理,但两者处理...

hblt-j
38分钟前
1
0
什么是公网IP、内网IP和NAT转换?

搞网络通信应用开发的程序员,可能会经常听到外网IP(即互联网IP地址)和内网IP(即局域网IP地址),但他们的区别是什么? 1、引言 搞网络通信应用开发的程序员,可能会经常听到外网IP(即互联网I...

linuxprobe16
44分钟前
1
0
Spring Cloud搭建微服务架构----流量回放

前言 系统微服务化后,传统的自测/测试方式都变得比较困难: 依赖的服务可能不稳定。 服务无法提供期望的响应数据。 缺少场景构造标准。 随着整体业务越来越复杂,微服务依赖的越来越多,测试...

春哥大魔王的博客
今天
4
0
记一次springboot模块配置问题导致读取Apollo配置中心配置文件始终错误的问题

现在正在做的一个项目采用的是微服务,主框架是spring cloud,配置中心用的是携程的Apollo。 项目下有多个服务,在测试服务器上启动用户服务的时候发现在eureka中心另一个服务被启动了,尝试...

zcqshine
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部