Интерфейсы SortedSet, NavigableSet и класс TreeSet в Java - Вопросы

SortedSet — интерфейс отсортированного множества (Java 1.2): элементы без повторов хранятся по возрастанию в естественном порядке (Comparable) или по Comparator. Он добавляет к Set методы first(), last(), headSet(), subSet(), tailSet() и comparator().

NavigableSet (Java 6) расширяет SortedSet методами навигации: ceiling(), floor(), higher(), lower(), pollFirst(), pollLast(), descendingSet(), descendingIterator() и перегрузками диапазонов с флагами inclusive.

TreeSet — класс, который реализует оба интерфейса на красно-чёрном дереве; потокобезопасная альтернатива — ConcurrentSkipListSet. Поэтому «SortedSet vs TreeSet» — вопрос о типе переменной: объявляйте NavigableSet, если нужны ceiling()/floor() или флаги диапазонов, и SortedSet, если хватает first(), last() и subSet().

NavigableSet<Integer> times = new TreeSet<>();

Все четыре ищут ближайший к аргументу элемент. ceiling(e) — наименьший элемент, больший или равный e; floor(e) — наибольший, меньший или равный; higher(e) и lower(e) — то же, но строго больше или меньше: равный элемент пропускается.

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30));
set.ceiling(20); // 20
set.higher(20);  // 30
set.floor(20);   // 20
set.lower(20);   // 10
set.ceiling(35); // null

Если подходящего элемента нет, методы возвращают null, а не бросают исключение. Поэтому times.lower(1600) безопаснее, чем times.headSet(1600).last(): на пустом подмножестве last() бросит NoSuchElementException. Ловушка — автораспаковка: int next = set.ceiling(100); при отсутствии элемента даёт NullPointerException, результат нужно хранить в Integer и проверять на null.

Методы SortedSet работают с полуоткрытым интервалом: нижняя граница включается, верхняя — нет. headSet(to) — элементы строго меньше to, tailSet(from) — больше или равные from, subSet(from, to) — от from включительно до to не включительно.

В NavigableSet есть перегрузки с флагами: headSet(to, inclusive), tailSet(from, inclusive), subSet(from, fromInclusive, to, toInclusive).

NavigableSet<Integer> nums = new TreeSet<>(List.of(10, 20, 30, 40, 50));
nums.subSet(20, 40);              // [20, 30]
nums.subSet(20, true, 40, true);  // [20, 30, 40]
nums.tailSet(30, false);          // [40, 50]
nums.subSet(15, 35);              // [20, 30]
nums.subSet(40, 20);              // IllegalArgumentException: fromKey > toKey

Границы не обязаны быть элементами множества. Нижняя граница должна идти первой; для обратного порядка используют descendingSet().subSet(40, 20).

Нет. headSet(), tailSet(), subSet() и descendingSet() возвращают представление исходного множества (backed-collection). Изменения видны в обе стороны: элемент, добавленный в исходный TreeSet, появляется в подмножестве, если попадает в его диапазон, а удаление через подмножество удаляет элемент из исходного.

TreeSet<Integer> all = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> head = all.headSet(30, true); // [10, 20, 30]
all.add(25);      // head: [10, 20, 25, 30]
head.remove(10);  // all: [20, 25, 30, 40, 50]
head.add(45);     // IllegalArgumentException: key out of range

Добавить через представление значение вне его диапазона нельзя. Если нужна независимая копия диапазона, её создают явно: new TreeSet<>(all.headSet(30, true)).

pollFirst() и pollLast() возвращают наименьший и наибольший элементы и сразу удаляют их; для пустого множества они возвращают null, тогда как first() и last() бросают NoSuchElementException. Цикл while ((x = set.pollFirst()) != null) обрабатывает элементы по возрастанию и одновременно очищает множество.

Обычный iterator() у TreeSet всегда идёт по возрастанию. Для обратного порядка есть descendingSet() — представление в обратном порядке — и descendingIterator() — итератор от большего к меньшему.

TreeSet<String> tasks = new TreeSet<>(List.of("b", "d", "a", "c"));
tasks.descendingSet(); // [d, c, b, a]
tasks.pollFirst();     // a
tasks.pollLast();      // d
System.out.println(tasks); // [b, c]

С Java 21 SortedSet расширяет SequencedSet: у TreeSet есть getFirst(), getLast(), removeFirst(), removeLast() и reversed(), а addFirst() и addLast() бросают UnsupportedOperationException — место элемента определяет компаратор.

TreeSet хранит элементы как ключи TreeMap — красно-чёрного дерева, поэтому add(), remove() и contains() выполняются за O(log n): медленнее, чем O(1) в среднем у HashSet, но быстрее линейного поиска в списке. Класс не потокобезопасен. Уникальность проверяется через compareTo() или compare(), а не через equals().

Конструкторы:

• TreeSet() — естественный порядок; элемент без Comparable даёт ClassCastException при add(), null — NullPointerException;
• TreeSet(Comparator) — порядок по компаратору;
• TreeSet(Collection) — копия в естественном порядке, дубликаты отбрасываются;
• TreeSet(SortedSet) — копирует и элементы, и компаратор.

Какой из двух последних вызовется, решает компилятор по объявленному типу аргумента: SortedSet с Comparator.reverseOrder(), переданный как Collection, будет молча пересортирован по возрастанию.