Как обеспечивается сортировка элементов в TreeSet при их добавлении?

TreeSet в Java автоматически поддерживает элементы в отсортированном порядке, используя самобалансирующееся бинарное дерево поиска — красно-черное дерево (Red-Black Tree).

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

1. Сравнение: Новый элемент сравнивается с узлами дерева, начиная с корня.
2. Определение позиции: Для сравнения используется:
   • Естественный порядок (метод compareTo() интерфейса Comparable), если элементы его реализуют.
   • Либо внешний Comparator, переданный в конструктор TreeSet.
3. Вставка и балансировка: Элемент добавляется как новый узел в дереве, после чего выполняется алгоритм балансировки красно-черного дерева для сохранения логарифмической высоты O(log n).

Пример:

// TreeSet использует естественный порядок (Comparable) для Integer
TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(10); // Становится корнем
numbers.add(5);  // 5 < 10 -> становится левым потомком
numbers.add(15); // 15 > 10 -> становится правым потомком
// Итоговый порядок при итерации: [5, 10, 15]

Ключевые следствия:

• Сложность операций add(), contains(), remove() — O(log n).
• Если элементы не реализуют Comparable и не передан Comparator, при добавлении будет выброшено ClassCastException.
• Итерация по TreeSet (for-each, iterator) возвращает элементы в отсортированном порядке.