На основе какой структуры данных реализован TreeSet в Java?

TreeSet<E> реализован на основе TreeMap<E, Object>, который, в свою очередь, использует красно-черное дерево (Red-Black Tree).

Красно-черное дерево — это самобалансирующееся бинарное дерево поиска (BST) со следующими свойствами, гарантирующими логарифмическую сложность O(log n) для ключевых операций (add, remove, contains):

1. Каждый узел имеет цвет: красный или черный.
2. Корень всегда черный.
3. Все листья (NIL) черные.
4. Красный узел не может иметь красного потомка.
5. Все пути от узла до его листьев содержат одинаковое количество черных узлов.

Внутреннее устройство TreeSet:

// Упрощенная концепция
public class TreeSet<E> {
    private transient TreeMap<E, Object> map;
    private static final Object PRESENT = new Object(); // Фиктивное значение

    public boolean add(E e) {
        return map.put(e, PRESENT) == null; // Элемент становится ключом в TreeMap.
    }
}

Пример и последствия:

TreeSet<Integer> set = new TreeSet<>();
set.add(50);
set.add(30);
set.add(70);
set.add(20);
// Внутри поддерживается сбалансированное дерево, примерно:
//        50 (черный)
//       /  
//     30    70 (красные)
//    /
//  20 (красный)

System.out.println(set); // [20, 30, 50, 70] - элементы отсортированы.

Ключевые характеристики TreeSet:

• Упорядоченность: Элементы хранятся в отсортированном порядке (natural order или Comparator).
• Сложность: O(log n) для основных операций благодаря балансировке.
• Запрет дубликатов: Следует контракту Set.
• Не потокобезопасен: Для многопоточного доступа требуется внешняя синхронизация.