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

TheDisguiser 2020-04-18 16:22:43 java常见问答 4343

红黑树,相信看过前面文章的小伙伴们都已经不陌生了,今天我们就来了解了解红黑树的具体应用场景,一起来看看吧。

首先先复习一下什么是红黑树吧,红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除等操作。

红黑树的性质

红黑树,听名字就知道,是通过红黑两种颜色域保证树的高度近似平衡。它的每个节点是一个五元组:color,key,left,right和p。

红黑树的定义也是它的性质,有以下五条:

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

性质2. 根是黑色

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

性质4. 如果一个节点是红的,则它的两个儿子都是黑的

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

红黑树应用场景

这五个性质强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。为什么呢?性质4暗示着任何一个简单路径上不能有两个毗连的红色节点,这样,最短的可能路径全是黑色节点,最长的可能路径有交替的红色和黑色节点。同时根据性质5知道:所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

的红色节点,这样,最短的可能路径全是黑色节点,最长的可能路径有交替的红色和黑色节点。同时根据性质5知道:所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

红黑树基本操作

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

总结:

红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。

当二叉查找树的高度较低时,这些操作执行的比较快,但是当树的高度较高时,这些操作的性能可能不比用链表好。红黑树(red-black tree)是一种平衡的二叉查找树,它能保证在最坏情况下,基本的动态操作集合运行时间为O(lgn)。

在实际场景中,Java的HashMap,Mysql的Innodb都是使用了红黑树进行数据的存储的。

以上就是本文章的所有内容了,有关Java一些知识问答的更多知识,想知道的话,就一直关注本站吧。