Почему в TreeSet присутствует слово Tree?

TreeSet и слово Tree: внутреннее устройство

Слово Tree в названии класса TreeSet не случайно — оно отражает то, что данная коллекция построена на основе красно-чёрного дерева (Red-Black Tree).

Почему именно дерево?

Red-Black Tree — это сбалансированное бинарное дерево поиска, в котором:

• Каждый узел окрашен в красный или чёрный цвет
• Элементы хранятся упорядоченно по компаратору или естественному порядку
• Высота дерева всегда остаётся логарифмической, даже при частых вставках и удалениях
• Это гарантирует O(log n) для основных операций (add, remove, contains)

Структура TreeSet в Java

Внутри TreeSet работает NavigableMap — конкретно TreeMap, которая реализует это красно-чёрное дерево:

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {
    
    private transient NavigableMap<E, Object> m; // Это TreeMap
    
    public TreeSet() {
        this(new TreeMap<E,Object>()); // По умолчанию создаётся TreeMap
    }
    
    public boolean add(E e) {
        return m.putIfAbsent(e, PRESENT) == null; // Добавление через TreeMap
    }
}

Каждый элемент TreeSet хранится как ключ в TreeMap, а значение всегда одно и то же — заглушка PRESENT.

Основные преимущества Red-Black Tree

1. Гарантированная балансировка:

• После каждой вставки или удаления дерево перебалансируется
• Высота остаётся O(log n), не О(n) как в несбалансированном дереве
• Это исключает деградацию на худших данных

2. Логарифмическая сложность:

TreeSet<Integer> set = new TreeSet<>();
set.add(5);      // O(log n) — спуск по дереву и вставка
set.add(3);      // O(log n)
set.add(7);      // O(log n)
set.remove(5);   // O(log n) — поиск и удаление с перебалансировкой
set.contains(3); // O(log n) — двоичный поиск

3. Упорядоченность:

TreeSet<Integer> set = new TreeSet<>(Arrays.asList(5, 3, 7, 1, 9));
set.forEach(System.out::println); // Выведет: 1, 3, 5, 7, 9 (в порядке сортировки)
set.first();  // 1
set.last();   // 9
set.subSet(3, 7); // [3, 5] — элементы в диапазоне

Сравнение с HashSet

Практические примеры

Пример 1: Отсортированное хранилище

TreeSet<String> words = new TreeSet<>();
words.addAll(Arrays.asList("zebra", "apple", "mango"));
words.forEach(System.out::println); // apple, mango, zebra

Пример 2: Поиск в диапазоне

TreeSet<Integer> scores = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));
NavigableSet<Integer> inRange = scores.subSet(20, 40); // [20, 30] (40 исключена)
inRange.forEach(System.out::println); // 20, 30

Пример 3: Кастомный компаратор

TreeSet<Person> people = new TreeSet<>((p1, p2) -> p1.getAge() - p2.getAge());
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));
people.add(new Person("Charlie", 35));
// people будет отсортирован по возрасту: Bob, Alice, Charlie

Заключение

Слово Tree в TreeSet прямо указывает на использование красно-чёрного дерева как базовой структуры данных. Это даёт нам три основных выигрыша: гарантированную логарифмическую сложность, сортировку и возможность range queries. TreeSet идеален, когда важна упорядоченность данных и частые операции поиска в диапазонах, но не требуется максимальная скорость вставки как в HashSet.