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

Декартово дерево (также известное как декартово дерево поиска, декартово дерево с приоритетами, treap или дерево-куча) — это структура данных, сочетающая свойства двоичного дерева поиска (BST) и двоичной кучи (heap). Каждый узел декартова дерева хранит два ключа: основной ключ (x), по которому дерево является двоичным деревом поиска, и приоритет (y), по которому дерево является кучей (обычно максимум-кучей). Основное свойство: для любого узла все ключи в левом поддереве меньше его ключа, все ключи в правом поддереве больше, а приоритеты всех потомков меньше (или равны) приоритета самого узла.

История и происхождение

Декартово дерево было независимо описано несколькими исследователями в конце 1980-х — начале 1990-х годов. Название «treap» (tree + heap) ввёл Сесил Седжвик (Cecil Sedgewick) в 1989 году. В 1991 году Вуйцик (Wojciech Plandowski) и другие польские учёные предложили аналогичную структуру. В русскоязычной литературе термин «декартово дерево» закрепился благодаря работам Никлауса Вирта и последующим публикациям по алгоритмам.

Идея объединения свойств BST и кучи возникла из потребности в структуре данных, которая поддерживает быстрый поиск, вставку и удаление, но при этом остаётся сбалансированной с высокой вероятностью (без необходимости в явных операциях балансировки, как в красно-чёрных деревьях).

Основные свойства

Декартово дерево определяется двумя параметрами для каждого узла:

• Ключ (x) — значение, по которому строится BST. Обычно это уникальные значения, но могут быть и неуникальные (тогда требуется дополнительное правило, например, вставка одинаковых ключей в левое или правое поддерево).
• Приоритет (y) — случайное число, которое генерируется при создании узла. Приоритеты должны быть уникальными (или, по крайней мере, строго упорядочены), чтобы избежать неоднозначности.

Свойства:

1. Свойство BST: для любого узла с ключом x все ключи в левом поддереве меньше x, а в правом — больше x.
2. Свойство кучи: для любого узла с приоритетом y все приоритеты его потомков меньше y (если куча максимальная).

Из этих свойств следует, что корнем дерева всегда является узел с максимальным приоритетом (в случае максимум-кучи). Если приоритеты генерируются случайно, дерево получается сбалансированным с высокой вероятностью — средняя высота составляет O(log n), где n — количество узлов.

Устройство и операции

Узел декартова дерева

Каждый узел содержит:

• Ключ (x)
• Приоритет (y)
• Указатели на левого и правого потомка (left, right)

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

Вставка

Вставка нового узла с ключом x и случайным приоритетом y выполняется в два этапа:

1. Сначала узел вставляется как в обычное BST: по ключу находится подходящее место (лист).
2. Затем, если приоритет нового узла нарушает свойство кучи (больше приоритета родителя), выполняется поворот (вращение) — подъём узла вверх по дереву, аналогично операциям в куче.

Повороты бывают правые и левые:

• Правый поворот (right rotate): узел поднимается, заменяя своего родителя; левый потомок родителя становится правым потомком поднимаемого узла.
• Левый поворот (left rotate): симметрично.

Среднее время вставки — O(log n).

Удаление

Удаление узла по ключу также двухэтапное:

1. Найти узел с заданным ключом (как в BST).
2. Если узел найден, его необходимо «опустить» вниз до листа, выполняя повороты (меняя местами с потомком с большим приоритетом), пока он не станет листом. Затем узел удаляется.

Время удаления — O(log n) в среднем.

Поиск

Поиск узла по ключу выполняется как в обычном BST: от корня, сравнивая ключи, выбирая левое или правое поддерево. Время — O(log n) в среднем.

Слияние и разделение

Декартово дерево поддерживает две мощные операции:

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

Эти операции позволяют реализовать вставку и удаление без поворотов, а также поддерживать множество других структур (например, неявное декартово дерево).

Классификация и разновидности

По типу приоритетов

• Случайные приоритеты — классический вариант, где приоритеты генерируются случайно (например, с помощью датчика случайных чисел). Обеспечивает вероятностную сбалансированность.
• Детерминированные приоритеты — приоритеты вычисляются по ключу (например, хеш-функция). Может привести к вырождению, если функция неудачна.

Неявное декартово дерево (Implicit Treap)

В неявном декартовом дереве ключом является не значение, а позиция элемента в последовательности (индекс). Приоритеты — случайные. Это позволяет эффективно выполнять операции над массивами: вставка, удаление, разворот отрезка, сдвиг, копирование. Широко применяется в задачах на строки и последовательности.

Декартово дерево по сумме (Sum Treap)

В узлах дополнительно хранятся агрегированные значения (например, сумма поддерева). Позволяет быстро вычислять сумму на отрезке.

Применение

Декартово дерево нашло применение в различных областях информатики:

• Базы данных — для индексации данных (например, в PostgreSQL используется в некоторых реализациях индексов).
• Алгоритмы на графах — для построения минимальных остовных деревьев (алгоритм Крускала с использованием декартова дерева для слияния компонент).
• Генерация случайных перестановок — декартово дерево может быть использовано для равномерного распределения элементов.
• Обработка последовательностей — неявное декартово дерево применяется в редакторах текста, в задачах на строки (например, в алгоритме Бойера — Мура — Хорспула).
• Спортивное программирование — treap является одной из самых популярных структур данных на олимпиадах по информатике благодаря простоте реализации и универсальности.

Преимущества и недостатки

Преимущества

• Простота реализации (по сравнению с красно-чёрными или AVL-деревьями).
• Средняя высота O(log n) с высокой вероятностью.
• Поддержка операций слияния и разделения за логарифмическое время.
• Возможность реализации неявного дерева для работы с последовательностями.

Недостатки

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

Интересные факты

• Название «treap» является контаминацией слов «tree» и «heap».
• Декартово дерево названо в честь Рене Декарта из-за аналогии с декартовой системой координат: каждый узел можно представить точкой на плоскости с координатами (x, y), где x — ключ, y — приоритет. Тогда дерево строится как геометрическая структура — «декартово дерево» в смысле «дерево, построенное на декартовых координатах».
• В 1996 году Роберт Тарьян (Robert Tarjan) и другие исследователи показали, что декартово дерево может быть построено за линейное время для отсортированных ключей.
• В некоторых реализациях (например, в библиотеке STL в C++) treap используется как основа для контейнеров set и map (в частности, в GCC).

Источники

• Седжвик, Роберт. «Алгоритмы на C++». — 5-е изд. — М.: Вильямс, 2016. — 1120 с.
• Кормен, Т. и др. «Алгоритмы: построение и анализ». — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
• Вирт, Никлаус. «Алгоритмы и структуры данных». — М.: ДМК Пресс, 2010. — 272 с.
• Пландовски, В. и др. «Treap: A Randomised Binary Search Tree». — 1991.
• Тарьян, Р. «Efficient Algorithms for Sorting and Searching». — 1996.
• Документация GNU C++ Library (libstdc++), раздел «Tree Containers».