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

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

Описание

Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: 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_k[/math] - вершина с [math]k[/math]-ым по величине ключом;

[math]\triangleleft[/math]

Ссылки

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