Обычное дерево поиска хорошо, пока сбалансировано, но вырождается в список, если данные вставлять по порядку, — и поиск падает с O(log N) до O(N). Красно-чёрное дерево решает эту проблему: оно само себя балансирует при каждой вставке и удалении, гарантируя O(log N) при любом порядке данных. Плата — усложнение алгоритма.
Идея: не дать дереву перекоситься
Балансировка означает, что дерево не должно становиться слишком «однобоким» — глубина ветвей должна оставаться примерно одинаковой. Полностью выравнивать дерево при каждой вставке дорого. Красно-чёрное дерево идёт на компромисс: оно не идеально сбалансировано, но гарантирует, что самая длинная ветвь не более чем вдвое длиннее самой короткой. Этого достаточно, чтобы удержать O(log N).
Чтобы отслеживать баланс, каждому узлу приписывают цвет — красный или чёрный. Цвет — это не данные, а служебная пометка, по которой дерево понимает, когда пора перестраиваться.
Красно-чёрные правила
Дерево считается сбалансированным, пока соблюдаются четыре правила:
- каждый узел либо красный, либо чёрный;
- корень всегда чёрный;
- у красного узла оба потомка чёрные (красные узлы не идут подряд);
- на любом пути от узла вниз до края число чёрных узлов одинаково.
Смысл в четвёртом правиле: оно не даёт одной ветви стать намного длиннее другой. Пока правила выполняются, дерево гарантированно неплохо сбалансировано. Как только вставка их нарушает, дерево восстанавливает их — и заодно баланс.
Два инструмента восстановления
Правила чинят двумя приёмами.
Перекраска (color flip) — просто смена цветов узлов. Дешёвая операция: иногда достаточно перекрасить родителя и «дядю» узла, чтобы устранить два красных подряд.
Поворот (rotation) — перестройка формы дерева. При повороте узел «опускается», а его потомок «поднимается» на его место, при этом правило «левый меньше, правый больше» сохраняется. Повороты бывают левые и правые; они физически выравнивают перекошенную ветвь. Именно повороты переносят узлы так, чтобы дерево стало ниже и ровнее.
Как это работает при вставке
Новый узел всегда вставляют красным (чтобы не нарушить правило о числе чёрных узлов) на обычное место дерева поиска. Если его родитель чёрный — всё в порядке, готово. Если красный — возникают два красных подряд (нарушение правила 3), и дерево чинит это перекрасками и поворотами, поднимаясь от места вставки к корню. В конце корень при необходимости красят в чёрный. Число таких исправлений невелико — пропорционально высоте дерева, то есть O(log N).
Зачем это на практике
Красно-чёрные деревья — не учебная экзотика: на них построены упорядоченные коллекции во многих стандартных библиотеках (например, отсортированные словари и множества). Их берут, когда нужна структура с гарантированно быстрыми поиском, вставкой и удалением и с сохранением порядка ключей (чего не даёт хеш-таблица). Реализовать их с нуля сложно из-за множества случаев в поворотах и перекрасках, поэтому обычно пользуются готовыми.
Коротко
- Обычное дерево поиска вырождается на отсортированных данных; красно-чёрное дерево балансируется само и держит O(log N) при любом порядке вставки.
- Баланс отслеживают через цвет узлов (красный/чёрный) и четыре правила; ключевое — одинаковое число чёрных узлов на всех путях вниз.
- Нарушенные вставкой правила чинят перекраской и поворотами, поднимаясь к корню; это стоит O(log N).
- Дают быстрые поиск/вставку/удаление с сохранением порядка; сложны в реализации — обычно берут готовые из библиотек.
Дальше — деревья 2-3-4: другой способ гарантировать баланс, из которого естественно вырастают B-деревья для баз данных.