Курсовая работа: Обзор декартова дерева

Оглавление
Введение
Глава 1. Теоретический обзор декартова дерева
1.1 Описание операций в декартовом дереве
1.2 Сравнение с деревом отрезков и деревом Фенвика
1.3 Задачи, решаемые с помощью декартовых деревьев
Глава 2. Программная реализация
2.1 Описание программного кода
Глава 3. Оптимизация программного кода
3.1. Оптимизация
Заключение
Список литературы
Приложение 1. Код программы
Содержимое файла Traep.h
Содержимое файла Treap2.h
Содержимое файла CartesianTree.cpp
Приложение 2. Результат работы кода

Введение

Декартово дерево — легко реализующаяся структура данных, которая с минимальными усилиями позволит производить многие скоростные операции над массивами данных.
В узлах декартова дерева хранятся:
· ссылки на правое и левое поддерево;
· ссылка на родительский узел (необязательно);
· ключи x и y, которые являются двоичным деревом поиска по ключу x и двоичной кучей по ключу y; а именно, для любого узла дерева n:
o ключи x узлов правого (левого) поддерева больше (меньше) либо равны ключу x узла n;
o ключи y узлов правого и левого детей больше либо равны ключу y узла n.
Ссылка на родительский узел не обязательна, она желательна только для линейного алгоритма построения дерева.
Декартово дерево не является самобалансирующимся, и применяют его по следующим причинам:
Проще реализуется по срав