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

На відміну від HashSet, де порядок елементів є хаотичним і залежить від хеш-кодів, у TreeSet елементи впорядковані або за їхнім природним порядком (Natural Ordering через інтерф...

🟢 Junior Level

1. Призначення та основні властивості

TreeSet — це реалізація інтерфейсу NavigableSet (який розширює SortedSet), у якій усі елементи автоматично зберігаються у відсортованому порядку, а дублікати суворо виключаються.

На відміну від HashSet, де порядок елементів є хаотичним і залежить від хеш-кодів, у TreeSet елементи впорядковані або за їхнім природним порядком (Natural Ordering через інтерфейс Comparable), або за допомогою переданого в конструктор об’єкта Comparator.

// Природне сортування (Natural Order)
Set<Integer> numbers = new TreeSet<>();
numbers.add(42);
numbers.add(10);
numbers.add(5);
numbers.add(99);

System.out.println(numbers); // Завжди виведе: [5, 10, 42, 99]

2. Ключові особливості `TreeSet`

Автоматичне сортування: при кожній вставці новий елемент негайно займає правильну позицію в структурі.
Внутрішня будова: є обгорткою над збалансованим червоно-чорним деревом TreeMap.
Заборона null: спроба додати null у стандартний TreeSet призводить до викидання NullPointerException, оскільки null неможливо порівняти з іншими елементами (null.compareTo(...)).
Складність операцій: основні операції (add, remove, contains) виконуються за $O(\log N)$, що повільніше за середній час $O(1)$ у HashSet.

🟡 Middle Level

1. Архітектура під капотом: червоно-чорне дерево

TreeSet делегує всі виклики внутрішньому екземпляру NavigableMap<E, Object> m (за замовчуванням TreeMap):

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();

    public TreeSet() {
        this(new TreeMap<>());
    }

    public boolean add(E e) {
        return m.put(e, PRESENT) == null;
    }
}

В основі TreeMap лежить червоно-чорне дерево (Red-Black Tree) — самобалансоване бінарне дерево пошуку з такими ключовими інваріантами:

Кожен вузол є або червоним (RED), або чорним (BLACK).
Корінь дерева завжди чорний.
Усі листки (NIL/null) вважаються чорними.
Якщо вузол червоний, обидва його дочірні вузли обов’язково є чорними (два червоні вузли не можуть іти поспіль).
Будь-який простий шлях від даного вузла до будь-якого листового вузла містить однакову кількість чорних вузлів (чорна висота).

Завдяки цим інваріантам найдовший шлях від кореня до листка не перевищує найкоротший більш ніж удвічі, що гарантує висоту дерева $h \le 2 \log_2(N + 1)$ і час пошуку, вставки та видалення строго $O(\log N)$. При порушенні балансу виконуються перефарбовування вузлів та повороти (лівий і правий).

        15(B)
       /     \
     9(R)    23(R)
    /   \        \
  3(B)  11(B)    30(B)

2. Принциповий парадокс: `compareTo()` проти `equals()`

[!WARNING] TreeSet повністю ігнорує методи hashCode() та equals()! Унікальність та еквівалентність елементів визначаються виключно результатом роботи Comparable.compareTo() або Comparator.compare(). Два елементи вважаються однаковими тоді й лише тоді, коли compare(a, b) == 0.

Це фундаментальне відхилення від загального контракту Set, який передбачає перевірку унікальності через equals():

// Класичний приклад із BigDecimal:
Set<BigDecimal> hashSet = new HashSet<>();
Set<BigDecimal> treeSet = new TreeSet<>();

BigDecimal d1 = new BigDecimal("1.0");
BigDecimal d2 = new BigDecimal("1.00");

// equals() порівнює значення ТА масштаб (scale):
System.out.println(d1.equals(d2));       // false (scale 1 проти scale 2)
// compareTo() порівнює виключно числове значення:
System.out.println(d1.compareTo(d2));    // 0

hashSet.add(d1);
hashSet.add(d2);
System.out.println(hashSet.size());      // 2 (обидва елементи додані!)

treeSet.add(d1);
treeSet.add(d2);
System.out.println(treeSet.size());      // 1 (d2 відкинутий як дублікат!)

