Сбалансированное дерево: почему дерево иногда вырождается в список

Скорость дерева зависит от его высоты — а высота сильно зависит от того, в каком порядке в него клали элементы.

Сбалансированное дерево — это дерево, которое следит за своей формой и не позволяет себе вытянуться в бесполезную цепочку.

Откуда у дерева скорость

Деревья поиска хороши тем, что на каждом шаге отбрасывают половину вариантов: больше искомого — идём вправо, меньше — влево. Если дерево «пушистое» и раскидистое, путь от вершины до любого листа короткий, и поиск занимает время, пропорциональное высоте — O(log n). У миллиона элементов это около двадцати шагов. Очень быстро.

Но есть подвох: эта скорость держится только пока дерево остаётся низким и широким. А оно таким остаётся не всегда.

Как дерево вырождается

Представьте, что вы вставляете в дерево поиска числа уже по порядку: 1, 2, 3, 4, 5. Каждое следующее больше предыдущего, поэтому всё время уходит вправо. Получается не дерево, а наклонная цепочка — по сути, тот же связный список.

И вся прелесть теряется. Чтобы найти пятёрку, придётся пройти все пять узлов: высота дерева стала равна числу элементов. Поиск из быстрого O(log n) превратился в медленный O(n). Структура называется деревом, а ведёт себя как список — худший случай.

В чём корень беды

Дерево поиска само по себе никак не следит за своей формой. Какой порядок вставки ему дали — такую форму оно и приняло. На случайных данных деревья обычно вырастают неплохими, но полагаться на удачу нельзя: упорядоченный или почти упорядоченный ввод гарантированно его испортит.

Идея балансировки

Сбалансированное дерево решает проблему так: после каждой вставки и удаления оно проверяет, не перекосило ли его, и при необходимости само себя выпрямляет. Цель — держать высоту около log n, что бы в него ни добавляли.

Главный инструмент выпрямления — вращение (поворот). Это локальная перестройка нескольких узлов, которая меняет, кто кому родитель, но сохраняет порядок «меньше слева, больше справа». Перекосило вправо — поворот налево вытягивает правую ветку наверх и укорачивает дерево. Несколько таких поворотов — и баланс восстановлен.

Что значит «сбалансировано»

Разные деревья меряют баланс по-своему. AVL-дерево строгое: оно следит, чтобы у каждого узла высоты левого и правого поддеревьев отличались не больше чем на единицу. Красно-чёрное дерево мягче: оно красит узлы в два цвета и соблюдает правила раскраски, которые не дают одной ветке стать вдвое длиннее другой. AVL держит форму идеальнее и потому чуть быстрее ищет; красно-чёрное реже перестраивается и потому быстрее меняется. Компромисс на любой вкус.

Где это всё работает

Сбалансированные деревья — невидимые трудяги. TreeMap и TreeSet в Java построены на красно-чёрных деревьях. Индексы в базах данных используют родственные сбалансированные структуры (B-деревья), чтобы поиск по таблице оставался быстрым при миллиардах строк. Планировщик задач в ядре Linux одно время выбирал следующий процесс именно с помощью красно-чёрного дерева.

Суть проста: обычное дерево поиска быстрое «в среднем», но беззащитно перед неудачным порядком данных. Балансировка превращает «обычно быстро» в «быстро всегда, при любом вводе» — а в серьёзных системах гарантия дороже везения.