Декартово дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(+ split)
Строка 8: Строка 8:
 
== Операция split ==
 
== Операция split ==
  
Тут будет split
+
== Операция split ==
 +
 
 +
Операция <tex>\mathrm{split}</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{split}(T, x) \to \{T_1, T_2\}</tex>.
 +
 
 +
Как же устроена сея замечательная операция?
 +
 
 +
Рассмотрим случай, в котором требуется распилить дерево по ключу, большему ключа корня.
 +
Посмотрим, как будут устроены результирующие деревья <tex>T_1</tex> и <tex>T_2</tex>:
 +
* <tex>T_1</tex>: левое поддерево <tex>T_1</tex> совпадёт с левым поддеревом <tex>T</tex>. Для нахождения правого поддерева <tex>T_1</tex>, нужно распилить правое поддерево <tex>T</tex> на <tex>T^R_1</tex> и <tex>T^R_2</tex> по ключу <tex>x</tex> и взять <tex>T^R_1</tex>.
 +
* <tex>T_2</tex> совпадёт с <tex>T^R_2</tex>.
 +
 
 +
Случай, в котором требуется распилить дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.
 +
 
 +
Оценим время работы операции <tex>\mathrm{split}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{split}</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>.
 +
 
 +
{{TODO|t=Запилить рисунок}}
  
 
== Операция merge ==
 
== Операция merge ==

Версия 05:42, 8 апреля 2011

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

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

Более строго, это структура данных, которая хранит пары [math] (X,Y) [/math] в виде бинарного дерева таким образом, что она является бинарным деревом поиска по [math]x[/math] и бинарной пирамидой по [math]y[/math]. Предполагая, что все [math]X[/math] и все [math]Y[/math] являются различными, получаем, что если некоторый элемент дерева содержит [math](X_0,Y_0)[/math], то [math]у[/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] — высота дерева. Так как высота декартова дерева — [math]\mathcal{O}(\log n)[/math], то и операция [math]\mathrm{split}[/math] работает за [math]\mathcal{O}(\log n)[/math].


TODO: Запилить рисунок

Операция merge

А тут будет merge

Операция add

Операция [math]add(T, k)[/math] добавляет в дерево [math]T[/math] элемент [math]k[/math], где [math]k.x[/math] — ключ, а [math]k.y[/math]— приоритет.

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

  1. Разбиваем наше дерево по ключу, который мы хотим добавить, то есть [math]split(T, T_1, T_2, k.x)[/math].
  2. Сливаем первое дерево с новым элементом, то есть [math]merge(T_1, T_1, k)[/math].
  3. Сливаем получившиеся дерево со вторым, то есть [math]merge(T, T_1, T_2)[/math].


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

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


Операция remove

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

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

  1. Разбиваем наше дерево по ключу, который мы хотим удалить, то есть [math]split(T, T_1, T_2, x)[/math].
  2. Теперь отделяем от второго дерева элемент [math]x[/math], опять таки разбивая по ключу [math]x[/math], то есть [math]split(T_2, T_2, T_3, x)[/math].
  3. Сливаем первое дерево со третьим, то есть [math]merge(T, T_1, T_3)[/math].

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

Спускаемся по дереву (как в обычном бинарном дереве поиска по [math]x[/math]), ища удаляемый элемент. Найдя элемент, мы просто вызываем [math]merge[/math] его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента, то есть [math]merge(T,T.l,T.r)[/math].