Ответ
TreeMap<K, V> в Java реализован на основе красно-черного дерева (Red-Black Tree) — самобалансирующегося бинарного дерева поиска (BST). Балансировка происходит автоматически при вставке и удалении элементов для поддержания логарифмической высоты дерева.
Правила красно-черного дерева:
- Каждый узел имеет цвет: красный или черный.
- Корень всегда черный.
- Листья (null-узлы) считаются черными.
- Два красных узла не могут быть смежными (красный узел не может иметь красного родителя или красного потомка).
- Путь от любого узла до каждого из его листьев содержит одинаковое количество черных узлов (свойство черной высоты).
Операции балансировки: При нарушении правил после вставки/удаления применяются преобразования:
- Перекрашивание (Recoloring): Изменение цвета узлов.
- Повороты (Rotations):
- Левый поворот
- Правый поворот
Пример вставки с балансировкой:
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "A"); // Вставка корня (черный)
map.put(20, "B"); // Вставка красного узла -> правило 4 может нарушиться
map.put(30, "C"); // Может потребоваться поворот и перекрашивание
// Дерево автоматически перестроится, чтобы остаться сбалансированным.Результат: Гарантированная временная сложность O(log n) для операций put(), get(), remove(), в отличие от несбалансированного BST, который может выродиться в список (O(n)).