286
правок
Изменения
→Split
===Вспомогательная величина С===
Решается эта проблема довольно просто. Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины''' (в поддерево включается и сама вершина). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути от корня до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.
[[Файл:DDpoNK.png|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]
===Split===
Пусть процедура <tex>\mathrm{split}</tex> запущена в корне дерева с требованием отрезать от дерева <tex>k</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим все возможные случаи:
* <tex>l \geq geqslant k</tex>. В этом случае нужно рекурсивно запустить процедуру <tex>\mathrm{split}</tex> от левого сына с тем же параметром <tex>k</tex>. При этом новым левым сыном корня станет правая часть ответа рекурсивной процедуры, а правой частью ответа станет корень.
* <tex>l < k</tex> Случай симметричен предыдущему. Рекурсивно запустим процедуру <tex>\mathrm{split}</tex> от правого сына с параметром <tex>k - l - 1</tex>. При этом новым правым сыном корня станет левая часть ответа рекурсивной процедуры, а левой частью ответа станет корень.
Псевдокод:
'''<tex>\langle</tex>Treap, Treap<tex>\rangle</tex>''' split('''Treap''' t, '''int''' k) '''if''' t == <tex> \varnothing </tex> '''return''' <tex>\langle</tex><tex> \varnothing </tex>, <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)
t.left = t2
update(vt) r = v; '''return''' <tex>\langle</tex>t1, t2t<tex>\rangle</tex>
'''else'''
<tex>\langle</tex>t1, t2<tex>\rangle</tex> = split(t.right, k - l - 1)
t.right = t1
update(vt) l = v '''return''' <t1tex>\langle</tex>t, t2<tex>\rangle</tex>
===Merge===
Псевдокод:
'''void''' update('''Treap''' t)
t.size = 1 + t.left.size + t.right.size
==Применение описанного дерева==
* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка,
* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке,
* с помощью используя идеи декартова дерева по неявному ключу , можно эффективно реализовать такую структуру данных как [[Rope|Rope]].
== См. также ==
