Красно-чёрное дерево

Положите все 19 073 землетрясения из каталога USGS в красно-чёрное дерево в том порядке, в каком они случались. Дерево вырастет до 26 этажей: правила разрешают не больше 28, а АВЛ-дерево на тех же ключах обходится пятнадцатью. Самый свежий толчок лежит у красно-чёрного дерева на 26-м этаже — на самом дне. И всё же средний поиск в нём делает 13,79 сравнения против 13,28 у АВЛ-дерева, всего на 4 % больше. Именно красно-чёрные деревья стоят в ядре Linux, в std::map и в TreeMap. Ниже оба дерева растут из одних и тех же ключей — трёх настоящих потоков.

Слева АВЛ-дерево, справа красно-чёрное; ширина полосы — сколько узлов на этаже, по логарифмической шкале, так что полный этаж выглядит ступенькой треугольника. На времени землетрясений, где каждый ключ больше всех прежних, АВЛ-дерево получается почти идеальным, а у красно-чёрного под ровным треугольником тянется хвост — этажи с 16-го по 26-й, которых у АВЛ-дерева нет вовсе. На адресах сайта, которые в карте сайта идут кусками по алфавиту, хвост короче: 18 этажей против 16. На словах «Войны и мира», которые приходят почти вразнобой, высота одинаковая — 17. Зато красно-чёрное дерево меньше поворачивает: на словах романа 618 поворотов на тысячу вставок против 748 у АВЛ-дерева.

Идея

Каждый узел покрашен в красный или чёрный цвет. Чёрные узлы держат идеальное равновесие: на любом пути от узла вниз их одинаковое число. Красные — запас гибкости: красный узел не может стоять под красным, поэтому на любом пути красных не больше, чем чёрных, и самый длинный путь вниз не длиннее самого короткого больше чем вдвое. Вставка и удаление нарушают правила только рядом с местом изменения; чинят их перекрашивания, которые могут подниматься к корню, и несколько поворотов — не больше двух при вставке и трёх при удалении.

Правила обычно записывают пятью пунктами — так они перечислены и в комментарии к файлу lib/rbtree.c ядра Linux:

1. каждый узел красный или чёрный;
2. корень чёрный;
3. все листья — пустые ссылки — считаются чёрными;
4. оба ребёнка красного узла чёрные;
5. на всех путях от узла вниз до пустых листьев одинаковое число чёрных узлов.

Число чёрных узлов из пятого правила называют чёрной высотой. Первое и третье правила — договорённости, второе удобно, но не обязательно. Вся суть — в четвёртом и пятом. Сам по себе этот список ничего не объясняет: почему именно такие правила, откуда взялись случаи вставки и почему поворотов так мало. Объяснение одно, и оно видно, если посмотреть на дерево под другим углом.

Рентген: B-дерево внутри

Приклейте каждый красный узел к его чёрному родителю. Получатся узлы с одним, двумя или тремя ключами: чёрный сам по себе, чёрный с одним красным ребёнком, чёрный с двумя. Это B-дерево с узлами на три ключа и четыре ребёнка, его называют 2-3-4-деревом. Четвёртое правило запрещает склеивать больше: красный под красным дал бы узел на четыре ключа. А пятое правило — ровно то, что у B-дерева все листья на одной глубине: каждый склеенный узел содержит один чёрный узел, и чёрная высота — это число этажей 2-3-4-дерева.

Красно-чёрное дерево и придумали как запись B-дерева двоичными узлами: Рудольф Байер в 1972 году назвал его симметричным двоичным B-деревом. Каждое действие с цветами — действие с узлами B-дерева. Вставьте числа по одному и смотрите на нижнюю картинку.

Новый ключ всегда красный: он приклеивается к листу 2-3-4-дерева и чёрную высоту не трогает. Если родитель чёрный, в узле было место, и всё. Если родитель красный, бывает два случая.

• Дядя красный. Отец, дед и дядя — это узел 2-3-4-дерева, в котором уже три ключа, и новый оказался четвёртым. B-дерево делит переполненный узел и поднимает средний ключ к родителю. В красно-чёрном дереве это одно перекрашивание: отец и дядя чернеют, дед краснеет. Красный дед — это средний ключ, приклеенный к узлу этажом выше, и там всё может повториться. В сцене переполненный узел на мгновение появляется внизу с четырьмя ключами в оранжевой рамке. Если перекрашивание дошло до корня, корень снова красят в чёрный, и у 2-3-4-дерева появляется новый этаж — только так оно и растёт.
• Дядя чёрный. В узле было два ключа, стало три, но записан узел криво: два красных подряд. Поворот (или два, если узлы стоят зигзагом) переставляет те же три ключа так, чтобы средний стал чёрным, а крайние — его красными детьми. Узел 2-3-4-дерева не меняется, меняется только то, как он нарисован двоичными узлами; выше ничего не происходит.

