Що таке TreeSet і як він працює?

🟢 Junior Level

TreeSet — відсортована колекція унікальних елементів.

Проста аналогія: Словник — слова завжди в алфавітному порядку, незалежно від того, в якому порядку ви їх додавали.

TreeSet<Integer> set = new TreeSet<>();
set.add(5);
set.add(2);
set.add(8);
set.add(1);

System.out.println(set);  // → [1, 2, 5, 8] (завжди відсортовано!)

Особливості:

Елементи завжди відсортовані
Не можна null
Повільніший за HashSet: O(log n) замість O(1) + кожен вузол — окремий об’єкт у купі (cache miss при обході). Але дані відсортовані.

🟡 Middle Level

Всередині: TreeMap

// TreeSet = адаптер над TreeMap
private transient TreeMap<E, Object> m;
private static final Object PRESENT = new Object();

// Всі операції делегуються TreeMap
// Складність: O(log n) для add/remove/contains

Червоно-чорне дерево

Самобалансувальне бінарне дерево:
  → Висота завжди O(log n)
  → При вставці/видаленні: rebalancing (повороти)
    Повороти = перебудова зв'язків між вузлами дерева, щоб висота залишалася O(log n). Без поворотів дерево виродиться у linked list з O(n).
  → Кольори вузлів (червоний/чорний) для балансу

    5(B)
   /   \
  2(R)  8(R)
 /  \
1(B) 3(B)

Навігація

TreeSet<Integer> set = new TreeSet<>(Set.of(1, 3, 5, 7, 9));

set.floor(6);    // → 5 (найближчий ≤ 6)
set.ceiling(6);  // → 7 (найближчий ≥ 6)
set.lower(5);    // → 3 (строго < 5)
set.higher(5);   // → 7 (строго > 5)

set.subSet(3, 8);    // → [3, 5, 7] (діапазон)
set.headSet(5);      // → [1, 3] (менше 5)
set.tailSet(5);      // → [5, 7, 9] (більше або дорівнює)

compareTo vs equals

// TreeSet використовує compareTo, НЕ equals!
class Person implements Comparable<Person> {
    String name;
    public int compareTo(Person o) {
        return name.compareTo(o.name);  // За ім'ям
    }
}

// Якщо compareTo = 0 → елемент НЕ додасться
// Навіть якщо equals повертає false!

// → equals та compareTo повинні бути узгоджені!

Коли НЕ використовувати TreeSet

Потрібна тільки унікальність — HashSet швидший (O(1) vs O(log n))
Елементи не імлементують Comparable та немає Comparator — TreeSet не зможе сортувати
Пам’ять критична — TreeSet у 3-4 рази більший за HashSet (вузли дерева з prev/next/left/right)

🔴 Senior Level

Memory Footprint

Кожен Entry у TreeMap:
  Object Header: 12 байт
  K key: 4-8 байт
  V value: 4 байти (PRESENT)
  Entry left: 4-8 байт
  Entry right: 4-8 байт
  Entry parent: 4-8 байт
  boolean color: 1 байт
  Padding: до 8 байт

Разом: ~40-48 байт на елемент!

→ TreeSet у 3-4 рази більший за HashSet

Cache Locality проблема

Вузли дерева розкидані по Heap:
  [Entry1]...[Entry2]...[Entry3]

Кожен перехід до нащадка = cache miss!
  → Очікування з RAM: 100+ циклів

→ Ітерація TreeSet повільніша за HashSet

Java 21: SequencedSet

// TreeSet → SequencedSet (SequencedSet — вимагає Java 21+, недоступно на Java 11/17.)
set.getFirst();   // Найменший елемент
set.getLast();    // Найбільший елемент
set.reversed();   // Зворотний порядок (view)

// addFirst/addLast → UnsupportedOperationException
// → Порядок дерева фіксований!

View семантика

NavigableSet<Integer> view = set.subSet(3, true, 7, true);
// → "Живе" представлення, не копія!

view.add(5);       // Додає у ВИХІДНИЙ set
set.remove(5);     // Видаляє з view теж!

