Декартово дерево

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

Описание

Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: 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

Операция 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

Операция 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]— приоритет.

• Реализация №1

1. Разобьём наше дерево по ключу, который мы хотим добавить, то есть [math]\mathrm{Split}(T, k.x) \to \{T_1, T_2\}[/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 \{T_1, T_2\}[/math] от найденного элемента (от элемента вместе со всем его поддеревом)
3. Полученные [math]T_1[/math] и [math]T_2[/math] записываем в качестве левого и правого сына добавляемого элемента.
4. Полученное дерево ставим на место элемента, найденного в первом пункте.

Remove

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

• Реализация №1

1. Разобьём наше дерево по ключу, который мы хотим удалить, то есть [math]\mathrm{Split }(T, k.x) \to \{T_1, T_2\}[/math].
2. Теперь отделяем от первого дерева элемент [math]x[/math], опять таки разбивая по ключу [math]x[/math], то есть [math]\mathrm{Split }(T_1, k.x - \varepsilon) \to \{T_1, T_3\}[/math].
3. Сливаем первое дерево со вторым, то есть [math]\mathrm{Merge }(T_1, T_2) \to T[/math].

• Реализация №2

1. Спускаемся по дереву (как в обычном бинарном дереве поиска по [math]x[/math]), ища удаляемый элемент.
2. Найдя элемент, вызываем [math]Merge[/math] его левого и правого сыновей
3. Возвращаемое значение функции [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\limits_{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\limits_{i=1}^nA_i)=\sum\limits_{i=1}^nM(A_i)=\sum\limits_{i=1}^n\frac{1}{|i-k|+1}=[/math] [math]=\sum\limits_{i=1}^k\frac{1}{k-i+1}+\sum\limits_{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]

Ссылки

• Декартово дерево — Википедия