286
правок
Изменения
→Split
==Операции, поддерживающие структуру декартова дерева==
Структура обычного декартова дерева поддерживается с помощью двух операций: '''<tex>\mathrm{split''' }</tex> {{---}} разбиение одного декартова дерева на два таких, что в одном ключ <tex>X</tex> меньше, чем заданное значение, а в другом {{---}} больше, и '''<tex>\mathrm{merge''' }</tex> {{---}} слияние двух деревьев, в одном из которых все ключи <tex>X</tex> меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: <tex>\mathrm{split(root, t)}</tex> {{---}} разбиение дерева на два так, что в левом окажется ровно <tex>t</tex> вершин, и <tex>\mathrm{merge(root1, root)}</tex> {{---}} слияние двух любых деревьев, соответственно.
===Split===
Пусть процедура '''<tex>\mathrm{split''' }</tex> запущена в корне дерева с требованием отрезать от дерева <tex>tk</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим сначала два тривиальных случая. Первыйвсе возможные случаи: * <tex>l = t\geqslant k</tex>. В этом случае процедура '''нужно рекурсивно запустить процедуру <tex>\mathrm{split''' должна просто пометить, что у корня больше нет }</tex> от левого сына, и вернуть его бывшего левого сына в качестве левого с тем же параметром <tex>k</tex>. При этом новым левым сыном корня станет правая часть ответарекурсивной процедуры, а сам правой частью ответа станет корень .* <tex>l < k</tex> Случай симметричен предыдущему. Рекурсивно запустим процедуру <tex>\mathrm{{---split}} в качестве </tex> от правого. Второй случай (сына с параметром <tex>t = k - l + - 1</tex>) рассматривается аналогично. Следующий случай не так тривиаленПри этом новым правым сыном корня станет левая часть ответа рекурсивной процедуры, а левой частью ответа станет корень. Псевдокод: ''' <tex>\langle</tex>Treap, Treap<tex>\rangle</tex>''' split('''Treap''' t , '''int''' k) '''if''' t == <tex> \varnothing < l/tex> '''return''' <tex>\langle</tex><tex> \varnothing </tex>, <tex> \varnothing </tex><tex>\rangle</tex> '''int''' l = t. В этом случае нужно рекурсивно запустить процедуру left.size '''splitif''' от левого сына с тем же параметром l <tex>\small{\geqslant}</tex> k <tex>t\langle</tex>t1, и левая часть сына станет левым ответом нашей процедурыt2<tex>\rangle</tex> = split(t.left, а правая часть станет левым сыном корня, после чего корень станет правым ответомk) t. Случай left = t2 update(t) '''return''' <tex>\langle</tex>t1, t <tex> l + 1\rangle</tex> '''else''' <tex>\langle</tex> рассматривается аналогичноt1, с той лишь разницей, что от правого сына отрезается t2<tex>\rangle</tex>= split(t .right, k - l - 1) t.right = t1 update(t) '''return''' <tex>\langle</tex>t, t2<tex>\rangle</tex> вершин.
===Merge===
Посмотрим любую из [[Декартово дерево#Операция merge|реализаций ]] процедуры '''<tex>\mathrm{merge'''}</tex>. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры '''<tex>\mathrm{merge''' }</tex> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.
===Поддержание корректности значений <tex>C</tex>===
Единственное действие, обеспечивающее корректность этих значений заключается в том, что после любого действия с детьми вершины нужно записать в ее поле <tex>C</tex> сумму этих значений в ее новых детях, увеличенную на единицу.
Псевдокод:
'''void''' update('''Treap''' t)
t.size = 1 + t.left.size + t.right.size
==Применение описанного дерева==
Таким образом, описана структура, от которой можно отрезать слева кусок часть произвольной длины и слить два любых куска две любые части в один одну в нужном порядке. Теперь мы имеем возможность:* вставить элемент в любое место (отрежем нужное количество элементов слева, сольем левое дерево с деревом из одного добавленного элемента и результат {{---}} с правым деревом),* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке),* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.,* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке,* используя идеи декартова дерева по неявному ключу, можно реализовать такую структуру данных как [[Rope|Rope]]. == См. также ==* [[Splay-дерево]] ==Источники информации==* [http://habrahabr.ru/post/102364/ Habrahabr {{---}} Декартово дерево по неявному ключу]* [http://e-maxx.ru/algo/treap#7 MAXimal :: algo :: Неявные декартовы деревья] [[Категория: Деревья поиска]][[Категория: Дискретная математика и алгоритмы]][[Категория: Структуры данных]]