红黑树是什么?红黑树特点有哪些?

KLQ 2020-06-23 15:46:37 java常见问答 4292

对于红黑树你了解多少呢?很多刚刚接触java的人都不知道红黑树是什么,那么下面就一起来看一下红黑树的概念以及它的特点吧!

一、什么是红黑树?

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

红黑树是一种特化的AVL树,也就是平衡二叉树,都是在进行插入和删除操作的的时候,通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。

红黑树是复杂的,可是,它的最坏情况运行时间也是非常良好的,并且在实践中是高效的。

红黑树可以在O(log n)时间内做查找,插入和删除(这里的n 是树中元素的数目)。

对于红黑树你都了解了吧,那么下面再一起来看看红黑树的都有哪些特点吧!

二、红黑树的特点有哪些?

红黑树的颜色是红色或者是黑色的,是每个节点都带有颜色属性的二叉查找树。

在二叉查找树强制一般要求之外,对于任何有效的红黑树我们增加了如下的额外要求:

1、性质1-根节点是黑色;

2、性质2-节点是红色或者是黑色;

3、性质3-从任一节点到它的每个叶子的所有路径都包含相同数目的黑色节点;

4、性质4-所有的叶子都是黑色,叶子是NUIL节点;

5、性质5-每个红色节点的两个子节点都是黑色,从每个叶子到根的所有路径上不可以有两个连续的红色节点;

上面的这些约束,强制了红黑树的关键性质。

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

结果就是,这个数大致上是平衡的,这是由于操作,就好比插入、删除和查找某个值的最坏情况时间都要求和树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

性质5导致了路径上不可以有2个连续的红色节点确保了这个结果。

最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。

这主要是由于,依据性质3所有最长的路径都有相同数目的黑色节点,这就充分的表明了没有路径能多于任何其他路径的两倍长。

注意,因为,红黑树它是一种一种特化的二叉查找树,所以红黑树上的只读操行和普通二叉查找树相同。

红黑树的概念以及红黑树的特点你都了解了吧,红黑树在java当中也是经常会涉及到的知识点,假如你还想了解更多和红黑树相关的知识,可以继续通过本站的java架构师栏目来进行进一步的了解。

推荐阅读:

跳跃表和红黑树的区别是什么?它们都有什么概念?

红黑树的底层实现原理有哪些?红黑树又是什么?

红黑树应用场景和性质都有哪些?