Красно-чёрное дерево: баланс по цвету

Если ты понимаешь идею красно-чёрного дерева (чёрная высота одинакова, красный без красного ребёнка → путь не более чем вдвое длиннее), знаешь, что оно балансирует мягче АВЛ и потому вращает реже, листай до «Теперь сам».

Как думаешь, можно ли балансировать, не считая высоты

АВЛ хранит в каждом узле высоту и после каждого изменения кропотливо её пересчитывает вверх до корня - строго, но хлопотно, и вращает часто. А что если ослабить требование? Нам ведь не нужен ИДЕАЛЬНЫЙ баланс - достаточно, чтобы высота осталась O(log n). Для этого хватит гарантии «самый длинный путь не сильно длиннее самого короткого». Как обеспечить её без арифметики высот? Идея неожиданная: раскрасить узлы в два цвета и потребовать, чтобы чёрных на всех путях было поровну, а красные не шли подряд. Тогда пути не смогут сильно разойтись по длине - и высота останется логарифмической, но правило проще чинить, чем точный баланс высот.

На что это похоже

Дорога с обязательными «чёрными» столбами через равные промежутки и необязательными «красными» знаками между ними, причём два красных знака подряд ставить запрещено. Тогда на любом отрезке дороги число столбов одинаково, а красных знаков между двумя столбами - максимум один. Значит самый «загруженный» отрезок (столб-знак-столб-знак…) не длиннее удвоенного самого «пустого» (только столбы). Дорога не может внезапно растянуться. Красно-чёрное дерево держит форму этим же приёмом: чёрные узлы - «столбы» (их поровну на всех путях), красные - «знаки» (не подряд), и путь не растягивается больше чем вдвое.

Механизм: пять правил и их следствие

Каждый узел красный или чёрный. Пустые ссылки считаются чёрными «листьями». Правила:

1. каждый узел красный или чёрный
2. корень чёрный
3. все пустые листья чёрные
4. у красного узла оба ребёнка ЧЁРНЫЕ (нет двух красных подряд)
5. на любом пути от узла вниз до листьев - ОДИНАКОВОЕ число чёрных узлов
   (это число, не считая пустых листьев, называют ЧЁРНОЙ ВЫСОТОЙ)

Главное следствие правил 4 и 5: возьми самый короткий путь (все узлы чёрные) и самый длинный (чёрные вперемежку с красными). Чёрных на них поровну (правило 5), а красных между чёрными не больше одного (правило 4) - значит длинный путь не больше чем ВДВОЕ длиннее короткого. Отсюда высота ≤ 2·log₂(n+1) - Θ(log n). После вставки новый узел красят КРАСНЫМ (чтобы не сбить чёрную высоту) и чинят возможные нарушения: два красных подряд лечатся либо ПЕРЕКРАСКОЙ (если «дядя» красный - просто перекрашиваем, поворотов нет), либо ВРАЩЕНИЕМ с перекраской (если дядя чёрный). Обычно хватает пары операций у места вставки.

Правило

Красно-чёрное дерево балансируется ЦВЕТОМ, а не высотой. Пять правил, суть двух главных: на любом пути вниз одинаковое число ЧЁРНЫХ узлов (правило 5), и у красного нет красных детей (правило 4). Отсюда длинный путь не более чем ВДВОЕ длиннее короткого → высота Θ(log n), операции Θ(log n). Баланс МЯГЧЕ, чем у АВЛ: дерево кособочее, зато при удалении нужно меньше вращений (часто хватает ПЕРЕКРАСКИ без поворотов). Поэтому красно-чёрные деревья - выбор стандартных библиотек: чуть медленнее поиск, дешевле изменения.

Разбор: почему цветовые правила дают ту же Θ(log n), что и высоты АВЛ

