90
правок
Изменения
м
Нет описания правки
'''Декартово дерево''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: <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>y</tex> у всех элементов в левом поддереве <tex>X < X_0</tex>, у всех элементов в правом поддереве <tex> X > X_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> Y < Y_0</tex>.
Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.
