Декартово дерево по неявному ключу

Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree+heap) и дерамида (дерево+пирамида).

Более строго, это структура данных, которая хранит пары (X,Y) в виде бинарного дерева таким образом, что она является бинарным деревом поиска по x и бинарной пирамидой по y. Предполагая, что все X и все Y являются различными, получаем, что если некоторый элемент дерева содержит (X0,Y0), то у всех элементов в левом поддереве X X0, а также и в левом, и в правом поддереве имеем: Y &lt Y0.

Дерамиды были предложены Сиделем (Siedel) и Арагон (Aragon) в 1989 г.

Преимущества такой организации данных

В том применении, которое мы рассматриваем (мы будем рассматривать дерамиды, поскольку декартово дерево — это фактически более общая структура данных), X’ы являются ключами (и одновременно значениями, хранящимися в структуре данных), а Y’и — называются приоритетами. Если бы приоритетов не было, то было бы обычное бинарное дерево поиска по X, и заданному набору X’ов могло бы соответствовать много деревьев, некоторые из которых являются вырожденными (например, в виде цепочки), а потому чрезвычайно медленными (основные операции выполнялись бы за O (N)).

В то же время, приоритеты позволяют однозначно указать дерево, которое будет построено (разумеется, не зависящее от порядка добавления элементов) (это доказывается соответствующей теоремой). Теперь очевидно, что если выбирать приоритеты случайно, то этим мы добьёмся построения невырожденных деревьев в среднем случае, что обеспечит асимптотику O (log N) в среднем. Отсюда и понятно ещё одно название этой структуры данных — рандомизированное бинарное дерево поиска.

Операции

Итак, treap предоставляет следующие операции:

  • Insert (X, Y) — за O (log N) в среднем
    Выполняет добавление в дерево нового элемента.
    Возможен вариант, при котором значение приоритета Y не передаётся функции, а выбирается случайно (правда, нужно учесть, что оно не должно совпадать ни с каким другим Y в дереве).
  • Search (X) — за O (log N) в среднем
    Ищет элемент с указанным значением ключа X. Реализуется абсолютно так же, как и для обычного бинарного дерева поиска.
  • Erase (X) — за O (log N) в среднем
    Ищет элемент и удаляет его из дерева.
  • Build (X1, . XN) — за O (N)
    Строит дерево из списка значений. Эту операцию можно реализовать за линейное время (в предположении, что значения X1, . XN отсортированы), но здесь эта реализация рассматриваться не будет.
    Здесь будет использоваться только простейшая реализация — в виде последовательных вызовов Insert, т.е. за O (N log N).
  • Union (T1, T2) — за O (M log (N/M)) в среднем
    Объединяет два дерева, в предположении, что все элементы различны (впрочем, эту операцию можно реализовать с той же асимптотикой, если при объединении нужно удалять повторяющиеся элементы).
  • Intersect (T1, T2) — за O (M log (N/M)) в среднем
    Находит пересечение двух деревьев (т.е. их общие элементы). Здесь реализация этой операции не будет рассматриваться.

Кроме того, за счёт того, что декартово дерево является и бинарным деревом поиска по своим значениям, к нему применимы такие операции, как нахождение K-го по величине элемента, и, наоборот, определение номера элемента.

Описание реализации

С точки зрения реализации, каждый элемент содержит в себе X, Y и указатели на левого L и правого R сына.

Для реализации операций понадобится реализовать две вспомогательные операции: Split и Merge.

Split (T, X) — разделяет дерево T на два дерева L и R (которые являются возвращаемым значением) таким образом, что L содержит все элементы, меньшие по ключу X, а R содержит все элементы, большие X. Эта операция выполняется за O (log N). Реализация её довольно проста — очевидная рекурсия.