Отсюда и знаменитое обещание: вставка делает не больше двух поворотов, потому что поворачивают только в последнем случае, а он завершает работу. Перекрашивания могут подниматься до корня, как деления в B-дереве, но и деления, и перекрашивания в среднем дёшевы: на словах романа их 0,524 на вставку. Удаление устроено так же — это слияние и перераспределение узлов 2-3-4-дерева, — только случаев больше; поворотов в нём не больше трёх.

Высота

У АВЛ-дерева граница строже — примерно 1,44·log₂ n, — и первая сцена показывает, что разница не только на бумаге. Листинг ниже прошёл по правому краю красно-чёрного дерева из землетрясений, от корня к самому новому ключу:

quake times in RB, from the root down to the newest key: BRBRBRBRBRBRBRBRBRBRBRBRBR (26 nodes)

Чёрный, красный, чёрный, красный — тринадцать раз. Это граница из доказательства в чистом виде: красных столько же, сколько чёрных, и путь вдвое длиннее чёрной высоты. На языке 2-3-4-дерева: все узлы на правом краю двухключевые, и каждый записан одинаково — чёрный узел с красным правым ребёнком, — так что на каждый этаж 2-3-4-дерева путь тратит два двоичных узла. Ключи, которые всё время приходят справа, такую запись и поддерживают: каждая вставка поворачивает у правого края и снова оставляет его таким. Для журналов, где чаще всего спрашивают о самых свежих записях, это заметная плата: новый ключ найти дороже всех остальных. АВЛ-дерево на тех же данных держит новый ключ на 15-м этаже.

Против АВЛ-дерева: что показывают данные

В учебниках сравнение обычно звучит так: АВЛ-дерево ниже и быстрее ищет, красно-чёрное меньше поворачивает и быстрее меняется. Листинг ниже проверяет это на трёх настоящих потоках ключей, а потом удаляет все слова романа в случайном порядке. Повороты считаются поштучно: двойной поворот АВЛ-дерева — это два.

Верно обе половины, но в другой мере, чем обычно кажется. Поиск. Высота у красно-чёрного дерева бывает намного больше, а средняя глубина — почти та же: разница от 0,7 до 4 %. Длинный хвост тонкий, в нём мало узлов, и средний поиск его почти не замечает; страдают только ключи на самом краю. Вставка. Красно-чёрное дерево поворачивает реже, когда ключи приходят вразнобой, — на 16–17 %, — и ровно так же часто, когда они идут по порядку: обоим деревьям приходится поворачивать почти на каждой вставке. Удаление. В среднем разницы почти нет:

deleting 20000 words: rotations per deletion RB 0.393, AVL 0.380; the most in one deletion RB 3, AVL 7

Разница — в худшем случае. Красно-чёрное дерево обещает не больше трёх поворотов на любое удаление и держит обещание. АВЛ-дерево однажды повернуло семь раз за одно удаление — каскад к корню, о котором рассказано в статье о нём. Для обычного словаря это неважно, а вот там, где поворот дорог, — важно. В ядре Linux у узла дерева бывают дополнительные поля, вычисленные по поддереву: у планировщика это наименьшее виртуальное время среди задач поддерева. Каждый поворот обязан эти поля пересчитать, поэтому интерфейс дополненных деревьев в rbtree_augmented.h требует от пользователя отдельную функцию для поворота. Чем меньше поворотов гарантировано, тем дешевле такие деревья.

Есть и бытовая причина: цвет — это один бит. Ядро Linux хранит его в младшем бите указателя на родителя (указатели выровнены, и младшие биты всегда нули), так что узел красно-чёрного дерева занимает ровно три указателя. АВЛ-дереву нужно два бита на баланс; их тоже можно спрятать в указатель, но обычно хранят высоту целым полем.

Код

Классическая реализация с указателями на родителя — та, что в учебнике Кормена и соавторов и, с вариациями, в ядре Linux и в TreeMap. Вставка поднимается вверх, пока у узла красный отец: красный дядя — перекрашивание и шаг на два этажа вверх, чёрный дядя — один или два поворота и конец. Удаление сначала вырезает узел, как в обычном дереве поиска; если вырезан чёрный, на путях через его место не хватает одного чёрного, и цикл исправляет это, глядя на брата. Метод as_234 склеивает красные узлы с родителями и печатает то же дерево как 2-3-4-дерево; метод check проверяет все правила. Для сравнения в листинге есть сжатое АВЛ-дерево из соседней статьи.

