Разбор красно-черных деревьев: пошаговая инструкция с видео

Красно-черные деревья — это один из фундаментальных алгоритмов и структур данных в компьютерных науке, балансирующее бинарное дерево поиска (БДП). Оно обеспечивает гарантированную логарифмическую сложность основных операций (вставка, удаление, поиск) даже в худшем случае, что делает его основой для реализации ассоциативных массивов (например, в стандартных библиотеках C++ и Java). Однако их алгоритмы балансировки, основанные на перекрашивании узлов и поворотах, часто кажутся сложными для понимания. Данная инструкция разбирает их по шагам, сопровождая каждый этап визуальными аналогиями.

Основные правила, которые делают дерево «красно-черным», всего четыре: 1) Каждый узел либо красный, либо черный. 2) Корень дерева всегда черный. 3) Все листья (NIL-узлы, пустые потомки) считаются черными. 4) Если узел красный, то оба его потомка обязаны быть черными (красный узел не может иметь красного потомка). 5) Для каждого узла все простые пути от него до любых листьев-потомков содержат одинаковое количество черных узлов (черная высота). Ключевое следствие этих правил: самый длинный путь (чередуя красные и черные узлы) не более чем в два раза длиннее самого короткого (состоящего только из черных). Это и обеспечивает сбалансированность.

Чтобы понять, как поддерживать эти инварианты при вставке, рассмотрим пошаговый алгоритм. Шаг 1: Вставка как в обычное БДП. Мы проходим от корня, находим место для нового узла (Z) и добавляем его. Новый узел всегда окрашивается в КРАСНЫЙ. Почему? Потому что вставка черного узла сразу нарушит правило 5 (черная высота для путей через этот узел увеличится). Вставка красного может нарушить только правило 4 (конфликт с красным родителем).

Шаг 2: Анализ окружения. После вставки красного узла Z мы смотрим на его родителя P. Если P черный — все правила соблюдены, вставка завершена. Но если P тоже красный — у нас «двойное красное» нарушение. Теперь нужно смотреть на «дядю» U (брата родителя P). Далее рассматривается несколько случаев, которые иллюстрируют, как дерево «само себя лечит».

Случай 1: Дядя U красный. Это самый простой случай для понимания. Решение: перекрашиваем родителя P и дядю U в черный цвет, а их общего родителя — дедушку G (который был черным по правилу 4) — в красный. Теперь локально правило 4 восстановлено (P и U стали черными), но дедушка G стал красным. Это могло создать новый конфликт на уровне выше (если его родитель тоже красный). Поэтому мы рекурсивно применяем алгоритм балансировки к узлу G, как к новому нарушителю. Этот процесс может подняться до корня.

Случай 2: Дядя U черный (или NIL), и новый узел Z — «внутренний» потомок относительно дедушки G (т.е. Z — правый ребенок, а P — левый ребенок, или наоборот). Это zig-zag конфигурация. Решение: сначала выполняется поворот вокруг родителя P в направлении, противоположном положению Z. Это превращает ситуацию в Случай 3. Поворот — это операция, меняющая связи между узлами, чтобы изменить высоту поддеревьев, не нарушая порядка БДП (левое поддерево < узел < правое поддерево).

Случай 3: Дядя U черный, и новый узел Z — «внешний» потомок (Z и P оба левые или оба правые дети). Решение: перекрашиваем родителя P в черный, дедушку G — в красный. Затем выполняем поворот вокруг дедушки G в направлении, противоположном положению P. После этого правило 4 восстанавливается, а черная высота остается неизменной для всего поддерева с корнем в G. Это завершающий случай, балансировка останавливается.

Для закрепления теории критически важна визуализация. В текстовом формате мы можем лишь описать шаги, но представьте себе анимацию, где: 1) Новый красный узел появляется, создавая конфликт с красным родителем. 2) Цвета P, U и G меняются, как в Случае 1, волна перекрашивания идет вверх. 3) В Случае 2 и 3 вы видите, как узлы плавно поворачиваются, меняя свою иерархию, подобно тому, как механик переставляет шестеренки, чтобы сбалансировать механизм. Поворот — это не магия, а четко определенная перелинковка указателей.

Алгоритм удаления сложнее, но основан на аналогичных идеях: сначала удаление как из обычного БДП, а затем устранение «двойного черного» нарушения, которое может возникнуть при удалении черного узла. И здесь на помощь приходят перекрашивания и повороты, чтобы восстановить черную высоту.

Почему это работает в реальности? Потому что набор случаев (1, 2, 3) исчерпывает все возможные конфигурации вокруг нарушающего узла. Алгоритм либо завершается локально (случай 3), либо рекурсивно поднимается вверх (случай 1), но не более чем на O(log n) уровней. Таким образом, общая сложность вставки остается O(log n).

Изучая красно-черные деревья, не пытайтесь просто запомнить случаи. Поймите их цель: сохранить черную высоту (правило 5) и избежать двух красных узлов подряд (правило 4). Повороты и перекрашивания — это инструменты для достижения этой цели. Рекомендуется не только читать, но и самостоятельно реализовать дерево на выбранном языке программирования, а также использовать визуализаторы, где вы можете пошагово выполнять вставку и наблюдать, как дерево балансируется. Это превратит абстрактные правила в интуитивно понятный механизм.