Изменения

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

== Описание =='''Декартово деревоили дерамида''' (англ. ''Treap'') {{---}} это структура данных, объединяющая в себе [[Дерево поиска, наивная реализация|бинарное дерево поиска ]] и [[Двоичная куча|бинарную кучу ]] (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), так же также существует название курево (куча + дерево).

Более строго, это структура данныхбинарное дерево, которая хранит в узлах которого хранятся пары <tex> (Xx,Yy) </tex> в виде бинарного дерева таким образом, что она где <tex>x</tex> {{---}} это ключ, а <tex>y</tex> {{---}} это приоритет. Также оно является бинарным двоичным деревом поиска по <tex>x</tex> и бинарной пирамидой по <tex>y</tex>. Предполагая, что все <tex>Xx</tex> и все <tex>Yy</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(X_0x_0,Y_0y_0)</tex>, то у всех элементов в левом поддереве <tex>X x < X_0x_0</tex>, у всех элементов в правом поддереве <tex> X x > X_0x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> Y y < Y_0y_0</tex>.

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

=== Split split ===

Операция <tex>\mathrm{Splitsplit}</tex> (''разрезать'') позволяет сделать следующее: разрезать декартово исходное дерево <tex>T</tex> по ключу <tex>xk</tex> и получить два других декартовых дерева: . Возвращать она будет такую пару деревьев <tex>\langle T_1</tex> и <tex>, T_2\rangle </tex>, причем что в дереве <tex>T_1</tex>находятся все ключи дерева <tex>T</tex>, не большие меньше <tex>xk</tex>, а в дереве <tex>T_2</tex> {{---}} большие <tex>x</tex>. все остальные: <tex>\mathrm{Splitsplit}(T, xk) \to \{langle T_1, T_2\}rangle </tex>.

* <tex>T_1</tex>: левое поддерево <tex>T_1</tex> совпадёт с левым поддеревом <tex>T</tex>. Для нахождения правого поддерева <tex>T_1</tex>, нужно разрезать правое поддерево <tex>T</tex> на <tex>T^R_1</tex> и <tex>T^R_2</tex> по ключу <tex>xk</tex> и взять <tex>T^R_1</tex>.

Оценим время работы операции === Псевдокод ===  '''<tex>\langle</tex>Treap, Treap<tex>\rangle</tex>''' split(t: '''Treap''', k: '''int'''): '''if''' t == <tex> \varnothing </tex> '''return''' <tex>\langle</tex><tex> \varnothing </tex>, <tex> \varnothing </tex><tex>\mathrm{Split}rangle</tex> '''else if''' k > t. Во время выполнения вызывается одна операция x <tex>\mathrm{Split}langle</tex> длядерева хотя бы на один меньшей высоты и делается ещё t1, t2<tex>\mathcal{O}rangle</tex> = split(1t.right, k) t.right = t1 '''return''' <tex>\langle</tex>t, t2<tex>\rangle</tex> операция. Тогда итоговая трудоёмкость этой операцииравна '''else''' <tex>\langle</tex>t1, t2<tex>\mathcal{O}rangle</tex> = split(ht.left, k) t.left = t2 '''return''' <tex>\langle</tex>t1, где t<tex>h\rangle</tex> {{---}} высота дерева. === Время работы ===

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

Рассмотрим вторую операцию с декартовыми деревьями {{---}} <tex>\mathrm{Mergemerge}</tex>(''слить'').

ПричемПричём, все ключи в первом(''левом'') дереве должны быть меньше, чемключи во втором(''правом''). В результате получается дерево, в котором есть все ключи из первого и второго деревьев. : <tex>\mathrm{Mergemerge}(T_1, T_2) \to \{T\}</tex>

Корнем станет вершина из <tex>T_1</tex> или <tex>T_2</tex> с наибольшим ключом приоритетом <tex>y</tex>. Но вершина с самым большим <tex>y</tex> из всех вершин деревьев

