Какие операции легче реализовать на TreeSet в Java

Что проверяют

Понимаете ли вы, ради чего берут TreeSet вместо HashSet. Ждут не «добавление за log n», а навигацию по порядку: соседи, диапазоны, крайние элементы. Следом спрашивают, что будет, если компаратор несогласован с equals.

Как отвечать

TreeSet это обёртка над TreeMap, то есть красно-чёрное дерево. add, remove, contains стоят O(log n), у HashSet O(1) в среднем. Выигрыш дерева не в базовых операциях, а в методах NavigableSet:

• соседи: floor(x) и ceiling(x) дают ближайший элемент не больше и не меньше x, lower и higher то же строго. «Ближайшая свободная дата» решается одним вызовом за O(log n);
• диапазоны: subSet(from, true, to, false), headSet, tailSet возвращают представления, а не копии. Изменения видны в исходном множестве, а вставка за границы диапазона бросает IllegalArgumentException;
• крайние элементы: first(), last(), а pollFirst() и pollLast() ещё и удаляют. Всё за O(log n), до края дерева надо спуститься;
• обратный порядок: descendingSet() и descendingIterator();
• упорядоченный обход: итератор отдаёт элементы по возрастанию, отдельная сортировка не нужна.

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

Порядок задаёт Comparable элементов или Comparator в конструкторе. Уникальность тоже решает компаратор: если compare вернул 0, второй элемент не добавится, даже когда equals считает их разными.

Где спотыкаются

Называют first() и last() операциями за O(1). В TreeMap крайний узел ищется спуском по дереву, это O(log n).

Пишут компаратор по одному полю, например по цене, и теряют товары с одинаковой ценой. Нужен второй критерий, например идентификатор.

Кладут null или меняют поле сортировки у уже вставленного элемента. В первом случае при естественном порядке будет NullPointerException, во втором дерево ломается, и contains перестаёт находить элемент.