为什么红黑树化实施的Java TreeMap的？ [英] Why red-black tree based implementation for java TreeMap?

问题描述

Wikipedia关于AVL树的文章的第三段说：由于AVL树是更严格的平衡，他们更快比红黑树的查询密集型应用。

The third paragraph of wikipedia's article on AVL trees says: "Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications."

所以，不应该 TreeMap的使用AVL树来实现的红 - 黑树代替（如将有更多的查找密集applictions为散列基于数据结构）？

So, shouldn't TreeMap be implemented using AVL trees instead of red-black trees(as there will be more look up intensive applictions for a hashing based data structure ) ?

推荐答案

红黑树是更通用的。该做的比较出色的添加，删除和查询，但AVL树有更快的查找窗口以较慢的添加/删除成本。 Java的一般政策是提供最好的通用数据结构。这也是同样的原因Java的默认的Array.sort（Object []对象一）实施合并的排序，而不是快速排序。

Red-Black trees are more general purpose. The do relatively well on add, remove, and look-up but AVL trees have faster look-ups at the cost of slower add/remove. Java's general policy is to provide the best general purpose data structures. It's also the same reason Java's default Array.sort(Object[] a) implementation is merge sort instead of quicksort.

这篇关于为什么红黑树化实施的Java TreeMap的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！