Декартово дерево: баланс через случайность

Если ты понимаешь, что декартово дерево - это BST по ключу и куча по случайному приоритету, почему пара свойств задаёт форму однозначно и почему случайные приоритеты дают ожидаемую высоту O(log n), листай до «Теперь сам».

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

АВЛ считает высоты, красно-чёрное красит узлы - обе структуры АКТИВНО следят за формой и правят её. А что порождает перекос? Неудачный ПОРЯДОК вставок (отсортированный вход). Если бы ключи приходили в случайном порядке, обычный BST в среднем был бы неплохо сбалансирован - высота O(log n) в ожидании (это известный факт про случайные BST). Беда в том, что порядок вставок мы не контролируем - данные приходят как приходят. Но что если СДЕЛАТЬ ВИД, будто порядок случайный? Припишем каждому ключу случайный «возраст» и построим дерево так, будто вставляли по возрасту, а не по времени прихода. Тогда форма перестанет зависеть от реального порядка данных - и станет случайной, то есть в среднем сбалансированной. Это и есть идея декартова дерева.

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

Живая очередь, которую пересобирают по тайным номеркам. Люди подходят в каком угодно порядке (может, все по росту - «отсортированный» вход), но каждому при входе выдают СЛУЧАЙНЫЙ номерок, и очередь выстраивают не по времени прихода, а по номеркам. Даже если пришли строго по росту, номерки перемешают их - и очередь получится такой, будто люди подходили вразнобой. Декартово дерево так же: реальный порядок ключей не важен, форму задаёт случайный приоритет, и перекос, который дал бы отсортированный вход, растворяется в случайности номерков.

Механизм: два свойства и как их держат

Каждый узел хранит КЛЮЧ (данные) и ПРИОРИТЕТ (случайное число, назначается при вставке). Дерево держит инварианты одновременно:

по КЛЮЧАМ:       дерево поиска - левое поддерево меньше, правое больше
по ПРИОРИТЕТАМ:  куча - приоритет родителя ВЫШЕ, чем у обоих детей

Важный факт: при заданном наборе (ключ, приоритет) с РАЗНЫМИ приоритетами такое дерево ЕДИНСТВЕННО. Корень - узел с наибольшим приоритетом (свойство кучи); его ключ делит остальные на меньшие (левое поддерево) и большие (правое) - и так рекурсивно. Форма определена парой свойств однозначно, а не порядком операций.

Операции держат оба свойства:

вставка(ключ):
    дать ключу случайный приоритет
    вставить как в обычный BST (по ключу) - он попадёт в лист
    пока приоритет нового узла ВЫШЕ, чем у родителя - ВРАЩЕНИЕ (поднять узел),
        восстанавливая свойство кучи, но НЕ ломая порядок по ключу
удаление(ключ):
    вращениями «опустить» узел до листа (каждый раз поднимая ребёнка с бОльшим приоритетом),
    затем отцепить

Балансировку делают всё те же ВРАЩЕНИЯ, но запускает их не подсчёт высот, а случайный приоритет: узел всплывает ровно на ту глубину, которую диктует его случайное число.

Правило

Декартово дерево (treap) держит два свойства сразу: по КЛЮЧАМ - дерево поиска, по случайным ПРИОРИТЕТАМ - куча (родитель выше детей). Эта пара задаёт форму ОДНОЗНАЧНО, и, поскольку приоритеты случайны, форма получается как при случайном порядке вставок - а он даёт высоту O(log n) в ОЖИДАНИИ. Балансировку делают вращения, но запускает их не подсчёт высот, а случайный приоритет узла. Так случайность заменяет явную балансировку: никаких высот и цветов - достаточно бросить кость на каждый ключ.

Разбор: почему пара свойств задаёт единственное дерево

Это неочевидно, но важно: набор пар (ключ, приоритет) с различными приоритетами определяет декартово дерево ОДНОЗНАЧНО - от порядка операций форма не зависит. Докажем построением. Свойство кучи требует, чтобы в корне был узел с НАИБОЛЬШИМ приоритетом - выбора нет, корень определён. Свойство BST требует, чтобы слева от корня были все ключи меньше корневого, справа - все большие; значит разбиение на левое и правое поддеревья тоже определено однозначно. Теперь в каждом поддереве повторяем то же рассуждение: корень поддерева - узел с наибольшим приоритетом среди его элементов, он делит остальные по ключу, и так далее. На каждом шаге выбор ВЫНУЖДЕН, поэтому дерево одно. Отсюда ключевое следствие: раз форма не зависит от порядка вставок, а только от приоритетов, и приоритеты случайны - форма ВСЕГДА случайна, при любом (даже отсортированном) порядке прихода данных. Именно это растворяет вырождение.

