java Java的TreeSet和TreeMap用的是什么树？

What kind of tree is used in Java's TreeSet and TreeMap?

提问by Craig P. Motlin

Are they AVL trees, red-black trees, or something else?

它们是 AVL 树、红黑树还是其他什么树？

回答by Kru

Red-blacktrees as described in the first line of the javadoc.

如 javadoc 的第一行中所述的红黑树。

• Tree Map
• Tree Set

• 树图
• 树集

回答by polygenelubricants

From the java.util.TreeMap<K,V>documentation:

从java.util.TreeMap<K,V>文档：

A Red-Black treebased NavigableMapimplementation.

一个红黑树的基础NavigableMap实施。

For questions like these, you should always first consult the documentation. The API shouldn't describe ALLof the inner-workings of a class, but elementary informations such as general data structures and algorithms used are usually documented.

对于此类问题，您应该始终首先查阅文档。API 不应描述 a 的所有内部工作原理class，但通常记录基本信息，例如使用的通用数据结构和算法。

---

---

Other Java Collections Framework trivias

其他 Java 集合框架琐事

These are all little trivias that are also clearly documented:

这些都是小细节，也清楚地记录在案：

• TreeSetis implemented with a TreeMap
• HashSetis implemented with a HashMap
• Collections.sortuses modified mergesort
• Map<K,V>is not a Collection<?>
• ArrayListdoesn't specify exact growth policy (unlike, say, Vector)

• TreeSet是用一个 TreeMap
• HashSet是用一个 HashMap
• Collections.sort使用修改后的归并排序
• Map<K,V>不是一个 Collection<?>
• ArrayList没有指定确切的增长政策（不像，说，Vector）

Related questions

相关问题

• Why does java.util.Arrays.sort(Object[])use 2 kinds of sorting algorithms?
• Why does the Java Collections Framework offer two different ways to sort?
• Why doesn't Java Map extends Collection?

• 为什么java.util.Arrays.sort(Object[])使用2种排序算法？
• 为什么 Java Collections Framework 提供两种不同的排序方式？
• 为什么 Java Map 不扩展 Collection？

回答by WonderCsabo

It is a red-black tree in the Oracle desktop Java implementation, but an AVL-tree in Android.

它在 Oracle 桌面 Java 实现中是红黑树，但在 Android 中是AVL 树。

回答by matt b

The first sentence of the TreeMap Javadocstates:

TreeMap Javadoc的第一句话指出：

A Red-Black tree based NavigableMapimplementation.

基于红黑树的NavigableMap实现。

回答by u290629

TreeSet is based on TreeMap. And they uses red-black tree, red-black tree is a kind of AVL.

TreeSet 基于 TreeMap。他们使用红黑树， 红黑树是 AVL 的一种。