Merge (T1, T2) — объединяет два поддерева T1 и T2, и возвращает это новое дерево. Эта операция также реализуется за O (log N). Она работает в предположении, что T1 и T2 обладают соответствующим порядком (все значения X в первом меньше значений X во втором). Таким образом, нам нужно объединить их так, чтобы не нарушить порядок по приоритетам Y. Для этого просто выбираем в качестве корня то дерево, у которого Y в корне больше, и рекурсивно вызываем себя от другого дерева и соответствующего сына выбранного дерева.

Теперь очевидна реализация Insert (X, Y). Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по X), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше Y. Мы нашли позицию, куда будем вставлять наш элемент. Теперь вызываем Split (X) от найденного элемента (от элемента вместе со всем его поддеревом), и возвращаемые ею L и R записываем в качестве левого и правого сына добавляемого элемента.

Также понятна и реализация Erase (X). Спускаемся по дереву (как в обычном бинарном дереве поиска по X), ища удаляемый элемент. Найдя элемент, мы просто вызываем Merge от его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента.

Операцию Build реализуем за O (N log N) просто с помощью последовательных вызовов Insert.

Наконец, операция Union (T1, T2). Теоретически её асимптотика O (M log (N/M)), однако на практике она работает очень хорошо, вероятно, с весьма малой скрытой константой. Пусть, не теряя общности, T1->Y > T2->Y, т.е. корень T1 будет корнем результата. Чтобы получить результат, нам нужно объединить деревья T1->L, T1->R и T2 в два таких дерева, чтобы их можно было сделать сыновьями T1. Для этого вызовем Split (T2, T1->X), тем самым мы разобъём T2 на две половинки L и R, которые затем рекурсивно объединим с сыновьями T1: Union (T1->L, L) и Union (T1->R, R), тем самым мы построим левое и правое поддеревья результата.

Реализация

Реализуем все описанные выше операции. Здесь для удобства введены другие обозначения — приоритет обозначается prior, значения — key.

Поддержка размеров поддеревьев

Чтобы расширить функциональность декартового дерева, очень часто необходимо для каждой вершины хранить количество вершин в её поддереве — некое поле int cnt в структуре item. Например, с его помощью легко будет найти за O (log N) K-ый по величине элемент дерева, или, наоборот, за ту же асимптотику узнать номер элемента в отсортированном списке (реализация этих операций ничем не будет отличаться от их реализации для обычных бинарных деревьев поиска).

При изменении дерева (добавлении или удалении элемента и т.д.) должны соответствующим образом меняться и cnt некоторых вершин. Реализуем две функции — функция cnt() будет возвращать текущее значение cnt или 0, если вершина не существует, а функция upd_cnt() будет обновлять значение cnt для указанной вершины, при условии, что для её сыновей l и r эти cnt уже корректно обновлены. Тогда, понятно, достаточно добавить вызовы функции upd_cnt() в конец каждой из функций insert, erase, split, merge, чтобы постоянно поддерживать корректные значения cnt.

Построение декартового дерева за O (N) в оффлайн

Неявные декартовы деревья

Неявное декартово дерево — это простая модификация обычного декартового дерева, которая, тем не менее, оказывается очень мощной структурой данных. Фактически, неявное декартово дерево можно воспринимать как массив, над которым можно реализовать следующие операции (все за O (log N) в режиме онлайн):

  • Вставка элемента в массив в любую позицию
  • Удаление произвольного элемента
  • Сумма, минимум/максимум на произвольном отрезке, и т.д.
  • Прибавление, покраска на отрезке
  • Переворот (перестановка элементов в обратном порядке) на отрезке

Ключевая идея заключается в том, что в качестве ключей key следует использовать индексы элементов в массиве. Однако явно хранить эти значения key мы не будем (иначе, например, при вставке элемента пришлось бы изменять key в O (N) вершинах дерева).

Заметим, что фактически в данном случае ключ для какой-то вершины — это количество вершин, меньших неё. Следует заметить, что вершины, меньшие данной, находятся не только в её левом поддереве, но и, возможно, в левых поддеревьях её предков. Более строго, неявный ключ для некоторой вершины t равен количеству вершин cnt(t->l) в левом поддереве этой вершины плюс аналогичные величины cnt(p->l)+1 для каждого предка p этой вершины, при условии, что t находится в правом поддереве для p.

