Сравнительный анализ сбалансированных деревьев поиска

Введение 5
Глава 1 Деревья поиска 8
1.1 Декартово дерево 8
1.2 Рандомизированное бинарное дерево поиска 14
1.3 Splay-дерево 19
1.4 АВЛ-дерево 23
1.5 B-дерево 28
Глава 2 Тестирование деревьев поиска 34
2.1 Поиск оптимального параметра t для B-дерева 34
2.2 Тестирование на задаче построения дерева 37
2.3 Тестирование на задаче поиска ключа 40
2.4 Тестирование на всех операциях 41
2.5 Выводы по тестированию 42
Заключение 45
Список используемой литературы 46
Купить

Одной из часто встречающихся задач в программировании является построение множества, элементами которого являются значения из очень большого диапазона, поиска в нем и его модификации. Так как диапазон велик, невозможно для каждого из возможных значений хранить в памяти информацию о том, находится ли оно во множестве.
Основной операцией во множестве является поиск значения по ключу. Можно хранить все элементы, находящиеся во множестве в списке или массиве, и просто перебирать их, пока не найдется тот, который нужен, либо будет достигнут конец списка, однако такой способ может оказаться слишком медленным, если размер множества большой, ведь он тратит O(n) на поиск (п - размер множества). Возможным решением для ускорения может стать двоичный поиск, для его применения необходимо, чтобы элементы множества находились в памяти в отсортированном порядке, тогда на каждой итерации поиска отрезок, на котором может находиться искомый ключ будет уменьшаться в 2 раза, значит время поиска составит O(logn) [2].
Однако данные во множестве чаще всего не являются статическими, ключи добавляются и удаляются, структура также должна поддерживать эти операции. Чтобы добавить или удалить ключ в последовательный отсортированный блок памяти, необходимо сдвинуть все ключи, находящиеся после добавляемого/удаляемого ключа в памяти, на одну позицию, что может занять O(n) времени, сделав модификацию множества тяжелой операцией.
Выбирая между хранением ключей в случайном порядке и хранением в отсортированном, мы, по сути, выбираем между вариантом с быстрой (O(logn)) вставкой/удалением, но медленным (O(n)) поиском и вариантом с медленной (O(n)) вставкой/удалением, но быстрым (O(logn)) поиском.
Для решения задачи быстрой вставки/удаления и поиска ключа были созданы деревья поиска. Такие структуры позволяют достигнуть оценки O(logn) для всех необходимых операций и занимают O(n) памяти. Было изобретено множество различных сбалансированных деревьев поиска. В 1989 году Сидель Раймундом (Seidel Raimund) и Цецилия Арагон (Aragon Cecilia) создали декартово дерево, которое также называют дерамидой. Советские ученые Адельсон-Вельский и Ландис в 1962 году изобрели АВЛ-дерево, бинарное дерево, баланс в котором поддерживается за счет того, что разница высот левого и правого поддерева для каждой из вершин не превышает 1. Это свойство АВЛ-дерева делает его высоту примерно равной O(logn). В 1970 году Р Бейер и Э. МакКрейт создали B-дерево, сильно ветвящееся, сбалансированное дерево, которое может содержать несколько ключей в каждой из вершин, тем самым позволяющее уменьшить количество операций чтения с диска. Благодаря этой особенности B-деревья часто используются при построении индексов в базах данных [20]. Сбалансированные деревья поиска используют для решения следующих задач:
1. Так называемая «словарная проблема». Примером такого множества на практике может являться англо-русский словарь, в котором ключ - это слово на английском, а значение это перевод данного слова на русский, также хороший пример - это телефонная книга, где ключом является ФИО человека а значением - его телефонный номер. В программировании словари обычно называются ассоциативными массивами, и они уже реализованы в стандартных библиотеках (map в C++, TreeMap в Java).
2. Структура данных rope, представляющая из себя сбалансированное двоичное дерево. Эта структура для хранения больших строк, которая позволяет совершать многие операции вроде конкатенации, взятия подстроки на строках длины n с асимптотикой порядка O(logn). Эффективность достигается за счет того, что строка хранится в памяти не как массив из символов, а разбита на небольшие части, которые хранятся в узлах дерева rope.
3. Индексы в базах данных основаны на деревьях поиска, одним из наиболее часто используемых является В-дерево. Так как элементы в деревьях расположены в отсортированном порядке, они позволяют не только искать ключи с конкретными значениями, но и, например, искать наименьший ключ со значением больше заданного, или вычислять количество ключей из заданного диапазона.
Данная работа посвящена теоретическому и практическому сравнительному анализу сбалансированных деревьев поиска.
Объект исследования - процесс модификации и поиска во множестве.
Предметом исследования являются декартово дерево, рандомизированное дерево поиска, АВЛ-дерево, splay-дерево, В-дерево.
Целью бакалаврской работы является сравнение эффективности рассматриваемых деревьев поиска на различных задачах, выявление сильных и слабых сторон структур при использовании на практике.
Для достижения поставленной цели необходимо выполнить следующие задачи:
1. Рассмотреть задачи, решаемые с помощью деревьев поиска.
2. Рассмотреть различные деревья поиска.
3. Провести теоретический сравнительный анализ рассматриваемых структур на предмет эффективности.
4. Реализовать рассматриваемые деревья поиска на языке программирования C++.
5. Провести генерирование данных для тестирования деревьев на предмет производительности.
6. Провести тестирование на сгенерированных данных.
7. Осуществить сравнительный анализ деревьев поиска на сгенерированных данных.
Бакалаврская работа состоит из введения, двух глав и заключения.
В первой главе дано описание различных сбалансированных деревьев поиска, приведена асимптотическая оценка их работы.
Вторая глава посвящена тестированию рассмотренных структур на различных задачах и сравнительному анализу на основании результатов тестирования.

Купить