Разбор: почему случайные приоритеты дают высоту O(log n) в ожидании

Здесь работает уже известный факт: обычный BST, в который ключи вставляют в СЛУЧАЙНОМ порядке, имеет ожидаемую высоту O(log n) (средняя глубина узла около 1.39·log₂ n, а ожидаемая высота - около 3·log₂ n). Причём «случайный порядок вставок» и «случайные приоритеты» дают ОДНО И ТО ЖЕ распределение форм: дерево, где корень - случайно выбранный элемент (наибольший приоритет = равновероятно любой из n), а поддеревья устроены так же рекурсивно, - это в точности случайный BST. Значит ожидаемая высота декартова дерева - O(log n), как у случайного BST, но БЕЗ зависимости от реального порядка данных: случайность мы внесли САМИ, приоритетами. Оговорка та же, что у рандомизированного quickselect и универсального хеширования: это ОЖИДАНИЕ, а не гарантия - крайне маловероятно, но возможно, что приоритеты лягут неудачно и дерево вытянется. Ожидание относится к распределению случайных приоритетов, независимых от ключей. Для численной оценки риска превысить конкретную высоту нужна отдельная хвостовая оценка; одна запись O(log n) в ожидании такой оценки не задаёт.

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

Первая ошибка - назначать приоритеты НЕ случайно (например, по порядку вставки или по значению ключа): тогда пропадёт вся защита - дерево может выродиться ровно как обычный BST. Приоритет должен быть случайным и независимым от ключа. Вторая - брать приоритеты из слишком узкого диапазона, где часты СОВПАДЕНИЯ: при равных приоритетах свойство кучи неоднозначно, форма «плывёт»; берут широкий диапазон (или аккуратно разрешают равенства). Третья - думать, что декартово дерево даёт ГАРАНТИЮ O(log n): это ОЖИДАНИЕ, как у всех рандомизированных структур; гарантию худшего случая дают деревья с жёсткими правилами баланса (АВЛ, красно-чёрное). Четвёртая - забыть восстановить свойство кучи после вставки вращениями: без всплытия узла по приоритету дерево перестанет быть treap и потеряет баланс.

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

Декартово дерево ценят за ПРОСТОТУ реализации: балансировка «бесплатна» - не надо кодировать разбор случаев АВЛ или хитрое удаление красно-чёрного дерева, достаточно вставки как в BST плюс несколько вращений по приоритету (в среднем меньше двух на вставку). Поэтому его любят в олимпиадном программировании и там, где нужна сбалансированная структура «за полчаса», а не готовая из библиотеки. Особенно хорош его вариант с операциями SPLIT (разрезать дерево по ключу на два) и MERGE (склеить два дерева) - на них элегантно делаются вставка/удаление отрезков, конкатенация последовательностей, персистентные структуры. Но шире декартово дерево - это ещё один яркий пример ОБЩЕГО приёма всего курса: случайность внутри алгоритма заменяет сложную детерминированную машинерию и защищает от худшего случая, не завися от данных. Тот же мотив ты видел в quickselect, в универсальном хешировании - и сейчас в балансировке дерева. В главе о дереве отрезков появится декартово дерево по неявному ключуРазбирается в разделе 8, глава «Дерево отрезков и дерево Фенвика»: Декартово дерево по неявному ключу: массив с вырезанием и разворотом за логарифм: там вместо ключа хранится размер поддерева, чтобы резать последовательность по позиции. Следующие уроки - ещё две вариации: splay (баланс через «подтягивание вверх») и списки с пропусками (баланс через случайные уровни, вообще без дерева).

Теперь сам

В декартово дерево с приоритетами вставляют ключи так, что новый ключ 5 получил случайный приоритет ВЫШЕ, чем у текущего корня. Куда он в итоге встанет и почему это не нарушит порядок по ключу?