Ясно, как теперь быстро вычислять для текущей вершины её неявный ключ. Поскольку во всех операциях мы приходим в какую-либо вершину, спускаясь по дереву, мы можем просто накапливать эту сумму, передавая её функции. Если мы идём в левое поддерево — накапливаемая сумма не меняется, а если идём в правое — увеличивается на cnt(t->l)+1.

Приведём новые реализации функций split и merge:

Теперь перейдём к реализации различных дополнительных операций на неявных декартовых деревьях:

  • Вставка элемента.
    Пусть нам надо вставить элемент в позицию pos. Разобьём декартово дерево на две половинки: соответствующую массиву [0..pos-1] и массиву [pos..sz]; для этого достаточно вызвать split (t, t1, t2, pos). После этого мы можем объединить дерево t1 с новой вершиной; для этого достаточно вызвать merge (t1, t1, new_item) (нетрудно убедиться в том, что все предусловия для merge выполнены). Наконец, объединим два дерева t1 и t2 обратно в дерево t — вызовом merge (t, t1, t2).
  • Удаление элемента.
    Здесь всё ещё проще: достаточно найти удаляемый элемент, а затем выполнить merge для его сыновей l и r, и поставить результат объединения на место вершины t. Фактически, удаление из неявного декартова дерева не отличается от удаления из обычного декартова дерева.
  • Сумма/минимум и т.п. на отрезке.
    Во-первых, для каждой вершины создадим дополнительное поле f в структуре item, в котором будет храниться значение целевой функции для поддерева этой вершины. Такое поле легко поддерживать, для этого надо поступить аналогично поддержке размеров cnt (создать функцию, вычисляющую значение этого поля, пользуясь его значениями для сыновей, и вставить вызовы этой функции в конце всех функций, меняющих дерево).
    Во-вторых, нам надо научиться отвечать на запрос на произвольном отрезке [A;B]. Научимся выделять из дерева его часть, соответствующую отрезку [A;B]. Нетрудно понять, что для этого достаточно сначала вызвать split (t, t1, t2, A), а затем split (t2, t2, t3, B-A+1). В результате дерево t2 и будет состоять из всех элементов в отрезке [A;B], и только них. Следовательно, ответ на запрос будет находиться в поле f вершины t2. После ответа на запрос дерево надо восстановить вызовами merge (t, t1, t2) и merge (t, t, t3).
  • Прибавление/покраска на отрезке.
    Здесь мы поступаем аналогично предыдущему пункту, но вместо поля f будем хранить поле add, которое и будет содержать прибавляемую величину (или величину, в которую красят всё поддерево этой вершины). Перед выполнением любой операции эту величину add надо "протолкнуть" — т.е. соответствующим образом изменить t-l->add и t->r->add, а у себя значение add снять. Тем самым мы добьёмся того, что ни при каких изменениях дерева информация не будет потеряна.
  • Переворот на отрезке.
    Этот пункт почти аналогичен предыдущему — нужно ввести поле bool rev, которое ставить в true, когда требуется произвести переворот в поддереве текущей вершины. "Проталкивание" поля rev заключается в том, что мы обмениваем местами сыновья текущей вершины, и ставим этот флаг для них.

Реализация. Приведём для примера полную реализацию неявного декартова дерева с переворотом на отрезке. Здесь для каждой вершины также хранится поле value — собственно значение элемента, стоящего в массиве на текущей позиции. Приведена также реализация функции output(), которая выводит массив, соответствующий текущему состоянию неявного декартова дерева.

Дека́ртово де́рево — это двоичное дерево, в узлах которого хранятся:

  • ссылки на правое и левое поддерево;
  • ссылка на родительский узел (необязательно);
  • ключи x и y, которые являются двоичным деревом поиска по ключу x и двоичной кучей по ключу y; а именно, для любого узла дерева n:
  • ключи x узлов правого (левого) поддерева больше (меньше) либо равны ключа x узла n;
  • ключи y узлов правого и левого детей больше либо равны ключу y узла n.

