开发者社区> 大数据> 正文

红黑树基本概念

简介: 红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。

红黑树基本概念

【维基百科】 红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。

它是在1972年由鲁道夫·贝尔发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。

它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n是树中元素的数目。

红黑树放松了对平衡的限制。可以不再是严格意义上的平衡二叉树。

【解释】:红黑树属于平衡二叉树。说它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1。但红黑树高度依然是平均log(n),且最坏情况高度不会超过2log(n),这有数学证明。所以它算平衡树,只是不严格。不过严格与否并不影响数据结构的复杂度。红黑树多用于系统底层。

红黑树与AVL树的相同点与区别?

【解读】:红黑树和之前所讲的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。

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

红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。前面说了,红黑树,是一种二叉查找树,既然是二叉查找树,那么它必满足二叉查找树的一般性质。

红黑树是通过节点分为红、黑两种颜色并根据一定的规则确保在一定程度上是平衡的,从而保证在红黑树中查找、删除、插入操作都只需要O(logk)的时间。

在STL中set和multiset都是基于红黑树实现的。

红黑树的性质:

1)  红黑树节点要么是红节点、要么是黑节点;

2)  根节点为黑节点;

3)  叶节点(空节点)为黑节点;

4)  每个红节点的两个子节点是黑节点;

5)  对于每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑节点。

红黑树的时间复杂度:

1.在一棵二叉查找树上,执行查找、插入、删除等操作的最好情况时间复杂度为O(lgn)。 因为,一棵由n个结点,随机构造的二叉查找树的高度为lgn,所以顺理成章,一般操作的执行时间为O(lgn)。

2.但若是一棵具有n个结点的线性链,则此些操作最坏情况运行时间为O(n)。

而红黑树,能保证在最坏情况下,基本的动态几何操作的时间均为O(lgn)。

 

dog 二分查找树(类似二分查找) 二叉平衡树(AVL树) 红黑树
最坏时间复杂度 O(n) O(logn) O(logn)
最好时间复杂度 O(logn) O(logn) O(logn)
平均时间复杂度 O(logn) O(logn) O(logn)

作者:铭毅天下
来源:CSDN
原文:https://blog.csdn.net/laoyang360/article/details/8026653
版权声明:本文为博主原创文章,转载请附上博文链接!

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

大数据计算实践乐园,近距离学习前沿技术

其他文章