166
правок
Изменения
Нет описания правки
''Эта статья про Курево''
== Описание =='''Декартово дерево''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: <tex>treap (tree+heap)</tex> и дерамида (дерево+пирамида), так же существует название курево (куча + дерево).
Более строго, это структура данных, которая хранит пары <tex> (X,Y) </tex> в виде бинарного дерева таким образом, что она является бинарным деревом поиска по <tex>x</tex> и бинарной пирамидой по <tex>y</tex>. Предполагая, что все <tex>X</tex> и все <tex>Y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(X_0,Y_0)</tex>, то у всех элементов в левом поддереве <tex>X < X_0</tex>, у всех элементов в правом поддереве <tex> X > X_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> Y < Y_0</tex>.
Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.
== Операция split Операции в декартовом дереве ===== Split ===
[[file:split.png|thumb|400px|Операция split]]
Операция <tex>\mathrm{splitSplit}</tex> (''разрезать'') позволяет сделать следующее: разрезать декартово дерево <tex>T</tex> по ключу
<tex>x</tex> и получить два других декартовых дерева: <tex>T_1</tex> и <tex>T_2</tex>, причем в <tex>T_1</tex>
находятся все ключи дерева <tex>T</tex>, не большие <tex>x</tex>, а в <tex>T_2</tex> {{---}} большие <tex>x</tex>.
<tex>\mathrm{splitSplit}(T, x) \to \{T_1, T_2\}</tex>.
Эта операция устроена следующим образом.
Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.
Оценим время работы операции <tex>\mathrm{splitSplit}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{splitSplit}</tex> для
дерева хотя бы на один меньшей высоты и делается ещё <tex>\mathcal{O}(1)</tex> операция. Тогда итоговая трудоёмкость этой операции
равна <tex>\mathcal{O}(h)</tex>, где <tex>h</tex> {{---}} высота дерева. Так как высота декартова дерева {{---}} <tex>\mathcal{O}(\log n)</tex>, то и операция <tex>\mathrm{split}</tex> работает за <tex>\mathcal{O}(\log n)</tex>.
== Операция merge = Merge ===
[[file:merge.png|thumb|400px|Операция merge]]
Рассмотрим вторую операцию с декартовыми деревьями {{---}} <tex>\mathrm{mergeMerge}</tex>(''слить'').
С помощью этой операции можно слить два декартовых дерева в одно.
ключи во втором(''правом''). В результате получается дерево, в котором есть все ключи из первого и второго деревьев.
<tex>\mathrm{mergeMerge}(T_1, T_2) \to T</tex>
Рассмотрим принцип работы этой операции. Пусть нужно слить деревья <tex>T_1</tex> и <tex>T_2</tex>.
<tex>T_1</tex> и дерева <tex>T_2</tex>.
Рассуждая аналогично операции <tex>\mathrm{splitSplit}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{mergeMerge}</tex> равна <tex>\mathcal{O}(\log nh)</tex>, где <tex>h</tex> {{---}} высота дерева.
== Операция add = Insert ===Операция <tex>\mathrm{addInsert}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет.
====Реализация №1:====# Разобьём наше дерево по ключу, который мы хотим добавить, то есть <tex>\mathrm{splitSplit}(T, k.x) \to \{T_1, T_2\}</tex>.# Сливаем первое дерево с новым элементом, то есть <tex>\mathrm{mergeMerge}(T_1, k) \to T_1</tex>.# Сливаем получившиеся дерево со вторым, то есть <tex>\mathrm{mergeMerge}(T_1, T_2) \to T</tex>.
==== Реализация №2 ====
# Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>.
# Теперь вызываем <tex>\mathrm{Split }(T, k.x) \to \{T_1, T_2\}</tex> от найденного элемента (от элемента вместе со всем его поддеревом)
# Полученные <tex>T_1</tex> и <tex>T_2</tex> записываем в качестве левого и правого сына добавляемого элемента.
# Полученное дерево подвешиваем на место элемента, найденного в первом пункте.
=== Реализация №2: Remove ===Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>. Мы нашли позицию, куда будем вставлять наш элемент. Теперь вызываем Операция <tex>\mathrm{split Remove}(T, k.x) \to \{T_1, T_2\}</tex> от найденного элемента (от элемента вместе со всем его поддеревом), и возвращаемые ею удаляет из дерева <tex>T_1T</tex> и элемент с ключом <tex>T_2x</tex> записываем в качестве левого и правого сына добавляемого элемента.
==== Реализация №1 ====
====Реализация №1:№2====# Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), ища удаляемый элемент. # Найдя элемент, вызываем <tex>Merge</tex> его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента, то есть <tex>\mathrm{Merge }(T.l, T.t) \to T</tex>.
===Реализация №2:===Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>x</tex>), ища удаляемый элемент. Найдя элемент, мы просто вызываем <tex>merge</tex> его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента, то есть <tex>\mathrm{merge }(T.l, T.t) \to T</tex>. == Литература Ссылки ==
Todo
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
