TreeMap / TreeSet

TreeMap и TreeSet — версии Map/Set, которые всегда держат элементы отсортированными. В обычном HashMap/HashSet порядок не гарантирован, а в TreeMap/TreeSet — элементы всегда идут по возрастанию (или по своему компаратору):

Set<Integer> sorted = new TreeSet<>();
sorted.add(5);
sorted.add(1);
sorted.add(3);
sorted;   // [1, 3, 5] — всегда по порядку, без усилий с твоей стороны

Map<String, Integer> ages = new TreeMap<>();
ages.put("Борис", 30);
ages.put("Артур", 25);
ages;   // {Артур=25, Борис=30} — ключи по алфавиту

Копнуть глубже

Свой порядок сортировки задаётся через Comparator:

Set<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
byLength.add("ab");
byLength.add("a");
byLength.add("abc");
byLength;   // [a, ab, abc] — по длине, а не по алфавиту

Бонусные методы, которых нет у HashMap/HashSet, ровно потому что есть порядок:

TreeSet<Integer> nums = new TreeSet<>(Set.of(1, 5, 10, 20));
nums.first();        // 1 — наименьший
nums.last();          // 20 — наибольший
nums.higher(5);       // 10 — ближайший больше 5
nums.lower(10);       // 5  — ближайший меньше 10

Под капотом

TreeMap/TreeSet построены на красно-чёрном дереве (red-black tree) — самобалансирующемся бинарном дереве поиска. Это даёт гарантию O(log n) на вставку, удаление и поиск — медленнее, чем O(1) у HashMap, но взамен элементы всегда отсортированы.

Платишь за порядок логарифмической скоростью вместо константной — выбирай TreeMap только когда сортировка реально нужна, иначе HashMap будет быстрее.

🎤 Закрыл тему, если можешь объяснить:

• чем `TreeMap`/`TreeSet` отличаются от `HashMap`/`HashSet`;
• на чём основан `TreeMap` и почему он медленнее `HashMap` (если дошёл до 3-го слоя).