166
правок
Изменения
Нет описания правки
''Эта статья про Курево''
'''Декартово дерево''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), так же существует название курево (куча + дерево).
Более строго, это структура данных, которая хранит пары <tex> (Xx,Yy) </tex> в виде бинарного дерева таким образом, что она является бинарным деревом поиска по <tex>x</tex> и бинарной пирамидой по <tex>y</tex>. Предполагая, что все <tex>Xx</tex> и все <tex>Yy</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(X_0x_0,Y_0y_0)</tex>, то у всех элементов в левом поддереве <tex>X x < X_0x_0</tex>, у всех элементов в правом поддереве <tex> X x > X_0x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> Y y < Y_0y_0</tex>.
Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.
