文档章节

JDK TreeMap Red-Black Tree

zuoer
 zuoer
发布于 2011/12/18 16:19
字数 529
阅读 364
收藏 1

介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas  Robert Sedgewick改成一个比较摩登的名字:红黑树。

红黑树和之前所讲的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。不过在我了解了红黑树的实现原理后,并不相信这是真的,关于这一点我们会在后面进行讨论。

红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。之前我们在讲解AVL树时,已经领教过AVL树的复杂,但AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。

红黑树的平衡

红黑树首先是一棵二叉查找树,它每个结点都被标上了颜色(红色或黑色),红黑树满足以下5个性质:

1、 每个结点的颜色只能是红色或黑色。

2、 根结点是黑色的。

3、 每个叶子结点都带有两个空的黑色结点(被称为黑哨兵),如果一个结点n的只有一个左孩子,那么n的右孩子是一个黑哨兵;如果结点n只有一个右孩子,那么n的左孩子是一个黑哨兵。

4、 如果一个结点是红的,则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

5、 对于每个结点来说,从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

© 著作权归作者所有

zuoer
粉丝 21
博文 26
码字总数 22430
作品 0
嘉定
高级程序员
私信 提问
TreeMap实现原理

在用TreeMap之前我们要对TreeMap有个整体的认识。 1、TreeMap介绍 TreeMap是一个通过红黑树实现有序的key-value集合。 TreeMap继承AbstractMap,也即实现了Map,它是一个Map集合 TreeMap实现...

kukudeku
2016/08/24
3.9K
2
TreeMap实现原理

在用TreeMap之前我们要对TreeMap有个整体的认识。 1、TreeMap介绍 TreeMap是一个通过红黑树实现有序的key-value集合。 TreeMap继承AbstractMap,也即实现了Map,它是一个Map集合 TreeMap实现...

kukudeku
2016/08/24
169
0
HashMap和TreeMap

hashMap HashMap工作原理我对hashMap的认识基本是对的,hashCode() and equals() is important for hashMap. 除了这个完全不知道 当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两...

Finley.Hamilton
2014/12/04
230
0
Java Map 按key排序和按Value排序

Java Map 按key排序和按Value排序 一.理论准备 Map是键值对的集合接口,它的实现类主要包括:HashMap,TreeMap,Hashtable以及LinkedHashMap等。 TreeMap:基于红黑树(Red-Black tree)的 Na...

writeademo
2016/10/12
34
0
数据结构:红黑树的结构以及方法剖析 (上)

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

xue无止境
2018/10/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

c++运算符重载

这个运算符重载觉得有点像java的装箱 #ifndef INTERGER_H #define INTERGER_H //学习下运算符的重载 class Interger { public: Interger(); Interger(int value):m_value(value){}......

南桥北木
30分钟前
5
0
微信公众号如何推送文章

公众号推送消息格式,可以推送文本、图文消息、小程序、优惠券、会员卡、图片、视频、语音,不仅仅只能推送文章即图文消息,支持素材永久链接,表情符号等。 通过公众号接口可以开发各种各样...

保持美好
30分钟前
4
0
云桌面经常被吐槽,为什么还有很多人在用

说起云桌面我们会发现一个很奇怪的现象,那就是我们在网上经常能看到有人在吐槽云桌面的,说云桌面的性能差、价格贵和各种的不好用。虽然说网上有很多人都在吐槽云桌面,但是我们会发现使用它...

GZASD
37分钟前
5
0
支付宝20积分兑换15天会员

支付宝20积分兑换30天会员 活动地址:https://openact.ximalaya.com/alipay-vip/#/(或支付宝扫码打开)

xiaogg
40分钟前
6
0
DDoS攻击是怎么打垮游戏企业的?

1.占用服务器的有限资源。比如TCP连接数资源(服务器的连接数是有限制的),有的TCP连接会断开,有的会保持通信;比如一家餐馆,攻击者打比方是地痞流氓总是去排队,但是并不去消费,那么此时正...

云漫网络Ruan
41分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部