Эта статья про Курево
Описание
Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), так же существует название курево (куча + дерево).
Более строго, это структура данных, которая хранит пары [math] (X,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
Операция [math]\mathrm{Split}[/math] (разрезать) позволяет сделать следующее: разрезать декартово дерево [math]T[/math] по ключу
[math]x[/math] и получить два других декартовых дерева: [math]T_1[/math] и [math]T_2[/math], причем в [math]T_1[/math]
находятся все ключи дерева [math]T[/math], не большие [math]x[/math], а в [math]T_2[/math] — большие [math]x[/math].
[math]\mathrm{Split}(T, x) \to \{T_1, T_2\}[/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]x[/math] и взять [math]T^R_1[/math].
- [math]T_2[/math] совпадёт с [math]T^R_2[/math].
Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.
Оценим время работы операции [math]\mathrm{Split}[/math]. Во время выполнения вызывается одна операция [math]\mathrm{Split}[/math] для
дерева хотя бы на один меньшей высоты и делается ещё [math]\mathcal{O}(1)[/math] операция. Тогда итоговая трудоёмкость этой операции
равна [math]\mathcal{O}(h)[/math], где [math]h[/math] — высота дерева.
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].
Рассуждая аналогично операции [math]\mathrm{Split}[/math] приходим к выводу, что трудоёмкость операции [math]\mathrm{Merge}[/math]
равна [math]\mathcal{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]\mathrm{Split}(T, k.x) \to \{T_1, T_2\}[/math].
- Сливаем первое дерево с новым элементом, то есть [math]\mathrm{Merge}(T_1, k) \to T_1[/math].
- Сливаем получившиеся дерево со вторым, то есть [math]\mathrm{Merge}(T_1, T_2) \to T[/math].
- Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по [math]k.x[/math]), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше [math]k.y[/math].
- Теперь вызываем [math]\mathrm{Split }(T, k.x) \to \{T_1, T_2\}[/math] от найденного элемента (от элемента вместе со всем его поддеревом)
- Полученные [math]T_1[/math] и [math]T_2[/math] записываем в качестве левого и правого сына добавляемого элемента.
- Полученное дерево ставим на место элемента, найденного в первом пункте.
Remove
Операция [math]\mathrm{Remove}(T, x)[/math] удаляет из дерева [math]T[/math] элемент с ключом [math]x[/math].
- Разобьём наше дерево по ключу, который мы хотим удалить, то есть [math]\mathrm{Split }(T, k.x) \to \{T_1, T_2\}[/math].
- Теперь отделяем от первого дерева элемент [math]x[/math], опять таки разбивая по ключу [math]x[/math], то есть [math]\mathrm{Split }(T_1, k.x - \varepsilon) \to \{T_1, T_3\}[/math].
- Сливаем первое дерево со вторым, то есть [math]\mathrm{Merge }(T_1, T_2) \to T[/math].
- Спускаемся по дереву (как в обычном бинарном дереве поиска по [math]x[/math]), ища удаляемый элемент.
- Найдя элемент, вызываем [math]Merge[/math] его левого и правого сыновей
- Возвращаемое значение функции [math]Merge[/math] ставим на место удаляемого элемента.
Высота декартового дерева
Мы уже выяснили, что сложность операций с декартовым деревом линейно зависит от его высоты. В действительности высота декартова дерева может быть линейной относительно его размеров. Например, высота декартова дерева, построенного по набору ключей [math](1, 1), \ldots, (n, n)[/math], будет равна [math]n[/math]. Во избежание таких случаев, полезным оказывается выбирать приоритеты в ключах случайно.
| Теорема: |
Декартово дерево из [math]n[/math] узлов, ключи [math]y[/math] которых являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением, имеет высоту [math]O(\log n)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Замечание: В следующих утверждениях мы будем считать, что [math]x_1 \lt x_2 \lt \ldots x_n[/math], а каждое [math]y_i[/math] выбрано случайно и независимо с одинаковым распределением, а также будем называть [math]i[/math]-м узлом узел с ключом [math]x_i[/math].
| Лемма: |
[math]i[/math]-й узел является прародителем [math]k[/math]-го узла тогда и только, когда [math]y_i \lt y_j[/math] для любого [math]j[/math] такого, что [math]i \lt j \leqslant k[/math] или [math]k \leqslant j \lt i[/math]. |
| Доказательство: |
| [math]\triangleright[/math] | |
Рассмотрим случай [math]i \lt k[/math], в случае [math]i \gt k[/math] доказательство аналогично.
Необходимость. Допустим, что [math]y_i \lt y_j[/math] для всех [math]i \lt j \leqslant k[/math]. Тогда по свойствам кучи [math]i[/math]-й узел не может лежать в поддереве с корнем в [math]k[/math]-м узле. Более того, не может существовать индекс [math]j[/math] такой, что [math]j[/math]-й узел общий прародитель [math]i[/math]-го и [math]k[/math]-го узлов, но эти узлы лежат в его разных поддеревьях. Если он существует, то [math]x_i \lt x_j \lt x_k[/math], следовательно, [math]i \lt j \lt k[/math]. Но тогда [math]j[/math]-й не мог быть прародителем [math]i[/math]-го узла (опять же по свойствам кучи). Остался последний вариант взаимного расположения [math]i[/math]-го и [math]k[/math]-го узлов: [math]i[/math]-й является прародителем [math]k[/math]-го узла.
Достаточность. Пусть [math]i[/math]-й узел является предком [math]k[/math]-го узла. Докажем от противного. Предположим, что существует [math]j[/math] такое, что [math]i \lt j \leqslant k[/math] и [math]y_j \lt y_i[/math]. По свойствам кучи [math]i[/math]-й узел не может быть прародителем [math]j[/math]-го узла. Если [math]j[/math]-й узел является прародителем [math]i[/math]-го узла, то из неравенства [math]x_i \lt x_j \lt x_k[/math] следует, что [math]i[/math]-й узел содержится в левом поддереве [math]j[/math]-го узла, а [math]k[/math]-й в правом. Это противоречит тому, что [math]i[/math]-й узел прародитель [math]k[/math]-го узла. Остается последний вариант взаимного расположения [math]i[/math]-го и [math]j[/math]-го узла: некоторый [math]l[/math]-й узел является их общим прародителям, но они содержатся в его разных поддеревьях. Тогда получаем неравенство [math]x_i \lt x_l \lt x_j \leqslant x_k[/math], из которого следует, что [math]k[/math]-й узел содержится в правом поддереве [math]l[/math]-го узла. Снова противоречие. Значит, наше предположение не верно. | | [math]\triangleleft[/math] |
| Лемма (о математическом ожидании глубины узла): |
Математическое ожидание глубины [math]k[/math]-го узла равно [math]H_k + H_{n-k+1} - 1[/math], где [math]H_j = \sum_{i=1}^j\frac{1}{i} \approx \ln j[/math]. |
| Доказательство: |
| [math]\triangleright[/math] | |
Глубина [math]k[/math]-го узла - это количество узлов, которые являются прародителями этого узла. Введем случайную величину [math]A_i[/math], равную единице, если [math]i[/math]-й узел является прародителем [math]k[/math]-го узла, и нулю в противном случае. Легко проверить, что [math]A_i[/math] и [math]A_j[/math] независимы при [math]i \ne j[/math]. Из того, что [math]y_i[/math] выбраны случайно и независимо с одинаковым распределением и предыдущей леммы следует, что [math]M(A_i) = \frac{1}{|i - k| + 1}[/math] при [math]i \ne k[/math].
[math]M(depth_k)=M(\sum_{i=1}^nA_i)=\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[/math]. | | [math]\triangleleft[/math] |
Таким образом, мы доказали, что матожидание глубины конкретного узла [math]O(\log n)[/math]. |
| [math]\triangleleft[/math] |
Ссылки
