Материал: Larin_Anton_AiSD_21_KW
МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра МО ЭВМ
Курсовая РАБОТА
по дисциплине «АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ»
Тема: Бинарное дерево поиска. АВЛ-дерево
Вариант 16
Демонстрация
|
Студент гр. 8383 |
|
Ларин А. |
|
Преподаватель |
|
Фирсов М.А. |
Санкт-Петербург
2019
ЗАДАНИЕ
на курсовую работу
|
Студент Ларин А. |
||
|
Группа 8383 |
||
|
Тема работы: Бинарное дерево поиска. АВЛ-дерево
|
||
|
Исходные данные: Пользователем при помощи графического интерфейса задается исходное АВЛ-дерево |
||
|
|
||
|
Предполагаемый объем пояснительной записки: Не менее 15 страниц. |
||
|
Дата выдачи задания: 11.10.2019 |
||
|
Дата сдачи реферата: |
||
|
Дата защиты реферата: |
||
|
Студент |
|
Ларин А. |
|
Преподаватель |
|
Фирсов М.А. |
Аннотация
В данной работе реализована взаимодействие с АВЛ-деревом, добавление, удаление элементов и автоматическое перевешивание дерева.
Для графической демонстрации использована среда Qt Creator.
Данная программа написана на языке программирования C++.
Взаимодействие пользователя с программой производится при помощи графического интерфейса, так же реализованного при помощи Qt Creator.
Summary
Given work provides an interaction with AVL-tree, adding, removing elements from it and automatic re-balancing of a tree.
For graphical demonstration an Qt Creator environment was used.
This program is written using C++ programming language.
Interaction between an user and a program is provided through graphical interface, made using Qt Creator as well
|
|
содержание
|
|
|
|
Введение |
5 |
|
1. |
Описание структур данных |
6 |
|
1.1. |
Бинарное дерево поиска |
6 |
|
1.2. |
АВЛ-дерево |
8 |
|
2. |
Описание алгоритмов |
9 |
|
2.1. |
Добавление элементов |
9 |
|
2.2. |
Удаление элементов |
9 |
|
2.3 |
Перебалансировка дерева |
10 |
|
3. |
Программная реализация структуры данных и функций |
11 |
|
3.1. |
Структура node |
11 |
|
3.2. |
Класс AVL |
11 |
|
3.3 |
Функции балансировки AVL и вспомогательные функции |
12 |
|
3.4 |
Функция вставки элемента в AVL |
13 |
|
3.5 |
Функция удаления из AVL и вспомогательные функции |
14 |
|
3.6 |
Класс логгер ListViewActionLogger |
15 |
|
3.7 |
Метод логгера logAction |
15 |
|
3.8 |
Метод логгера clear |
16 |
|
3.9 |
Сигнал логгера reselect |
16 |
|
3.10 |
Класс графики GraphGraphicView |
16 |
|
3.11 |
Методы класса графики slotDrawAvl и _slotDrawAvl |
17 |
|
3.12 |
Ивент класса графики resizeEvent |
17 |
|
4. |
Описание интерфейса пользователя |
18 |
|
4.1 |
Интерфейс взаимодействия со структурой |
18 |
|
4.2 |
Интерфейс обзора структуры на каждом шаге работы алгоритмов |
18 |
|
5. |
Тестирование |
19 |
|
|
Заключение |
22 |
|
|
Список использованных источников |
23 |
|
|
Приложение А. Содержимое main.cpp |
24 |
|
|
Приложение Б. Содержимое mainwindow.h |
25 |
|
|
Приложение В. Содержимое mainwindow.cpp |
27 |
|
|
Приложение Г. Содержимое graphgraphicview.h |
31 |
|
|
Приложение Д. Содержимое graphgraphicview.cpp |
33 |
|
|
Приложение Е. Содержимое listviewactionlogger.h |
37 |
|
|
Приложение З. Содержимое listviewactionlogger.cpp |
38 |
|
|
Приложение И. Содержимое AVLTreeClass.h |
39 |
Введение
Цель данной работы состоит в изучении работы такой структуры данных как AVL-дерево, изучение принципа ее функционирования и реализация основных алгоритмов для работы с ней, таких как вставка и удаление.
Среди задач можно выделять в первую очередь нахождение ресурсов и изучение работы АВЛ-дерева, способы работы и взаимодействия с ним, алгоритмы, требуемые для обработки данной структуры данных.
По итогам стоит задача написать программу с графическим интерфейсом, наглядным и понятным отображением АВЛ-деревом для демонстрации изученных алгоритмов и реализации наглядного пособия, помогающего в понимании принципов работы изученной структуры данных.
Для решения поставленных задач были изучены ресурсы, предоставляющие информацию, описывающую требуемую структуру данных и алгоритмы для работы с ней, а так же изучения среда QtCreator, которая в дальнейшем была использована для реализации взаимодействия с пользователем и демонстрации АВЛ-дерева и работы с ним при помощи его наглядного графического отображения.
1. Описание структур данных
1.1. Бинарное дерево поиска
Бинарное
дерево — это иерархическая структура
данных, в которой каждый узел имеет
значение (оно же является в данном случае
и ключом) и ссылки на левого и правого
потомка. Узел, находящийся на самом
верхнем уровне (не являющийся чьим либо
потомком) называется корнем. Узлы, не
имеющие потомков (оба потомка которых
равны NULL) называются листьями.
Рис. 1 Бинарное дерево
Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева. То есть, данные в бинарном дереве поиска хранятся в отсортированном виде. При каждой операции вставки нового или удаления существующего узла отсортированный порядок дерева сохраняется. При поиске элемента сравнивается искомое значение с корнем. Если искомое больше корня, то поиск продолжается в правом потомке корня, если меньше, то в левом, если равно, то значение найдено и поиск прекращается.
Рис.
2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.
Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей.
1.2. АВЛ-дерево
А
ВЛ-дерево
— это прежде всего двоичное дерево
поиска, ключи которого удовлетворяют
стандартному свойству: ключ любого узла
дерева не меньше любого ключа в левом
поддереве данного узла и не больше
любого ключа в правом поддереве этого
узла. Это значит, что для поиска нужного
ключа в АВЛ-дереве можно использовать
стандартный алгоритм. Для простоты
дальнейшего изложения будем считать,
что все ключи в дереве целочисленны и
не повторяются. Особенностью АВЛ-дерева
является то, что оно является
сбалансированным в следующем смысле:
для любого узла дерева высота его правого
поддерева отличается от высоты левого
поддерева не более чем на единицу.
Доказано, что этого свойства достаточно
для того, чтобы высота дерева логарифмически
зависела от числа его узлов: высота h
АВЛ-дерева с n ключами лежит в диапазоне
от log2(n
+ 1) до 1.44 log2(n
+ 2) − 0.328. А так как основные операции
над двоичными деревьями поиска (поиск,
вставка и удаление узлов) линейно зависят
от его высоты, то получаем гарантированную
логарифмическую зависимость времени
работы этих алгоритмов от числа ключей,
хранимых в дереве