Ссылка на родительский узел не обязательна, она желательна только для линейного алгоритма построения дерева.

Декартово дерево не является самобалансирующимся в обычном смысле, и применяют его по следующим причинам:

  • Проще реализуется, по сравнению, например, с настоящими самобалансирующимися деревьями вроде красно-чёрного.
  • Хорошо ведёт себя «в среднем», если ключи y раздать случайно.
  • Типичная для сортирующего дерева операция «расчленить по ключу x на „меньше x0“ и „не меньше x0“» работает за O(h), где h — высота дерева. На красно-чёрных деревьях придётся восстанавливать балансировку и окраску узлов.

Недостатки декартового дерева:

  • Большие накладные расходы на хранение: вместе с каждым элементом хранятся два-три указателя и случайный ключ y.
  • Скорость доступа O(n) в худшем, хотя и маловероятном, случае. Поэтому декартово дерево недопустимо, например, в ядрах ОС.

Содержание

Терминология [ править | править код ]

В англоязычной литературе декартово дерево, построенное для массива из заданных ключей и присвоенных им при построении случайных весов называется словом-бумажником treap, так как совмещает свойства сортирующего дерева-кучи (heap) и случайного двоичного дерева (tree) с логарифмическим ожиданием высоты. В русском языке были предложены аналогичные слову treap слова дуча [1] (дерево+куча), дерамида (дерево+пирамида), курево (куча+дерево).

Простейший алгоритм построения декартового дерева [ править | править код ]

Простейший для понимания алгоритм построения декартового дерева по множеству данных пар (x, y) выглядит следующим образом. Упорядочим все пары по ключу x и пронумеруем получившуюся последовательность ключей y:

Найдём минимальный ключ y. Пусть это будет y(k). Он будет корнем дерева. Ключ y(k) делит последовательность ключей y на две:

В каждой из них найдём минимальный y — это будут дети узла y(k) — левый и правый. С получившимися 4 кусочками (возможно меньше) поступим аналогичным образом. Предложенный алгоритм построения декартового дерева основан на рекурсии: находим в последовательности минимальный y и назначаем его корнем. найденный y разбивает последовательность на две части, для каждой из частей запускаем алгоритм построения декартового дерева.

Схематически это можно записать так:

Свойство однозначности структуры [ править | править код ]

Из данного алгоритма следует, что множество пар (x, y) однозначно определяет структуру декартового дерева. Заметим для сравнения, что множество ключей, которые хранятся в двоичном дереве поиска не определяют однозначно структуру дерева. То же самое касается двоичной кучи — какова будет структура двоичной кучи (как ключи распределятся по узлам) зависит не только от самого множества ключей, но и от последовательности их добавления. В декартовом дереве такой неоднозначности нет.

Линейный алгоритм построения дерева [ править | править код ]

Другой алгоритм построения дерева также основан на рекурсии. Только теперь мы последовательно будем добавлять элементы y и перестраивать дерево. Дерево T(y(1), …, y(k+1)) будет строиться из дерева T(y(1), …, y(k)) и следующего элемента y(k+1).

На каждом шаге будем помнить ссылку на последний добавленный узел. Он будет самым правым. Действительно, мы упорядочили ключи y по прикреплённому к ним ключу x. Так как декартово дерево — это дерево поиска, то после проекции на горизонтальную прямую ключи x должны возрастать слева направо. Самый правый узел всегда имеет максимально возможное значение ключа x.