=== Псевдокод ===  '''Treap''' merge(t1: '''Treap''', t2: '''Treap'''): '''if''' t2 == <tex> \varnothing </tex> '''return''' t1 '''if''' t1 == <tex> \varnothing </tex> '''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 === Время работы === Рассуждая аналогично операции <tex>\mathrm{Splitsplit}</tex> , приходим к выводу, что трудоёмкость операции <tex>\mathrm{Mergemerge}</tex> равна <tex>\mathcal{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> {{---}} приоритет.

=== Insert ===Операция Представим что элемент <tex>\mathrm{Insert}(T, k)</tex> добавляет , это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево <tex>T</tex> элемент , очевидно, нам нужно их слить. Но <tex>kT</tex>может содержать ключи как меньше, где так и больше ключа <tex>k.x</tex> {{---}} ключ, а поэтому сначала нужно разрезать <tex>T</tex> по ключу <tex>k.yx</tex>{{---}} приоритет.

# Разобьём наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{Splitsplit}(T, k.x) \to \{langle T_1, T_2\}rangle</tex>.# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{Mergemerge}(T_1, k) \to T_1</tex>.# Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{Mergemerge}(T_1, T_2) \to T</tex>.

# Теперь вызываем <tex>\mathrm{Split split}(T, k.x) \to \{langle T_1, T_2\}rangle</tex> от найденного элемента (от элемента вместе со всем его поддеревом)

В первой реализации два раза используется <tex>\mathrm{merge}</tex>, а во второй реализации слияние вообще не используется. === Remove remove ===Операция <tex>\mathrm{Removeremove}(T, x)</tex> удаляет из дерева <tex>T</tex> элемент с ключом <tex>x</tex>.

# Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{Split 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\}T_2 </tex>.# Сливаем первое дерево со вторым, то есть <tex>\mathrm{Merge merge }(T_1, T_2) \to T</tex>.

# Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), ища и ищем удаляемый элемент. # Найдя элемент, вызываем <tex>Merge\mathrm{merge}</tex> его левого и правого сыновей# Возвращаемое значение функции Результат процедуры <tex>Merge\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\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>. === Алгоритм за <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>.

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

|statement = Декартово дерево В декартовом дереве из <tex>n</tex> узлов, ключи приоритеты <tex>y</tex> которых которого являются незавимыми непрерывными [[Дискретная случайная величина|случайными величинами с одинаковым вероятностным ]] c равномерным распределением, имеет высоту средняя глубина вершины <tex>O(\log 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\\ 0 ,&& \text{otherwise}\\\end{array}\right.</tex>* <tex>d(v)</tex> {{---}} глубина вершины <tex>v</tex>; В следующих утверждениях силу обозначений глубину вершины можно записать как количество предков::<tex>d(x_k) = \sum\limits_{i = 1}^{n} A_{i,k} </tex>. Теперь можно выразить [[Математическое ожидание случайной величины|математическое ожидание]] глубины конкретной вершины::<tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] </tex> {{---}} здесь мы будем считатьиспользовали линейность математического ожидания, и то что <tex>E(X) = Pr[X = 1]</tex> для индикаторной величины <tex>X</tex> (<tex>Pr[A]</tex> {{---}} вероятность события <tex>A</tex>).Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того, что вершина <tex>x_i</tex> является предком вершины <tex>x_k</tex>, то есть <tex>Pr[A_{i,k} = 1]</tex>. Введём новое обозначение:* <tex>X_{i, k}</tex> {{---}} множество ключей <tex>x_1 \{x_i, \ldots, x_k\}< x_2 /tex> или < tex>\{x_k, \ldots x_n, x_i\}</tex>, а каждое в зависимости от <tex>i < k</tex> или <tex>i > k</tex>. <tex>y_iX_{i, k}</tex> выбрано случайно и независимо с одинаковым распределением, а также будем называть <tex>X_{k, i}</tex>-м узлом узел с ключом обозначают одно и тоже, их мощность равна <tex>x_i|k - i| + 1</tex>.

|statement = Для любых <tex>i\ne k</tex> , <tex>x_i</tex>-й узел является прародителем предком <tex>kx_k</tex>-го узла тогда и толькотогда, когда <tex>y_i x_i< y_j/tex> имеет наибольший приоритет среди <tex>X_{i, k}</tex> для любого .|proof=Если <tex>jx_i</tex> такогоявляется корнем, что то оно является предком <tex>i < j \leqslant kx_k</tex> или и по определению имеет максимальный приоритет среди всех вершин, следовательно, и среди <tex>X_{i, k \leqslant j < i}</tex>.|proof=Рассмотрим случай С другой стороны, если <tex>x_k</tex> {{---}} корень, то <tex>i x_i</tex> {{---}} не предок < ktex>x_k</tex>, и <tex>x_k</tex> имеет максимальный приоритет в случае декартовом дереве; следовательно, <tex>x_i</tex> не имеет наибольший приоритет среди <tex>X_{i > , k}</tex> доказательство аналогично.

Необходимость. ДопустимТеперь предположим, что какая-то другая вершина <tex>y_i < y_j</tex> для всех <tex>i < j \leqslant k</tex>. Тогда по свойствам кучи <tex>ix_m</tex>{{--й узел не может лежать в поддереве с корнем в <tex>k</tex>-м узле}} корень. Более тогоТогда, не может существовать индекс если <tex>j</tex> такой, что <tex>j</tex>-й узел общий прародитель <tex>ix_i</tex>-го и <tex>kx_k</tex>-го узлов, но эти узлы лежат в его разных поддеревьях. Если он существует, то <tex>x_i i < x_j m < x_kk</tex>, следовательно, или <tex>i < j < > m > k</tex>. Но тогда , следовательно, <tex>jx_m</tex>-й не мог быть прародителем содержится в <tex>X_{i, k}</tex>-го узла (опять же по свойствам кучи). Остался последний вариант взаимного расположения В этом случае <tex>ix_i</tex>{{--го и -}} не предок <tex>kx_k</tex>-го узлов: , и наибольший приоритет среди <tex>X_{i, k}</tex>-й является прародителем имеет вершина с номером <tex>km</tex>-го узла.

Достаточность. Пусть <tex>i</tex>-й узел является предком <tex>k</tex>-го узла. Докажем от противного. ПредположимНаконец, что существует если <tex>j</tex> такое, что <tex>i < j \leqslant kx_i</tex> и <tex>y_j < y_ix_k</tex>. По свойствам кучи <tex>i</tex>-й узел не может быть прародителем <tex>j</tex>-го узла. Если <tex>j</tex>-й узел является прародителем <tex>i</tex>-го узлалежат в одном поддереве, то из неравенства <tex>x_i < x_j < x_k</tex> следуетдоказательство применяется по индукции: пустое декартово дерево есть тривиальная база, что <tex>i</tex>-й узел содержится в левом поддереве <tex>j</tex>-го узла, а <tex>k</tex>-й в правом. Это противоречит тому, что <tex>i</tex>-й узел прародитель <tex>k</tex>-го узла. Остается последний вариант взаимного расположения <tex>i</tex>-го и <tex>j</tex>-го узла: некоторый <tex>l</tex>-й узел рассматриваемое поддерево является их общим прародителям, но они содержатся в его разных поддеревьях. Тогда получаем неравенство <tex>x_i < x_l < x_j \leqslant x_k</tex>, из которого следует, что <tex>k</tex>-й узел содержится в правом поддереве <tex>l</tex>-го узла. Снова противоречие. Значит, наше предположение не верноменьшим декартовым деревом.

{{Лемма|about=о математическом ожидании глубины узла|statement=Математическое ожидание глубины Так как распределение приоритетов равномерное, каждая вершина среди <tex>X_{i, k}</tex>-го узла равно может иметь максимальный приоритет, мы немедленно приходим к следующему равенству: : <tex>H_k Pr[A_{i, k} = 1] = \left\{\begin{array}{lllc} \dfrac{1}{k - i + H_1} ,&& k \ > \ i\\ 0 ,&& k\ =\ i\\\dfrac{1}{ni -k+1} - 1,&& k \ < \ i\\\end{array}\right.</tex>, где  Подставив последнее в нашу формулу с математическим ожиданием получим: :<tex>H_j E(d(x_k)) = \sum_sum\limits_{i=1}^j{n} Pr[A_{i,k} = 1] = \fracsum\limits_{i = 1}^{k - 1}\dfrac{1}{k - i+ 1} + \approx sum\ln j</tex>.|prooflimits_{i =Глубина <tex>k</tex>+ 1}^{n}\dfrac{1}{i -го узла - это количество узлов, которые являются прародителями этого узла. Введем случайную величину <tex>A_ik + 1} \leqslant </tex>, равную единице, если <tex>i</tex>\leqslant \ln(k) + \ln(n -й узел является прародителем <tex>k)+2</tex>-го узла, и нулю в противном случае. Легко проверить, что (здесь мы использовали неравенство <tex>A_i\sum\limits_{i = 1}^{n} \dfrac{1}{i} \leqslant \ln(n) + 1</tex> и ): <tex>A_j\log(n)</tex> независимы при отличается от <tex>i \ne jln(n)</tex>. Из тогов константу раз, что поэтому <tex>y_i</tex> выбраны случайно и независимо с одинаковым распределением и предыдущей леммы следует, что <tex>M\log(A_in) = O(\frac{1}{|i - k| + 1}</tex> при <tex>i \ne kln(n))</tex>.

В итоге мы получили что <tex>ME(depth_kd(x_k))=MO(\sum_{i=1}^nA_ilog(n)=\sum_{i=1}^nM(A_i)=\sum_{i=1}^n\frac{1}{|i-k|+1}=\sum_{i=1}^k\frac{1}{k-i+1}+\sum_{i=k}^n\frac{1}{i-k+1}-1=H_k+H_{n-k+1}-1</tex>.}}

Таким образом, мы доказали, что матожидание глубины конкретного узла среднее время работы операций <tex>\mathrm{split}</tex> и <tex>\mathrm{merge}</tex> будет <tex>O(\log (n))</tex>.

== Ссылки Источники информации ==