За счет чего происходит сортировка при добавлении элемента в TreeSet

Ответ

Сортировка в TreeSet: красно-чёрное дерево

TreeSet поддерживает автоматическую сортировку элементов благодаря использованию красно-чёрного дерева (Red-Black Tree) как внутренней структуры данных. Это сбалансированное бинарное дерево поиска, которое обеспечивает логарифмическую сложность операций.

Механизм сортировки

1. Сравнение через Comparable/Comparator

При добавлении нового элемента в TreeSet используется либо естественное упорядочивание (интерфейс Comparable), либо пользовательский компаратор (интерфейс Comparator). Каждый новый элемент сравнивается с элементами в дереве для определения его позиции.

// Натуральное упорядочивание
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(3);
numbers.add(7);
// Результат: [3, 5, 7]

// Пользовательский компаратор
TreeSet<String> words = new TreeSet<>(Comparator.reverseOrder());
words.add("apple");
words.add("zebra");
words.add("banana");
// Результат: [zebra, banana, apple]

2. Вставка элемента

Процесс добавления элемента в TreeSet:

• Начинаем с корня дерева
• Сравниваем новый элемент с текущим узлом
• Если элемент меньше — идём в левое поддерево
• Если больше — идём в правое поддерево
• Повторяем до тех пор, пока не найдём позицию для вставки
• Вставляем элемент и балансируем дерево

3. Балансировка красно-чёрного дерева

После вставки элемента дерево может стать несбалансированным. TreeSet автоматически выполняет операции ротации и перекрашивания узлов для поддержания свойств красно-чёрного дерева:

public class RedBlackTreeExample {
    public static void main(String[] args) {
        TreeSet<Integer> tree = new TreeSet<>();
        
        int[] values = {15, 10, 20, 8, 12, 17, 25, 6, 11};
        for (int val : values) {
            tree.add(val);
            System.out.println("Добавлен " + val + ", размер: " + tree.size());
        }
        
        System.out.println("Сортированный набор: " + tree);
    }
}

Сложность операций

• add() — O(log n) благодаря сбалансированности
• remove() — O(log n)
• contains() — O(log n)
• iteration — O(n)

Важные свойства красно-чёрного дерева

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

Эти свойства гарантируют, что высота дерева остаётся O(log n), обеспечивая эффективность всех операций.

Альтернативы

Если вам нужны элементы без сортировки, используйте HashSet. Если нужна сортировка по вставке, рассмотрите LinkedHashSet.