Якщо в об’єктів compareTo() == 0, але equals() == false, TreeSet не збереже другий об’єкт. Це поширена причина прихованих помилок при роботі з бізнес-сутністями.

3. Навігаційні методи `NavigableSet`

TreeSet реалізує багатий інтерфейс NavigableSet, надаючи операції пошуку найближчих граничних значень та отримання зрізів:

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

// Пошук граничних елементів:
System.out.println(set.lower(30));    // 20 (строго < 30)
System.out.println(set.floor(30));    // 30 (найбільший <= 30)
System.out.println(set.ceiling(35));  // 40 (найменший >= 35)
System.out.println(set.higher(40));   // 50 (строго > 40)

// Черга з пріоритетом:
System.out.println(set.pollFirst()); // 10 (вилучає та видаляє найменший)
System.out.println(set.pollLast());  // 50 (вилучає та видаляє найбільший)

🔴 Senior Level

1. Архітектура діапазонів (Live Views) та їхні пастки

Методи отримання діапазонів (subSet, headSet, tailSet) не створюють нової колекції в пам’яті! Вони повертають легковажну «проєкцію» (View — внутрішній клас AscendingSubMap або DescendingSubMap), що делегує запити вихідному дереву з динамічною перевіркою меж:

TreeSet<Integer> set = new TreeSet<>();
for (int i = 1; i <= 10; i++) set.add(i);

NavigableSet<Integer> view = set.subSet(3, true, 7, true);
System.out.println(view); // [3, 4, 5, 6, 7]

// Модифікація через View змінює вихідний TreeSet:
view.remove(5);
System.out.println(set.contains(5)); // false!

// Додавання у вихідний TreeSet миттєво відображається у View:
set.add(4);

// Спроба вставити елемент поза межами діапазону View:
view.add(100); // Викине java.lang.IllegalArgumentException: key out of range

Створення subSet() виконується за константний час $O(1)$, проте утримання посилання на subSet не дозволяє збирачу сміття вивільнити з пам’яті все вихідне дерево.

2. Аналіз споживання пам’яті (Memory Footprint) та Cache Misses

Вузол TreeMap$Entry — одна з найгроміздкіших структур у стандартній бібліотеці Java:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

На 64-бітній JVM з увімкненим Compressed OOPs (-XX:+UseCompressedOops):

Заголовок об’єкта: 12 байтів
Поля: 5 посилань (key, value, left, right, parent) по 4 байти = 20 байтів
Примітивне поле color (boolean): 1 байт
Вирівнювання (Padding) до кратності 8 байтів: 7 байтів
Разом розмір одного вузла: 40 байтів (проти 32 байтів у HashMap$Node).
Без Compressed OOPs розмір ноди сягає 64 байтів!

Проблема апаратної локалізації кешу (Cache Locality):

Вузли дерева створюються в різні моменти часу і хаотично розкидані по всій купі. Під час обходу дерева кожен перехід за посиланням node.left чи node.right спричиняє CPU Cache Miss (штраф 100–300 тактів процесора на читання з RAM). Через це послідовна ітерація мільйоном елементів у TreeSet працює в 10–50 разів повільніше, ніж ітерація суміжним масивом ArrayList чи навіть HashSet.

3. Інтеграція з Java 21: `SequencedSet`

У Java 21 TreeSet реалізує інтерфейс SequencedSet, що надає уніфікований API для впорядкованих послідовностей:

TreeSet<String> set = new TreeSet<>(List.of("alpha", "beta", "gamma"));

System.out.println(set.getFirst()); // "alpha"
System.out.println(set.getLast());  // "gamma"

// Отримання реверсивного представлення за O(1):
SequencedSet<String> reversed = set.reversed();
System.out.println(reversed.getFirst()); // "gamma"

// Пастка: методи явного позиціонування заборонені!
set.addFirst("omega"); // Викине java.lang.UnsupportedOperationException!
set.addLast("omega");  // Викине java.lang.UnsupportedOperationException!

