Декартово дерево
Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных.
Такое волшебное дерево, которое хранит в каждой вершине по два параметра, и при этом по ключам является деревом поиска, а по приоритетам — кучей.
Поля у составляют дерево приоритетов, а поля х могут браться либо случайно из диапазона или на основании любых достаточно случайных пользовательских данных. От их случайности зависит насколько высоким будет дерево. При хорошем рандоме полученное декартово дерево с очень высокой, стремящейся к 100% вероятностью, будет иметь высоту, не превосходящую 4 log2 N.
Вся подноготная работы с декартовым деревом заключается в двух основных операциях: Merge и Split
Merge
Операция Merge принимает на вход два декартовых дерева L и R. От нее требуется слить их в одно, тоже корректное, декартово дерево T. Следует заметить, что работать операция Merge может не с любыми парами деревьев, а только с теми, у которых все ключи одного дерева ( L ) не превышают ключей второго ( R )
Алгоритм работы Merge очень прост. Какой элемент станет корнем будущего дерева? Очевидно, с наибольшим приоритетом. Кандидатов на максимальный приоритет у нас два — только корни двух исходных деревьев. Сравним их приоритеты; пускай для однозначности приоритет y левого корня больше, а ключ в нем равен x. Новый корень определен, теперь стоит подумать, какие же элементы окажутся в его правом поддереве, а какие — в левом.
Легко понять, что все дерево R окажется в правом поддереве нового корня, ведь ключи-то у него больше x по условию. Точно так же левое поддерево старого корня L.Left имеет все ключи, меньшие x, и должно остаться левым поддеревом, а правое поддерево L.Right… а вот правое должно по тем же соображениям оказаться справа, однако неясно, куда тогда ставить его элементы, а куда элементы дерева R?
Стоп, почему неясно? У нас есть два дерева, ключи в одном меньше ключей в другом, и нам нужно их как-то объединить и полученный результат привесить к новому корню как правое поддерево. Просто рекурсивно вызываем Merge для L.Right и дерева R, и возвращенное ею дерево используем как новое правое поддерево. Результат налицо.
Симметричный случай — когда приоритет в корне дерева R выше — разбирается аналогично. И, конечно, надо не забыть про основу рекурсии, которая в нашем случае наступает, если какое-то из деревьев L и R, или сразу оба, являются пустыми.
Теперь об операции Split. На вход ей поступает корректное декартово дерево T и некий ключ x0. Задача о1перации — разделить дерево на два так, чтобы в одном из них ( L ) оказались все элементы исходного дерева с ключами, меньшими x0, а в другом ( R ) — с большими. Никаких особых ограничений на дерево не накладывается.
Рассуждаем похожим образом. Где окажется корень дерева T? Если его ключ меньше x0, то в L, иначе в R. Опять-таки, предположим для однозначности, что ключ корня оказался меньше x0.
Тогда можно сразу сказать, что все элементы левого поддерева T также окажутся в L — их ключи ведь тоже все будут меньше x0. Более того, корень T будет и корнем L, поскольку его приоритет наибольший во всем дереве. Левое поддерево корня полностью сохранится без изменений, а вот правое уменьшится — из него придется убрать элементы с ключами, большими x0, и вынести в дерево R. А остаток ключей сохранить как новое правое поддерево L. Снова видим идентичную задачу, снова напрашивается рекурсия!
Возьмем правое поддерево и рекурсивно разрежем его по тому же ключу x0 на два дерева L' и R'. После чего становится ясно, что L' станет новым правым поддеревом дерева L, а R' и есть непосредственно дерево R — оно состоит из тех и только тех элементов, которые больше x0.
Симметричный случай, при котором ключ корня больше, чем x0, тоже совершенно идентичен. Основа рекурсии здесь — случаи, когда какое-то из поддеревьев пустое.
Добавление элемента.
Помня универсальность операций Split/Merge, решение напрашивается практически сразу:
- Разделим (split) дерево по ключу x на дерево L, с ключами меньше икса, и дерево R, с большими.
- Создадим из данного ключа дерево M из единственной вершины (x, y), где y — только что сгенерированный случайный приоритет.
- Объединим (merge) по очереди L с M, то что получилось — с R.
У нас тут 1 применение Split, и 2 применения Merge — общее время работы O(log2 N). Короткий исходный код прилагается.
Удаление элемента
1. Разделим сначала дерево по ключу x-1. Все элементы, меньшие либо равные x-1, отправились в левый результат, значит, искомый элемент — в правом.
2. Разделим правый результат по ключу x (здесь стоит быть аккуратным с равенством!). В новый правый результат отправились все элементы с ключами, большими x, а в «средний» (левый от правого) — все меньшие либо равные x. Но поскольку строго меньшие после первого шага все были отсеяны, то среднее дерево и есть искомый элемент.
3. Теперь просто объединим снова левое дерево с правым, без среднего, и дерамида осталась без ключей x.
Время работы операции все так же O(log2 N), поскольку мы применили 2 раза Split и 1 раз Merge.