Функция F, которая отображает декартово дерево T(y(1), …, y(k)) предыдущего шага и очередное y(k+1) в новое дерево T(y(1), …, y(k+1)), выглядит следующим образом. Вертикаль для узла y(k+1) определена. Нам необходимо определиться с его горизонталью. Для начала мы проверяем, можно ли новый узел y(k+1) сделать правым ребёнком узла y(k) — это следует сделать, если y(k+1) > y(k). Иначе мы делаем шаг по склону от узла y(k) вверх и смотрим на значение y, которое там хранится. Поднимаемся вверх по склону, пока не найдём узел, в котором значение y меньше, чем y(k+1), после чего делаем y(k+1) его правым ребёнком, а его предыдущего правого ребёнка делаем левым ребёнком узла y(k+1).

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

Содержание

Основная идея [ править ]

Возьмем структуру данных динамический массив. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такую структуру можно реализовать на базе декартового дерева, результат часто называют декартово дерево по неявному ключу (англ. Treap with implicit key).

Ключ X [ править ]

Как известно, декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет [math]Y[/math] , а вместо ключа [math]X[/math] будем использовать следующую величину: количество элементов в нашей структуре, находящихся левее нашего элемента. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

Заметим, что при этом сохранится структура двоичного дерева поиска по этому ключу (то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется [math]O(n)[/math] времени, где [math]n[/math] — количество элементов в дереве.

Вспомогательная величина С [ править ]

Решается эта проблема довольно просто. Основная идея заключается в том, что такой ключ [math]X[/math] сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину [math]C[/math] : количество вершин в поддереве нашей вершины (в поддерево включается и сама вершина). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути от корня до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ [math]X[/math] .

Операции, поддерживающие структуру декартова дерева [ править ]

Структура обычного декартова дерева поддерживается с помощью двух операций: [math]mathrm[/math] — разбиение одного декартова дерева на два таких, что в одном ключ [math]X[/math] меньше, чем заданное значение, а в другом — больше, и [math]mathrm[/math] — слияние двух деревьев, в одном из которых все ключи [math]X[/math] меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: [math]mathrm[/math] — разбиение дерева на два так, что в левом окажется ровно [math]t[/math] вершин, и [math]mathrm[/math] — слияние двух любых деревьев, соответственно.

Split [ править ]

Пусть процедура [math]mathrm[/math] запущена в корне дерева с требованием отрезать от дерева [math]k[/math] вершин. Также известно, что в левом поддереве вершины находится [math]l[/math] вершин, а в правом [math]r[/math] . Рассмотрим все возможные случаи:

  • [math]l geqslant k[/math] . В этом случае нужно рекурсивно запустить процедуру [math]mathrm[/math] от левого сына с тем же параметром [math]k[/math] . При этом новым левым сыном корня станет правая часть ответа рекурсивной процедуры, а правой частью ответа станет корень.
  • [math]l lt k[/math] Случай симметричен предыдущему. Рекурсивно запустим процедуру [math]mathrm[/math] от правого сына с параметром [math]k — l — 1[/math] . При этом новым правым сыном корня станет левая часть ответа рекурсивной процедуры, а левой частью ответа станет корень.

Merge [ править ]

Посмотрим любую из реализаций процедуры [math]mathrm[/math] . Заметим, что в ней программа ни разу не обращается к ключу [math]X[/math] . Поэтому реализация процедуры [math]mathrm[/math] для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.

Поддержание корректности значений C [ править ]

Единственное действие, обеспечивающее корректность этих значений заключается в том, что после любого действия с детьми вершины нужно записать в ее поле [math]C[/math] сумму этих значений в ее новых детях, увеличенную на единицу.

Применение описанного дерева [ править ]

Таким образом, описана структура, от которой можно отрезать слева часть произвольной длины и слить две любые части в одну в нужном порядке. Теперь мы имеем возможность:

  • вставить элемент в любое место (отрежем нужное количество элементов слева, сольем левое дерево с деревом из одного добавленного элемента и результат — с правым деревом),
  • переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке),
  • совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка,
  • сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке,
  • используя идеи декартова дерева по неявному ключу, можно реализовать такую структуру данных как Rope.

[an error occurred while processing the directive]
Карта сайта