文档章节

数据结构-红黑树详解

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 2754
阅读 7
收藏 1
点赞 0
评论 0

介绍:

红黑树(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
朝阳
程序员
Java8 HashMap详解

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

sihailoveyan ⋅ 02/27 ⋅ 0

当我们在聊TreeMap(一)——红黑树详解Java代码实现

本文出自:https://blog.csdn.net/DT235201314/article/details/80661157 一丶概述 上一篇讲HashMap,避开了红黑树,这边讲TreeMap,好好说一下红黑树。 二丶概述目录图 三丶聊聊TreeMap 数据...

天一方蓝 ⋅ 06/13 ⋅ 0

Skip List(跳跃表)原理详解

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

黎嘉诚 ⋅ 2016/12/16 ⋅ 1

如何将 Linux 内核实现的红黑树 rbtree 运用到你的 C 程序中?

相信大家都知道红黑树是什么吧,但是呢......如果你确实不知道,你不该穿越到这儿的,你应该去这里,这里,还有这里看看,然后再来这里看看,最后如果大爷您赏脸,再来看看我吧 :-) 废话少说...

大卷卷 ⋅ 2012/09/03 ⋅ 1

Boolan微专业:C++第八周学习笔记

学习笔记大纲 deque 本质是分段容器,用如下方式模拟出“连续”的假象。 deque的分段连续 stack和queue都是依赖deque实现,都不允许遍历元素,也不提供iterator。两者可以选择list和deque做底...

逗之煞 ⋅ 2017/12/09 ⋅ 0

ConcurrentHashMap 1.8 源码分析

前两已经分析过几篇关于CHM的源码,本篇分析下1.8中的实现,已经弃用之前 segment 双桶的机制。但是本质还是将锁细化达到性能的提升,但是不是之前版本中定义的segment 上锁,而是用了synch...

ovirtKg ⋅ 2016/10/28 ⋅ 0

今天的几点感悟

今天实在很无聊,一点也不想工作,我不知道我这个人在无聊的时候除了思考还能干些什么,不过想到快30了还没有一点作为就一身冷汗,说什么也没有用,除了继续思考之外没有任何退路。 突然想到...

晨曦之光 ⋅ 2012/04/10 ⋅ 0

Java集合--TreeMap完全解析

4 TreeMap 上一篇,介绍了集合框架中的HashMap对象,主要讲述了HashMap的底层实现和基本操作。本篇,让我们继续来学习Map集合,今天的主角是TreeMap。 相比于HashMap来说,TreeMap理解起来更...

贾博岩 ⋅ 2017/09/10 ⋅ 0

数据结构之红黑树C源码实现与剖析

前言 红黑树作为一种经典而高级的数据结构,相信已经被不少人实现过,但是因为程序不够完善而无法运行,就是因为程序完全没有注释,初学者根本就看不懂。——这句话相对赞 此份红黑树的C源码...

SibylY ⋅ 2013/07/31 ⋅ 1

java8中的HashMap的putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (......

清尘V ⋅ 2016/03/28 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

如何解决s权限位引发postfix及crontab异常

一、问题现象 业务反馈某台应用服务器,普通用户使用mutt程序发送邮件时,提示“postdrop warning: mail_queue_enter: create file maildrop/713410.6065: Permission denied”,而且普通用法...

问题终结者 ⋅ 18分钟前 ⋅ 0

Unable to load database on disk

由于磁盘空间满了以后,导致zookeeper异常退出,清理磁盘空间后,zk启动报错,信息如下: 2018-06-25 17:18:46,904 INFO org.apache.zookeeper.server.quorum.QuorumPeerConfig: Reading co...

刀锋 ⋅ 37分钟前 ⋅ 0

css3 box-sizing:border-box 实现div一行多列

<!DOCTYPE html><html><head><style> div.container{ background:green; padding:10px 10px;}div.box{box-sizing:border-box;-moz-box-sizing:border-box; /* Fir......

qimh ⋅ 42分钟前 ⋅ 0

Homebrew简介和基本使用

一、Homebrew是什么 Homebrew是一款Mac OS平台下的软件包管理工具,拥有安装、卸载、更新、查看、搜索等很多实用的功能。简单的一条指令,就可以实现包管理,而不用你关心各种依赖和文件路径...

说回答 ⋅ 49分钟前 ⋅ 0

文件压缩和打包zip、tar

第六章 文件压缩和打包 6.5 zip压缩工具 zip命令可以用来解压缩文件,或者对文件进行打包操作。zip是个使用广泛的压缩程序,文件经它压缩后会另外产生具有“.zip”扩展名的压缩文件。 注意:...

弓正 ⋅ 51分钟前 ⋅ 0

vuex

一、状态对象如何赋值给内部对象。三种方式: 1、使用computed赋值,一定要写this,不然找不到$store。 computed:{ count(){ return this.$store.state.count; }} 2、通...

大美琴 ⋅ 今天 ⋅ 0

javaScript 设计模式

1、构造函数模式 ` /** 构造一个动物的函数 */ function Animal(name, color){ this.name = name; this.color = color; this.getName = function(){ return this.name; } } // 实例一个对象 ......

fangPeng_ ⋅ 今天 ⋅ 0

日常嘚瑟:TeamCity构建中解压和打包tar

要弄一个新的构建,很简单,从两个构建的tar格式Artifact中分别取一部分,重新打一个tar。 所以,我去写个脚本用curl下载两个依赖的Artifact,然后解压移动重新打个tar? 开什么玩笑,我的技...

谷永权 ⋅ 今天 ⋅ 0

Istio官方文档中文版

阅读目录 Istio官方文档中文版 回到目录 Istio官方文档中文版 http://istio.doczh.cn/ https://istio.io/docs/concepts/what-is-istio/goals.html 为什么要使用Istio? 在从单体应用程序向分...

xiaomin0322 ⋅ 今天 ⋅ 0

CentOS 7 Omnibus 包安装 GitLab 并汉化记录

系统环境 操作系统:CentOS 7GitLab:gitlab-ce-10.8.4-ce.0.el7.x86_64.rpm 下载Omnibus安装包 使用国内镜像加速下载地址 # wget https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el......

admin_qing ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部