2. Описание алгоритмов

2.1. Добавление элементов

Вставка нового ключа в АВЛ-дерево выполняется так же, как это делается в простых деревьях поиска: спускаемся вниз по дереву, выбирая правое или левое направление движения в зависимости от результата сравнения ключа в текущем узле и вставляемого ключа. Единственное отличие заключается в том, что при возвращении из рекурсии (т.е. после того, как ключ вставлен либо в правое, либо в левое поддерево, и это дерево сбалансировано) выполняется балансировка текущего узла

2.2. Удаление элементов

Удаление уз лов из АВЛ-дерева. За основу берется вариант, который обычно применяется при удалении узлов из стандартного двоичного дерева поиска. Находим узел p с заданным ключом k (если не находим, то делать ничего не надо), в правом поддереве находим узел min с наименьшим ключом и заменяем удаляемый узел p на найденный узел min.

2.3. Перебалансировка дерева

В процессе добавления или удаления узлов в АВЛ-дереве возможно возникновение ситуации, когда возникает разбалансировка поддерева. Для выправления ситуации применяются повороты вокруг тех или иных узлов дерева. Так, при разбалансировке в правую сторону проискодит, при необходимости правый поворот правой ветви, после чего левый поворот вокруг корня. Поворот направо относительно узла p производится путем нахождения его левого поддерева q, подстановка правого поддерева q в левое поддерево p, после чего установка p в качестве правого поддерева q. Узел q является новым корнем данного поддерева. При левом повороте происходят зеркальные действия.

3. Программная реализация структуры данных и функций

3.1. Структура node

struct node // структура для представления узлов дерева
    {
        Elem key;
        unsigned char height;
        node* left;
        node* right;
        bool highlight=false;
        bool highlightLeft=false;
        bool highlightRight=false;
        node(Elem k) { key = k; left = right = 0; height = 1; }
    };

Данная структура используется для представления узла бинарного дерева. Она содержит в себе следующие поля:

• key — значение, хранимое в узле дерева типа Elem. Тип Elem определен шаблоном родительского класса

height - Высота поддерева, задаваемого данным узлом

left — указатель на левое поддерево

right — указатель на правое поддерево

highlight,  highlightLeft, highlightRight — нужны для графического изображения дерева. Устанавливают выделение корня, левого и правого узлов соответственно.

template <class Elem>////Template class
class AVL

Данный класс представляет из себя структуру данных АВЛ-дерева. Он предоставляет сторонним программам удобный интерфейс для работы с АВЛ-деревом, вставки элементов в дерево, удаления элементов, прохода по дереву, а так же поиска элементов в нем. 
	В данном классе содержатся следующие поля:

node* Root- Указатель на узел node,  который и является представлением корня данного дерева. Если дерево пустое Root=0

ListViewActionLogger* logger - Указатель на класс-логгер, для сообщения внешней программе о изменениях дерева для графического пошагового разбора. Данный класс будет разобран ниже

3.3. Функции балансировки avl и вспомогательные функции

Для балансировки дерева используются следующие вспомогательные функции:

int bfactor(node* p) — фактор равновесия - разница между высотой правой и левой ветви дерева. Принимает указатель на корень дерева p, возвращает целое число — разницу между высотами ветвей. Считается путем вычитания из высоты правой ветви высоты левой.

node* rotateright(node* p) — Левый поворот дерева вокруг выбранного узла p. Возвращает указатель на корень нового поддерева с учетом переворота. Поворот направо относительно узла p производится путем нахождения его левого поддерева q, подстановка правого поддерева q в левое поддерево p, после чего установка p в качестве правого поддерева q. Узел q является новым корнем данного поддерева.

	node* rotateleft(node* q) — Правый поворот дерева вокруг выбранного узла q. Производится зеркально правому повороту. Возвращает указатель на корень нового поддерева с учетом переворота.

