Древовидные структуры данных

1 Постановка задачи

Для курсовой определен 15 вариант, который предусматривает ис-пользование в работе файла base3.dat – база данных "Обманутые вкладчи-ки". Для поиск необходимо построить АВЛ-дерево. Программный про-дукт должен обеспечить выполнение следующих заданий:
 вывести на экран количество и фамилии всех адвокатов из базы данных;
 вывести в алфавитном порядке (по полю ФИО вкладчика) список вкладчиков которые имеют адвоката с заданной фамилией и вклад больше заданной суммы;
 Фамилию адвоката и сумму вводить с клавиатуры.
Входные данные – база данных «Обманутые вкладчики» (бинарный файл base3.dat), которая содержит 4000 записей. Структура записи базы данных:
ФИО вкладчика: текстовое поле 32 символа формат <Фамилия> _<Имя>_<Отчество>)
Сумма вклада: целое шестнадцатиразрядное положительное число
Дата вклада: текстовое поле 8 символов формат дд-мм-гг
ФИО адвоката: текстовое поле 22 символа формат <Фамилия> _<буква>_<буква>
Пример записи из БД:
Петpов_Иван_Федоpович___________130 15-03-46 Иванова_И_В_________
Если длина текстового поля превышает размер хранимой в нем ин-формации, то оно дополняется пробелами справа.
Выходная информация. В соответствии с заданием выходная инфор-мация должна быть представлена в виде двух отчетов. Первый отчет со-держит ФИО адвоката и их количество. Второй отчет представляет собой список вкладчиков отсортированный по алфавиту, которые имеют адвока-та с заданной фамилией и вклад больший заданной суммы.
Для решения задачи необходимо использовать следующие структу-ры данных: АВЛ-дерево, очередь. Построение АВЛ-дерева позволяет вы-полнить сортировку записей. Если обходить дерево рекурсивно слева направо получим отсортированный по возрастанию список, справа налево – по убыванию. Очередь должна использоваться для формирования спис-ка очередности вывода информации.
Приложение должно иметь дружественный интерфейс. В данном случае должно быть разработано консольное меню управления работой приложения. Пункты меню:
 Вывести весь список вкладчиков.
 Вывести список адвокатов
 Вывести список вкладчиков, которые имеют адвоката с задан-ной фамилией и вклад больше заданной суммы.
 Выход
При выборе пункта меню экран должен очищаться и появляться ин-формация по выбранному пункту, а затем сам отчет.
При выборе третьего пункта меню необходимо предоставить пользо-вателю список адвокатов. Одну из этих фамилий он должен ввести с клави-атуры. При этом необходимо напомнить пользователю, что ввести нужно только фамилию без инициалов.
По окончанию выполнения пункта меню, экран должен очищаться и снова появляться пункты меню.
Вывод списков должен выполняться постранично при нажатии на клавишу Enter. Должно быть предусмотрено прекращение вывода списка при нажатии на клавишу Esc. Информация о этих возможностях должна присутствовать на экране.

2 Хаpактеpистика алгоpитмов

АВЛ-дерево – разновидность двоичного дерева поиска, основная характеристика которого сбалансированность. Сбалансирован-ным называется такое двоичное дерево поиска, в котором высота каждого из поддеревьев, имеющих общий корень, отличается не более чем на неко-торую константу k, и при этом выполняются условия характерные для двоичного дерева поиска.
АВЛ-дерево – сбалансированное двоичное дерево поиска с k=1. Для его узлов определен коэффициент сбалансированности (balance factor). Balance factor – это разность высот правого и левого поддеревьев, прини-мающая одно значение из множества {-1, 0, 1}.
Операции с АВЛ-деревом:
 поиск;
 балансировка;
 создание дерева;
 добавление узла ;
 удаление узла.
Для представления АВЛ-деревьев используется либо структура, ли-бо класс.
Структура описывает узлы и включает следующие поля:
– указатель на правое поддерево;
– указатель на левое поддерево;
– ключ узла;
– высота поддерева.
– коэффициент сбалансированности узла.
2.1 Поиск ключа
Для поиска элемента в АВЛ-дереве необходимо искомый ключ срав-нивать со значением ключа узла. Если ключи совпали, то поиск завершен. Иначе для дальнейшего сравнения выбирается левое или правое поддере-во. Выбор поддерева зависит от результатов сравнения искомого ключа с ключом корневого узла. Процедура продолжается пока не будет найден узел дерева или новые узлы для сравнения не найдены. Блок-схема алго-ритма приведена на рисунке 1.




Рисунок 1 – Блок-схема поиска ключа


2.2 Алгоритм балансировки
Балансировкой вершины – это операция, которая в случае разницы высот(h) левого(L) и правого (R) поддеревьев |h(L)−h(R)|=2, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева |h(L)−h(R)|⩽1, иначе ничего не меняет. Для выполнения балансировки необходимо хранить для каждой вершины разницу между высотой её левого и правого поддерева diff[i]=h(L)−h(R).
Для балансировки вершины используются один из 4 типов враще-ний: малое и большое левое вращение, малое и большое правое вращение. На рисунке 2 представлено ситуация, в случае которой выполняется малое левое вращение.

Рисунок 2 – Ситуация для проведения малого левого вращения

На рисунке 3 представлена блок-схема алгоритма малого левого вращения. На рисунке 4 вид дерева после малого левого вращения.

Рисунок 3 – Блок-схема алгоритма малого левого вращения для узла a

Рисунок 4 – Результат малого левого вращения

На рисунке 5 представлено АВЛ-дерево, требующее большого лево-го вращения.

Рисунок 5 – Ситуация для проведения большого левого вращения

На рисунке 6 представлена блок-схема алгоритма большого левого вращения, а на рисунке 7 – его результат.


Рисунок 6 – Блок-схема алгоритма малого левого вращения для узла a

Рисунок 7 – Результат большого левого вращения для узла a

Малое правое и большое правое вращение выполняются симмет-рично малому и большому левому вращению. Вращения всегда приводят к нужному результату, а полная высота не может увеличиваться, а либо не уменьшается либо уменьшается на 1.
2.3 Добавление узла.
В АВЛ-дерево необходимо добавить ключ t. Спуск по дереву осу-ществляется спускаться по дереву, как при поиске ключа t. Рассмотрим вершину a и нам надо идти в поддерево, которого нет, то делаем ключ t листом, а вершину a его корнем. Далее выполняется подъем вверх по пути поиска и пересчитывается баланс у вершин. Если мы поднялись в вершину ii из левого поддерева, то diff[i] увеличивается на единицу, если из правого, то уменьшается на единицу. Если баланс в вершину стал рав-ным нулю, то это значит высота поддерева не изменилась и подъём оста-навливается. Если пришли в вершину и её баланс стал равным 1 или −1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или −2, то выполняется ба-лансировка, если после вращения баланс стал равным нулю, то добавление завершилось, иначе продолжается подъём. Алгоритм добавления приведен на рисунке 8.