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

Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: [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].

Наивная реализация:

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

2) Сливаем первое дерево с новым элементом, то есть [math]merge(T_1, T_1, k)[/math].

3) Сливаем получившиеся дерево со вторым, то есть [math]merge(T, T_1, T_2)[/math].

Операция remove

Операция [math]remove(T, k)[/math] удаляет из дерева [math]T[/math] элемент [math]k[/math].

Наивная реализация:

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

2) Теперь отделяем от (первого, второго) дерева элемент [math]k[/math], опять таки разбивая по ключу [math]k[/math], то есть [math]Split(T_1, T_1, T_3, k+1)[/math].

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