Для балансировки дерева служит данная функция^

	node* balance(node* p)

	Функция принимает указатель на корень несбалансированного дерева p, возвращает указатель на  соответствующее сбалансированное дерево. Данная функция вычисляет фактор равновесия узла и соответствующим образом перевешивает дерево.
	Если фактор равновесия не больше 1 по модулю, то дерево считается сбалансированным
	Фактору равновесия 2 соответствует перевес в правую сторону. В этом случае в первую очередь производится проверка правого поддерева, и если его фактор равновесия смещает влево, то перевешивает его правым поворотом. После этого производится левый поворот вокруг узла корня данного поддерева. В случае перевеса в левую сторону происходят аналогичные, зеркальные действия по перевешиванию дерева вправо.

С полным кодом можно ознакомиться в приложении И.

3.4. Функция вставки элемента в avl

Для вставки элемента в дерево используется следующая функция:

node* _insert(node* p, Elem k, int lvl = 0) — принимает указатель на корень поддерева, в которое требуется вставить элемент p, сам элемент k, и глубину рекурсии lvl для отладки. Возвращает указатель на корень поддерева со вставленным элементом k.

Для вставки элемента первую очередь производится рекурсивный обход дерева для нахождения позиции для вставки. Согласно структуре бинарного дерева поиска(левое поддерево меньше корня, правое больше) ключ k сравнивается с очередным корнем, и если меньше него — рекурсивно заходит в левое поддерево, если больше — в правое. При нахождении пустого поддерева считаем, что место для элемента найдено. Так же может оказаться, что наш элемент равен узлу — это значит, что элемент уже есть в дерево и добавлять его не требуется.

Для вставки элемента в AVL реализован метод — обертка на описанной выше функцией

void insert(Elem key) — данный метод вызывает функцию  _insert для корня Root, подавая в качестве элемента Key

С полным кодом можно ознакомиться в приложении И.

3.5. Функция удаления из avl и вспомогательные функции

Для удаления элемента из AVL используются следующие вспомогательные функции

node* findmin(node* p) — Ищет минимальный элемент поддерева p путем захода, пока возможно, в левое поддерево. Возвращает указатель на узел с минимальным значением.

	node* removemin(node* p) — Удаляет минимальный узел поддерева p путем подстановки вместо него его правого поддерева. Возвращает указатель на новое поддерево без минимального элемента, предварительно его сбалансировав.

Для удаления элемента из AVL служит данная функция:

node* _remove(node* p, Elem k) — принимает указатель на корень поддерева из которого требуется произвести удаление - p, и элемент, который требуется удалить k.

Для удаления элемента первую очередь производится рекурсивный обход дерева для его нахождения. Согласно структуре бинарного дерева поиска(левое поддерево меньше корня, правое больше) элемент k сравнивается с очередным корнем, и если меньше него — рекурсивно заходит в левое поддерево, если больше — в правое. При нахождении пустого поддерева считаем, что данного элемента нет в дереве. При равенстве элемента k с одним из узлов считаем, что элемент найден. Далее проверяем его левое поддерево. Если оно пусто — подставляем вместо элемента его левое поддерево, а старый корень удаляет. Если правое поддерево не пусто — при помощи функции findmin ищем минимальный элемент правого поддерева. Ставим его на место удаляемого элемента, и удаляем минимальный элемент со старого места функцией removemin.

3.6. Класс логгер ListViewActionLogger

class ListViewActionLogger : public QListView
Данный класс используется для отслеживания изменений в дереве вследствие его обработки при помощи функций.
	Данный класс содержит в себе следующие поля:
	QStandardItemModel *model = new QstandardItemModel — список логированных изменений.
    	std::list<AVL::AVL<int> > treeList - Список деревьев для каждого шага.
Каждому элементу списка с текстовым описанием изменения соответствует изображение дерева. Класс наследуется от класса QListView, который используется для списочного представления строковых данных.
	С полным кодом можно ознакомиться в приложениях Е и З.

3.7. Метод логгера logAction

void logAction(std::string str, AVL::AVL<int> tree) — данный метод предназначен для добавление новой записи в список изменений. Метод принимает параметр str — текстовое описание действий, производимых над деревом, и tree — изображение дерева ему соответствующее.
	С полным кодом можно ознакомиться в приложениях Е и З.

3.8. Метод логгера clear

	void clear() - данный метод очищает список действий, ставя последнее изображение дерево в качество текущего, затем очищает список деревьев и строк.
	С полным кодом можно ознакомиться в приложениях Е и З.

