На чем основан TreeSet и какая сложность операций?

TreeSet — это реализация интерфейса NavigableSet в Java, которая хранит элементы в отсортированном порядке. Его внутренняя структура данных — это экземпляр TreeMap, где элементы являются ключами, а в качестве значения используется фиктивный объект. Ключевым аспектом TreeMap, а значит и TreeSet, является использование самобалансирующегося бинарного дерева поиска, а именно красно-черного дерева.

Внутренняя реализация: Красно-черное дерево

Красно-черное дерево — это разновидность бинарного дерева поиска, которая автоматически поддерживает балансировку после операций вставки и удаления. Это гарантирует, что глубина дерева остаётся логарифмической относительно числа узлов, что и обеспечивает эффективность операций. Основные правила красно-черного дерева включают: каждый узел окрашен в красный или чёрный цвет, корень всегда чёрный, красные узлы не могут иметь красных дочерних узлов, и все пути от корня к листьям содержат одинаковое количество чёрных узлов.

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

• add(E e): O(log n). Элемент вставляется в правильную позицию для сохранения порядка, после чего дерево может быть перебалансировано.
• remove(Object o): O(log n). Узел находится и удаляется, дерево балансируется.
• contains(Object o): O(log n). Выполняется стандартный поиск в бинарном дереве поиска.
• first() / last(): O(1). TreeSet хранит ссылки на самый левый (наименьший) и самый правый (наибольший) узлы.
• Итерация по всем элементам: O(n). Используется обход дерева в порядке возрастания (in-order traversal).
• Операции на подмножествах (headSet, tailSet): Получение представления — O(1), но итерация по нему будет зависеть от размера подмножества.

Пример использования

TreeSet полезен, когда требуется коллекция без дубликатов, автоматически отсортированная. Например, для хранения рейтингов или уникальных событий в хронологическом порядке.

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        // Создаём TreeSet для целых чисел (естественный порядок)
        TreeSet scores = new TreeSet<>();
        scores.add(95);
        scores.add(80);
        scores.add(100);
        scores.add(80); // Дубликат не добавится
        
        System.out.println("Все баллы по порядку: " + scores); // [80, 95, 100]
        System.out.println("Наивысший балл: " + scores.last()); // 100
        
        // Получаем подмножество баллов строго меньше 95
        System.out.println("Баллы ниже 95: " + scores.headSet(95)); // [80]
        
        // Поиск ближайшего элемента
        System.out.println("Балл, >= 90: " + scores.ceiling(90)); // 95
    }
}

Вывод: TreeSet стоит применять, когда критически важно поддерживать элементы в отсортированном порядке и выполнять частые операции поиска, вставки или удаления с логарифмической сложностью. Если порядок не важен, а приоритетом является скорость операций O(1), лучше использовать HashSet.