83

有人可以解释这两种数据结构之间的主要区别是什么吗？我一直试图在网上找到一个突出差异/相似之处的资源，但我没有发现任何信息量太大的东西。在什么情况下，一种会比另一种更受欢迎？哪些实际情况使一个比另一个“更好”使用？

4

9 回答 9

102

AVL 树比红黑树保持更严格的平衡。AVL 树中从根到最深叶的路径最多为~1.44 lg(n+2)，而在红黑树中最多为~2 lg (n+1)。

因此，在 AVL 树中的查找通常更快，但由于更多的旋转操作，这是以更慢的插入和删除为代价的。因此，如果您希望查找次数支配树的更新次数，请使用 AVL 树。

于 2013-07-23T23:32:40.083 回答
56

对于小数据：

插入：RB 树和 avl 树具有恒定的最大旋转次数，但 RB 树会更快，因为平均 RB 树使用较少的旋转。

查找：AVL 树更快，因为 AVL 树的深度较小。

删除：RB 树的最大旋转次数是恒定的，但 AVL 树的旋转次数可能是 O(log N) 次最差。并且平均而言，RB树的旋转次数也更少，因此RB树更快。

对于大数据：

插入：AVL 树更快。因为您需要在插入之前查找特定节点。当您拥有更多数据时，查找特定节点的时间差与 O(log N) 成正比增长。但是 AVL 树和 RB 树在最坏的情况下仍然只需要恒定的旋转次数。因此，瓶颈将成为您查找该特定节点的时间。

查找：AVL 树更快。（与小数据情况相同）

delete：平均而言，AVL 树更快，但在最坏的情况下，RB 树更快。因为你还需要在移除之前查找一个非常深的节点进行交换（类似于插入的原因）。平均而言，两棵树都有恒定的旋转次数。但是RB树有一个恒定的旋转上限。

于 2015-03-04T04:11:00.073 回答
8

引用自：AVL 和红黑树之间的区别

RB-Tree 和 AVL 树一样是自平衡的。它们都提供 O(log n) 的查找和插入性能。不同之处在于 RB-Trees 保证每个插入操作的 O(1) 次旋转。这就是在实际实现中实际成本性能的原因。简化后，RB-Trees 从概念上是 2-3 棵树获得了这一优势，而无需携带动态节点结构的开销。物理上，RB-Trees 被实现为二叉树，红/黑标志模拟 2-3 行为。

因此，根据定义，每个 AVL 都是 Red-Black 的子集。人们应该能够为任何 AVL 树着色，而无需重组或旋转，将其转换为红黑树。

于 2013-04-27T23:06:47.973 回答
3

树木的最大高度对于保持平衡至关重要。它几乎等于1.44 * log(n)AVL，但对于 RB 树，它是2 * log(n). 因此我们可以得出结论，当问题是搜索激励时，最好使用 AVL。重要的是 AVL 和 RB 树的另一个问题。RB树在面对随机插入时优于AVL，旋转成本较低，但AVL适合插入升序或降序数据。所以如果问题是插入激励，我们可以使用RB树。

于 2014-06-15T04:00:14.470 回答
3

AVL 树通常与红黑树进行比较，因为它们都支持相同的操作集并且需要O(log n)时间进行基本操作。对于查找密集型应用程序，AVL 树比红黑树更快，因为它们更严格地平衡。与红黑树类似，AVL 树是高度平衡的。对于任何 μ ≤ ½，两者通常都不是重量平衡的，也不是 μ 平衡的；也就是说，兄弟节点可以有非常不同数量的后代。

来自关于AVL 树的维基百科文章

于 2013-12-07T22:33:42.827 回答
3

要了解 AVL 树的工作原理，此交互式可视化会有所帮助。

AVL 和 RedBlack 树是高度平衡的树数据结构。它们非常相似，真正的区别在于在任何添加/删除操作时完成的旋转操作的数量 - 在 AVL 的情况下更高，以保持整体更均匀的平衡。

两种实现都缩放为 a O(lg N)，其中 N 是叶子的数量，但实际上 AVL 树在查找密集型任务上更快：利用更好的平衡，树的遍历平均更短。另一方面，在插入和删除方面，AVL 树的速度较慢：需要更多的旋转次数才能在修改时正确地重新平衡数据结构。

对于通用实现（即先验，尚不清楚查找是否是主要的操作），首选红黑树：它们更容易实现，并且在常见情况下速度更快 - 无论数据结构的修改频率与搜索频率一样高. 一个例子，TreeMap在TreeSetJava 中使用了一个支持的 RedBlack Tree。

于 2015-12-17T14:58:54.703 回答
2

RedBlack 树的旋转较少这一事实可以使它们在插入/删除时更快，但是......。由于它们通常更深一些，因此它们在插入和删除时也可能更慢。每次从树中的一个级别转到下一个级别时，都会发生很大的变化，即请求的信息不在缓存中，必须从 RAM 中检索。因此，由于它必须更深入地导航，因此必须更频繁地更新其缓存，因此可能已经失去了更少旋转所获得的时间。是否能够从缓存中操作会产生很大的不同。如果相关信息在缓存中，那么您可以在需要导航一个附加级别并且下一级信息不在缓存中的时间内进行多次旋转操作。因此，如果 RedBlack 在理论上更快，仅查看所需的操作，在实践中可能会更慢，

于 2016-01-08T15:25:20.820 回答
1

从我所看到的情况来看，AVL 树似乎做了尽可能多的旋转（有时递归地向上树）以获得所需的 AVL 树高度（Log n）。这使它更加严格地平衡。

对于红黑树，您需要 5 套规则来确保插入和移除，您可以在此处找到http://en.wikipedia.org/wiki/Red-black_tree。

对红黑树可能有帮助的主要因素是，如果叔叔是红色的，那么根据这五个规则，您可以递归地将树着色到根。如果叔叔是黑人，您最多需要进行两次旋转来解决您遇到的任何问题，但是在那一两次旋转之后，您就完成了。把它打包并说晚安，因为这就是你需要做的操作的结束。

大规则是数字 5...“从给定节点到其任何后代叶子的每个简单路径都包含相同数量的黑色节点”。

这将导致您需要使树工作的大部分旋转，并导致树不会失去平衡。

于 2013-07-23T22:56:53.593 回答
1

总结：AvlTrees 比 RedBlackTrees 更平衡。两棵树的查找、插入和删除总共需要 O(log n) 时间，但对于插入和删除，前者需要 O(log n) 次旋转，而后者只需要 O(1) 次旋转。

由于旋转意味着写入内存，而写入内存的成本很高，因此 RedBlackTrees 在实践中比 AvlTrees 更新速度更快

于 2015-05-11T17:18:51.483 回答