Декартово дерево

Декартово дерево — это структура данных, реализующая двоичное дерево поиска. Стандартный сценарий использования декартового дерева - это реализация следующего функционала:

• Вставка элемента в множество
• Удаление элемента из множества
• Нахождение элемента в множестве
• Нахождение первого элемента, меньшего $x$
• и многое-многое другое

Структура дерева

В каждой вершине мы будем хранить два числа — ключ $x$, по которому наша структура будет бинарным деревом поиска, а также приоритет $y$, по которому наше дерево будет кучей. Приоритеты нужно выбирать случайно, на этом будет опираться оценка высоты дерева. Пока что будем считать, что высота дерева $O(\log n)$, но докажем это ниже.

Основные операции

Все операции с декартовым деревом реализуются с помощью двух основных — $split$ и $merge$:

• $split(t,\ x)$ делит декартово дерево $t$ на два — в одном все ключи меньше $x$, все остальные вершины в другом.
• $merge(l,\ r)$ сливает два декартовых дерева в одно при условии, что все ключи в $l$ меньше, чем в $r$.

Реализовать $insert\ x$ можно через

l, r = split(t, x)

l = merge (x, new node(x))

t = merge (l, r)

Аналогичным образом можно выразить и остальные операции.