Изменения

'''Декартово дерево''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: <tex>treap (tree+heap) </tex> и дерамида (дерево+пирамида).

Более строго, это структура данных, которая хранит пары <tex> (X,Y) </tex> в виде бинарного дерева таким образом, что она является бинарным деревом поиска по <tex>x </tex> и бинарной пирамидой по <tex>y</tex>. Предполагая, что все <tex>X </tex> и все <tex>Y </tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(X0X_0,Y0Y_0)</tex>, то <tex>у </tex> всех элементов в левом поддереве <tex>X < X0X_0</tex>, у всех элементов в правом поддереве <tex> X > X0X_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> Y < Y0Y_0</tex>.

== Операция add ==Операция <tex>Add(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>. Наивная реализация:1) Разбиваем наше дерево по ключу, который мы хотим добавить, то есть <tex>split(T, k, T1, T2)</tex>.2) Сливаем первое дерево с новым элементом, то есть <tex>merge(T1, T1, k)</tex>.3) Сливаем получившиеся дерево со вторым. то есть <tex>merge(T, T1, T2)</tex>.