АВЛ ограничивает разницу ВЫСОТ, красно-чёрное - разницу ДЛИН ПУТЕЙ через цвет; и то, и другое запирает высоту в Θ(log n), но разными средствами. Ключ - «чёрная высота»: число чёрных узлов на пути вниз, одинаковое для всех путей (правило 5). Обозначим её bh. Тогда в дереве не меньше 2^bh − 1 узлов (каждый чёрный уровень как минимум удваивает число узлов - можно доказать индукцией), значит bh ≤ log₂(n+1). А полная высота h не больше 2·bh (правило 4: между двумя чёрными не больше одного красного, так что красные лишь удваивают длину). Итого h ≤ 2·log₂(n+1) - логарифм. Разница с АВЛ количественная: АВЛ держит h ≤ 1.44·log₂ n + 1 (строже, ниже дерево), красно-чёрное - h ≤ 2·log₂(n+1) (мягче, чуть выше). Оба Θ(log n), но у АВЛ константа меньше - поиск чуть быстрее, ценой более частых вращений.

Разбор: почему библиотеки выбирают красно-чёрное, а не АВЛ

При равной асимптотике выбор решает КОНСТАНТА изменений. У АВЛ после удаления перебалансировка может идти вращениями на всём пути до корня (до O(log n) поворотов). У красно-чёрного дерева доказано: вставка - не больше 2 вращений, удаление - не больше 3, а остальные нарушения гасятся ПЕРЕКРАСКОЙ (изменить цвет узла - O(1), без перестройки ссылок; цепочка перекрасок может подняться до корня - O(log n) в худшем случае, но это лишь смена цветов, без вращений). Перекраска дешевле поворота и не двигает узлы. Для контейнеров общего назначения (std::map, TreeMap, множества ядра ОС) нагрузка смешанная - много и вставок, и удалений, - поэтому экономия на вращениях важнее, чем чуть более быстрый поиск АВЛ. Отсюда исторический выбор: красно-чёрное дерево - «универсал» (сбалансированный компромисс), АВЛ - «специалист» под поиск-интенсивные задачи. Это тот же мотив, что везде в разделе: строгость баланса покупается ценой изменений, и оптимум зависит от нагрузки.

Что ломается без этого

Первая ошибка - красить новый узел ЧЁРНЫМ при вставке: это сразу собьёт чёрную высоту (правило 5) на его пути, и чинить придётся сложнее. Новый узел красят КРАСНЫМ - он не меняет число чёрных. Вторая - забыть перекрасить корень в чёрный после операций (правило 2): корень обязан быть чёрным. Третья - считать, что красно-чёрное всегда ниже или всегда выше АВЛ конкретно: оно в среднем чуть ВЫШЕ (мягче баланс), поэтому поиск чуть медленнее - если поиск критичен, а изменения редки, АВЛ лучше. Четвёртая - лезть реализовывать красно-чёрное дерево вручную в проде: оно знаменито обилием случаев в удалении; на практике берут готовое из стандартной библиотеки, а руками пишут разве что для учёбы или очень специальных нужд.

Зачем это в работе

Красно-чёрное дерево - самая используемая сбалансированная структура в реальном коде, часто невидимо для программиста. std::map/std::set/std::multimap в C++, TreeMap/TreeSet в Java, ассоциативные контейнеры многих языков, планировщик задач CFS в ядре Linux (задачи упорядочены по времени выполнения), таймеры - всё это красно-чёрные деревья. Знать их - значит понимать, ЧТО именно даёт упорядоченный контейнер: гарантированные O(log n) на всё, обход по порядку, поиск ближайшего и диапазоны - и почему он выбран вместо АВЛ (дешевле изменения при той же асимптотике поиска) и вместо хеш-таблицы (порядок и гарантия худшего случая ценой множителя log n). А сама идея «балансировать не точным измерением, а простым локальным правилом (цветом), которое гарантирует нужное свойство» - образец инженерного компромисса, который встретится ещё не раз.

Теперь сам

Почему из правил «чёрных на всех путях поровну» и «нет двух красных подряд» следует, что самый длинный путь не более чем вдвое длиннее самого короткого? И почему это даёт высоту Θ(log n)?