Какое дерево лежит в основе TreeMap?

Red-Black Tree в TreeMap

TreeMap использует структуру данных Red-Black Tree (красно-чёрное дерево) для хранения и организации элементов. Это одна из самых важных реализаций сбалансированных двоичных деревьев поиска.

Что такое Red-Black Tree?

Red-Black Tree — это самобалансирующееся двоичное дерево поиска с дополнительными свойствами для обеспечения эффективности операций.

Свойства Red-Black Tree

1. Каждый узел окрашен в красный или чёрный цвет
2. Корень всегда чёрный
3. Листья (null) всегда чёрные (так называемые sentinel nodes)
4. Красный узел не может иметь красного потомка (родитель красного узла должен быть чёрным)
5. Все пути от узла к листьям должны содержать одинаковое количество чёрных узлов (black-height)

Эти свойства гарантируют, что дерево остается примерно сбалансированным.

Пример структуры

        [10-black]
       /          \
   [5-red]      [15-black]
   /    \         /      \
[3-b]  [7-b]   [12-r]   [20-b]

Временная сложность операций TreeMap

// Все основные операции имеют O(log n) сложность благодаря балансировке
TreeMap<Integer, String> map = new TreeMap<>();

map.put(5, "Five");              // O(log n)
map.get(5);                       // O(log n)
map.remove(5);                    // O(log n)
map.containsKey(5);               // O(log n)
map.firstKey();                   // O(1)
map.lastKey();                    // O(1)
map.headMap(10);                  // O(log n)
map.subMap(5, 15);                // O(log n + k) где k - размер результата

Сравнение с другими структурами

// HashMap - O(1) в среднем, но не отсортирован
HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(5, "Five");
// Без гарантии порядка

// TreeMap - O(log n), но отсортирован
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(5, "Five");
// Элементы в порядке сортировки

// LinkedHashMap - O(1), сохраняет порядок вставки
LinkedHashMap<Integer, String> linkedMap = new LinkedHashMap<>();
linkedMap.put(5, "Five");
// Элементы в порядке вставки

Использование TreeMap

TreeMap<Integer, String> map = new TreeMap<>();
map.put(50, "Fifty");
map.put(30, "Thirty");
map.put(70, "Seventy");
map.put(20, "Twenty");
map.put(40, "Forty");

// Итерация в отсортированном порядке
for (int key : map.keySet()) {
    System.out.println(key); // 20, 30, 40, 50, 70
}

// Навигационные методы
System.out.println(map.firstKey());    // 20
System.out.println(map.lastKey());     // 70
System.out.println(map.lowerKey(50));  // 40 - наибольший < 50
System.out.println(map.floorKey(50));  // 50 - наибольший <= 50
System.out.println(map.higherKey(50)); // 70 - наименьший > 50
System.out.println(map.ceilingKey(50));// 50 - наименьший >= 50

// Range операции
Map<Integer, String> submap = map.subMap(30, 70); // [30, 70)
Map<Integer, String> headmap = map.headMap(50);   // < 50
Map<Integer, String> tailmap = map.tailMap(50);   // >= 50

Балансировка при вставке/удалении

Когда TreeMap вставляет или удаляет элемент, он может нарушить свойства Red-Black Tree. Поэтому дерево выполняет rotation (ротации) и перекраску узлов:

// При вставке элемента может быть нарушено свойство 4
// (красный узел с красным потомком)
// TreeMap автоматически выполняет ротации и перекраску

TreeMap<Integer, String> map = new TreeMap<>();
for (int i = 1; i <= 10; i++) {
    map.put(i, String.valueOf(i));
    // После каждой вставки дерево остается сбалансированным
}

// Высота дерева не превышает 2 * log(n)
int maxHeight = (int)(2 * Math.log(map.size()) / Math.log(2));
System.out.println("Max height: " + maxHeight);

Когда использовать TreeMap

Используй TreeMap когда:

• Нужно хранить элементы в отсортированном порядке
• Нужны диапазонные операции (subMap, headMap, tailMap)
• Нужна навигация (firstKey, lastKey, lowerKey, higherKey и т.д.)
• Используется натуральный порядок элементов

// Пример: хранение событий в хронологическом порядке
TreeMap<LocalDateTime, String> events = new TreeMap<>();
events.put(LocalDateTime.of(2024, 3, 1, 10, 0), "Event 1");
events.put(LocalDateTime.of(2024, 3, 15, 14, 30), "Event 2");
events.put(LocalDateTime.of(2024, 3, 20, 9, 15), "Event 3");

// Все события автоматически в хронологическом порядке
for (LocalDateTime time : events.keySet()) {
    System.out.println(time);
}

// События за конкретный период
LocalDateTime start = LocalDateTime.of(2024, 3, 10, 0, 0);
LocalDateTime end = LocalDateTime.of(2024, 3, 19, 23, 59);
Map<LocalDateTime, String> rangeEvents = 
    events.subMap(start, end);

Избегай TreeMap когда:

• Нужна только быстрая вставка/поиск (используй HashMap)
• Нужен случайный доступ (используй List)
• Не нужна сортировка

Пользовательский компаратор

// TreeMap с обратной сортировкой
TreeMap<Integer, String> reverseMap = new TreeMap<>(
    Collections.reverseOrder()
);
reverseMap.put(30, "Thirty");
reverseMap.put(10, "Ten");
reverseMap.put(20, "Twenty");

for (int key : reverseMap.keySet()) {
    System.out.println(key); // 30, 20, 10
}

// Пользовательский компаратор
TreeMap<String, Integer> customMap = new TreeMap<>(
    Comparator.comparingInt(String::length)
        .thenComparing(String::compareTo)
);
customMap.put("hello", 1);
customMap.put("world", 2);
customMap.put("hi", 3);

Резюме

Red-Black Tree — это идеальная структура для TreeMap потому что:

• Гарантирует O(log n) для всех операций поиска/вставки/удаления
• Остается сбалансированным автоматически
• Позволяет эффективно проходить элементы в отсортированном порядке
• Поддерживает навигационные операции (first, last, lower, higher и т.д.)

Это делает TreeMap идеальным выбором для приложений, которым нужны отсортированные данные с быстрым доступом.