first 12 words: лев толстой том первый часть первая поместья мой верный раб ну здравствуйте
black height 2 | rotations 5 | recolourings 3
2-3-4 level 1: [лев первая толстой]
2-3-4 level 2: [верный здравствуйте]  [мой ну]  [первый поместья раб]  [том часть]

Первые двенадцать слов романа — от «лев толстой том первый» до «здравствуйте» — уложились в 2-3-4-дерево из двух этажей: корень на три ключа и четыре листа под ним. Пять поворотов, три перекрашивания. Строки сравниваются побуквенно, а в Go — побайтно; для русских букв в UTF-8 это один и тот же порядок, поэтому оба языка строят одно и то же дерево.

Сколько это стоит

Память — O(n): ключ, две ссылки на детей, обычно ещё ссылка на родителя и бит цвета. Ссылка на родителя нужна, потому что исправление идёт снизу вверх циклом, без рекурсии, и потому что по ней удобно ходить к следующему ключу — так итераторы std::map и TreeMap идут по порядку. «В среднем O(1)» в таблице — о последовательностях операций: деление узлов 2-3-4-дерева, которое кажется дорогим, оплачивается вставками, которые эти узлы наполняли. В данных это видно: перекрашиваний на вставку от 0,52 до 1.

Где работает

Ядро Linux. Красно-чёрные деревья — общий инструмент ядра, файл lib/rbtree.c. Планировщик EEVDF, который в версии 6.6 сменил CFS, держит готовые к работе задачи в красно-чёрном дереве, упорядоченном по виртуальному дедлайну, и в каждом узле хранит наименьшее виртуальное время своего поддерева. Комментарий к функции pick_eevdf объясняет зачем: дерево одновременно упорядочено по дедлайнам и работает как куча по времени, и задачу, которой процессор уже положен, с ближайшим дедлайном находят за O(log n). Её предшественник CFS держал задачи в таком же дереве по виртуальному времени; как это работало, рассказано в главе курса о планировании. В красно-чёрном дереве epoll хранит наблюдаемые дескрипторы, а очередь таймеров высокого разрешения — их сроки. А вот области памяти процесса в версии 6.1 переехали из красно-чёрного дерева в maple tree — разновидность B-дерева, у которой у узла 10–16 детей, ради меньшего числа промахов кэша.

Стандартные библиотеки. В libstdc++ — стандартной библиотеке C++ из GCC — std::map и std::set построены на шаблоне _Rb_tree. В Java документация TreeMap начинается словами «реализация NavigableMap на красно-чёрном дереве». В HashMap красно-чёрные деревья появляются внутри хеш-таблицы: если в одной корзине набралось восемь элементов, а таблица не меньше 64 ячеек, цепочка превращается в дерево, и поиск в корзине стоит O(log n), даже если кто-то нарочно подобрал ключи с одинаковым хешем; при шести элементах дерево снова становится списком. Код этих деревьев, как сказано в комментарии, переделан из книги Кормена, Лейзерсона и Ривеста. Об атаке коллизиями — в статье о хеш-таблице.

Где нет. В стандартной библиотеке Rust упорядоченный словарь — BTreeMap, B-дерево: в памяти, как и на диске, широкий узел лучше дружит с кэшем. В Python и Go готового дерева нет. Индексы баз данных — B-деревья, хранилища ключ-значение с большим потоком записей — LSM-деревья, у которых в памяти часто список с пропусками.

История

В 1972 году Рудольф Байер описал симметричные двоичные B-деревья — запись B-дерева с узлами на три ключа двоичными узлами. В 1978 году Леонидас Гибас и Роберт Седжвик в статье «Дихроматическая схема для сбалансированных деревьев» перевели эту идею на язык двух цветов, и с тех пор такие деревья называют красно-чёрными. Почему красный, авторы потом объясняли по-разному: по одной версии, красный лучше всех получался у цветного лазерного принтера, которым они пользовались, по другой — у них были красные и чёрные ручки, чтобы рисовать деревья. В 1993 году Арне Андерссон предложил упрощённый вариант, где красным может быть только правый ребёнок, а в 2008 году Седжвик — «левосторонние» красно-чёрные деревья, в которых красным бывает только левый ребёнок, и вставка с удалением записываются заметно короче. Классическая схема с пятью правилами осталась в ядрах и стандартных библиотеках.

Задачи

В первой задаче нужно проверить, что дерево с раскраской действительно красно-чёрное, — дерево большое, и проверка «каждый узел со своими детьми» обманывается. Вторая — сколько вообще существует раскрасок данной формы: оказывается, одну и ту же форму иногда можно раскрасить тысячами способов, а иногда ни одним.