红黑树和 AVL 树 - 数据结构

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

82458 次浏览
小开

读读这个 文章

它提供了一些很好的见解，差异，相似之处，性能等。

下面是这篇文章中的一句话:

RB 树和 AVL 树都是自平衡的，它们都提供 O (logn)查找和插入性能。

区别在于 RB 树保证每个插入操作都有 O (1)旋转，这实际上是真实实现中的性能成本。

简单来说，RB 树从概念上来说是2-3棵树而不需要承担动态节点结构的开销，从而获得了这种优势。物理上，RB 树实现为二叉树，红色/黑色标志模拟2-3行为

就我个人的理解而言，AVL 树和 RB 树在性能方面差距不大。RB 树只是 B 树的一个变体，平衡的实现与 AVL 树不同。

小开

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

红黑相间的树木和 美国吸血鬼联盟的树都是最常用的 平衡二叉搜索树平衡二叉搜索树，它们支持在有保证的 O(logN) time中插入、删除和查找。然而，两者之间有以下几点可以比较:

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

红黑树的应用是什么？

红黑相间的树木更具有通用性。它们在添加、删除和查找方面做得相对较好，但是 AVL 树以较慢的添加/删除为代价来获得更快的查找。红黑树的用途如下:

小开

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

AVL 树不支持常数 摊销的更新费用[但红黑树支持]

资料来源: Mehlhorn & Sanders (2008)(7.4节)

因此，当 RB 和 AVL 树都保证 O (log (N))最坏情况下的查找、插入和删除时间时，恢复 AVL/RB 属性 之后可以在 O (1) 分期付款时间中为红黑树插入或删除节点。

小开

多年来，我们对性能差异的理解已经有所提高，现在使用红黑树而不使用 AVL 的主要原因将是无法访问一个好的 AVL 实现，因为它们可能不太常见，因为它们没有包含在 CLRS 中。

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

所以研究过红黑树但没有研究过 AVL 树的人倾向于选择红黑树。红黑树的主要用途详见 他们的维基百科条目。

小开

插入 AVL 树和 RB 树都需要最多2次旋转:

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

小开

它们都是最常用的树类型，但红黑树有更快的插入速度，因为它们具有放松的平衡性，除此之外，它们都有 O (log N)搜索时间，这是它们之间的共同点。它们都很好，但是 AVL 通常更平衡，因为它的 logN 复杂度为1.44 logN，而 logN 复杂度为2


提交答案