Введение 3
1. Описание исследуемой области 5
2. Методика эксперимента 6
3. Структуры данных 7
3.1. Бинарное дерево поиска 7
3.2. АВЛ дерево 9
3.3. Красно-черное дерево 17
3.4. Сравнение АВЛ-деревьев и красно-черных 20
3.5. В-дерево 23
4. Анализ результатов 30
5. Амортизированный анализ 35
Заключение 35
Список литературы
На сегодняшний день сложно найти сферу деятельности человека, в которой не хранились бы большие объемы информации. В связи с этим, конечно, возникает необходимость в эффективном управлении данных. Работа в этом направлении подразумевает запись информации, ее хранение, необходимую обработку, а также удаление уже не актуальных данных. Однако, помимо этих первоочередных функций, огромное значение имеют такие параметры, как время работы выбранных методов, память.
Часто выбор алгоритма решения задачи зависит от способа представления данных. Одна из наиболее распространенных структур данных для реализации операций поиска, удаления и вставки - Дерево поиска. Деревья поиска предназначены для быстрого доступа к данным. Эта структура имеет древовидную форму с набором связанных узлов и используется при реализации словаря. Кроме того, является связным графом, не содержащим циклы.
Предметом исследования данной работы являются:
-Бинарное дерево (его еще называют двоичным деревом) поиска;
-АВЛ дерево;
-Красно-Черное дерево;
-B-дерево.
Целью данной работы является сравнительный анализ временной и пространственной сложности указанных структур данных. Для достижения данной цели необходимо выполнить следующие задачи:
- разработать программирование деревьев;
- провести анализ стандартных функций;
- выявить положительные и отрицательные стороны;
- произвести сравнительный анализ различных видов деревьев;
-Сформулировать рекомендации какое дерево в каких ситуациях лучше использовать.
Известно довольно много работ, темой которых является анализ деревьев в сфере it, отличительной особенностью данной дипломной работы является формулировка практических рекомендаций по оптимальному применению деревьев к различным наборам данных.
Актуальность данной дипломной работы обуславливается тем, что программирование в последние десятилетия находится в стадии постоянного развития. На сегодняшний день известно и широко применяется множество структур данных и алгоритмов сортировки, которые являются основой современного компьютерного программирования. В данной дипломной работе осуществляется сравнительный анализ некоторых методов обработки данных и форм их организации в программах.
В ходе проведения данной дипломной работы нами были запрограммированы различные структуры данных, выполнен анализ стандартных функций, проведено сопоставление теоретического анализа с практическими данными, выявлены как положительные, так и отрицательные стороны. Также был выполнен сравнительный анализ по критериям амортизированной сложности, в результате чего были выведены некоторые рекомендации для эффективного выбора деревьев на определенные наборы данных.
В заключение данной дипломной работы мы пришли к выводу, что наиболее оптимальным вариантом при работе с небольшим количеством неупорядоченных элементов является Бинарное дерево. В то время, как наилучшим образом при работе с маленьким набором упорядоченных данных себя показало Красно-черное дерево, с условием, что в работе будут часто применяться функции вставки и удаления. В случае преобладания операции поиска рекомендовано применение АВЛ - дерева.
При необходимости поступления большого набора данных явным лидером себя зарекомендовало В - дерево.
Таким образом, имеющиеся теоретические данные в большинстве случаев совпали с результатами наших практических исследований. Поставленная цель достигнута.