Чому addFirst() / addLast() викидають виняток: порядок елементів у дереві жорстко детермінований значеннями ключів та компаратором. Клієнтський код не може вручну призначити елемент першим або останнім у впорядкованій множині.

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

30-секундна відповідь (Elevator Pitch)

«TreeSet — це реалізація NavigableSet, що базується на самобалансованому червоно-чорному дереві TreeMap. Вона забезпечує зберігання унікальних елементів у відсортованому вигляді зі складністю $O(\log N)$ для додавання, видалення та пошуку. Принципова особливість: унікальність та рівність елементів перевіряються виключно через Comparable.compareTo() або переданий Comparator, повністю ігноруючи equals() та hashCode(). За замовчуванням забороняє null (викликає NullPointerException). Надає багатий API діапазонів (subSet, floor, ceiling), що повертає легковажні живі проєкції (Views) за $O(1)$».

4 каверзних питання на інтерв’ю з відповідями

1. Що відбудеться, якщо додати в `HashSet` та в `TreeSet` два об’єкти `BigDecimal("2.0")` та `BigDecimal("2.00")`?

Відповідь:

У HashSet буде збережено 2 елементи, оскільки HashSet використовує метод equals(). Метод BigDecimal.equals() перевіряє не лише числову величину, але й масштаб (scale). Оскільки scale дорівнює 1 та 2 відповідно, equals() поверне false.
У TreeSet опиниться лише 1 елемент, оскільки TreeSet використовує compareTo(). Метод BigDecimal.compareTo() порівнює виключно математичне значення (2.0 == 2.00), повертаючи 0. Другий об’єкт буде відхилено як дублікат.

2. Чи можна додати `null` у `TreeSet`?

Відповідь: За замовчуванням не можна — буде викинуто NullPointerException. Проте якщо створити TreeSet із користувацьким компаратором, який явно підтримує null (наприклад, new TreeSet<>(Comparator.nullsFirst(Comparator.naturalOrder()))), то елемент null успішно додасться (за компаратором він вважатиметься валідним мінімальним елементом).

3. Як влаштований метод `subSet()` і чи створює він копію даних?

Відповідь: Метод subSet() не копіює дані ($O(1)$ за часом і пам’яттю). Він повертає внутрішню проєкцію (AscendingSubMap / DescendingSubMap), що накладає фільтрацію за діапазоном ключів [fromKey, toKey] поверх вихідного дерева. Усі зміни у subSet негайно відбиваються у вихідному TreeSet і навпаки. Спроба додати у View елемент за межами його діапазону призводить до IllegalArgumentException.

4. Чому методи `addFirst()` та `addLast()`, що з’явилися в Java 21 через `SequencedSet`, викидають `UnsupportedOperationException` у `TreeSet`?

Відповідь: У TreeSet розташування елементів не залежить від виклику розробника — воно суворо зумовлене значеннями самих елементів та їхнім компаратором. Дозвіл виклику addFirst(x) зламав би інваріант сортування червоно-чорного дерева, тому ці методи оголошені непідтримуваними.

Типові помилки та Red Flags

❌ Неузгодженість compareTo() та equals(): Якщо a.compareTo(b) == 0, але a.equals(b) == false, TreeSet мовчки відкине об’єкт b, порушуючи контракт Set.
❌ Мутація полів об’єкта, що беруть участь у сортуванні: Якщо змінити поле ключа після додавання в TreeSet, дерево перейде в неузгоджений стан: бінарний пошук піде хибною гілкою, елемент стане неможливо знайти або видалити.
❌ Використання TreeSet заради збереження порядку вставки: Для збереження порядку додавання потрібен LinkedHashSet ($O(1)$), а не TreeSet ($O(\log N)$).
❌ Припущення, що TreeSet є потокобезпечним: TreeSet не синхронізований. Паралельний запис здатний зруйнувати внутрішню структуру червоно-чорного дерева. Потрібна зовнішня синхронізація або ConcurrentSkipListSet.

🟢 Junior Level

1. Призначення та основні властивості

2. Ключові особливості TreeSet

🟡 Middle Level

1. Архітектура під капотом: червоно-чорне дерево

2. Принциповий парадокс: compareTo() проти equals()

3. Навігаційні методи NavigableSet