view.add(10);      // → IllegalArgumentException!
// → 10 поза діапазоном [3, 7]

Custom Comparator з null

// TreeSet не приймає null за замовчуванням
// Але можна через Comparator:
TreeSet<String> set = new TreeSet<>(
    Comparator.nullsFirst(Comparator.naturalOrder())
);
set.add(null);  // OK! null перший

Spliterator оптимізації

Spliterator<Integer> spliterator = set.spliterator();
// Характеристики:
//   SORTED   → Stream API оптимізує
//   DISTINCT → distinct() безкоштовний
//   SIZED    → відомий розмір

set.stream()
   .distinct()  // → Нічого не робить! Вже унікальні
   .count();    // → O(1), знає розмір

Production Experience

Реальний сценарій: Tax brackets

// Податкові ставки за порогом доходу
NavigableMap<Integer, Double> taxBrackets = new TreeMap<>();
taxBrackets.put(0, 0.0);      // 0% до 0
taxBrackets.put(10000, 0.1);  // 10% до 10к
taxBrackets.put(50000, 0.2);  // 20% до 50к

// Знайти ставку для доходу 35,000
double rate = taxBrackets.floorEntry(35000).getValue();
// → 0.1 (10%)

// HashMap НЕ зможе! Потрібне сортування

Best Practices

TreeMap всередині → O(log n) операції
compareTo = equals контракт!
null заборонений (без custom Comparator)
View = live, не копія
Java 21 → SequencedSet API
Cache miss при ітерації — враховуйте
Пам’ять у 3-4 рази більша за HashSet

Резюме для Senior

TreeSet = TreeMap + PRESENT заглушка
Червоно-чорне дерево → O(log n), балансування
compareTo визначає унікальність, не equals
NavigableSet → floor/ceiling/subSet
View = live представлення, O(1) створення
Cache Locality погана → вузли розкидані
Memory ~40-48 байт на елемент
SequencedSet (Java 21) → getFirst/reversed

🎯 Шпаргалка для інтерв’ю

Обов’язково знати:

TreeSet = адаптер над TreeMap, елементи зберігаються як ключі, значення = static final Object PRESENT
Всередині: червоно-чорне дерево (самобалансувальне бінарне дерево), висота завжди O(log n)
Складність: O(log n) для add/remove/contains — повільніший за HashSet (O(1))
NavigableSet API: floor, ceiling, lower, higher, subSet, headSet, tailSet
Не приймає null (без custom Comparator) — NullPointerException
compareTo визначає унікальність, а не equals — якщо compareTo = 0, елемент не додасться
Memory: ~40-48 байт на елемент (left, right, parent, color) — у 3-4 рази більше за HashSet
Cache locality погана — вузли розкидані по heap, кожен перехід = cache miss
View (subSet і т.д.) = live представлення, не копія, O(1) створення

Часті уточнюючі запитання:

Чому TreeSet повільніший за HashSet? — O(log n) через дерево + cache miss при кожному переході між вузлами.
Що буде якщо compareTo та equals не узгоджені? — TreeSet може вважати різні елементи (за equals) однаковими (за compareTo = 0) — втрата даних.
Як додати null у TreeSet? — Через Comparator.nullsFirst(Comparator.naturalOrder()).
Навіщо потрібні View (subSet) та які у них обмеження? — Live представлення діапазону. Можна додавати тільки елементи всередині діапазону — інакше IllegalArgumentException.

Червоні прапорці (НЕ говорити):

❌ «TreeSet використовує equals для порівняння елементів» — використовує compareTo!
❌ «TreeSet швидший за HashSet» — у 50 разів повільніший через O(log n) та cache miss
❌ «TreeSet можна використовувати з null за замовчуванням» — ні, тільки з custom Comparator
❌ «subSet створює копію даних» — це live view, зміни відображаються у вихідній множині

Пов’язані теми:

[[11. В чому різниця між HashSet, LinkedHashSet та TreeSet]]
[[15. В чому різниця між HashMap, LinkedHashMap та TreeMap]]
[[16. Коли використовувати TreeMap]]
[[14. Що таке Map і які реалізації існують]]