Изменения

==Постановка задачиОсновная идея==Возьмем структуру данных '''[[Саморасширяющийся массив|вектординамический массив]]'''. В её стандартной реализации мы умеем добавить добавлять элемент в конецвектора, узнать узнавать значение элемента и изменить , стоящего на определенной позиции, изменять элемент по номеру, и удалить удалять последний элемент. Расширим круг задачПредположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: теперь мы хотим добавлять добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалять удалить любой элемент (также с тем же самым уточнениемсоответствующим изменением нумерации). Теперь нам нужно придумать Такую структуруможно реализовать на базе декартового дерева, называемую результат часто называют '''Декартово декартово дерево по неявному ключу'''(англ. ''Treap with implicit key'').===Ключ X===Как известно, [[декартово дерево]] {{---}} это структура данных, объединяющая в себе [[Дерево_поиска, или _наивная_реализация|бинарное дерево поиска]] и [[Двоичная_куча|бинарную кучу]]. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет <tex>Y</tex>, а вместо ключа <tex>X</tex> будем использовать следующую величину: '''ropeколичество элементов в нашей структуре, находящихся левее нашего элемента'''. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.  Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу (англто есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве. ===Вспомогательная величина С===Решается эта проблема довольно просто. Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится.Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''веревкаколичество вершин в поддереве нашей вершины'''(в поддерево включается и сама вершина). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути от корня до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>. [[Файл:DDpoNK.png|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]] ==Операции, поддерживающие структуру декартова дерева==Структура обычного декартова дерева поддерживается с помощью двух операций: <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>k</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим все возможные случаи: * <tex>l \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(t)Напомним '''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 = 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> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в себе бинарное дерево поиска и бинарную кучуобычном декартовом дереве. Для решения задачи ===Поддержание корректности значений C===Единственное действие, поставленной обеспечивающее корректность этих значений заключается в предыдущей главетом, попробуем слегка модифицировать эту структуру. Если конкретнее, то оставим что после любого действия с детьми вершины нужно записать в нем только один ключ - ключ ее поле <tex>YC</tex>сумму этих значений в ее новых детях, увеличенную на единицу. Вместо второго ключа будем использовать следующую величину Псевдокод: '''void''' update('''количество элементов в нашей структуре, находящихся левее нашего элементаTreap'''t) t.size = 1 + t.left.size + t. Если проще, то будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицуright. Заметимsize ==Применение описанного дерева==Таким образом, что при этом сохранится описана структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключуот которой можно отрезать слева часть произвольной длины и слить две любые части в одну в нужном порядке. Теперь мы имеем возможность:* вставить элемент в любое место (т.е. наше модифицированное декартово отрежем нужное количество элементов слева, сольем левое дерево так с деревом из одного добавленного элемента и останется декартовым результат {{---}} с правым деревом),* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке),* совершать групповые операции с элементами. ОднакоВспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с этим подходом появляется две проблемы: наши описанным деревом. В групповые операции добавления включается, естественно, и удаления элемента могут поменять нумерациювзятие функции от отрезка,* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и при наивной реализации нечетных на изменение всех ключей потребуется <tex>O(n)<отрезке,* используя идеи декартова дерева по неявному ключу, можно реализовать такую структуру данных как [[Rope|Rope]]. == См. также ==* [[Splay-дерево]] ==Источники информации==* [http://habrahabr.ru/post/tex> времени, где <tex>n<102364/tex> Habrahabr {{---}} количество элементов в деревеДекартово дерево по неявному ключу]* [http://e-maxx.ru/algo/treap#7 MAXimal :: algo :: Неявные декартовы деревья] [[Категория: Деревья поиска]][[Категория: Дискретная математика и алгоритмы]][[Категория: Структуры данных]]