Изменения

{{Q|width=30%=Основная идея==Возьмем структуру данных [[Саморасширяющийся массив|Декартово динамический массив]]. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такую структуру можно реализовать на базе декартового дерева, результат часто называют '''декартово дерево правит миромпо неявному ключу''' (англ. За логарифм''Treap with implicit key'').|Неизвестный автор===Ключ X===Как известно, [[декартово дерево]] {{---}}это структура данных, объединяющая в себе [[Дерево_поиска,_наивная_реализация|бинарное дерево поиска]] и [[Двоичная_куча|бинарную кучу]]. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет <tex>Y</tex>, а вместо ключа <tex>X</tex> будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

==Постановка задачи==Возьмем структуру данных '''Заметим, что при этом сохранится структура [[Саморасширяющийся массивДерево_поиска,_наивная_реализация|вектордвоичного дерева поиска]]'''. В её стандартной реализации мы умеем добавить элемент в конец, узнать значение элемента и изменить элемент по номеру, и удалить последний элемент. Расширим круг задач: теперь мы хотим добавлять элемент в любое место этому ключу (с соответствующим изменением нумерации элементов) то есть модифицированное декартово дерево так и удалять любой элемент (с тем же самым уточнениемостанется декартовым деревом). Теперь нам нужно придумать структуруОднако, называемую '''Декартово дерево по неявному ключу'''с этим подходом появляется проблема: операции добавления и удаления элемента могут поменять нумерацию, или же '''rope'''и при наивной реализации на изменение всех ключей потребуется <tex>O(''англ.'''веревка'''''n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.

==Основная идея=Вспомогательная величина С===[[Файл:Tree_1Решается эта проблема довольно просто.png|right|250px|thumb|Пример описанного дерева с демонстрацией определения ключа Основная идея заключается в том, что такой ключ <tex>X</tex>]]Напомним, '''[[Декартово дерево]]''' {{---}} это структура данных, объединяющая в сам по себе бинарное дерево поиска и бинарную кучунигде не хранится. Для решения задачи, поставленной в предыдущей главе, попробуем слегка модифицировать эту структуру. Если конкретнее, то оставим в нем только один ключ - ключ Вместо него будем хранить вспомогательную величину <tex>YC</tex>. Вместо второго ключа будем использовать следующую величину: '''количество элементов вершин в поддереве нашей структуре, находящихся левее нашего элементавершины'''(в поддерево включается и сама вершина). Если прощеОбратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути от корня до некой вершины просуммировать все такие величины в левых поддеревьях, то будем считать ключом порядковый номер нашего элемента в деревекоторые мы не пошли, уменьшенный увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.

Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализацияФайл:DDpoNK.png|двоичного Пример описанного дерева поиска]] по этому ключу(т.е. наше модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: наши операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве. Как же нам быть? Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины'''(в поддерево включается и сама вершину). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммируем все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ демонстрацией определения ключа <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> {{---}} слияние двух любых деревьев, соответственно.

Пусть процедура '''<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|реализаций ]] процедуры '''<tex>\mathrm{merge'''}</tex>. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры '''<tex>\mathrm{merge''' }</tex> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.

===Поддержание корректности значений <tex>C</tex>===

Что же мы получили? У нас есть Таким образом, описана структура, от которой можно отрезать слева кусок часть произвольной длины и слить два любых куска две любые части в один одну в нужном порядке. Теперь мы можемимеем возможность:* вставить элемент в любое место (отрежем нужное количество элементов слева, сольем левое дерево с деревом из одного добавленного элемента и результат {{---}} с правым деревом),* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке),* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.,* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке (одно из домашних заданий),* используя идеи декартова дерева по неявному ключу, можно реализовать такую структуру данных как [[Rope|Rope]]. == См. также ==* [[Splay-дерево]] ==Источники информации==* [http://habrahabr.ru/post/102364/ Habrahabr {{---}} Декартово дерево по неявному ключу]* повелевать миром[http://e-maxx.ru/algo/treap#7 MAXimal :: algo :: Неявные декартовы деревья] [[Категория: Деревья поиска]][[Категория: Дискретная математика и алгоритмы]][[Категория: Структуры данных]]