文档章节

红黑树

ZooKeeper
 ZooKeeper
发布于 2013/12/31 12:20
字数 2758
阅读 67
收藏 0
点赞 0
评论 0

红黑树(RBT)的定义:它或者是一颗空树,或者是具有一下性质的二叉查找树:

1.节点非红即黑。

2.根节点是黑色。

3.所有NULL结点称为叶子节点,且认为颜色为黑

4.所有红节点的子节点都为黑色。

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

看完红黑树的定义是不是可晕?怎么这么多要求!!这怎么约束啊?我刚看到这5条约束,直接无语了,1-3、4还好说,第5点是怎么回事啊?怎么约束?整这么复杂的条件好干啥啊?我来简单说说呵:第3条,显然这里的叶子节点不是平常我们所说的叶子节点,如图标有NIL的为叶子节点,为什么不按常规出牌,因为按一般的叶子节点也行,但会使算法更复杂;第4条,即该树上决不允许存在两个连续的红节点;第5条,比如图中红8到1左边的叶子节点的路径包含2个黑节点,到6下的叶子节点的路径也包含2个黑节点。所有性质1-5合起来约束了该树的平衡性能--即该树上的最长路径不可能会大于2倍最短路径。为什么?因为第1条该树上的节点非红即黑,由于第4条该树上不允许存在两个连续的红节点,那么对于从一个节点到其叶子节点的一条最长的路径一定是红黑交错的,那么最短路径一定是纯黑色的节点;而又第5条从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点,这么来说最长路径上的黑节点的数目和最短路径上的黑节点的数目相等!而又第2条根结点为黑、第3条叶子节点是黑,那么可知:最长路径<=2*最短路径。一颗二叉树的平衡性能越好,那么它的效率越高!显然红黑树的平衡性能比AVL的略差些,但是经过大量试验证明,实际上红黑树的效率还是很不错了,仍能达到O(logN),这个我不知道,我现在不可能做过大量试验,只是听人家这样说,O(∩_∩)O哈哈~但你至少知道他的时间复杂度一定小于2O(logN)!

上边的性质看个10遍,看懂看透彻再看操作!

插入操作

由于性质的约束:插入点不能为黑节点,应插入红节点。因为你插入黑节点将破坏性质5,所以每次插入的点都是红结点,但是若他的父节点也为红,那岂不是破坏了性质4?对啊,所以要做一些“旋转”和一些节点的变色!另为叙述方便我们给要插入的节点标为N(红色),父节点为P,祖父节点为G,叔节点为U。下边将一一列出所有插入时遇到的情况:

情形1该树为空树,直接插入根结点的位置,违反性质1,把节点颜色有红改为黑即可

情形2插入节点N的父节点P为黑色,不违反任何性质,无需做任何修改

 情形1很简单,情形2中P为黑色,一切安然无事,但P为红就不一样了,下边是P为红的各种情况,也是真正要学的地方!

情形3N为红,P为红,(祖节点一定存在,且为黑,下边同理)U也为红,这里不论P是G的左孩子,还是右孩子;不论N是P的左孩子,还是右孩子

操作:如图把P、U改为黑色,G改为红色,未结束。

解析:N、P都为红,违反性质4;若把P改为黑,符合性质4,显然左边少了一个黑节点,违反性质5;所以我们把G,U都改为相反色,这样一来通过G的路径的黑节点数目没变,即符合4、5,但是G变红了,若G的父节点又是红的不就有违反了4,是这样,所以经过上边操作后未结束,需把G作为起始点,即把G看做一个插入的红节点继续向上检索----属于哪种情况,按那种情况操作~要么中间就结束,要么知道根结点(此时根结点变红,一根结点向上检索,那木有了,那就把他变为黑色吧)。

情形4:N为红,P为红,U为黑,P为G的左孩子,N为P的左孩子(或者P为G的右孩子,N为P的左孩子;反正就是同向的)。

操作:如图P、G变色,P、G变换即左左单旋(或者右右单旋),结束。

解析:要知道经过P、G变换(旋转),变换后P的位置就是当年G的位置,所以红P变为黑,而黑G变为红都是为了不违反性质5,而维持到达叶节点所包含的黑节点的数目不变!还可以理解为:也就是相当于(只是相当于,并不是实事,只是为了更好理解;)把红N头上的红节点移到对面黑U的头上;这样即符合了性质4也不违反性质5,这样就结束了。

 

情形5:N为红,P为红,U为黑,P为G的左孩子,N为P的右孩子(或者P为G的右孩子,N为P的左孩子;反正两方向相反)。

 

操作:需要进行两次变换(旋转),图中只显示了一次变换-----首先P、N变换,颜色不变;然后就变成了情形4的情况,按照情况4操作,即结束。

解析:由于P、N都为红,经变换,不违反性质5;然后就变成4的情形,此时G与G现在的左孩子变色,并变换,结束。

 

 

删除操作

我们知道删除需先找到“替代点”来替代删除点而被删除,也就是删除的是替代点,而替代点N的至少有一个子节点为NULL,那么,若N为红色,则两个子节点一定都为NULL(必须地),那么直接把N删了,不违反任何性质,ok,结束了;若N为黑色,另一个节点M不为NULL,则另一个节点M一定是红色的,且M的子节点都为NULL(按性质来的,不明白,自己分析一下)那么把N删掉,M占到N的位置,并改为黑色,不违反任何性质,ok,结束了;若N为黑色,另一个节点也为NULL,则把N删掉,该位置置为NULL,显然这个黑节点被删除了,破坏了性质5,那么要以N节点为起始点检索看看属于那种情况,并作相应的操作,另还需说明N为黑点(也许是NULL,也许不是,都一样),P为父节点,S为兄弟节点(这个我真想给兄弟节点叫B(brother)多好啊,不过人家图就是S我也不能改,在重画图,太浪费时间了!S也行呵呵,就当是sister也行,哈哈)分为以下5中情况:

情形1S为红色(那么父节点P一定是黑,子节点一定是黑),N是P的左孩子(或者N是P的右孩子)。

操作:P、S变色,并交换----相当于AVL中的右右中旋转即以P为中心S向左旋(或者是AVL中的左左中的旋转),未结束。

解析:我们知道P的左边少了一个黑节点,这样操作相当于在N头上又加了一个红节点----不违反任何性质,但是到通过N的路径仍少了一个黑节点,需要再把对N进行一次检索,并作相应的操作才可以平衡(暂且不管往下看)。

 

 

情形2:P、S及S的孩子们都为黑。

操作:S改为红色,未结束。
解析:S变为红色后经过S节点的路径的黑节点数目也减少了1,那个从P出发到其叶子节点到所有路径所包含的黑节点数目(记为num)相等了。但是这个num比之前少了1,因为左右子树中的黑节点数目都减少了!一般地,P是他父节点G的一个孩子,那么由G到其叶子节点的黑节点数目就不相等了,所以说没有结束,需把P当做新的起始点开始向上检索。

 

情形3:P为红(S一定为黑),S的孩子们都为黑。

 

操作:P该为黑,S改为红,结束。

解析:这种情况最简单了,既然N这边少了一个黑节点,那么S这边就拿出了一个黑节点来共享一下,这样一来,S这边没少一个黑节点,而N这边便多了一个黑节点,这样就恢复了平衡,多么美好的事情哈!

 

 

情形4:P任意色,S为黑,N是P的左孩子,S的右孩子SR为红,S的左孩子任意(或者是N是P的右孩子,S的左孩子为红,S的右孩子任意)。


操作:SR(SL)改为黑,P改为黑,S改为P的颜色,P、S变换--这里相对应于AVL中的右右中的旋转(或者是AVL中的左左旋转),结束。
解析:P、S旋转有变色,等于给N这边加了一个黑节点,P位置(是位置而不是P)的颜色不变,S这边少了一个黑节点;SR有红变黑,S这边又增加了一个黑节点;这样一来又恢复了平衡,结束。

 

 

情形5:P任意色,S为黑,N是P的左孩子,S的左孩子SL为红,S的右孩子SR为黑(或者N是P的有孩子,S的右孩子为红,S的左孩子为黑)。

 

操作:SL(或SR)改为黑,S改为红,SL(SR)、S变换;此时就回到了情形4,SL(SR)变成了黑S,S变成了红SR(SL),做情形4的操作即可,这两次变换,其实就是对应AVL的右左的两次旋转(或者是AVL的左右的两次旋转)。
解析:这种情况如果你按情形4的操作的话,由于SR本来就是黑色,你无法弥补由于P、S的变换(旋转)给S这边造成的损失!所以我没先对S、SL进行变换之后就变为情形4的情况了,何乐而不为呢?

 

本文转载自:http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

共有 人打赏支持
ZooKeeper
粉丝 52
博文 28
码字总数 13920
作品 0
杭州
程序员
JAVA中的数据结构 - 真正的去理解红黑树

一, 红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储 红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树 二叉树-->搜索二叉树-...

浮躁的码农
2015/06/23
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
0
0
《算法导论》学习笔记之Chapter13红黑树

第13章 红黑树 红黑树是一种平衡搜索树中的一种,他可以保证在最坏情况下基本动态集合操作时间复杂度为O(logn)。所以,在学习红黑树之前,我需要先去调研一下平衡树; 先看一下平衡树的定义:...

u010483897
2017/12/13
0
0
java集合框架(四):TreeMap

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

