红黑树的应用

Question

红黑树的应用是什么？是否有任何应用程序只能使用RB树而没有其他数据结构？

Answer 1

一个红黑树是一种特定实现的平衡树,今天它似乎是执行最流行的选择.

二进制搜索树用于实现有限映射,您可以在其中存储一组具有关联值的键.您也可以仅使用密钥而不存储任何值来实现集合.

需要平衡树以保证良好的性能,否则树可以退化为列表,例如,如果插入已经排序的键.

搜索树优于哈希表的优点是您可以按排序顺序有效地遍历树.

AVL树是平衡二叉搜索树的另一种变体.在红黑树知之前,它们很受欢迎.它们更加仔细平衡,左右子树的高度之间的最大差异为1(RB树最多保证两倍).它们的主要缺点是重新平衡需要更多的努力.

所以红黑树肯定是好的,但不是这个应用的唯一选择.

Answer 2

红黑树来自一类自平衡BST,并且如其他人所回答的,可以使用任何这种自平衡树.我想补充一点,红黑树被广泛用作系统符号表.例如,它们用于实现以下内容:

• Java:java.util.TreeMap,java.util.TreeSet.
• C++ STL:map,multimap,multiset.
• Linux内核:完全公平的调度程序,linux/rbtree.h

Answer 3

除非您有非常具体的性能要求,否则RB树可以被其他一些自平衡二叉树替换,例如AVL树.在两者之间进行选择基本上是性能优化 - 它们提供相同的基本操作.

并不是说它们中的任何一个都明确地比另一个"更快",只是它们的不同之处在于它们的特定用途往往具有略微不同的性能,其他条件相同.因此,如果你仔细地或者只是偶然地提出你的要求,你最终可能会有一个"足够快"供你使用,而另一个则没有.RB提供的插入速度比AVL略快,但查找速度稍慢.

Answer 4

没有像红黑这样的规则只能在特定情况下使用它取决于应用程序，例如您只需要构建一次树并且必须多次查询它然后您可以选择 AVL 树，因为在AVL树中搜索相当快..但它是严格平衡的，因此插入和删除可能需要一些时间AVl树可能用于语言词典，您只需构建一次数据结构，而红黑树则用于完全现在在当前的 Linux 内核中使用 Fair Scheduler 已经有几天了。

应用在红黑树上的约束也强调了从根到最远叶子的路径的长度不超过从根到最近叶子的路径的两倍。

顺便说一句，您可以在此处查找红黑树所需的各种搜索和插入等时间

        Average     Worst case

Space   O(n)        O(n) 

Search  O(log n)    O(log n)

Insert  O(log n)    O(log n)

Delete  O(log n)    O(log n)