3.9. Сигнал логгера reselect

	void reselect(int) — данный сигнал активируется при изменении выделения элемента в списке, и сигнализирует о необходимости отображения нового дерева на экране. В целочисленном аргумента передается индекс нужного дерева и описания в списке.

С полным кодом можно ознакомиться в приложениях Е и З.

3.10. Класс графики GraphGraphicView

class GraphGraphicView : public QGraphicsView

Данный класс используется для графического изображения дерева на экране. Он содержит следующие поля:

QGraphicsScene *scene — Поле, на котором происходит размещение элементов

    	QGraphicsItemGroup  *group_1 
    	QGraphicsItemGroup  *group_2 — группы, в которые помещаются элементы для размещения на поле.
    	AVL::AVL<int> last_drawn_avl — хранится последнее изображенное дерево для перерисовки по необходимости
    	int _width — ширина поля
    	int _height - высота поля
    	float _nodeSize - размер изображения одного узла
    	float _lvlInt — интервал между уровнями дерева

Данный класс наследуется от класса QGraphicsView, служещего для изображения графики

С полным кодом можно ознакомиться в приложениях Г и Д.

3.11. Методы класса графики slotDrawAvl и _slotDrawAvl

	void slotDrawAvl(AVL::AVL<int> _avl) — данный метод служит для начала отрисовки дерева _avl. В нем происходит вычисление параметров изображения, после чего для отрисовки дерева на экране происходит вызов метода _slotDrawAvl
	void _slotDrawAvl(AVL::AVL<int> avl, int lvl, float xCoord) — данный метод служит непосредственного рекурсивного изображения дерева avl на экране. Параметр lvl отвечает за значение текущего уровня отрисовки,  xCoord - координата x корня данного поддерева.
	В начале данного метода происходит отрисовка окружности и текста в ней для корня текущего поддерева. Далее, при необходимости, отрисовываются соединительные линии с левым и правым поддеревом. Линии, как и эллипс могут быть выделены, если это указано в структуре корня текущего поддерева.
	Когда отрисовка данного нода и линий окончена функция рекурсивно вызывается для дочерних поддеревьев.

С полным кодом можно ознакомиться в приложениях Г и Д.

3.12. Ивент класса графики resizeEvent

void resizeEvent(QResizeEvent *event) - данный ивент вызывается при масштабировании окна с изображением. Через него передается указатель  event — служебная информация о ивенте.
При его вызове происходит повторная отрисовка дерева при помощи функции slotDrawAvl с учетом новых параметров рабочей области.
	С полным кодом можно ознакомиться в приложениях Г и Д.

4. Описание интерфейса пользователя

4.1. Интерфейс взаимодействия со структурой

Для взаимодействия со структурой данных происходит при помощи кнопочного интерфейса. В боксе для элементов управления находятся следующие элементы слева направо:

• New. Создает новое дерево, удаляя старое и очищая список предыдущих шагов.

• Add. Добавляет в текущее дерево элемент со значением, указанным в поле для ввода правее. Данное действие добавляет в список все изменения, произошедшие для его выполнения

• Rem. Добавляет из текущего дерева элемент со значением, указанным в поле для ввода правее. Данное действие добавляет в список все изменения, произошедшие для его выполнения

• Поле для ввода. Используется для ввода значения элемента для удаления или вставки.

• Clear. Очистка списка действий. Перерисовывает дерево в последней конфигурации, очищает список действий, произведенных ранее.

4.2. Интерфейс обзора структуры на каждом шаге работы алгоритмов

Интерфейс обзора структуры и шагов работы с ней поделен на две части.

В левой части показано изображение дерева соответствующего выделенному в данный момент шагу. Сам список шагов находится в левой части экрана, и позволяет при помощи мыши либо клавиатуры перемещаться по истории действий, анализируя произошедшие изменения

5. Тестирование

Для удаления элемента из AVL реализован метод — обертка на описанной выше функцией

	void remove(Elem key) — данный метод вызывает функцию  _remove для корня Root, подавая в качестве элемента Key

С полным кодом можно ознакомиться в приложении И.