chenzanjin
2017/11/07
0
1
数据结构之红黑树C源码实现与剖析

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

SibylY
2013/07/31
0
1
图解红黑树

红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。在了解红黑树之前我们需要简述一下二叉查找树。 BST 二叉查找树,...

卡巴拉的树
2017/11/09
0
0
红黑树的原理和常见操作

1. 概述 在jdk1.8中,HashMap和ConcurrentHashMap中都采用了红黑树这一数据结构。即当链表达到一定的长度后,就把链表转化成红黑树。这其中主要利用了红黑树的良好性质,不管你节点怎样,他始...

maskwang520
01/13
0
0
【死磕Java并发】-----J.U.C之ConcurrentHashMap红黑树转换分析

原文出处http://cmsblogs.com/ 『chenssy』 在【死磕Java并发】—–J.U.C之Java并发容器:ConcurrentHashMap一文中详细阐述了ConcurrentHashMap的实现过程,其中有提到在put操作时,如果发现...

chenssy
2017/06/26
0
0
【死磕Java并发】—–J.U.C之ConcurrentHashMap红黑树转换分析

原文出处http://cmsblogs.com/ 『chenssy』 在【死磕Java并发】—–J.U.C之Java并发容器:ConcurrentHashMap一文中详细阐述了ConcurrentHashMap的实现过程,其中有提到在put操作时,如果发现...

chenssy
2017/06/26
0
0
红黑树 (附 STL 源码学习注释)

除了 AVL 树之外,另一个颇具历史并被广泛运用的平衡二叉搜索树是红黑树。同 AVL 树一样,红黑树的高度也近似为 O(logN),它是通过给节点标记上两种不同的颜色 (红、黑) 来实现此目的的。 模...

jelly_9
2017/11/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Android 复制和粘贴功能

做了一回搬运工,原文地址:https://blog.csdn.net/kennethyo/article/details/76602765 Android 复制和粘贴功能,需要调用系统服务ClipboardManager来实现。 ClipboardManager mClipboardM...

她叫我小渝
今天
0
0
拦截SQLSERVER的SSL加密通道替换传输过程中的用户名密码实现运维审计(一)

工作准备 •一台SQLSERVER 2005/SQLSERVER 2008服务 •SQLSERVER jdbc驱动程序 •Java开发环境eclipse + jdk1.8 •java反编译工具JD-Core 反编译JDBC分析SQLSERVER客户端与服务器通信原理 SQ...

紅顏為君笑
今天
6
0
jQuery零基础入门——(六)修改DOM结构

《jQuery零基础入门》系列博文是在廖雪峰老师的博文基础上,可能补充了个人的理解和日常遇到的点,用我的理解表述出来,主干出处来自廖雪峰老师的技术分享。 在《零基础入门JavaScript》的时...

JandenMa
今天
0
0
linux mint 1.9 qq 安装

转: https://www.jianshu.com/p/cdc3d03c144d 1. 下载 qq 轻聊版,可在百度搜索后下载 QQ7.9Light.exe 2. 去wine的官网(https://wiki.winehq.org/Ubuntu) 安装 wine . 提醒网页可以切换成中...

Canaan_
今天
0
0
PHP后台运行命令并管理运行程序

php后台运行命令并管理后台运行程序 class ProcessModel{ private $pid; private $command; private $resultToFile = ''; public function __construct($cl=false){......

colin_86
今天
1
0
数据结构与算法4

在此程序中,HighArray类中的find()方法用数据项的值作为参数传递,它的返回值决定是否找到此数据项。 insert()方法向数组下一个空位置放置一个新的数据项。一个名为nElems的字段跟踪记录着...

沉迷于编程的小菜菜
今天
1
1
fiddler安装和基本使用以及代理设置

项目需求 由于开发过程中客户端和服务器数据交互非常频繁,有时候服务端需要知道客户端调用接口传了哪些参数过来,这个时候就需要一个工具可以监听这些接口请求参数,已经接口的响应的数据,这种...

银装素裹
今天
0
0
Python分析《我不是药神》豆瓣评论

读取 Mongo 中的短评数据,进行中文分词 对分词结果取 Top50 生成词云 生成词云效果 看来网上关于 我不是药神 vs 达拉斯 的争论很热啊。关于词频统计就这些,代码中也会完成一些其它的分析任...

猫咪编程
今天
0
0
虚拟机怎么安装vmware tools

https://blog.csdn.net/tjcwt2011/article/details/72638977

AndyZhouX
昨天
1
0
There is no session with id[xxx]

参考网页 https://blog.csdn.net/caimengyuan/article/details/52526765 报错 2018-07-19 23:04:35,330 [http-nio-1008-exec-8] DEBUG [org.apache.shiro.web.servlet.SimpleCookie] - Found......

karma123
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部