Декартово дерево
Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), также существует название курево (куча + дерево).
Более строго, это бинарное дерево, в узлах которого хранится пары двоичным деревом поиска по и пирамидой по . Предполагая, что все и все являются различными, получаем, что если некоторый элемент дерева содержит , то у всех элементов в левом поддереве , у всех элементов в правом поддереве , а также и в левом, и в правом поддереве имеем: .
, где — это ключ, а — это приоритет. Также оно являетсяДерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.
Содержание
Операции в декартовом дереве
split
Операция
(разрезать) позволяет сделать следующее: разрезать декартово дерево по ключу и получить два других декартовых дерева: и , причем в находятся все ключи дерева , не большие , а в — большие ..
Эта операция устроена следующим образом.
Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня. Посмотрим, как будут устроены результирующие деревья
и :- : левое поддерево совпадёт с левым поддеревом . Для нахождения правого поддерева , нужно разрезать правое поддерево на и по ключу и взять .
- совпадёт с .
Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.
Псевдокод:
<Treap, Treap> split(t : Treap, k : int): if k > t.x <t1, t2> = split(t.right, k) t.right = t1 return <t1, t2> else <t1, t2> = split(t.left, k) t.left = t2 return <t1, t2>
Оценим время работы операции . Во время выполнения вызывается одна операция для
дерева хотя бы на один меньшей высоты и делается ещё операций. Тогда итоговая трудоёмкость этой операции
равна , где — высота дерева.
merge
Рассмотрим вторую операцию с декартовыми деревьями —
(слить).С помощью этой операции можно слить два декартовых дерева в одно. Причем, все ключи в первом(левом) дереве должны быть меньше, чем ключи во втором(правом). В результате получается дерево, в котором есть все ключи из первого и второго деревьев.
Рассмотрим принцип работы этой операции. Пусть нужно слить деревья
и . Тогда, очевидно, у результирующего дерева есть корень. Корнем станет вершина из или с наибольшим приоритетом . Но вершина с самым большим из всех вершин деревьев и может быть только либо корнем , либо корнем . Рассмотрим случай, в котором корень имеет больший , чем корень . Случай, в котором корень имеет больший , чем корень , симметричен этому.Если
корня больше корня , то он и будет являться корнем. Тогда левое поддерево совпадёт с левым поддеревом . Справа же нужно подвесить объединение правого поддерева и дерева .Псевдокод:
func merge(t1 : Treap, t2 : Treap): if t1 == null or t2 == null if t2 == null return left else return right else if t1.y > t2.y merge(t1.right, t1.right, t2) return t1 else merge(t2.left, t1, t2.left) return t2
Рассуждая аналогично операции
приходим к выводу, что трудоёмкость операции равна , где — высота дерева.insert
Операция
добавляет в дерево элемент , где — ключ, а — приоритет.Представим что элемент
, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево , очевидно, нам нужно их слить. Но может содержать ключи как меньше, так и больше ключа , поэтому сначала нужно разрезать по ключу .- Реализация №1
- Разобьём наше дерево по ключу, который мы хотим добавить, то есть .
- Сливаем первое дерево с новым элементом, то есть .
- Сливаем получившиеся дерево со вторым, то есть .
- Реализация №2
- Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по ), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше .
- Теперь вызываем от найденного элемента (от элемента вместе со всем его поддеревом)
- Полученные и записываем в качестве левого и правого сына добавляемого элемента.
- Полученное дерево ставим на место элемента, найденного в первом пункте.
В первой реализации два раза используется
, а во второй реализации слияние вообще не используется.remove
Операция
удаляет из дерева элемент с ключом .- Реализация №1
- Разобьём наше дерево по ключу, который мы хотим удалить, то есть .
- Теперь отделяем от первого дерева элемент , опять таки разбивая по ключу , то есть .
- Сливаем первое дерево со вторым, то есть .
- Реализация №2
- Спускаемся по дереву (как в обычном бинарном дереве поиска по ), ища удаляемый элемент.
- Найдя элемент, вызываем его левого и правого сыновей
- Результат процедуры ставим на место удаляемого элемента.
В первой реализации два раза используется
, а во второй реализации разрезание вообще не используется.Построение декартова дерева
Пусть нам известно из каких пар
требуется построить декартово дерево, причем также известно, что .Рекурсивный алгоритм
Рассмотрим приоритеты пирамиды в корне должен быть элемент с максимальным приоритетом). Проделав то же самое с и , получим соответственно левого и правого сына .
и выберем максимум среди них, пусть это будет , и сделаем корнем дерева (по свойствуТакой алгоритм работает за
.Алгоритм за O(n)
Будем строить дерево слева направо, то есть начиная с двоичное дерево поиска. При добавлении , пытаемся сделать его правым сыном , это следует сделать если , иначе делаем шаг к предку последнего элемента и смотрим его значение . Поднимаемся до тех пор, пока приоритет в рассматриваемом элементе меньше приоритета в добавляемом, после чего делаем его правым сыном, а предыдущего правого сына делаем левым сыном .
по , при этом помнить последний добавленный элемент . Он будет самым правым, так как у него будет максимальный ключ, а по ключам декартово дерево представляет собойЗаметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в чьем-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за
.Случайные приоритеты
Мы уже выяснили, что сложность операций с декартовым деревом линейно зависит от его высоты. В действительности высота декартова дерева может быть линейной относительно его размеров. Например, высота декартова дерева, построенного по набору ключей
, будет равна . Во избежание таких случаев, полезным оказывается выбирать приоритеты в ключах случайно.Высота в декартовом дереве с случайными приоритетами
Теорема: | ||||||
В декартовом дереве из случайными величинами c равномерным распределением, средняя глубина вершины . узлов, приоритеты которого являются | ||||||
Доказательство: | ||||||
Будем считать, что все выбранные приоритеты попарно различны.Для начала введем несколько обозначений:
В силу обозначений глубину вершины можно записать как количество предков:
Теперь можно выразить математическое ожидание глубины конкретной вершины:
Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того, что вершина является предком вершины , то есть .Введем новое обозначение:
Так как распределение приоритетов равномерное, каждая вершина среди может иметь минимальный приоритет, мы немедленно приходим к следующему равенству:Подставив последнее в нашу формулу с математическим ожиданием получим:
| ||||||
Таким образом, среднее время работы операций
и будет .