红黑树和AVL树的区别

Question

有没有人能够解释一下这两种数据结构之间的主要区别是什么？我一直在试图寻找一个在线资源来突出它们的差异/相似之处，但我没有找到很有启发性的内容。在什么情况下会更倾向于使用其中一种而不是另一种？有哪些实际情况使其中一种比另一种“更好”使用呢？

- Bob John

Answer 1

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

因此，在AVL树中查找通常更快，但这付出了更慢的插入和删除成本，因为需要进行更多的旋转操作。因此，如果您期望查找数量支配树更新数量，则使用AVL树。

- Fred Foo

---

想更好地理解概念。 AVL树和红黑树每次插入节点最多需要进行两次旋转。那么，你怎么能说AVL树很慢呢？ - user2626445

@larsmans！性能差异如此之大，以至于需要创建一个新的概念吗？ - Shashwat

@Shashwat 我不明白你的意思。新概念？ - Fred Foo

@larsmans！我的意思是，既然AVL树的插入、删除和更新性能与红黑树只有轻微差异，为什么我们还要如此著名地使用红黑树这个概念呢？是否有什么重大的因素使红黑树不同于AVL树？ - Shashwat

维护它们的算法是不同的，因此它们有不同的名称。据我所知，它们支持相同的操作集和相同的大O时间复杂度界限。 - Fred Foo

Answer 2

对于小数据:

插入: RB 树和 AVL 树的最大旋转次数是常数，但 RB 树会更快，因为平均来说 RB 树使用更少的旋转次数。

查找: AVL 树更快，因为 AVL 树的深度更浅。

删除: RB 树的最大旋转次数是常数，但 AVL 树最坏情况下可能需要 O(log N) 次旋转。平均来看，RB 树的旋转次数也更少，因此 RB 树更快。

对于大数据:

插入: AVL 树更快。因为在插入之前需要查找特定节点，随着数据增多，在查找特定节点上花费的时间会按照 O(log N) 增长。但是 AVL 树和 RB 树最坏情况下仍然只需要常数次旋转。因此瓶颈将成为查找特定节点所需的时间。

查找: AVL 树更快。(与小数据情况相同)

删除: 平均来说，AVL 树更快，但在最坏情况下 RB 树更快。因为在删除之前也需要查找非常深的节点进行交换(类似于插入的原因)。平均来看，两种树的旋转次数都是常数。但是 RB 树具有旋转次数的常数上限。

- DU Jiaen

---

这似乎意味着在处理大量数据时，AVL树几乎总是更优选的。那么为什么Java和C++ STL中会使用红黑树呢？https://dev59.com/3m865IYBdhLWcg3wR8Wh - emschorsch

你需要有一定量的数据（例如100万）才能使AVL树在插入/删除情况下比红黑树更好，而这确实取决于你如何实现它。一个聪明的AVL实现甚至可以在较少的数据量下击败std::map。例如，如果父节点的高度大于5，则无需检查子节点和孙子节点是否为空。 - DU Jiaen

这是一项出色的分析，应该成为任何数据结构比较的典范。比被接受的答案更好。 - pterodragon

作为“小数据”的简短总结，我从中得出的结论是：AVL在前期会做更多的工作并且更加严格（写入/旋转），以便在后期提高性能（读取）。随着数据的增长，阅读变得更加重要，因为您会读取比写入更多的数据（与搜索相比，旋转将变得微不足道）。因此，AVL在所有方面都胜出，因为它针对读取进行了优化。 - Ben Butterworth

Answer 3

引用自这里：AVL树和红黑树的区别

RB-Tree和AVL-Tree一样是自平衡的。它们都提供O(log n)的查找和插入性能。不同之处在于，RB-Tree保证每次插入操作只需要进行O(1)次旋转。这实际上是真正影响性能的地方。 简单来说，RB-Tree从概念上讲是2-3树，但没有动态节点结构的开销。物理上，RB-Tree被实现为二叉树，红/黑标志模拟2-3行为。

由定义可知，每个AVL树都是红黑树的子集。可以将任何AVL树着色，而无需重构或旋转，以将其转换为红黑树。

- taocp

Answer 4

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

- zhpmatrix

Answer 5

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

AVL树和红黑树都是高度平衡的树形数据结构。它们非常相似，真正的区别在于任何添加/删除操作所需的旋转次数——AVL需要更多的旋转操作，以保持整体更加均衡。

两种实现都以O(lg N)的时间复杂度进行扩展，其中N是叶子节点的数量，但在实际应用中，AVL树在查找密集型任务上更快：利用更好的平衡性，树的遍历平均较短。另一方面，在插入和删除方面，AVL树较慢：需要更多的旋转来正确地重新平衡数据结构。

对于通用实现（即先验不清楚查找是否为主要操作），首选红黑树：它们更易于实现，并且在常见情况下更快——无论数据结构被修改还是搜索。例如，Java中的TreeMap和TreeSet使用支持红黑树。

- Paolo Maresca

Answer 6

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

来自AVL Trees的维基百科文章。

- user3078685

Answer 7

红黑树比起其他树，在插入和删除操作中旋转次数较少，这使得它们可能更快一些。然而，由于红黑树通常比其他树结构要深得多，因此在插入和删除操作中速度也可能会比较慢。每当你从树的一个级别转移到下一个级别时，所请求的信息很可能不在缓存中，必须从 RAM 中检索。因此，通过减少旋转次数所获得的时间可能已经失去了，因为它必须导航到更深的位置，因此必须更频繁地更新其缓存。能否从缓存中运行或不能从缓存中运行会有很大的区别。如果相关信息在缓存中，则可以进行多个旋转操作，而不需要导航到另一级别并且下一级别的信息不在缓存中。因此，在理论上红黑树可能更快的情况下，仅考虑所需操作，实际上可能变得更慢，因为缓存未命中。

- Jimmy Venema

Answer 8

从我所看到的来看，AVL树会做尽可能多的旋转（有时会递归地向上旋转），以达到AVL树的期望高度（Log n）。这使得它更加严格平衡。

对于红黑树，你需要确保在插入和删除过程中遵循5组规则，可以在此处找到http://en.wikipedia.org/wiki/Red-black_tree。

对于红黑树而言，最重要的是，根据这五个规则，如果叔叔节点为红色，则可以将树递归地着色到根。如果叔叔节点为黑色，则需要进行最多两次旋转来解决任何问题，但在一两次旋转后，您就完成了操作。结束并说晚安，因为您需要进行的操纵已经完成。

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

这将导致大多数所需的旋转，使树不会过分失衡。

- Leon

Answer 9

总之：Avl树比RedBlack树平衡略好。两种树在查找、插入和删除方面总共需要O(log n)的时间，但是对于插入和删除操作，前者需要O(log n)次旋转，而后者仅需要O(1)次旋转。

由于旋转意味着写入内存，而写入内存是昂贵的，因此实际上RedBlack树比Avl树更快地更新。

- beanmoon