143

除了节点中的红色和黑色外，AVL 和红黑树都是自平衡的。选择红黑树而不是 AVL 树的主要原因是什么？红黑树的应用有哪些？

4

5 回答 5

161

选择红黑树而不是 AVL 树的主要原因是什么？

红黑树和AVL树都是最常用的平衡二叉搜索树，它们都支持保证的插入、删除和查找O(logN) time。但是，两者之间有以下比较点：

  • AVL 树更严格地平衡，因此提供更快的查找。因此，对于查找密集型任务，使用 AVL 树。
  • 对于插入密集型任务，请使用红黑树。
  • AVL 树在每个节点存储平衡因子。这需要O(N)额外的空间。但是，如果我们知道要插入树中的键总是大于零，我们可以使用键的符号位来存储红黑树的颜色信息。因此，在这种情况下，红黑树不会占用额外的空间。

红黑树的应用有哪些？

红黑树更通用。它们在添加、删除和查找方面做得相对较好，但 AVL 树的查找速度更快，但添加/删除速度较慢。红黑树用于以下情况：

于 2014-04-24T18:50:40.037 回答
21

尝试阅读这篇文章

它提供了一些关于差异、相似性、性能等的很好的见解。

这是文章的引述：

RB-Tree 和 AVL 树一样是自平衡的。它们都提供 O(log n) 的查找和插入性能。

不同之处在于 RB-Trees 保证每个插入操作的 O(1) 次旋转。这就是在实际实现中实际成本性能的原因。

简化后，RB-Trees 从概念上是 2-3 棵树获得了这一优势，而无需携带动态节点结构的开销。物理上，RB-Trees 被实现为二叉树，红/黑标志模拟 2-3 行为

就我自己的理解而言，AVL 树和 RB 树在性能上相差不远。RB 树只是 B 树的变体，平衡的实现方式与 AVL 树不同。

于 2012-12-13T04:22:55.350 回答
11

多年来，我们对性能差异的理解有所提高，现在在 AVL 上使用红黑树的主要原因是无法获得良好的 AVL 实现，因为它们不太常见，可能是因为 CLRS 没有涵盖它们。

这两种树现在都被认为是等级平衡树的形式，但红黑树在现实世界的测试中始终慢约 20%。插入顺序数据时甚至会慢 30-40% 。

所以研究过红黑树但没有研究过AVL树的人倾向于选择红黑树。红黑树的主要用途在Wikipedia 条目中有详细说明。

于 2017-10-11T19:45:07.747 回答
4

这里的其他答案很好地总结了 RB 和 AVL 树的优缺点，但我发现这种差异特别有趣：

AVL 树不支持恒定摊销更新成本[但红黑树支持]

资料来源：Mehlhorn & Sanders (2008)（第 7.4 节）

因此，虽然 RB 和 AVL 树都保证 O(log(N)) 最坏情况下的查找、插入和删除时间，但在插入或删除节点后恢复 AVL/RB 属性可以在 O(1)分摊时间内完成红黑树。

于 2017-09-14T14:33:18.547 回答
0

AVL 树和 RB 树中的插入都需要最多 2 次旋转。来自https://adtinfo.org/：

红黑树的主要优点是，在 AVL 树中，从包含 n 个节点的树中删除一个节点可能需要 log 2 n 次旋转，但在红黑树中删除不需要超过 3 次旋转。

于 2021-07-14T15:54:59.587 回答