Изменения
Нет описания правки
'''Декартово дерево ''' {{---}} одно из сбалансированных деревьев это структура данных, объединяющая в себе бинарное дерево поискаи бинарную кучу (отсюда и второе её название: treap (tree+heap) и дерамида (дерево+пирамида).
Более строго, это структура данных, которая хранит пары (X,Y) в виде бинарного дерева таким образом, что она является бинарным деревом поиска по x и бинарной пирамидой по y. Предполагая, что все X и все Y являются различными, получаем, что если некоторый элемент дерева содержит (X0,Y0), то у всех элементов в левом поддереве X < X0, у всех элементов в правом поддереве X > X0, а также и в левом, и в правом поддереве имеем: Y < Y0.
Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.
== Операция split ==
