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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Высота в декартовом дереве с случайными приоритетами)
м (rollbackEdits.php mass rollback)
 
(не показаны 93 промежуточные версии 14 участников)
Строка 1: Строка 1:
''Эта статья про Курево''
+
''Эта статья про курево''
  
'''Декартово дерево''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), так же существует название курево (куча + дерево).
+
'''Декартово дерево или дерамида''' (англ. ''Treap'') {{---}} это структура данных, объединяющая в себе [[Дерево поиска, наивная реализация|бинарное дерево поиска]] и [[Двоичная куча|бинарную кучу]] (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), также существует название курево (куча + дерево).
  
Более строго, это бинарное дерево, в узлах которого хранится пары <tex> (x,y) </tex>, где <tex>x</tex> - это ключ, а <tex>y</tex> - это приоритет. Также оно является [[Дерево поиска, наивная реализация|двоичным деревом поиска]] по <tex>x</tex> и [[Двоичная куча|пирамидой]] по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.
+
Более строго, это бинарное дерево, в узлах которого хранятся пары <tex> (x,y) </tex>, где <tex>x</tex> {{---}} это ключ, а <tex>y</tex> {{---}} это приоритет. Также оно является двоичным деревом поиска по <tex>x</tex> и пирамидой по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.
  
Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.
+
Дерамиды были предложены Сиделем (Siedel) и Арагон (Aragon) в 1996 г.
  
 
== Операции в декартовом дереве ==
 
== Операции в декартовом дереве ==
=== Split ===
+
=== split ===
 
[[file:split.png|thumb|400px|Операция split]]
 
[[file:split.png|thumb|400px|Операция split]]
  
Операция <tex>\mathrm{Split}</tex> (''разрезать'') позволяет сделать следующее: разрезать декартово дерево <tex>T</tex> по ключу  
+
Операция <tex>\mathrm{split}</tex> (''разрезать'') позволяет сделать следующее: разрезать исходное дерево <tex>T</tex> по ключу <tex>k</tex>. Возвращать она будет такую пару деревьев <tex>\langle T_1, T_2\rangle </tex>, что в дереве <tex>T_1</tex> ключи меньше <tex>k</tex>, а в дереве <tex>T_2</tex> все остальные:  <tex>\mathrm{split}(T, k) \to \langle T_1, T_2\rangle </tex>.  
<tex>k</tex> и получить два других декартовых дерева: <tex>T_1</tex> и <tex>T_2</tex>, причем в <tex>T_1</tex>
 
находятся все ключи дерева <tex>T</tex>, не большие <tex>k</tex>, а в <tex>T_2</tex> {{---}} большие <tex>k</tex>.
 
 
 
<tex>\mathrm{Split}(T, k) \to \{T_1, T_2\}</tex>.  
 
  
 
Эта операция устроена следующим образом.
 
Эта операция устроена следующим образом.
Строка 26: Строка 22:
 
Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.
 
Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.
  
Псевдокод:
+
=== Псевдокод ===
<pre>
+
 
Split(Treap t, int k, Treap &t1, Treap &t2)
+
'''<tex>\langle</tex>Treap, Treap<tex>\rangle</tex>''' split(t: '''Treap''', k: '''int'''):
  if t == NULL
+
  '''if''' t == <tex> \varnothing </tex>
     t1 = t2 = NULL;
+
    '''return''' <tex>\langle</tex><tex> \varnothing </tex>, <tex> \varnothing </tex><tex>\rangle</tex>      
  else if k > T.x  
+
  '''else if''' k > t.x  
    Split(t.right, k, t.right, t2);
+
    <tex>\langle</tex>t1, t2<tex>\rangle</tex> = split(t.right, k)
    t1 = t;
+
    t.right = t1
  else
+
    '''return''' <tex>\langle</tex>t, t2<tex>\rangle</tex>
    Split(t.left, k, t1, t.left);
+
  '''else'''
    t2 = t;
+
    <tex>\langle</tex>t1, t2<tex>\rangle</tex> = split(t.left, k)
</pre>
+
    t.left = t2
 +
    '''return''' <tex>\langle</tex>t1, t<tex>\rangle</tex>
 +
 
 +
=== Время работы ===
  
Оценим время работы операции <tex>\mathrm{Split}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{Split}</tex> для
+
Оценим время работы операции <tex>\mathrm{split}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{split}</tex> для
дерева хотя бы на один меньшей высоты и делается ещё <tex>O(1)</tex> операция. Тогда итоговая трудоёмкость этой операции
+
дерева хотя бы на один меньшей высоты и делается ещё <tex>O(1)</tex> операций. Тогда итоговая трудоёмкость этой операции
 
равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
 
равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
  
=== Merge ===
+
=== merge ===
 
[[file:merge.png|thumb|400px|Операция merge]]
 
[[file:merge.png|thumb|400px|Операция merge]]
  
Рассмотрим вторую операцию с декартовыми деревьями {{---}} <tex>\mathrm{Merge}</tex> (''слить'').  
+
Рассмотрим вторую операцию с декартовыми деревьями {{---}} <tex>\mathrm{merge}</tex> (''слить'').  
  
 
С помощью этой операции можно слить два декартовых дерева в одно.
 
С помощью этой операции можно слить два декартовых дерева в одно.
Причем, все ключи в первом(''левом'') дереве должны быть меньше, чем
+
Причём, все ключи в первом(''левом'') дереве должны быть меньше, чем
ключи во втором(''правом''). В результате получается дерево, в котором есть все ключи из первого и второго деревьев.
+
ключи во втором(''правом''). В результате получается дерево, в котором есть все ключи из первого и второго деревьев<tex>\mathrm{merge}(T_1, T_2) \to \{T\}</tex>
 
 
<tex>\mathrm{Merge}(T_1, T_2) \to \{T\}</tex>
 
  
 
Рассмотрим принцип работы этой операции. Пусть нужно слить деревья <tex>T_1</tex> и <tex>T_2</tex>.
 
Рассмотрим принцип работы этой операции. Пусть нужно слить деревья <tex>T_1</tex> и <tex>T_2</tex>.
 
Тогда, очевидно, у результирующего дерева <tex>T</tex> есть корень.  
 
Тогда, очевидно, у результирующего дерева <tex>T</tex> есть корень.  
Корнем станет вершина из <tex>T_1</tex> или <tex>T_2</tex> с наибольшим ключом <tex>y</tex>. Но вершина с самым большим <tex>y</tex> из всех вершин деревьев  
+
Корнем станет вершина из <tex>T_1</tex> или <tex>T_2</tex> с наибольшим приоритетом <tex>y</tex>. Но вершина с самым большим <tex>y</tex> из всех вершин деревьев  
 
<tex>T_1</tex> и <tex>T_2</tex> может быть только либо корнем <tex>T_1</tex>, либо корнем <tex>T_2</tex>.
 
<tex>T_1</tex> и <tex>T_2</tex> может быть только либо корнем <tex>T_1</tex>, либо корнем <tex>T_2</tex>.
 
Рассмотрим случай, в котором корень <tex>T_1</tex> имеет больший <tex>y</tex>, чем корень <tex>T_2</tex>.
 
Рассмотрим случай, в котором корень <tex>T_1</tex> имеет больший <tex>y</tex>, чем корень <tex>T_2</tex>.
Строка 65: Строка 62:
 
<tex>T_1</tex> и дерева <tex>T_2</tex>.
 
<tex>T_1</tex> и дерева <tex>T_2</tex>.
  
Псевдокод:
+
=== Псевдокод ===
<pre>
+
 
Merge(Treap &t, Treap t1, Treap t2)
+
'''Treap''' merge(t1: '''Treap''', t2: '''Treap'''):
  if t1 == NULL or t2 == NULL
+
  '''if''' t2 == <tex> \varnothing </tex>
    if t1 != NULL
+
    '''return''' t1
      t = t1;
+
  '''if''' t1 == <tex> \varnothing </tex>
    else
+
    '''return''' t2
      t = t2;
+
  '''else if''' t1.y > t2.y
  else if t1.y > t2.y
+
    t1.right = merge(t1.right, t2)
    Merge(t1.right, t1.right, t2);
+
    '''return''' t1
    t = t1;
+
  '''else'''
  else  
+
    t2.left = merge(t1, t2.left)
    Merge(t2.left, t1, t2.left);
+
    '''return''' t2
    t = t2;
+
 
</pre>
+
=== Время работы ===
  
Рассуждая аналогично операции <tex>\mathrm{Split}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{Merge}</tex>  
+
Рассуждая аналогично операции <tex>\mathrm{split}</tex>, приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex>  
 
равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
 
равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
  
=== Insert ===
+
=== insert ===
Операция <tex>\mathrm{Insert}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет.
+
Операция <tex>\mathrm{insert}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex> {{---}} приоритет.
  
 
Представим что элемент <tex>k</tex>, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево <tex>T</tex>, очевидно, нам нужно их слить. Но <tex>T</tex> может содержать ключи как меньше, так и больше ключа <tex>k.x</tex>, поэтому сначала нужно разрезать <tex>T</tex> по ключу <tex>k.x</tex>.
 
Представим что элемент <tex>k</tex>, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево <tex>T</tex>, очевидно, нам нужно их слить. Но <tex>T</tex> может содержать ключи как меньше, так и больше ключа <tex>k.x</tex>, поэтому сначала нужно разрезать <tex>T</tex> по ключу <tex>k.x</tex>.
  
 
* Реализация №1  
 
* Реализация №1  
# Разобьём наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{Split}(T, k.x) \to \{T_1, T_2\}</tex>.
+
# Разобьём наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{split}(T, k.x) \to \langle T_1, T_2\rangle</tex>.
# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{Merge}(T_1, k) \to T_1</tex>.
+
# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{merge}(T_1, k) \to T_1</tex>.
# Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{Merge}(T_1, T_2) \to T</tex>.
+
# Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{merge}(T_1, T_2) \to T</tex>.
  
 
* Реализация №2   
 
* Реализация №2   
 
# Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>.
 
# Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>.
# Теперь вызываем <tex>\mathrm{Split}(T, k.x) \to \{T_1, T_2\}</tex> от найденного элемента (от элемента вместе со всем его поддеревом)  
+
# Теперь вызываем <tex>\mathrm{split}(T, k.x) \to \langle T_1, T_2\rangle</tex> от найденного элемента (от элемента вместе со всем его поддеревом)  
 
# Полученные <tex>T_1</tex> и <tex>T_2</tex> записываем в качестве левого и правого сына добавляемого элемента.
 
# Полученные <tex>T_1</tex> и <tex>T_2</tex> записываем в качестве левого и правого сына добавляемого элемента.
 
# Полученное дерево ставим на место элемента, найденного в первом пункте.
 
# Полученное дерево ставим на место элемента, найденного в первом пункте.
  
В первой реализации два раза используется <tex>\mathrm{Merge}</tex>, а во второй реализации слияние вообще не используется.
+
В первой реализации два раза используется <tex>\mathrm{merge}</tex>, а во второй реализации слияние вообще не используется.
  
=== Remove ===
+
=== remove ===
Операция <tex>\mathrm{Remove}(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.
+
Операция <tex>\mathrm{remove}(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.
  
 
* Реализация №1
 
* Реализация №1
  
# Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{Split }(T, k.x) \to \{T_1, T_2\}</tex>.
+
# Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{split }(T, k.x) \to \langle T_1, T_2\rangle</tex>.
# Теперь отделяем от первого дерева элемент <tex>x</tex>, опять таки разбивая по ключу <tex>x</tex>, то есть <tex>\mathrm{Split }(T_1, k.x - \varepsilon) \to \{T_1, T_3\}</tex>.
+
# Теперь отделяем от первого дерева элемент <tex>x</tex>, то есть самого левого ребёнка дерева <tex> T_2 </tex>.
# Сливаем первое дерево со вторым, то есть <tex>\mathrm{Merge }(T_1, T_2) \to T</tex>.  
+
# Сливаем первое дерево со вторым, то есть <tex>\mathrm{merge }(T_1, T_2) \to T</tex>.  
  
 
* Реализация №2
 
* Реализация №2
# Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), ища удаляемый элемент.  
+
# Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), и ищем удаляемый элемент.  
# Найдя элемент, вызываем <tex>\mathrm{Merge}</tex> его левого и правого сыновей
+
# Найдя элемент, вызываем <tex>\mathrm{merge}</tex> его левого и правого сыновей
# Результат процедуры <tex>\mathrm{Merge}</tex> ставим на место удаляемого элемента.
+
# Результат процедуры <tex>\mathrm{merge}</tex> ставим на место удаляемого элемента.
  
В первой реализации два раза используется <tex>\mathrm{Split}</tex>, а во второй реализации разрезание вообще не используется.
+
В первой реализации один раз используется <tex>\mathrm{split}</tex>, а во второй реализации разрезание вообще не используется.
  
 
== Построение декартова дерева ==
 
== Построение декартова дерева ==
Пусть нам известно из каких пар <tex>(x_i, y_i)</tex> требуется построить декартово дерево, причем также известно, что <tex>x_1 < x_2 < \ldots < x_n</tex>.
+
Пусть нам известно из каких пар <tex>(x_i, y_i)</tex> требуется построить декартово дерево, причём также известно, что <tex>x_1 < x_2 < \ldots < x_n</tex>.
=== Рекурсивный алгоритм ===
+
=== Алгоритм за <tex>O(n\log n)</tex> ===
Рассмотрим приоритеты <tex>y_1 , y_2 , \ldots , y_n</tex> и выберем максимум среди них, пусть это будет <tex>y_k</tex>, и сделаем <tex>(x_k, y_k)</tex> корнем дерева (по свойству [[Двоичная куча|пирамиды]] в корне должен быть элемент с максимальным приоритетом). Проделав то же самое с <tex>y_1 , y_2 , \ldots , y_{k-1}</tex> и <tex>y_{k+1} , y_{k+2} , \ldots , y_n</tex>, получим соответственно левого и правого сына <tex>(x_k, y_k)</tex>.
+
Отсортируем все приоритеты по убыванию за <tex> O(n\log n) </tex> и выберем первый из них, пусть это будет <tex>y_k</tex>. Сделаем <tex>(x_k, y_k)</tex> корнем дерева. Проделав то же самое с остальными вершинами получим левого и правого сына <tex>(x_k, y_k)</tex>. В среднем высота Декартова дерева <tex>\log n</tex> (см. далее) и на каждом уровне мы сделали <tex>O(n)</tex> операций. Значит такой алгоритм работает за <tex>O(n\log n)</tex>.
 +
 
  
Такой алгоритм работает за <tex>O(n^2)</tex>.
+
=== Другой алгоритм за <tex>O(n\log n)</tex> ===
 +
Отсортируем пары <tex>(x_i, y_i)</tex> по убыванию <tex>x_i</tex>  и положим их в очередь. Сперва достанем из очереди первые <tex>2</tex> элемента и сольём их в дерево и положим в конец очереди, затем сделаем то же самое со следующими двумя и т.д. Таким образом, мы сольём сначала <tex>n</tex> деревьев размера <tex>1</tex>, затем <tex>\dfrac{n}{2}</tex> деревьев размера <tex>2</tex> и так далее. При этом на уменьшение размера очереди в два раза мы будем тратить суммарно <tex>O(n)</tex> время на слияния, а всего таких уменьшений будет <tex>\log n</tex>. Значит полное время работы алгоритма будет <tex>O(n\log n)</tex>.
  
=== Алгоритм за O(n) ===
+
=== Алгоритм за <tex>O(n)</tex> ===
 
Будем строить дерево слева направо, то есть начиная с <tex>(x_1, y_1)</tex> по <tex>(x_n, y_n)</tex>, при этом помнить последний добавленный элемент <tex>(x_k, y_k)</tex>. Он будет самым правым, так как у него будет максимальный ключ, а по ключам декартово дерево представляет собой [[Дерево поиска, наивная реализация|двоичное дерево поиска]]. При добавлении <tex>(x_{k+1}, y_{k+1})</tex>, пытаемся сделать его правым сыном <tex>(x_k, y_k)</tex>, это следует сделать если <tex>y_k > y_{k+1}</tex>, иначе делаем шаг к предку последнего элемента и смотрим его значение <tex>y</tex>. Поднимаемся до тех пор, пока приоритет в рассматриваемом элементе меньше приоритета в добавляемом, после чего делаем <tex>(x_{k+1}, y_{k+1})</tex> его правым сыном, а предыдущего правого сына делаем левым сыном <tex>(x_{k+1}, y_{k+1})</tex>.
 
Будем строить дерево слева направо, то есть начиная с <tex>(x_1, y_1)</tex> по <tex>(x_n, y_n)</tex>, при этом помнить последний добавленный элемент <tex>(x_k, y_k)</tex>. Он будет самым правым, так как у него будет максимальный ключ, а по ключам декартово дерево представляет собой [[Дерево поиска, наивная реализация|двоичное дерево поиска]]. При добавлении <tex>(x_{k+1}, y_{k+1})</tex>, пытаемся сделать его правым сыном <tex>(x_k, y_k)</tex>, это следует сделать если <tex>y_k > y_{k+1}</tex>, иначе делаем шаг к предку последнего элемента и смотрим его значение <tex>y</tex>. Поднимаемся до тех пор, пока приоритет в рассматриваемом элементе меньше приоритета в добавляемом, после чего делаем <tex>(x_{k+1}, y_{k+1})</tex> его правым сыном, а предыдущего правого сына делаем левым сыном <tex>(x_{k+1}, y_{k+1})</tex>.
  
Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в чьем-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за <tex>O(n)</tex>.
+
 
 +
Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в чьём-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за <tex>O(n)</tex>.
  
 
== Случайные приоритеты ==
 
== Случайные приоритеты ==
Строка 140: Строка 140:
 
Будем считать, что все выбранные приоритеты <tex>y</tex> попарно различны.
 
Будем считать, что все выбранные приоритеты <tex>y</tex> попарно различны.
  
Для начала введем несколько обозначений:
+
Для начала введём несколько обозначений:
 
* <tex>x_k</tex> {{---}} вершина с <tex>k</tex>-ым по величине ключом;
 
* <tex>x_k</tex> {{---}} вершина с <tex>k</tex>-ым по величине ключом;
* индикаторная величина <tex>A_{i, j} = \left\{\begin{array}{lllc} 1 &&, x_i\  \text{is ancestor of} \ x_j\\  
+
* индикаторная величина <tex>A_{i, j} = \left\{\begin{array}{lllc} 1 ,&& x_i\  \text{is ancestor of} \ x_j\\  
0 &&, \text{otherwise}\\
+
0 ,&& \text{otherwise}\\
 
\end{array}\right.
 
\end{array}\right.
 
</tex>
 
</tex>
* <tex>d(v)</tex> - глубина вершины <tex>v</tex>;
+
* <tex>d(v)</tex> {{---}} глубина вершины <tex>v</tex>;
  
 
В силу обозначений глубину вершины можно записать как количество предков:
 
В силу обозначений глубину вершины можно записать как количество предков:
Строка 155: Строка 155:
 
Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того,  что вершина <tex>x_i</tex> является предком вершины <tex>x_k</tex>, то есть <tex>Pr[A_{i,k} = 1]</tex>.
 
Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того,  что вершина <tex>x_i</tex> является предком вершины <tex>x_k</tex>, то есть <tex>Pr[A_{i,k} = 1]</tex>.
  
Введем новое обозначение:
+
Введём новое обозначение:
 
* <tex>X_{i, k}</tex> {{---}}  множество ключей <tex>\{x_i, \ldots, x_k\}</tex> или <tex>\{x_k, \ldots, x_i\}</tex>,  в зависимости от <tex>i < k</tex> или <tex>i > k</tex>. <tex>X_{i, k}</tex> и <tex>X_{k, i}</tex> обозначают одно и тоже, их мощность равна <tex>|k - i| + 1</tex>.  
 
* <tex>X_{i, k}</tex> {{---}}  множество ключей <tex>\{x_i, \ldots, x_k\}</tex> или <tex>\{x_k, \ldots, x_i\}</tex>,  в зависимости от <tex>i < k</tex> или <tex>i > k</tex>. <tex>X_{i, k}</tex> и <tex>X_{k, i}</tex> обозначают одно и тоже, их мощность равна <tex>|k - i| + 1</tex>.  
  
 
{{Лемма
 
{{Лемма
|statement=Для любых <tex>i \ne k</tex> , <tex>x_i</tex> является предком <tex>x_k</tex> тогда и только тогда, когда <tex>x_i</tex> имеет наименьший приоритет среди <tex>X_{i, k}</tex>.
+
|statement=Для любых <tex>i \ne k</tex> , <tex>x_i</tex> является предком <tex>x_k</tex> тогда и только тогда, когда <tex>x_i</tex> имеет наибольший приоритет среди <tex>X_{i, k}</tex>.
|proof=Если <tex>x_i</tex> является корнем, то оно является предком <tex>x_k</tex> и по определению имеет минимальный приоритет среди всех вершин, следовательно, и среди <tex>X_{i, k}</tex>.
+
|proof=Если <tex>x_i</tex> является корнем, то оно является предком <tex>x_k</tex> и по определению имеет максимальный приоритет среди всех вершин, следовательно, и среди <tex>X_{i, k}</tex>.
  
С другой стороны,  если <tex>x_k</tex> {{---}}  корень,  то <tex>x_i</tex> {{---}}  не предок <tex>x_k</tex>, и <tex>x_k</tex> имеет минимальный приоритет в декартовом дереве; следовательно, <tex>x_i</tex> не имеет наименьший приоритет среди <tex>X_{i, k}</tex>.
+
С другой стороны,  если <tex>x_k</tex> {{---}}  корень,  то <tex>x_i</tex> {{---}}  не предок <tex>x_k</tex>, и <tex>x_k</tex> имеет максимальный приоритет в декартовом дереве; следовательно, <tex>x_i</tex> не имеет наибольший приоритет среди <tex>X_{i, k}</tex>.
  
Теперь предположим, что какая-то другая  вершина <tex>x_m</tex> корень. Тогда, если <tex>x_i</tex> и <tex>x_k</tex> лежат в разных поддеревьях, то <tex>i < m < k</tex> или <tex>i > m > k</tex>, следовательно, <tex>x_m</tex> содержится в <tex>X_{i , k}</tex>. В этом случае <tex>x_i</tex> не предок <tex>x_k</tex>, и наименьший приоритет среди <tex>X_{i, k}</tex> имеет вершина с номером <tex>m</tex>.
+
Теперь предположим, что какая-то другая  вершина <tex>x_m</tex> {{---}} корень. Тогда, если <tex>x_i</tex> и <tex>x_k</tex> лежат в разных поддеревьях, то <tex>i < m < k</tex> или <tex>i > m > k</tex>, следовательно, <tex>x_m</tex> содержится в <tex>X_{i , k}</tex>. В этом случае <tex>x_i</tex> {{---}} не предок <tex>x_k</tex>, и наибольший приоритет среди <tex>X_{i, k}</tex> имеет вершина с номером <tex>m</tex>.
  
 
Наконец,  если <tex>x_i</tex> и <tex>x_k</tex> лежат в одном поддереве,  то доказательство применяется по индукции: пустое декартово дерево есть тривиальная база,  а рассматриваемое поддерево является меньшим декартовым деревом.  
 
Наконец,  если <tex>x_i</tex> и <tex>x_k</tex> лежат в одном поддереве,  то доказательство применяется по индукции: пустое декартово дерево есть тривиальная база,  а рассматриваемое поддерево является меньшим декартовым деревом.  
 
}}
 
}}
  
Так как распределение приоритетов равномерное, каждая вершина среди <tex>X_{i, k}</tex> может иметь минимальный приоритет,  мы немедленно приходим к следующему равенству:  
+
Так как распределение приоритетов равномерное, каждая вершина среди <tex>X_{i, k}</tex> может иметь максимальный приоритет,  мы немедленно приходим к следующему равенству:  
: <tex>Pr[A_{i, j} = 1] = \left\{\begin{array}{lllc} \frac{1}{k - i + 1} &&, k \ > \ i\\  
+
: <tex>Pr[A_{i, k} = 1] = \left\{\begin{array}{lllc} \dfrac{1}{k - i + 1} ,&& k \ > \ i\\  
0 &&, k\ =\ i\\
+
0 ,&& k\ =\ i\\
\frac{1}{i - k + 1} &&, k \ < \ i\\
+
\dfrac{1}{i - k + 1} ,&& k \ < \ i\\
 
\end{array}\right.
 
\end{array}\right.
 
</tex>
 
</tex>
  
Подставив последнее в нашу формулу с математическим ожиданием получим:
+
Подставив последнее в нашу формулу с математическим ожиданием получим:  
: <tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] = \sum\limits_{i = 1}^{k - 1} \frac{1}{k - i + 1} + \sum\limits_{i = k + 1}^{n} \frac{1}{i - k + 1} \le \ln(k) + \ln(n-k) + 2</tex> (здесь мы использовали неравенство <tex>\sum\limits_{i = 1}^{n}  \frac{1}{i} \le \ln(n) + 1</tex>)
+
:<tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] = \sum\limits_{i = 1}^{k - 1}\dfrac{1}{k - i + 1} + \sum\limits_{i = k + 1}^{n}\dfrac{1}{i - k + 1} \leqslant </tex>
 +
<tex>\leqslant \ln(k) + \ln(n - k)+2</tex> (здесь мы использовали неравенство <tex>\sum\limits_{i = 1}^{n}  \dfrac{1}{i} \leqslant \ln(n) + 1</tex>)
 
: <tex>\log(n)</tex> отличается от <tex>\ln(n)</tex> в константу раз, поэтому <tex>\log(n) = O(\ln(n))</tex>.
 
: <tex>\log(n)</tex> отличается от <tex>\ln(n)</tex> в константу раз, поэтому <tex>\log(n) = O(\ln(n))</tex>.
  
Строка 183: Строка 184:
 
}}
 
}}
  
Таким образом, среднее время работы операций <tex>\mathrm{Split}</tex> и <tex>\mathrm{Merge}</tex> будет <tex>O(\log(n))</tex>.
+
Таким образом, среднее время работы операций <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex> будет <tex>O(\log(n))</tex>.
  
 
== См. также ==
 
== См. также ==
 
* [[Декартово дерево по неявному ключу]]
 
* [[Декартово дерево по неявному ключу]]
  
== Ссылки ==
+
== Источники информации ==
 
*[http://ru.wikipedia.org/wiki/Декартово_дерево Декартово дерево — Википедия]
 
*[http://ru.wikipedia.org/wiki/Декартово_дерево Декартово дерево — Википедия]
 
*[http://rain.ifmo.ru/cat/data/theory/trees/treaps-2006/article.pdf Treaps и T-Treaps]
 
*[http://rain.ifmo.ru/cat/data/theory/trees/treaps-2006/article.pdf Treaps и T-Treaps]

Текущая версия на 19:35, 4 сентября 2022

Эта статья про курево

Декартово дерево или дерамида (англ. Treap) — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), также существует название курево (куча + дерево).

Более строго, это бинарное дерево, в узлах которого хранятся пары [math] (x,y) [/math], где [math]x[/math] — это ключ, а [math]y[/math] — это приоритет. Также оно является двоичным деревом поиска по [math]x[/math] и пирамидой по [math]y[/math]. Предполагая, что все [math]x[/math] и все [math]y[/math] являются различными, получаем, что если некоторый элемент дерева содержит [math](x_0,y_0)[/math], то у всех элементов в левом поддереве [math]x \lt x_0[/math], у всех элементов в правом поддереве [math] x \gt x_0[/math], а также и в левом, и в правом поддереве имеем: [math] y \lt y_0[/math].

Дерамиды были предложены Сиделем (Siedel) и Арагон (Aragon) в 1996 г.

Операции в декартовом дереве

split

Операция split

Операция [math]\mathrm{split}[/math] (разрезать) позволяет сделать следующее: разрезать исходное дерево [math]T[/math] по ключу [math]k[/math]. Возвращать она будет такую пару деревьев [math]\langle T_1, T_2\rangle [/math], что в дереве [math]T_1[/math] ключи меньше [math]k[/math], а в дереве [math]T_2[/math] все остальные: [math]\mathrm{split}(T, k) \to \langle T_1, T_2\rangle [/math].

Эта операция устроена следующим образом.

Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня. Посмотрим, как будут устроены результирующие деревья [math]T_1[/math] и [math]T_2[/math]:

  • [math]T_1[/math]: левое поддерево [math]T_1[/math] совпадёт с левым поддеревом [math]T[/math]. Для нахождения правого поддерева [math]T_1[/math], нужно разрезать правое поддерево [math]T[/math] на [math]T^R_1[/math] и [math]T^R_2[/math] по ключу [math]k[/math] и взять [math]T^R_1[/math].
  • [math]T_2[/math] совпадёт с [math]T^R_2[/math].

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

Псевдокод

[math]\langle[/math]Treap, Treap[math]\rangle[/math] split(t: Treap, k: int):
  if t == [math] \varnothing [/math]
    return [math]\langle[/math][math] \varnothing [/math], [math] \varnothing [/math][math]\rangle[/math]     
  else if k > t.x 
    [math]\langle[/math]t1, t2[math]\rangle[/math] = split(t.right, k)
    t.right = t1
    return [math]\langle[/math]t, t2[math]\rangle[/math]
  else 
    [math]\langle[/math]t1, t2[math]\rangle[/math] = split(t.left, k)
    t.left = t2
    return [math]\langle[/math]t1, t[math]\rangle[/math]

Время работы

Оценим время работы операции [math]\mathrm{split}[/math]. Во время выполнения вызывается одна операция [math]\mathrm{split}[/math] для дерева хотя бы на один меньшей высоты и делается ещё [math]O(1)[/math] операций. Тогда итоговая трудоёмкость этой операции равна [math]O(h)[/math], где [math]h[/math] — высота дерева.

merge

Операция merge

Рассмотрим вторую операцию с декартовыми деревьями — [math]\mathrm{merge}[/math] (слить).

С помощью этой операции можно слить два декартовых дерева в одно. Причём, все ключи в первом(левом) дереве должны быть меньше, чем ключи во втором(правом). В результате получается дерево, в котором есть все ключи из первого и второго деревьев: [math]\mathrm{merge}(T_1, T_2) \to \{T\}[/math]

Рассмотрим принцип работы этой операции. Пусть нужно слить деревья [math]T_1[/math] и [math]T_2[/math]. Тогда, очевидно, у результирующего дерева [math]T[/math] есть корень. Корнем станет вершина из [math]T_1[/math] или [math]T_2[/math] с наибольшим приоритетом [math]y[/math]. Но вершина с самым большим [math]y[/math] из всех вершин деревьев [math]T_1[/math] и [math]T_2[/math] может быть только либо корнем [math]T_1[/math], либо корнем [math]T_2[/math]. Рассмотрим случай, в котором корень [math]T_1[/math] имеет больший [math]y[/math], чем корень [math]T_2[/math]. Случай, в котором корень [math]T_2[/math] имеет больший [math]y[/math], чем корень [math]T_1[/math], симметричен этому.

Если [math]y[/math] корня [math]T_1[/math] больше [math]y[/math] корня [math]T_2[/math], то он и будет являться корнем. Тогда левое поддерево [math]T[/math] совпадёт с левым поддеревом [math]T_1[/math]. Справа же нужно подвесить объединение правого поддерева [math]T_1[/math] и дерева [math]T_2[/math].

Псевдокод

Treap merge(t1: Treap, t2: Treap):
  if t2 == [math] \varnothing [/math]
    return t1
  if t1 == [math] \varnothing [/math]
    return t2
  else if t1.y > t2.y
    t1.right = merge(t1.right, t2)
    return t1
  else 
    t2.left = merge(t1, t2.left)
    return t2

Время работы

Рассуждая аналогично операции [math]\mathrm{split}[/math], приходим к выводу, что трудоёмкость операции [math]\mathrm{merge}[/math] равна [math]O(h)[/math], где [math]h[/math] — высота дерева.

insert

Операция [math]\mathrm{insert}(T, k)[/math] добавляет в дерево [math]T[/math] элемент [math]k[/math], где [math]k.x[/math] — ключ, а [math]k.y[/math] — приоритет.

Представим что элемент [math]k[/math], это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево [math]T[/math], очевидно, нам нужно их слить. Но [math]T[/math] может содержать ключи как меньше, так и больше ключа [math]k.x[/math], поэтому сначала нужно разрезать [math]T[/math] по ключу [math]k.x[/math].

  • Реализация №1
  1. Разобьём наше дерево по ключу, который мы хотим добавить, то есть [math]\mathrm{split}(T, k.x) \to \langle T_1, T_2\rangle[/math].
  2. Сливаем первое дерево с новым элементом, то есть [math]\mathrm{merge}(T_1, k) \to T_1[/math].
  3. Сливаем получившиеся дерево со вторым, то есть [math]\mathrm{merge}(T_1, T_2) \to T[/math].
  • Реализация №2
  1. Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по [math]k.x[/math]), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше [math]k.y[/math].
  2. Теперь вызываем [math]\mathrm{split}(T, k.x) \to \langle T_1, T_2\rangle[/math] от найденного элемента (от элемента вместе со всем его поддеревом)
  3. Полученные [math]T_1[/math] и [math]T_2[/math] записываем в качестве левого и правого сына добавляемого элемента.
  4. Полученное дерево ставим на место элемента, найденного в первом пункте.

В первой реализации два раза используется [math]\mathrm{merge}[/math], а во второй реализации слияние вообще не используется.

remove

Операция [math]\mathrm{remove}(T, x)[/math] удаляет из дерева [math]T[/math] элемент с ключом [math]x[/math].

  • Реализация №1
  1. Разобьём наше дерево по ключу, который мы хотим удалить, то есть [math]\mathrm{split }(T, k.x) \to \langle T_1, T_2\rangle[/math].
  2. Теперь отделяем от первого дерева элемент [math]x[/math], то есть самого левого ребёнка дерева [math] T_2 [/math].
  3. Сливаем первое дерево со вторым, то есть [math]\mathrm{merge }(T_1, T_2) \to T[/math].
  • Реализация №2
  1. Спускаемся по дереву (как в обычном бинарном дереве поиска по [math]x[/math]), и ищем удаляемый элемент.
  2. Найдя элемент, вызываем [math]\mathrm{merge}[/math] его левого и правого сыновей
  3. Результат процедуры [math]\mathrm{merge}[/math] ставим на место удаляемого элемента.

В первой реализации один раз используется [math]\mathrm{split}[/math], а во второй реализации разрезание вообще не используется.

Построение декартова дерева

Пусть нам известно из каких пар [math](x_i, y_i)[/math] требуется построить декартово дерево, причём также известно, что [math]x_1 \lt x_2 \lt \ldots \lt x_n[/math].

Алгоритм за [math]O(n\log n)[/math]

Отсортируем все приоритеты по убыванию за [math] O(n\log n) [/math] и выберем первый из них, пусть это будет [math]y_k[/math]. Сделаем [math](x_k, y_k)[/math] корнем дерева. Проделав то же самое с остальными вершинами получим левого и правого сына [math](x_k, y_k)[/math]. В среднем высота Декартова дерева [math]\log n[/math] (см. далее) и на каждом уровне мы сделали [math]O(n)[/math] операций. Значит такой алгоритм работает за [math]O(n\log n)[/math].


Другой алгоритм за [math]O(n\log n)[/math]

Отсортируем пары [math](x_i, y_i)[/math] по убыванию [math]x_i[/math] и положим их в очередь. Сперва достанем из очереди первые [math]2[/math] элемента и сольём их в дерево и положим в конец очереди, затем сделаем то же самое со следующими двумя и т.д. Таким образом, мы сольём сначала [math]n[/math] деревьев размера [math]1[/math], затем [math]\dfrac{n}{2}[/math] деревьев размера [math]2[/math] и так далее. При этом на уменьшение размера очереди в два раза мы будем тратить суммарно [math]O(n)[/math] время на слияния, а всего таких уменьшений будет [math]\log n[/math]. Значит полное время работы алгоритма будет [math]O(n\log n)[/math].

Алгоритм за [math]O(n)[/math]

Будем строить дерево слева направо, то есть начиная с [math](x_1, y_1)[/math] по [math](x_n, y_n)[/math], при этом помнить последний добавленный элемент [math](x_k, y_k)[/math]. Он будет самым правым, так как у него будет максимальный ключ, а по ключам декартово дерево представляет собой двоичное дерево поиска. При добавлении [math](x_{k+1}, y_{k+1})[/math], пытаемся сделать его правым сыном [math](x_k, y_k)[/math], это следует сделать если [math]y_k \gt y_{k+1}[/math], иначе делаем шаг к предку последнего элемента и смотрим его значение [math]y[/math]. Поднимаемся до тех пор, пока приоритет в рассматриваемом элементе меньше приоритета в добавляемом, после чего делаем [math](x_{k+1}, y_{k+1})[/math] его правым сыном, а предыдущего правого сына делаем левым сыном [math](x_{k+1}, y_{k+1})[/math].


Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в чьём-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за [math]O(n)[/math].

Случайные приоритеты

Мы уже выяснили, что сложность операций с декартовым деревом линейно зависит от его высоты. В действительности высота декартова дерева может быть линейной относительно его размеров. Например, высота декартова дерева, построенного по набору ключей [math](1, 1), \ldots, (n, n)[/math], будет равна [math]n[/math]. Во избежание таких случаев, полезным оказывается выбирать приоритеты в ключах случайно.

Высота в декартовом дереве с случайными приоритетами

Теорема:
В декартовом дереве из [math]n[/math] узлов, приоритеты [math]y[/math] которого являются случайными величинами c равномерным распределением, средняя глубина вершины [math]O(\log n)[/math].
Доказательство:
[math]\triangleright[/math]

Будем считать, что все выбранные приоритеты [math]y[/math] попарно различны.

Для начала введём несколько обозначений:

  • [math]x_k[/math] — вершина с [math]k[/math]-ым по величине ключом;
  • индикаторная величина [math]A_{i, j} = \left\{\begin{array}{lllc} 1 ,&& x_i\ \text{is ancestor of} \ x_j\\ 0 ,&& \text{otherwise}\\ \end{array}\right. [/math]
  • [math]d(v)[/math] — глубина вершины [math]v[/math];

В силу обозначений глубину вершины можно записать как количество предков:

[math]d(x_k) = \sum\limits_{i = 1}^{n} A_{i,k} [/math].

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

[math]E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] [/math] — здесь мы использовали линейность математического ожидания, и то что [math]E(X) = Pr[X = 1][/math] для индикаторной величины [math]X[/math] ([math]Pr[A][/math] — вероятность события [math]A[/math]).

Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того, что вершина [math]x_i[/math] является предком вершины [math]x_k[/math], то есть [math]Pr[A_{i,k} = 1][/math].

Введём новое обозначение:

  • [math]X_{i, k}[/math] — множество ключей [math]\{x_i, \ldots, x_k\}[/math] или [math]\{x_k, \ldots, x_i\}[/math], в зависимости от [math]i \lt k[/math] или [math]i \gt k[/math]. [math]X_{i, k}[/math] и [math]X_{k, i}[/math] обозначают одно и тоже, их мощность равна [math]|k - i| + 1[/math].
Лемма:
Для любых [math]i \ne k[/math] , [math]x_i[/math] является предком [math]x_k[/math] тогда и только тогда, когда [math]x_i[/math] имеет наибольший приоритет среди [math]X_{i, k}[/math].
Доказательство:
[math]\triangleright[/math]

Если [math]x_i[/math] является корнем, то оно является предком [math]x_k[/math] и по определению имеет максимальный приоритет среди всех вершин, следовательно, и среди [math]X_{i, k}[/math].

С другой стороны, если [math]x_k[/math] — корень, то [math]x_i[/math] — не предок [math]x_k[/math], и [math]x_k[/math] имеет максимальный приоритет в декартовом дереве; следовательно, [math]x_i[/math] не имеет наибольший приоритет среди [math]X_{i, k}[/math].

Теперь предположим, что какая-то другая вершина [math]x_m[/math] — корень. Тогда, если [math]x_i[/math] и [math]x_k[/math] лежат в разных поддеревьях, то [math]i \lt m \lt k[/math] или [math]i \gt m \gt k[/math], следовательно, [math]x_m[/math] содержится в [math]X_{i , k}[/math]. В этом случае [math]x_i[/math] — не предок [math]x_k[/math], и наибольший приоритет среди [math]X_{i, k}[/math] имеет вершина с номером [math]m[/math].

Наконец, если [math]x_i[/math] и [math]x_k[/math] лежат в одном поддереве, то доказательство применяется по индукции: пустое декартово дерево есть тривиальная база, а рассматриваемое поддерево является меньшим декартовым деревом.
[math]\triangleleft[/math]

Так как распределение приоритетов равномерное, каждая вершина среди [math]X_{i, k}[/math] может иметь максимальный приоритет, мы немедленно приходим к следующему равенству:

[math]Pr[A_{i, k} = 1] = \left\{\begin{array}{lllc} \dfrac{1}{k - i + 1} ,&& k \ \gt \ i\\ 0 ,&& k\ =\ i\\ \dfrac{1}{i - k + 1} ,&& k \ \lt \ i\\ \end{array}\right. [/math]

Подставив последнее в нашу формулу с математическим ожиданием получим:

[math]E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] = \sum\limits_{i = 1}^{k - 1}\dfrac{1}{k - i + 1} + \sum\limits_{i = k + 1}^{n}\dfrac{1}{i - k + 1} \leqslant [/math]

[math]\leqslant \ln(k) + \ln(n - k)+2[/math] (здесь мы использовали неравенство [math]\sum\limits_{i = 1}^{n} \dfrac{1}{i} \leqslant \ln(n) + 1[/math])

[math]\log(n)[/math] отличается от [math]\ln(n)[/math] в константу раз, поэтому [math]\log(n) = O(\ln(n))[/math].
В итоге мы получили что [math]E(d(x_k)) = O(\log(n))[/math].
[math]\triangleleft[/math]

Таким образом, среднее время работы операций [math]\mathrm{split}[/math] и [math]\mathrm{merge}[/math] будет [math]O(\log(n))[/math].

См. также

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