Изменения

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

Как известно, [[декартово дерево]] {{---}} это структура данных, объединяющая в себе [[Дерево_поиска,_наивная_реализация|бинарное дерево поиска ]] и [[Двоичная_куча|бинарную кучу]]. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет <tex>Y</tex>, а вместо ключа <tex>X</tex> будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

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

* <tex>l >= \geqslant k</tex>. В этом случае нужно рекурсивно запустить процедуру <tex>\mathrm{split}</tex> от левого сына с тем же параметром <tex>k</tex>. При этом новым левым сыном корня станет правая часть ответа рекурсивной процедуры, а правой частью ответа станет корень.

  ''' <pretex>\langle</tex>Treap, Treap<tex>\rangle</tex>''' split('''Treap ''' t, '''int ''' k) '''if''' t == <tex> \varnothing </tex> '''return''' <tex>\langle</tex><tex> \varnothing </tex>, Treap &t1, Treap &t2)<tex> \varnothing </tex><tex>\rangle</tex> '''int ''' l = t.left.size; '''if ''' l <tex>\small{\geqslant}</tex>= k <tex>\langle</tex>t1, t2<tex>\rangle</tex> = split(t.left, k, t1, ) t.left)= t2 update(vt) r = v; '''return''' <tex>\langle</tex>t1, t<tex>\rangle</tex> '''else''' <tex>\langle</tex>t1, t2<tex>\rangle</tex> = split(t.right, k - l - 1, ) t.right, t2)= t1 update(vt) l = v '''return''' <tex>\langle</tex>t, t2<tex>\rangle</pretex>

<pre> '''void''' update('''Treap ''' t) t.size = 1 + t.left.size + t.right.size</pre>

* вставить элемент в любое место (отрежем нужное количество элементов слева, сольем левое дерево с деревом из одного добавленного элемента и результат {{---}} с правым деревом);,* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке);,* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.,* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке.,* с помощью используя идеи декартова дерева по неявному ключу , можно эффективно реализовать такую структуру данных как [[Rope|Rope]]. == См. также ==* [[Splay-дерево]]

==СсылкиИсточники информации==

* [http://e-maxx.ru/algo/treap#7 E-maxx {{---}} MAXimal :: algo :: Неявные декартовы деревья]