维基百科关于 AVL 树的文章的第三段说：“因为 AVL 树更严格地平衡，所以对于查找密集型应用程序来说，它们比红黑树更快。”
那么，不应该使用 AVL 树而不是红黑树来实现TreeMap（因为对于基于散列的数据结构会有更多的查找密集型应用程序）？
问问题
9367 次
3 回答
24
红黑树更通用。它们在添加、删除和查找方面做得相对较好，但 AVL 树的查找速度更快，但添加/删除速度较慢。Java 的一般策略是提供最好的通用数据结构。这也是 Java 的默认 Array.sort(Object[] a) 实现是稳定的、自适应的、迭代合并排序而不是快速排序的原因。
于 2013-02-17T16:43:18.923 回答
2
从历史上看，旋转次数被认为非常重要，因此选择红黑树而不是 AVL，因为红黑树在随机插入时执行的旋转略少——每个插入的平均旋转为 0.6 对 0.7。
事后看来，AVL 树可能是更好的选择。您可以在此处查看 Java 中 AVL 和红黑树的性能比较： https ://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/
对于随机插入，性能是相似的。使用顺序数据时，AVL 树的性能要好得多 - 30% 或更多。
于 2017-10-20T23:13:39.937 回答
1
维基百科的文章是错误的（或者至少，没有支持引用来支持该声明）。确实，AVL 树的最坏情况高度（1.44 lg n）优于红黑 BST 的最坏情况高度（2 lg n），但这是最坏情况，可能没什么可做的具有真实世界的性能。
于 2013-02-17T19:12:15.360 回答