Просмотр кода страницы Декартово дерево

{{Структура данных
| оригинал названия = {{lang-en|Treap}}
| изображение = Treap.svg
| тип = [[Двоичное дерево поиска]]
| изобретена = 1989
| создатель = Cecilia Aragon, Raimund Seidel
| построение худшее = <math>O(n)</math>
| поиск в среднем = <math>O(\log n)</math>
| вставка в среднем = <math>O(\log n)</math>
| удаление в среднем = <math>O(\log n)</math>
}}
'''Дека́ртово де́рево''', '''дуча''', '''дерамида''' ({{lang-en|treap}} от {{lang-en|tree}} «дерево» + {{lang-en|heap}} «куча») — это структура данных, сочетающая в себе [[двоичное дерево]] и [[двоичная куча|двоичную кучу]]. Хранит пары ''(x, y)'', где для '''''ключа''''' ''x'' служит [[Двоичное дерево поиска|бинарным деревом поиска]], а для '''''приоритета''''' ''y'' — двоичной кучей.{{sfn|Ландовский|2016}}

Декартово дерево впервые было описано Сесилией Арагон и Раймундом Зиделем в 1989.<ref name="paper89">{{Citation | contribution=Randomized Search Trees | first1=Cecilia R. | last1=Aragon | first2=Raimund | last2=Seidel | contribution-url=http://faculty.washington.edu/aragon/pubs/rst89.pdf | title=Proc. 30th Symp. Foundations of Computer Science (FOCS 1989) | pages=540–545 | year=1989 | doi=10.1109/SFCS.1989.63531 | isbn=0-8186-1982-1 | publisher=IEEE Computer Society Press | location=Washington, D.C. | title-link=Symposium on Foundations of Computer Science | access-date=2023-07-04 | archive-date=2012-10-07 | archive-url=https://web.archive.org/web/20121007232834/http://faculty.washington.edu/aragon/pubs/rst89.pdf | url-status=live }}</ref>

== Свойства ==
Декартово дерево не является [[самобалансирующееся дерево|самобалансирующимся]] в обычном смысле, и применяют его по следующим причинам:
* Проще реализуется по сравнению, например, с настоящими самобалансирующимися деревьями вроде [[красно-чёрное дерево|красно-чёрного]].
* Хорошо ведёт себя «в среднем», если ключи ''y'' раздать случайно.
* Типичная для сортирующего дерева операция «разделить по ключу ''x'' на „меньше ''x''<sub>0</sub>“ и „не меньше ''x''<sub>0</sub>“» работает за ''O''(''h''), где ''h'' — высота дерева. На красно-чёрных деревьях придётся восстанавливать балансировку и окраску узлов.

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

== Терминология ==
В англоязычной литературе декартово дерево, построенное для массива из заданных ключей и присвоенных им при построении случайных весов называется [[слово-бумажник|словом-бумажником]] ''treap'', так как совмещает свойства [[сортирующее дерево|сортирующего дерева-кучи]] (''heap'') и случайного [[двоичное дерево|двоичного дерева]] (''tree'') с логарифмическим [[математическое ожидание|ожиданием]] высоты. В русском языке были предложены аналогичные слову ''treap'' слова ''дуча''<ref>{{книга
|подзаголовок
|заглавие=Искусство программирования, том 3. Сортировка и поиск
|оригинал=The Art of Computer Programming, vol.3. Sorting and Searching
|ссылка=
|автор=[[Дональд Кнут]]
|издание = 2-е изд
|год=2007
|место=М.
|издательство= [[Вильямс (издательство)|«Вильямс»]]
|isbn= 0-201-89685-0
}}</ref> (''дерево''+''куча''), ''дерамида'' (''дерево''+''пирамида'').

{{нп4|Вюйемен, Жан|Жан Вюйемен|en|Jean Vuillemin}} использовал для подобной структуры название {{lang-en|Cartesian tree}} — декартово дерево.<ref name="paper89" />

== Алгоритмы ==
{{Переработать раздел|дата=2023-07-05}}
=== Простейший алгоритм ===
Простейший для понимания алгоритм построения декартового дерева по множеству данных пар (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).

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

=== Добавление и удаление элементов ===
{{дополнить раздел|дата=2023-07-05}}
Добавление и удаление узлов дерева реализуется с помощью операций Merge и Split.{{sfn|Ландовский|2016}}

=== Применение ===
{{в планах|дата=2023-07-05}}

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE Декартово дерево на neerc.ifmo.ru/wiki]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE_%D0%BD%D0%B5%D1%8F%D0%B2%D0%BD%D0%BE%D0%BC%D1%83_%D0%BA%D0%BB%D1%8E%D1%87%D1%83 Декартово дерево по неявному ключу на neerc.ifmo.ru/wiki]
* [http://e-maxx.ru/algo/treap Реализация декартова дерева на C++ с сайта e-maxx.ru]

== Литература ==
* {{cite conference
 | author = Raimund Seidel, Cecilia R. Aragon
 | year = 1996
 | title = Randomized Search Trees
 | book-title = ALGORITHMICA
 | pages = 540—545
}}
* {{книга|автор=Ландовский, Владимир|заглавие=Структуры данных|издательство=Новосибирский государственный технический университет|год=2016|страниц=68||страницы=48—50|isbn=978-5-7782-3080-4|ref=Ландовский}}
* {{cite conference
| title = Fast set operations using treaps
| author1 = Guy E. Blelloch
| author2 = Margaret Reid-Miller
| year = 1998
| book-title = Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures
| publisher = Association for Computing Machinery
| location = Puerto Vallarta, Mexico
| pages = 16–26
| isbn = 0897919890
| doi = 10.1145/277651.277660
| url = https://doi.org/10.1145/277651.277660
}}

{{rq|refless|wikify|style}}
{{Деревья (структуры данных)}}

[[Категория:Алгоритмы]]
[[Категория:Деревья (структуры данных)]]
[[Категория:Деревья (графы)]]
[[Категория:Кучи (структуры данных)]]