文档章节

动态查找---->红黑树(Red-Black Tree)

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 725
阅读 1
收藏 0

红黑树 (Red-Black Tree)

 

红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(logn)时间内做查找,插入和删除,这里的n是树中元素的数目。包含n个内部节点的红黑树的高度是 O(log(n))。

一、性质

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

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

性质2. 根是黑色。

性质3. 所有叶子都是黑色(叶子是NIL节点)。

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

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

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

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

二、操作

因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的属性需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为 O(log n) 次。

2.1插入:

 

2.2删除:

 

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/04/06/5637104.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
私信 提问
常见数据结构(二)-树(二叉树,红黑树,B树)

常见数据结构(二)-树(二叉树,红黑树,B树) 标签: algorithms [TOC] 本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课...

brianway
2016/10/14
763
2
数据结构:红黑树的结构以及方法剖析 (上)

文章转载自:https://www.cnblogs.com/CarpenterLee/p/5503882.html,觉得作者写的非常好,特此转载此文章方便学习,如若侵权,立马删除! 本文以Java TreeMap为例,从源代码层面,结合详细的...

xue无止境
10/25
0
0
Red-Black Tree 的Java实现

Every node is either red or black. The root is black. Every leaf (NIL) is black. If a node is red, then both its children are black. For each node, all paths from the node to de......

Storm.X
2010/12/19
0
0
详解TreeMap的红黑树实现

红黑树 二叉查找树 二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找效率。 BST存在的主要...

那位先生
2016/12/16
33
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

没有更多内容

加载失败,请刷新页面

加载更多

Supervisor管理springboot应用

目录 概述 环境准备 spring boot应用 supervisor配置 启动应用 概述 前面博文介绍了Supervisor进程管理,实际应用可以对springboot应用进行管理,如果springboot应用挂掉,Supervisor还可以对它...

java_龙
7分钟前
1
0
将神经网络训练成一个“放大镜”

摘要: 想不想将神经网络训练成一个“放大镜”?我们就训练了一个这样炫酷的神经网络,点击文章一起看下吧! 低分辨率蝴蝶的放大 当我们网购时,我们肯定希望有一个贴近现实的购物体验,也就...

阿里云官方博客
7分钟前
0
0
在细节消息中包含能够捕获失败的信息(63)

程序由于未被捕获异常失败时,系统会自动打印该异常的堆栈轨迹 包含异常的字符串表示法(toString) 通常包含异常的类名,以及紧随其后的细节信息(detail message) 是检查程序失败的必须信...

Java搬砖工程师
8分钟前
0
0
day173-2018-12-10-英语流利阅读-待学习

如何评价特朗普在此次 G20 上的表现? 毛西 2018-12-10 1.今日导读 在公众眼里,特朗普一直是个不省事的主——他爱在推特吐槽,还喜欢到处树敌。但最近,阿根廷首都布宜诺斯艾利斯举行的 G2...

飞鱼说编程
10分钟前
1
0
adr adrl ldr mov简单科普

ADR是一条小范围的地址读取伪指令,它将基于PC的相对偏移的地址值读到目标寄存器中。格式:ADR register,exper。 编译源程序时,汇编器首先计算当前PC值(当前指令位置)到exper的距离,然后用...

天王盖地虎626
17分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部