БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
Ханты-Мансийского автономного округа-Югры
«Сургутский государственный университет»
Политехнический институт
Кафедра Автоматики и компьютерных систем
Пояснительная записка
к курсовому проекту
по дисциплине
Алгоритмы и структуры данных
Вариант 3 – Бинарное дерево
Выполнил: студент группы 609-81
Бардаков П.Д.
Проверил: старший преподаватель
кафедры автоматики и
компьютерных систем
Назаров Е.В.
Сургут
ЗАДАНИЕ
1. Провести анализ предметной области возможного применения проектируемого класса.
2. Провести анализ функциональности проектируемого класса.
3. Разработать интерфейс класса.
4. В соответствии с разработанным интерфейсом спроектировать тестовое приложение.
5. Выполнить проектирование класса, обоснованно выбирая:
· Необходимые поля класса;
· Методы класса, включив в обязательном порядке операции вставки, удаления, изменения, поиска отдельных элементов, входящих в класс.
6. Провести проектирование алгоритмов, лежащих в основе разрабатываемых методов.
7. Реализовать полученное проектное решение.
8. Реализовать тестовое приложение и провести тестирование разработанного и реализованного класса.
9. Провести исследование одной из операций (вставка, удаление, изменение, поиск) над элементами. Построить зависимость времени выполнения операции от числа элементов, над которыми она выполняется.
10. Оценить асимптотическую сложность реализованных алгоритмов вставки, удаления и поиска элементов класса.
АННОТАЦИЯ
В данной работе выполнен анализ различных существующих реализаций по взаимодействию с бинарными деревьями, определен и реализован функционал необходимых классов. Было написано приложение для тестирования готового класса. Также была исследована операция определения высоты дерева, построена зависимость времени выполнения операции от размера дерева.
Ключевые слова:
· Корень – самых верхний узел дерева
· Ребро – связь между двумя узлами.
· Потомок – узел, имеющий родительский узел.
· Родитель – узел, имеющий ребро, соединяющее его с узлом-потомком.
· Лист – узел, не имеющий узлов-потомков.
· Высота – наибольшая длина пути от корня к листу.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ. 5
1 АНАЛИЗ ЗАДАЧИ.. 6
1.1 ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ.. 6
1.2 ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ.. 6
1.2.1 ПЕРВАЯ РЕАЛИЗАЦИЯ.. 6
1.2.2 ВТОРАЯ РЕАЛИЗАЦИЯ.. 7
1.2.3 ТРЕТЬЯ РЕАЛИЗАЦИЯ.. 7
1.3 ТРЕБОВАНИЯ К РАЗРАБАТЫВАЕМОЙ ПРОГРАММЕ. 8
2 ПРОЕКТИРОВАНИЕ. 9
3 КОДИРОВАНИЕ И ОТЛАДКА.. 12
3.1 МЕТОДЫКЛАССА NODE. 12
3.2 МЕТОДЫКЛАССА TREE. 13
4 ТЕСТИРОВАНИЕ. 16
4.1 ИНТЕРФЕЙС ПРОГРАММЫ.. 16
4.2 ОЦЕНКА ВРЕМЕННЫХ ХАРАКТЕРИСТИК.. 22
5 СОПРОВОЖДЕНИЕ. 24
ЗАКЛЮЧЕНИЕ. 25
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ.. 26
ПРИЛОЖЕНИЯ.. 27
ПРИЛОЖЕНИЕ А. ПОЛНЫЕ ЛИСТИНГИ ФАЙЛОВ.. 27
А.1 ФАЙЛ NODE.PY.. 27
А.2 ФАЙЛ TREE.PY.. 28
А.3 ФАЙЛ MAIN.PY.. 30
А.4 ФАЙЛ TESTS.PY.. 33
ПРИЛОЖЕНИЕ Б. ТАБЛИЦЫС ПОЛУЧЕННЫМИ ДАННЫМИ.. 33
Б.1 ТАБЛИЦА ДАННЫХ ДЛЯ ПОСТРОЕНИЯ ГРАФИКА ЗАВИСИМОСТИ ВРЕМЕНИ ОТ РАЗМЕРА ДЕРЕВА.. 33
ВВЕДЕНИЕ
Этот документ является пояснительной запиской к программному продукту, требования для которого обозначены в задании. Цель данного курсового проекта состоит в создании программного обеспечения и сопровождения к нему. Работа разделена на следующие этапы:
1. Анализ цели, изучение готовых решений.
2. Проектирование: описание необходимых классов, полей, методов
3. Реализация запланированной структуры путем кодирования и отладки.
4. Тестирование продукта, выявление и устранение ошибок.
5. Предоставление продукта с сопровождением, в котором описано, как взаимодействовать с ним.
АНАЛИЗ ЗАДАЧИ
ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ
Бинарное дерево – одна из наиболее широко распространенных структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов.
Представляет собой набор объектов, называемых узлами. Узлы соединены ребрами. Каждый узел содержит значение или данные, и он может иметь не более двух дочерних узлов.
Все узлы дерева соединены линиями, называемыми ребрами. Это важная часть деревьев, потому что она обозначает связь между узлами.
Листья – это последние узлы на дереве. Эти узлы не имеют потомков.
Так как на основе бинарного дерева существует много полезных и более целенаправленных структур данных, было решено рассматривать двоичное дерево поиска. Но, перед этим, необходимо определиться, каким функционалом должно обладать решение. Чтобы правильно подойти к решению данного вопроса, можно проанализировать готовые продукты от других разработчиков, выделить особенности, что-то общее, и что-то, о чем точно нужно будет задуматься.
ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ
ПЕРВАЯ РЕАЛИЗАЦИЯ
Реализация, представленная на рис. 1.1, работает на JavaScript в режиме онлайн. Сайт [1] предоставляет следующие возможности:
· Создание дерева
· Поиск узла по значению
· Добавление узла
· Удаление узла
· Поиск родительского или дочернего узла
· Упорядоченный обход по дереву
Рисунок 1.1 – Первая реализация
Также сайт очень приятно визуализирует процесс взаимодействия с деревом, а точнее, позволяет наглядно увидеть, по какому пути идет алгоритм при изменении или обходе дерева.
ВТОРАЯ РЕАЛИЗАЦИЯ
Вторая реализация, представленная на сайте [2], также работает на JavaScript. Данный ресурс позволяет довольно легко добавлять, искать, удалять узлы из дерева, при этом визуализируя весь процесс. Также доступна возможность отмены последних действий. Пример бинарного дерева, построенного на данном ресурсе, можно увидеть на рис. 1.2.
Рисунок 1.2 – Вторая реализация
ТРЕТЬЯ РЕАЛИЗАЦИЯ
Третья реализация также, как и предыдущие две, существует в виде онлайн ресурса, размещенного на сайте [3], и работает на JavaScript. В отличии от предыдущих двух решений, данная версия позволяет работать не только с корнем дерева, но и с любым другим поддеревом. Для этого достаточно нажать левой кнопкой мыши на необходимый узел, и он подсветиться бордовым цветом. Пример можно увидеть на рис. 3. Также, в данном случае есть функции определения максимального, минимального значения в дереве, а также различные режимы обхода по дереву/поддереву.
Рисунок 1.3 – Третья реализация