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

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

Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: $treap (tree+heap)$ и дерамида (дерево+пирамида), так же существует название курево (куча + дерево).

Более строго, это структура данных, которая хранит пары $(X,Y)$ в виде бинарного дерева таким образом, что она является бинарным деревом поиска по $x$ и бинарной пирамидой по $y$. Предполагая, что все $X$ и все $Y$ являются различными, получаем, что если некоторый элемент дерева содержит $(X_0,Y_0)$, то у всех элементов в левом поддереве $X \lt X_0$, у всех элементов в правом поддереве $X \gt X_0$, а также и в левом, и в правом поддереве имеем: $Y \lt Y_0$.

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

Операция split

Операция split

Операция $\mathrm{split}$ (разрезать) позволяет сделать следующее: разрезать декартово дерево $T$ по ключу $x$ и получить два других декартовых дерева: $T_1$ и $T_2$, причем в $T_1$ находятся все ключи дерева $T$, не большие $x$, а в $T_2$ — большие $x$.

$\mathrm{split}(T, x) \to \{T_1, T_2\}$.

Эта операция устроена следующим образом.

Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня. Посмотрим, как будут устроены результирующие деревья $T_1$ и $T_2$:

• $T_1$: левое поддерево $T_1$ совпадёт с левым поддеревом $T$. Для нахождения правого поддерева $T_1$, нужно разрезать правое поддерево $T$ на $T^R_1$ и $T^R_2$ по ключу $x$ и взять $T^R_1$.
• $T_2$ совпадёт с $T^R_2$.

Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.

Оценим время работы операции $\mathrm{split}$. Во время выполнения вызывается одна операция $\mathrm{split}$ для дерева хотя бы на один меньшей высоты и делается ещё $\mathcal{O}(1)$ операция. Тогда итоговая трудоёмкость этой операции равна $\mathcal{O}(h)$, где $h$ — высота дерева. Так как высота декартова дерева — $\mathcal{O}(\log n)$, то и операция $\mathrm{split}$ работает за $\mathcal{O}(\log n)$.

Операция merge

Операция merge

Рассмотрим вторую операцию с декартовыми деревьями — $\mathrm{merge}$(слить).

С помощью этой операции можно слить два декартовых дерева в одно. Причем, все ключи в первом(левом) дереве должны быть меньше, чем ключи во втором(правом). В результате получается дерево, в котором есть все ключи из первого и второго деревьев.

$\mathrm{merge}(T_1, T_2) \to T$

Рассмотрим принцип работы этой операции. Пусть нужно слить деревья $T_1$ и $T_2$. Тогда, очевидно, у результирующего дерева $T$ есть корень. Корнем станет вершина из $T_1$ или $T_2$ с наибольшим ключом $y$. Но вершина с самым большим $y$ из всех вершин деревьев $T_1$ и $T_2$ может быть только либо корнем $T_1$, либо корнем $T_2$. Рассмотрим случай, в котором корень $T_1$ имеет больший $y$, чем корень $T_2$. Случай, в котором корень $T_2$ имеет больший $y$, чем корень $T_1$, симметричен этому.

Если $y$ корня $T_1$ больше $y$ корня $T_2$, то он и будет являться корнем. Тогда левое поддерево $T$ совпадёт с левым поддеревом $T_1$. Справа же нужно подвесить объединение правого поддерева $T_1$ и дерева $T_2$.

Рассуждая аналогично операции $\mathrm{split}$ приходим к выводу, что трудоёмкость операции $\mathrm{merge}$ равна $\mathcal{O}(\log n)$.

Операция add

Операция $\mathrm{add}(T, k)$ добавляет в дерево $T$ элемент $k$, где $k.x$ — ключ, а $k.y$— приоритет.

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

1. Разобьём наше дерево по ключу, который мы хотим добавить, то есть $\mathrm{split}(T, k.x) \to \{T_1, T_2\}$.
2. Сливаем первое дерево с новым элементом, то есть $\mathrm{merge}(T_1, k) \to T_1$.
3. Сливаем получившиеся дерево со вторым, то есть $\mathrm{merge}(T_1, T_2) \to T$.

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

Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по $k.x$), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше $k.y$. Мы нашли позицию, куда будем вставлять наш элемент. Теперь вызываем $\mathrm{split }(T, k.x) \to \{T_1, T_2\}$ от найденного элемента (от элемента вместе со всем его поддеревом), и возвращаемые ею $T_1$ и $T_2$ записываем в качестве левого и правого сына добавляемого элемента.

Операция remove

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

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

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

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

Спускаемся по дереву (как в обычном бинарном дереве поиска по $x$), ища удаляемый элемент. Найдя элемент, мы просто вызываем $merge$ его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента, то есть $\mathrm{merge }(T.l, T.t) \to T$.

Литература

Todo