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

algorithm java binary-search-tree red-black-tree avl-tree

2022-09-04 00:39:25

维基百科关于AVL树的文章的第三段说：“因为AVL树更严格平衡，所以对于查找密集型应用程序，它们比红黑树更快。

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

答案 1

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

答案 2

从历史上看，旋转次数被认为非常重要，因此选择了红黑树而不是AVL，因为红黑色使用随机插入进行稍少的旋转 - 每个插入物的平均旋转次数为.6 vs .7。

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

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