为什么要使用基于红黑树的Java TreeMap实现？

Question

维基百科关于AVL树的文章的第三段说:"由于AVL树更加严格平衡,因此对于查找密集型应用程序来说,它们比红黑树更快."

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

Answer 1

红黑树更通用.它们在添加,删除和查找方面表现相对较好,但AVL树的查找速度更快,代价是添加/删除速度较慢.Java的一般政策是提供最佳的通用数据结构.这也是Java默认的Array.sort(Object [] a)实现稳定,自适应,迭代合并排序而不是快速排序的原因.

Java对原始对象使用快速排序,因为它比普通情况下的合并排序更快.它使用合并排序对对象进行排序,因为合并排序是一种稳定的排序算法.参见:http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types (15认同)
由于Java 7 merge-sort被TimSort取代了http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6804124 (3认同)