Какая структура лежит в основе Java TreeSet?

Question

Java TreeSet - это самобалансирующаяся структура красно-черного дерева.

Но какова структура для хранения данных?Массив или связанный список?

Answer 1

TreeSet поддерживается TreeMap (аналогично HashSet поддерживается HashMap).Если вы посмотрите на конструктор TreeSet:

public TreeSet() {
    this(new TreeMap<E,Object>());
}

TreeMap внутренне хранит данные, используя узлы, представленные TreeMap.Entry классом:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
...

Там нет никакого дополнительного массива или списка.