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

Дека́ртово де́рево — это двоичное дерево, в узлах которого хранятся:

• ссылки на правое и левое поддерево;
• ссылка на родительский узел (необязательно);
• ключи $x$ и $y$, которые являются двоичным деревом поиска по ключу $x$ и двоичной кучей по ключу $y$; а именно, для любого узла дерева $n$:
  • ключи $x$ узлов правого (левого) поддерева больше (меньше либо равны) ключа $x$ узла $n$;
  • ключи $y$ узлов правого и левого детей больше либо равны ключу $y$ узла $n$.

Ссылка на родительский узел не обязательна, она желательна только для линейного алгоритма построения дерева.

Декартово дерево не является самобалансирующимся в обычном смысле, и применяют его по таким причинам:

• Очень просто программируется, намного проще настоящих самобалансирующихся деревьев наподобие красно-чёрного. Поэтому часто применяется на олимпиадах.
• Хорошо ведёт себя «в среднем», если ключи y раздать случайно.
• Типичная для сортирующего дерева операция «расчленить по ключу x на „меньше x₀“ и „не меньше x₀“» работает за O(h) как ни в чём не бывало.

Недостатки декартового дерева:

• Большие накладные расходы на хранение: вместе с каждым элементом хранятся два-три указателя и случайный ключ y.
• Скорость доступа O(n) в худшем случае. Поэтому декартово дерево недопустимо, например, в ядрах ОС.

Терминология

В англоязычной литературе декартово дерево, построенное для массива из заданных ключей и присвоенных им при построении случайных весов называется словом-бумажником treap, так как совмещает свойства cортирующего дерева-кучи (heap) и случайного двоичного дерева (tree) с логарифмическим ожиданием высоты. В русском языке было предложено аналогичное слову treap по построению слово дуча^[1] (дерево+куча).

Простейший алгоритм построения декартового дерева. Свойство однозначности структуры

Простейший для понимания алгоритм построения декартового дерева по множеству данных пар (x, y) выглядит следующим образом. Упорядочим все пары по ключу x и пронумеруем получившуюся последовательность ключей y:

y(1), y(2), y(3), …, y(n).

Найдём минимальный ключ y. Пусть это будет y(k). Он будет корнем дерева. Ключ y(k) делит последовательность ключей y на две:

y(1), …, y(k−1); y(k+1), …, y(n).

В каждой из них найдём минимальный y — это будут дети узла y(k) — левый и правый. С получившимися 4 кусочками (возможно меньше) поступим аналогичным образом. Предложенный алгоритм построения декартового дерева основан на рекурсии: находим в последовательности минимальный y и назначаем его корнем. найденный y разбивает последовательность на две части, для каждой из частей запускаем алгоритм построения декартового дерева.

Схематически это можно записать так:

T( y(1), ..., y(n) ) =  root: y(k)   
                           left_tree: T( y(1), ..., y(k−1) )   
                           right_tree: T( y(k+1), ..., y(n)) )
                        where  y(k) = min( y(1), ..., y(n) )

Из данного алгоритма следует, что множество пар (x, y) однозначно определяет структуру декартового дерева. Заметим для сравнения, что множество ключей, которые хранятся в двоичном дереве поиска не определяют однозначно структуру дерева. То же самое касается двоичной кучи — какова будет структура двоичной кучи (как ключи распределятся по узлам) зависит не только от самого множества ключей, но и от последовательности их добавления. В декартовом дереве такой неоднозначности нет.

Линейный алгоритм построения дерева

Другой алгоритм построения дерева также основан на рекурсии. Только теперь мы последовательно будем добавлять элементы y и перестраивать дерево. Дерево T(y(1), …, y(k+1)) будет строиться из дерева T(y(1), …, y(k)) и следующего элемента y(k+1).

T( y(1), ..., y(k+1) ) = F ( T( y(1), ..., y(k) ), y(k+1) )

На каждом шаге будем помнить ссылку на последний добавленный узел. Он будет самым правым. Действительно, мы упорядочили ключи y по прикреплённому к ним ключу x. Так как декартово дерево — это дерево поиска, то после проекции на горизонтальную прямую ключи x должны возрастать слева направо. Самый правый узел всегда имеет максимально возможное значение ключа x.

Функция F, которая отображает декартово дерево T(y(1), …, y(k)) предыдущего шага и очередное y(k+1) в новое дерево T(y(1), …, y(k+1)), выглядит следующим образом. Вертикаль для узла y(k+1) определена. Нам необходимо определиться с его горизонталью. Для начала мы проверяем, можно ли новый узел y(k+1) сделать правым ребёнком узла y(k) — это следует сделать, если y(k+1) > y(k). Иначе мы делаем шаг по склону от узла y(k) вверх и смотрим на значение y, которое там хранится. Поднимаемся вверх по склону, пока не найдём узел, в котором значение y меньше, чем y(k+1), после чего делаем y(k+1) его правым ребёнком, а его предыдущего правого ребёнка делаем левым ребёнком узла y(k+1).

Это алгоритм амортизационно (в сумме за все шаги) работает линейное (по числу добавляемых узлов) время. Действительно, как только мы «перешагнули» через какой-либо узел, поднимаясь вверх по склону, то мы его уже никогда не встретим при добавлении следующих узлов. Таким образом, суммарное число шагов вверх по склону не может быть больше общего числа узлов.

Примечания

1. ↑ Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — ISBN 0-201-89685-0

Ссылки

• Декартово дерево на neerc.ifmo.ru/wiki
• Декартово дерево по неявному ключу на neerc.ifmo.ru/wiki
• Декартово дерево и его реализация на C# на habrahabr.ru часть 1, часть 2, часть 3
• Реализация декартова дерева на C++ с сайта e-maxx.ru

Литература

• Seidel, Raimund; Aragon, Cecilia R. «Randomized Search Trees», 1996 г.

Для улучшения этой статьи желательно?: Викифицировать статью. Добавить иллюстрации. Исправить статью согласно стилистическим правилам Википедии.