Викиконспекты - Вклад участника [ru]

Декартово дерево по неявному ключу

2017-02-23T05:59:49Z

188.130.155.154: /* Split */

==Основная идея==
Возьмем структуру данных [[Саморасширяющийся массив|динамический массив]]. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такую структуру можно реализовать на базе декартового дерева, результат часто называют '''декартово дерево по неявному ключу''' (англ. ''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>. При этом новым правым сыном корня станет левая часть ответа рекурсивной процедуры, а левой частью ответа станет корень.

Псевдокод:

'''<Treap, Treap>''' split('''Treap''' t, '''int''' k)
'''int''' l = t.left.size
'''if''' l >= k
<t1, t2> = split(t.left, k)
t.left = t2
update(t)
'''return''' <t1, t>
'''else'''
<t1, t2> = split(t.right, k - l - 1)
t.right = t1
update(t)
'''return''' <t, t2>

===Merge===
Посмотрим любую из [[Декартово дерево#Операция merge|реализаций]] процедуры <tex>\mathrm{merge}</tex>. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры <tex>\mathrm{merge}</tex> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.

===Поддержание корректности значений C===
Единственное действие, обеспечивающее корректность этих значений заключается в том, что после любого действия с детьми вершины нужно записать в ее поле <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 :: Неявные декартовы деревья]

[[Категория: Деревья поиска]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]

Декартово дерево по неявному ключу

2017-02-23T05:52:06Z

188.130.155.154: /* Split */

==Основная идея==
Возьмем структуру данных [[Саморасширяющийся массив|динамический массив]]. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такую структуру можно реализовать на базе декартового дерева, результат часто называют '''декартово дерево по неявному ключу''' (англ. ''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>. При этом новым правым сыном корня станет левая часть ответа рекурсивной процедуры, а левой частью ответа станет корень.

Псевдокод:

'''<Treap, Treap>''' split('''Treap''' t, '''int''' k)
'''int''' l = t.left.size
'''if''' l >= k
<t1, t2> = split(t.left, k)
t.left = t2
update(v)
r = v
'''return''' <t1, t>
'''else'''
<t1, t2> = split(t.right, k - l - 1)
t.right = t1
update(v)
l = v
'''return''' <t, t2>

===Merge===
Посмотрим любую из [[Декартово дерево#Операция merge|реализаций]] процедуры <tex>\mathrm{merge}</tex>. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры <tex>\mathrm{merge}</tex> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.

===Поддержание корректности значений C===
Единственное действие, обеспечивающее корректность этих значений заключается в том, что после любого действия с детьми вершины нужно записать в ее поле <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 :: Неявные декартовы деревья]

[[Категория: Деревья поиска]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]