文档章节

动态查找---->红黑树(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
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
读书笔记-红黑树

前言 大家好,头回写博客,欢迎批评,以后我会尽量做到一个月2更,最近在重新温故算法。今日提供读书笔记红黑树 目的 记录所学,温故知新 Java中对应的结构 TreeMap,以下是自己安装书中实现...

温安适
2016/11/27
812
0

没有更多内容

加载失败,请刷新页面

加载更多

java JDK动态代理

本篇随笔是对java动态代理中的JDK代理方式的具体实现。 首先需要定义一个接口,为其定义了两个方法:   public interface UserService { public void add(); public void delete(); } 然后需...

编程SHA
23分钟前
2
0
轻松理解Dubbo分布式服务框架

Dubbo是什么? Dubbo是一个分布式服务框架,致力于提供高性能和透明化的RPC远程服务调用方案,以及SOA服务治理方案。简单的说,dubbo就是个服务框架,如果没有分布式的需求,其实是不需要用的...

别打我会飞
31分钟前
2
0
TypeScript基础入门之JSX(一)

转发 TypeScript基础入门之JSX(一) 介绍 JSX是一种可嵌入的类似XML的语法。 它旨在转换为有效的JavaScript,尽管该转换的语义是特定于实现的。 JSX在React框架中越来越受欢迎,但此后也看到了...

durban
55分钟前
1
0
JavaScript使用原型判断对象类型

1. constructor属性 在JavaScript创建对象(二)——构造函数模式中,我们说过可以使用对象的constructor属性判断对象的类型:p1.constructor === Person,可能当时就有细心的读者会想,我们...

Bob2100
57分钟前
1
0
10-《深度拆解JVM》JVM是怎么实现invokedynamic的?(下)

一、问题引入 上回讲到,为了让所有的动物都能参加赛马,Java 7 引入了 invokedynamic 机制,允许调用任意类的“赛跑”方法。不过,我们并没有讲解 invokedynamic,而是深入地探讨了它所依赖...

飞鱼说编程
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部