algorithm - 红黑树的应用

Question

红黑（RB）树有哪些应用？是否有任何应用程序只能使用 RB 树而不能使用其他数据结构？

score 37 · Accepted Answer

红黑树是自平衡二叉搜索树的一种特殊实现，如今它似乎是最流行的实现选择。

二叉搜索树用于实现有限映射，您可以在其中存储一组具有关联值的键。您还可以通过仅使用键而不存储任何值来实现集合。

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

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

AVL 树是平衡二叉搜索树的另一种变体。在红黑树出现之前，它们就很受欢迎。它们更仔细地平衡，左右子树的高度之间的最大差异为 1（RB 树最多保证两倍）。它们的主要缺点是再平衡需要更多的努力。

所以红黑树当然是一个不错的选择，但不是这个应用程序的唯一选择。

score 16 · Accepted Answer

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

score 9 · Accepted Answer

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

并不是说它们中的任何一个肯定比另一个“更快”，只是它们的不同之处足以使它们的特定用途往往具有稍微不同的性能，其他一切都相同。因此，如果您足够仔细地绘制您的需求，或者只是偶然地，您最终可能会得到其中一个“足够快”以供您使用，而另一个则不然。RB 提供比 AVL 稍快的插入，但代价是查找速度稍慢。

score 8 · Accepted Answer

没有像红黑这样的规则只能在特定情况下使用它取决于应用程序，例如当您必须只构建一次树并且必须多次查询它时，您可以选择 AVL 树，因为在 AVL 树中搜索非常快.. 但它是严格平衡的，因此插入和删除可能需要一些时间现在在当前 Linux 内核中使用的公平调度程序..

应用于红黑树的约束还强制指出从根到最远叶子的路径不超过从根到最近叶子的路径的两倍。

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

        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)

4 回答 4