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

Структура TreeSet

TreeSet построен на основе красно-чёрного дерева (Red-Black Tree), которое является самобалансирующимся бинарным деревом поиска.

Внутренняя реализация

public class TreeSet<E> extends AbstractSet<E> 
    implements NavigableSet<E>, Cloneable, Serializable {
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();
}

На самом деле TreeSet - это обертка над TreeMap, где ключами являются элементы, а значением - объект-заглушка PRESENT.

Красно-чёрное дерево

Это бинарное дерево со следующими свойствами:

1. Каждый узел окрашен в красный или чёрный цвет
2. Корневой узел всегда чёрный
3. Все листья (null) - чёрные
4. Красный узел не может иметь красных потомков
5. Путь от любого узла до листьев содержит одинаковое количество чёрных узлов

Эти правила гарантируют, что дерево остаётся сбалансированным.

Как это выглядит

// При добавлении элементов TreeSet автоматически их сортирует
TreeSet<Integer> set = new TreeSet<>();
set.add(10);
set.add(5);
set.add(15);
set.add(3);

// Итерация вернёт: 3, 5, 10, 15 (в отсортированном порядке)
for (Integer num : set) {
    System.out.println(num); // 3, 5, 10, 15
}

Производительность

• add(element) — O(log n)
• remove(element) — O(log n)
• contains(element) — O(log n)
• iteration — O(n), гарантированно в отсортированном порядке

Все операции логарифмические благодаря сбалансированности дерева.

Преимущества

1. Отсортированный порядок — элементы всегда в определённом порядке
2. Быстрый поиск — O(log n) благодаря двоичному поиску
3. Балансировка — красно-чёрное дерево автоматически остаётся сбалансированным
4. NavigableSet методы — headSet(), tailSet(), floor(), ceiling()

Когда использовать

• Когда нужны элементы в отсортированном порядке
• Когда часто требуется поиск диапазонов элементов
• Когда нужна логарифмическая производительность при вставке/удалении

TreeSet - идеальный выбор для приложений, требующих отсортированные, уникальные элементы с быстрым доступом.