Декартово дерево по неявному ключу — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Split)
(не показана 41 промежуточная версия 14 участников)
Строка 1: Строка 1:
{{Q|width=30%|Декартово дерево правит миром. За логарифм.|Неизвестный автор}}
+
==Основная идея==
 +
Возьмем структуру данных [[Саморасширяющийся массив|динамический массив]]. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такую структуру можно реализовать на базе декартового дерева, результат часто называют '''декартово дерево по неявному ключу''' (англ. ''Treap with implicit key'').
 +
===Ключ X===
 +
Как известно, [[декартово дерево]] {{---}} это структура данных, объединяющая в себе [[Дерево_поиска,_наивная_реализация|бинарное дерево поиска]] и [[Двоичная_куча|бинарную кучу]]. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет <tex>Y</tex>, а вместо ключа <tex>X</tex> будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.
  
==Основная идея==
+
Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу (то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.
Возьмем структуру данных '''[[Саморасширяющийся массив|вектор]]'''. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такая структура существует и называется '''Декартово дерево по неявному ключу''', или же '''rope''' (''англ.'''веревка''''').
 
[[Файл:Tree_1.png|right|250px|thumb|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]
 
Напомним, '''[[Декартово дерево]]''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу попробуем слегка модифицировать эту структуру. А именно, оставим в нем только один ключ - ключ <tex>Y</tex>. Вместо второго ключа будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.  
 
  
Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу (то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: наши операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.
+
===Вспомогательная величина С===
 +
Решается эта проблема довольно просто. Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины''' (в поддерево включается и сама вершина). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути от корня до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.
  
Необходимо решить эту проблему. Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины'''(в поддерево включается и сама вершину). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.
+
[[Файл:DDpoNK.png|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]
  
 
==Операции, поддерживающие структуру декартова дерева==
 
==Операции, поддерживающие структуру декартова дерева==
Структура обычного декартова дерева поддерживается с помощью двух операций: '''split''' {{---}} разбиение одного декартова дерева  на два таких, что в одном ключ <tex>X</tex> меньше, чем заданное значение, а в другом {{---}} больше, и '''merge''' {{---}} слияние двух деревьев, в одном из которых все ключи <tex>X</tex> меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: разбиение дерева на два так, что в левом окажется ровно <tex>t</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===
 
===Split===
Пусть процедура '''split''' запущена в корне дерева с требованием отрезать от дерева <tex>t</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим сначала два тривиальных случая. Первый: <tex>l = t</tex>. В этом случае процедура '''split''' должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левого ответа, а сам корень {{---}} в качестве правого. Второй случай (<tex>t = l + 1</tex>) рассматривается аналогично. Следующий случай не так тривиален: <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру '''split''' от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левым ответом нашей процедуры, а правая часть станет левым сыном корня, после чего корень станет правым ответом. Случай <tex>t > l + 1</tex> рассматривается аналогично, с той лишь разницей, что от правого сына отрезается <tex>t - l - 1</tex> вершин.
+
Пусть процедура <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===
Посмотрим любую из [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE#.D0.9E.D0.BF.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D1.8F_merge реализаций] процедуры '''merge'''. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры '''merge''' для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.
+
Посмотрим любую из [[Декартово дерево#Операция merge|реализаций]] процедуры <tex>\mathrm{merge}</tex>. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры <tex>\mathrm{merge}</tex> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.
  
===Поддержание корректности значений <tex>C</tex>===
+
===Поддержание корректности значений C===
 
Единственное действие, обеспечивающее корректность этих значений заключается в том, что после любого действия с детьми вершины нужно записать в ее поле <tex>C</tex> сумму этих значений в ее новых детях, увеличенную на единицу.
 
Единственное действие, обеспечивающее корректность этих значений заключается в том, что после любого действия с детьми вершины нужно записать в ее поле <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://habrahabr.ru/post/102364/ Habrahabr {{---}} Декартово дерево по неявному ключу]
 +
* [http://e-maxx.ru/algo/treap#7 MAXimal :: algo :: Неявные декартовы деревья]
  
 
[[Категория: Деревья поиска]]
 
[[Категория: Деревья поиска]]
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Структуры данных]]

Версия 16:10, 20 апреля 2018

Основная идея

Возьмем структуру данных динамический массив. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такую структуру можно реализовать на базе декартового дерева, результат часто называют декартово дерево по неявному ключу (англ. Treap with implicit key).

Ключ X

Как известно, декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет [math]Y[/math], а вместо ключа [math]X[/math] будем использовать следующую величину: количество элементов в нашей структуре, находящихся левее нашего элемента. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

Заметим, что при этом сохранится структура двоичного дерева поиска по этому ключу (то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется [math]O(n)[/math] времени, где [math]n[/math] — количество элементов в дереве.

Вспомогательная величина С

Решается эта проблема довольно просто. Основная идея заключается в том, что такой ключ [math]X[/math] сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину [math]C[/math]: количество вершин в поддереве нашей вершины (в поддерево включается и сама вершина). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути от корня до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ [math]X[/math].

Пример описанного дерева с демонстрацией определения ключа [math]X[/math]

Операции, поддерживающие структуру декартова дерева

Структура обычного декартова дерева поддерживается с помощью двух операций: [math]\mathrm{split}[/math] — разбиение одного декартова дерева на два таких, что в одном ключ [math]X[/math] меньше, чем заданное значение, а в другом — больше, и [math]\mathrm{merge}[/math] — слияние двух деревьев, в одном из которых все ключи [math]X[/math] меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: [math]\mathrm{split(root, t)}[/math] — разбиение дерева на два так, что в левом окажется ровно [math]t[/math] вершин, и [math]\mathrm{merge(root1, root)}[/math] — слияние двух любых деревьев, соответственно.

Split

Пусть процедура [math]\mathrm{split}[/math] запущена в корне дерева с требованием отрезать от дерева [math]k[/math] вершин. Также известно, что в левом поддереве вершины находится [math]l[/math] вершин, а в правом [math]r[/math]. Рассмотрим все возможные случаи:

  • [math]l \geqslant k[/math]. В этом случае нужно рекурсивно запустить процедуру [math]\mathrm{split}[/math] от левого сына с тем же параметром [math]k[/math]. При этом новым левым сыном корня станет правая часть ответа рекурсивной процедуры, а правой частью ответа станет корень.
  • [math]l \lt k[/math] Случай симметричен предыдущему. Рекурсивно запустим процедуру [math]\mathrm{split}[/math] от правого сына с параметром [math]k - l - 1[/math]. При этом новым правым сыном корня станет левая часть ответа рекурсивной процедуры, а левой частью ответа станет корень.

Псевдокод:

 [math]\langle[/math]Treap, Treap[math]\rangle[/math] split(Treap t, int k)
  if t == [math] \varnothing [/math]
    return [math]\langle[/math][math] \varnothing [/math], [math] \varnothing [/math][math]\rangle[/math]  
  int l = t.left.size
  if l [math]\small{\geqslant}[/math] k
    [math]\langle[/math]t1, t2[math]\rangle[/math] = split(t.left, k)
    t.left = t2
    update(t)
    return [math]\langle[/math]t1, t[math]\rangle[/math]
  else
    [math]\langle[/math]t1, t2[math]\rangle[/math] = split(t.right, k - l - 1)
    t.right = t1
    update(t)
    return [math]\langle[/math]t, t2[math]\rangle[/math]

Merge

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

Поддержание корректности значений C

Единственное действие, обеспечивающее корректность этих значений заключается в том, что после любого действия с детьми вершины нужно записать в ее поле [math]C[/math] сумму этих значений в ее новых детях, увеличенную на единицу.

Псевдокод:

void update(Treap t)
  t.size = 1 + t.left.size + t.right.size

Применение описанного дерева

Таким образом, описана структура, от которой можно отрезать слева часть произвольной длины и слить две любые части в одну в нужном порядке. Теперь мы имеем возможность:

  • вставить элемент в любое место (отрежем нужное количество элементов слева, сольем левое дерево с деревом из одного добавленного элемента и результат — с правым деревом),
  • переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке),
  • совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка,
  • сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке,
  • используя идеи декартова дерева по неявному ключу, можно реализовать такую структуру данных как Rope.

См. также

Источники информации