为什么基于红黑树的java TreeMap实现？

Question

wikipedia's article on AVL trees的第三段说：“由于AVL树更严格地平衡，所以对于查找密集型应用程序，它们比红黑树更快。”

那么，TreeMap不应该使用AVL树而不是红黑树来实现吗(因为基于散列的数据结构将有更多的查找密集型应用程序)？

Answer 1

红-黑树是更通用的。它们在添加、删除和查找上做得相对较好，但AVL树具有更快的查找速度，但代价是添加/删除速度较慢。Java的总体策略是提供最佳的通用数据结构。这也是Java默认的Array.sort(Object[] a)实现是稳定的、自适应的、迭代的合并排序而不是快速排序的原因。

Answer 2

历史上，旋转的次数被认为是非常重要的，所以选择红黑树而不是AVL，因为红黑树在随机插入的情况下旋转略少- .6与.7平均每个插入的旋转。

事后看来，AVL树可能是更好的选择。你可以在这里看到Java中的AVL和红黑树的性能比较：https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/

对于随机插入，性能是相似的。对于顺序数据，AVL树的性能要好得多- 30%或更多。

Answer 3

维基百科的文章是错误的(或者至少没有支持这一说法的引用)。AVL树的最坏情况下的高度(1.44lgn)确实好于红黑BST树的最坏情况下的高度(2lgn)，但这是最坏的情况，可能与实际性能没有太大关系。