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

Ответ 1

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

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

Ответ 2

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

A Red-Black tree на основе NavigableMap реализация.

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

Другие тривиальные схемы коллекций Java

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

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

Связанные вопросы

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

Ответ 3

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

Реализация NavigableMap на основе Red-Black.

Ответ 4

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

Ответ 5

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