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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
  
 
== Операция add==
 
== Операция add==
Операция <tex>add(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>.
+
Операция <tex>add(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> - ключ, а <tex>k.y</tex>- приоритет.
  
===Наивная реализация:===
+
===Реализация №1:===
<p>1) Разбиваем наше дерево по ключу, который мы хотим добавить, то есть <tex>split(T, T_1, T_2, k)</tex>.</p>
+
<p>1) Разбиваем наше дерево по ключу, который мы хотим добавить, то есть <tex>split(T, T_1, T_2, k.x)</tex>.</p>
 
<p>2) Сливаем первое дерево с новым элементом, то есть <tex>merge(T_1, T_1, k)</tex>.</p>
 
<p>2) Сливаем первое дерево с новым элементом, то есть <tex>merge(T_1, T_1, k)</tex>.</p>
 
<p>3) Сливаем получившиеся дерево со вторым, то есть <tex>merge(T, T_1, T_2)</tex>. </p>
 
<p>3) Сливаем получившиеся дерево со вторым, то есть <tex>merge(T, T_1, T_2)</tex>. </p>
 +
 +
 +
=== Реализация №2:  ===
 +
Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше <tex>k.y</tex>. Мы нашли позицию, куда будем вставлять наш элемент. Теперь вызываем <tex>split(T, T_1, T_2, k.x)</tex> от найденного элемента (от элемента вместе со всем его поддеревом), и возвращаемые ею <tex>T_1</tex> и <tex>T_2</tex> записываем в качестве левого и правого сына добавляемого элемента.
 +
  
 
== Операция remove ==
 
== Операция remove ==
Операция <tex>remove(T, k)</tex> удаляет из дерева <tex>T</tex> элемент <tex>k</tex>.
+
Операция <tex>remove(T, x)</tex> удаляет из дерева <tex>T</tex> элемент <tex>x</tex>.
  
===Наивная реализация:===
+
===Реализация №1:===
<p>1) Разбиваем наше дерево по ключу, который мы хотим удалить, то есть <tex>split(T, T_1, T_2, k)</tex>.</p>
+
<p>1) Разбиваем наше дерево по ключу, который мы хотим удалить, то есть <tex>split(T, T_1, T_2, x)</tex>.</p>
<p>2) Теперь отделяем от (первого, второго) дерева элемент <tex>k</tex>, опять таки разбивая по ключу <tex>k</tex>, то есть <tex>Split(T_2, T_2, T_3, k+1)</tex>.</p>
+
<p>2) Теперь отделяем от (первого, второго) дерева элемент <tex>k</tex>, опять таки разбивая по ключу <tex>k</tex>, то есть <tex>split(T_2, T_2, T_3, x+1)</tex>.</p>
 
<p>3) Сливаем первое дерево со третьим, то есть <tex>merge(T, T_1, T_3)</tex>. </p>
 
<p>3) Сливаем первое дерево со третьим, то есть <tex>merge(T, T_1, T_3)</tex>. </p>
 +
 +
===Реализация №2:===
 +
Спускаемся по дереву (как в обычном бинарном дереве поиска по <tex>k.x</tex>), ища удаляемый элемент. Найдя элемент, мы просто вызываем <tex>merge</tex> от его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого элемента.

Версия 05:17, 6 апреля 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

Операция 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]k[/math], опять таки разбивая по ключу [math]k[/math], то есть [math]split(T_2, T_2, T_3, x+1)[/math].

3) Сливаем первое дерево со третьим, то есть [math]merge(T, T_1, T_3)[/math].

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

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