Декартово дерево (Treap): Сбалансированный симбиоз дерева и кучи

Название Treap является слиянием слов Tree (дерево поиска) и Heap (куча). Каждый узел в этой структуре хранит не одно, а сразу два значения: Ключ (X) и Приоритет (Y).

Структура должна одновременно удовлетворять двум строгим математическим правилам:

• По ключу X это правильное Бинарное дерево поиска: все ключи в левом поддереве меньше ключа узла, а в правом — больше.
• По приоритету Y это правильная Бинарная куча (Max-Heap): приоритет любого родителя строго больше приоритета любого из его потомков.

Главный секрет Декартова дерева: ключи мы получаем от пользователя, а приоритеты Y мы генерируем абсолютно случайным образом! Математически доказано, что если мы строим дерево поиска, где элементы вставляются в порядке убывания случайно сгенерированных приоритетов, математическое ожидание высоты такого дерева составит строго O(log N). Вероятность того, что Treap выродится в линию, бесконечно мала.

Вся работа с Treap строится на двух базовых, очень простых в написании операциях:

1. Split (Разрезание): берет дерево и ключ K, и за O(log N) разрезает его на два дерева: в одном все ключи меньше K, в другом — больше или равны.
2. Merge (Слияние): берет два дерева (при условии, что все ключи первого меньше ключей второго) и объединяет их в одно за O(log N), просто сравнивая приоритеты корней, чтобы сохранить свойство кучи.

Добавление (Insert) и удаление (Delete) элементов выражаются буквально в пару строк через эти две операции. Более того, существует модификация "Декартово дерево по неявному ключу", в которой ключом X выступает не само значение, а индекс элемента в массиве. Такая структура позволяет за логарифмическое время вырезать кусок массива из середины и вставить его в начало (что невозможно сделать быстро ни в обычном массиве, ни в связанном списке), что делает Treap основой продвинутых текстовых редакторов (структура данных Rope).