105
правок
Изменения
м
ПричемПричём, все ключи в первом(''левом'') дереве должны быть меньше, чем
Отсортируем все приоритеты по убыванию === Другой алгоритм за <tex> O(n\log n) </tex> и выберем первый из них===Отсортируем парочки <tex>(x_i, пусть это будет y_i)</tex> по убыванию <tex>y_kx_i</tex> и положим их в очередь. Сделаем Сперва достанем из очереди первые <tex>(x_k, y_k)2</tex> корнем дерева. Проделав элемента и сольём их в дерево и положим в конец очереди, затем сделаем то же самое с остальными вершинами получим левого со следующими двумя и правого сына т.д. Таким образом, мы сольём сначала <tex>(x_k, y_k)n</tex> деревьев размера <tex>1</tex>. В среднем высота Декартова дерева , затем <tex>\log dfrac{n}{2}</tex> (смдеревьев размера <tex>2</tex> и так далее. далее) и При этом на каждом уровне уменьшение размера очереди в два раза мы сделали будем тратить суммарно <tex>O(n)</tex> время на слияния, а всего таких уменьшений будет <tex>\log n)</tex> операций. Значит такой алгоритм работает за полное время работы алгоритма будет <tex>O(n\log n)</tex>.
Введем Введём новое обозначение:
Нет описания правки
'''Декартово дерево или дерамида''' (англ. ''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>.
Дерамиды были предложены Сиделем (Siedel) и Арагоном Арагон (Aragon) в 1996 г.
== Операции в декартовом дереве ==
[[file:split.png|thumb|400px|Операция split]]
Операция <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>\mathrm{merge}(T_1, T_2) \to \{T\}</tex>
'''Treap''' merge(t1: '''Treap''', t2: '''Treap'''):
'''if''' t1 t2 == <tex> \varnothing </tex> '''return'''t1 'or''if' t2 '' t1 == <tex> \varnothing </tex> '''return''' t2 == <tex> \varnothing </tex> ? t1 : t2
'''else if''' t1.y > t2.y
t1.right = merge(t1.right, t2)
=== Время работы ===
Рассуждая аналогично операции <tex>\mathrm{split}</tex> , приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex>
равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
=== insert ===
Операция <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>\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 + 1) \to \langle T_1, T_2\rangle </tex>.
# Сливаем первое дерево со вторым, то есть <tex>\mathrm{merge }(T_1, T_2) \to T</tex>.
# Результат процедуры <tex>\mathrm{merge}</tex> ставим на место удаляемого элемента.
В первой реализации два раза один раз используется <tex>\mathrm{split}</tex>, а во второй реализации разрезание вообще не используется.
== Построение декартова дерева ==
Пусть нам известно из каких пар <tex>(x_i, y_i)</tex> требуется построить декартово дерево, причем причём также известно, что <tex>x_1 < x_2 < \ldots < x_n</tex>.
=== Алгоритм за <tex>O(n\log n)</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) </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>y</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>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>Pr[A_{i, j} = 1] = \left\{\begin{array}{lllc} \dfrac{1}{k - i + 1} ,&&, k \ > \ i\\ 0 ,&&, k\ =\ i\\\dfrac{1}{i - k + 1} ,&&, k \ < \ i\\
\end{array}\right.
</tex>
