Какое дерево используется в Java TreeSet и TreeMap?

Question

Это деревья AVL, красно-черные деревья или что-то еще?

Answer 1

Красно-черные деревья, как описано в первой строке javadoc.

• Карта деревьев
• Набор деревьев

Answer 2

Из документации java.util.TreeMap<K,V>:

A Красно-черное дерево на основе NavigableMap реализация.

Для вопросов, подобных этим, вы всегда должны сначала обратиться к документации. API не должен описывать ALL внутренней работы class, но элементарные сведения, такие как общие структуры данных и используемые алгоритмы, обычно документируются.

---

Другие мелочи платформы Java Collections Framework

Это все мелочи, которые также четко документированы:

• TreeSet реализовано с TreeMap
• HashSet реализовано с HashMap
• Collections.sort использует модифицированную сортировку слиянием
• Map<K,V> не является Collection<?>
• ArrayList не определяет точную политику роста (в отличие, скажем, Vector)

Смежные вопросы

• Почему java.util.Arrays.sort(Object[]) использует 2 вида алгоритмов сортировки?
• Почему Java Collections Framework предлагает два разных способа сортировки?
• Почему Java Map не расширяет коллекцию?

Answer 3

Это красно-черное дерево в реализации Java для настольных компьютеров Oracle, но AVL-дерево в Android .

Answer 4

В первом предложении Javadoc TreeMap говорится:

Реализация NavigableMap на основе красно-черного дерева

Answer 5

TreeSet основан на TreeMap. И они используют красно-черное дерево, красно-черное дерево - это разновидность AVL .