172
правки
Изменения
Нет описания правки
'''Декартово дерево''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), также существует название курево (куча + дерево).
Более строго, это бинарное дерево, в узлах которого хранится пары <tex> (x,y) </tex>, где <tex>x</tex> {{- --}} это ключ, а <tex>y</tex> {{--- }} это приоритет. Также оно является [[Дерево поиска, наивная реализация|двоичным деревом поиска]] по <tex>x</tex> и [[Двоичная куча|пирамидой]] по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.
Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.
\end{array}\right.
</tex>
* <tex>d(v)</tex> {{- --}} глубина вершины <tex>v</tex>;
В силу обозначений глубину вершины можно записать как количество предков:
