Изменения

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

Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу (то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <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>rC</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 :: Неявные декартовы деревья] [[Категория: Деревья поиска]][[Категория: Дискретная математика и алгоритмы]][[Категория: Структуры данных]]