Java TreeSet

TreeSet<E> — реализация Set, которая хранит элементы в отсортированном порядке. Под капотом используется красно-чёрное дерево (то же самое сбалансированное двоичное дерево поиска, что лежит в основе TreeMap), поэтому каждая операция — add, remove, contains, first, last, диапазонные запросы — выполняется за O(log n). Это медленнее, чем O(1) у HashSet, но взамен вы получаете то, что HashSet вообще не умеет: отсортированный итератор, наименьший элемент по запросу и возможность спросить «все теги между a и m».

TreeSet реализует расширенный интерфейс NavigableSet<E> (который расширяет SortedSet<E>), поэтому все диапазонные запросы и запросы соседей доступны непосредственно в классе, а не спрятаны в хелперах Collections. Если вы ещё не знакомы с базовым контрактом, сначала прочитайте главу об интерфейсе Set — всё, что там сказано (никаких дубликатов, add возвращает false при повторном добавлении), по-прежнему актуально.

Два способа задать порядок

Для TreeSet необходим способ сравнивать элементы. Их два:

1. Естественный порядок — тип элементов реализует Comparable<E>. String, Integer, LocalDate, любой враппер, любой enum, любой record, реализующий Comparable. Конструктор без аргументов new TreeSet<>() использует именно его.
2. Comparator<E>, который вы предоставляете — передайте его в конструктор. Множество будет использовать ваш компаратор для каждого сравнения.

Set<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.add("Banana");
caseInsensitive.add("apple");
caseInsensitive.add("BANANA");   // equals "Banana" by this comparator → not added
System.out.println(caseInsensitive); // [apple, Banana]

Второй пример важен. TreeSet определяет «равенство» по возвращаемому compareTo значению 0, а не по equals. Две строки, различные по естественному порядку, но равные по компаратору, схлопнутся в один элемент. Почти всегда это именно то, что нужно, — но это острый нюанс, если вы о нём не подозревали.

API NavigableSet

TreeSet предоставляет операции, недоступные обычному Set:

TreeSet<Integer> t = new TreeSet<>(List.of(10, 20, 30, 40, 50));
t.first();          // 10  — smallest
t.last();           // 50  — largest
t.lower(30);        // 20  — strictly less than 30
t.floor(30);        // 30  — ≤ 30
t.higher(30);       // 40  — strictly greater than 30
t.ceiling(30);      // 30  — ≥ 30
t.pollFirst();      // 10, removes
t.pollLast();       // 50, removes
t.headSet(30);      // {10, 20}        — strictly less than 30
t.tailSet(30);      // {30, 40, 50}    — ≥ 30
t.subSet(20, 40);   // {20, 30}        — [20, 40)
t.descendingSet();  // a reverse-order view

Именно эти операции оправдывают стоимость O(log n): HashSet не может выполнить ни одну из них без предварительной сортировки всего множества. Если вам нужна хотя бы одна из них — TreeSet правильный выбор.

Нет null

TreeSet не может содержать null, поскольку ему потребовалось бы сравнивать null с другими элементами, а compareTo(null) — это NullPointerException. Множество выбросит исключение при первой же вставке. Если нужно сигнальное значение, используйте другое значение типа элемента: Integer.MIN_VALUE, пустую String или специальный маркер в enum.

Мутировать элементы запрещено (та же ловушка, что у HashSet)

TreeSet определяет расположение в дереве во время вставки, вызывая compareTo (или ваш Comparator). Если после вставки изменить элемент таким образом, что изменится порядок сортировки, инварианты дерева нарушатся: contains будет искать не в том поддереве, remove может молча завершиться неудачей, а итерация может вернуть один и тот же элемент дважды или пропустить элементы.

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

Когда выбирать TreeSet

Алгоритм принятия решения:

• Нужна отсортированная итерация или диапазонные запросы → TreeSet. Единственный выбор.
• Нужна быстрая проверка вхождения, порядок не важен → HashSet. Выигрывает O(1).
• Нужна быстрая проверка вхождения и предсказуемый порядок итерации → LinkedHashSet. Порядок вставки, а не сортировка.
• Тип элементов — enum → EnumSet. Быстрее TreeSet и естественно упорядочен.

Полезный паттерн: выполните трудоёмкие вычисления на основе HashSet, пока важна скорость, а затем один раз сделайте new TreeSet<>(hashSet) в конце, если нужно представить результат в отсортированном виде. Строим быстро, показываем отсортированным.

Разобранный пример: таблица лидеров, компаратор и диапазонные запросы

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

Что следует вынести из запуска:

• Целые числа вернулись в порядке возрастания без явной сортировки. Этот инвариант сортировки поддерживается при каждом вызове add — цена этого O(log n) на вставку.
• Таблица лидеров использовала двухступенчатый компаратор: убывание по очкам, затем возрастание по имени, чтобы игроки с одинаковым счётом оставались отдельными элементами. Всегда добавляйте признак разрыва равенства, если очки могут повторяться, иначе TreeSet схлопнет их.
• Множество без учёта регистра отклонило "JAVA", потому что по компаратору оно равно "Java" — даже несмотря на то что "JAVA".equals("Java") возвращает false. Равенство по компаратору, а не по equals.
• null привёл к исключению — нет разумного способа сравнить его с другими элементами.

Что дальше

Set изучен; вторая половина фреймворка — Map, абстракция «ключ — значение». Set можно рассматривать как Map, в котором значения не важны. Следующая глава — об интерфейсе Map, и параллельная структура с Set станет очевидна, как только мы начнём. TreeSet фактически реализован на основе TreeMap, поэтому методы навигации по отсортированному отображению, которые вы видели здесь, снова появятся там, но с ключами вместо элементов.

Практика