Материал: Larin_Anton_AiSD_21_5

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра МО ЭВМ

отчет

по лабораторной работе №5

по дисциплине «АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ»

Тема: Бинарное дерево поиска. АВЛ-дерево

Санкт-Петербург

2019

Цель работы.

Научтся организовывать такую структуру данных, как бинарное дерево поиска. Изучить основные концепции БДП, методы работы с ним. Построить на его основе АВЛ-дерево.

Основные теоретические положения.

А ВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла. Это значит, что для поиска нужного ключа в АВЛ-дереве можно использовать стандартный алгоритм. Для простоты дальнейшего изложения будем считать, что все ключи в дереве целочисленны и не повторяются. Особенностью АВЛ-дерева является то, что оно является сбалансированным в следующем смысле: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Доказано, что этого свойства достаточно для того, чтобы высота дерева логарифмически зависела от числа его узлов: высота h АВЛ-дерева с n ключами лежит в диапазоне от log₂(n + 1) до 1.44 log₂(n + 2) − 0.328. А так как основные операции над двоичными деревьями поиска (поиск, вставка и удаление узлов) линейно зависят от его высоты, то получаем гарантированную логарифмическую зависимость времени работы этих алгоритмов от числа ключей, хранимых в дереве

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

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

Задание

Требуется:

1. По заданному файлу F (типа file of Elem), все элементы которого различны, построить структуру данных определённого типа – БДП или хеш-таблицу;

2. Выполнить одно из следующих действий:

а) Для построенной структуры данных проверить, входит ли в неё элемент е типа Elem, и если не входит, то добавить элемент е в структуру данных. Предусмотреть возможность повторного выполнения с другим элементом.

Вар.16. Группа 2. БДП: АВЛ-дерево; действие: 1+2а

Реализация

Функции и структуры данных

Согласно заданию была реализована структура данных АВЛ-дерево на базе структуры node обернутой в шаблонный класс AVL со значениями типа Elem.

template <class Elem>////Template class

class AVL

struct node

{

Elem key;

unsigned char height;

node* left;

node* right;

node(Elem k);

};

Структура node является представлением узла дерева. Она содержит в себе значение key, высоту дерева height, указатели на левого и правого потомка left и right соответственно, и конструктор для инициализации. Класс AVL является оберткой над структурой node, и служит для удобства использования. Данный класс хранит указатель на node, и позволяет управлять им при помощи методов.

Для работы с данным АВЛ-деревом описан следующий интерфейс:

• bool empty() // Проверяет дерево на пустоту

Не принимает параметров

Возвращает true если дерево пусто, false в противном случае.

• void insert(Elem key) // Вставляет в дерево узел со значением

Принимает значение key типа элем — значение узла для вставки

Не возвращает значений.

Алгоритм:

Рекурсивно обходим дерево, сравнивая значение ключа с узлами. Если значение key меньше значения очередного узла — заходим в левую ветвь. В противном случае - в правую. При заходе в пустую ветвь помещаем в нее новый узел. При этом разница баланса ветвей меняется не более чем на один. Соответственно может произойти ситуация, когда эта разница равна двум. В этом случае необходима балансировка. Она производится путем поворота узлов по или против часовой стрелки(против направления перевеса). Рассмотрим правый переворот вокруг узла p. Он выполняется следующим образом:

q = p->left;
p->left = q->right
q->right = p;
То есть правое поддерево левого узла становится левым поддеревом правого узла, а сам правый узел становится правым поддеревом левого узла.

• AVL find(Elem key)// Поиск узла с нужным значением в дереве

Принимает значение key типа элем — значение узла, который требуется найти

Возвращает найденное поддерево, если узел был найден, и пустое дерево — если не найден.

Алгоритм:

Рекурсивно обходим дерево, сравнивая значение ключа с узлами. Если значение key меньше значения очередного узла — заходим в левую ветвь. В противном случае - в правую. Если обнаруживаем равенство значений — узел найден. При заходе у пустое поддерево делаем вывод, что узла с нужным значением нет.

• AVL left()//Возвращает правую ветвь дерева

• AVL right()//Возвращает левую ветвь дерева

В основной функции main последовательно происходит:

Вызов функций parseArgs, которая обрабатывает аргумента командной строки;

Затем, если требуется, открытие файлов на вход и выход;

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

Дерево выводится в консоли или в файл.

Программа поддерживает настройку при помощи параметров из командной строки. Получить информацию от них можно аргументом «-h»

Они следуюшие:

-h help

-A [N] Автоматическое тестирование на списках глубины 0 — N-1 (N=1 по умолчанию; игнорирует параметры -i и -r при вводе)

-r Дает выбор перезапустить программу после исполнения. Не совместимо с «-i/-A»

-i [file] Ввод из файла file, вместо стандартного потока stdin («in» по умолчанию)

-o [file] Вывод в файл file вместо стандартного потока stdout («out по умолчанию»)

-d Вывод промежуточных данных при работе с деревом.

Тесты.

1.

Input:

1 4 5 9

Building AVL tree of entered sequence

Built tree:

4 5 9

1

Entered element:

3

Searching for '3' in subtree with root '4'

Current:4

Looking left

Current:1

Looking right

Not found!

Search completed

Adding element

Inserting element '3' in subtree with root '4'

Current:4

Going left

Current:1

Going right

Insertion place!

Rebalancing AVL

Rebalancing AVL

Insertion completed

Current AVL tree:

4 5 9

1 3

Entered element:

6

Searching for '6' in subtree with root '4'

Current:4

Looking right

Current:5

Looking right

Current:9

Looking left

Not found!

Search completed

Adding element

Inserting element '6' in subtree with root '4'

Current:4

Going right

Current:5

Going right

Current:9

Going left

Insertion place!

Rebalancing AVL

Rebalancing AVL

Rebalancing AVL

Insertion completed

Current AVL tree:

4 6 9

5

1 3

Entered element:

5

Searching for '5' in subtree with root '4'

Current:4

Looking right

Current:6

Looking left

Current:5

Found!

Search completed

Element already exists!

Current AVL tree:

4 6 9

5

1 3

2.

Input:

Building AVL tree of entered sequence

Built tree:

Entered element:

1

Adding element

Current AVL tree:

1

Entered element:

2

Adding element

Current AVL tree:

1 2

Entered element:

3

Adding element

Current AVL tree:

2 3

1

3.

Input:

4 5 6

Building AVL tree of entered sequence

Built tree:

5 6

4

Entered element:

1

Searching for '1' in subtree with root '5'

Current:5

Looking left

Current:4

Looking left

Not found!

Search completed

Adding element

Inserting element '1' in subtree with root '5'

Current:5

Going left

Current:4

Going left

Insertion place!

Rebalancing AVL

Rebalancing AVL

Insertion completed

Current AVL tree:

5 6

4

1

Entered element:

2

Searching for '2' in subtree with root '5'

Current:5

Looking left

Current:4

Looking left

Current:1

Looking right

Not found!

Search completed

Adding element

Inserting element '2' in subtree with root '5'

Current:5

Going left

Current:4

Going left

Current:1

Going right

Insertion place!

Rebalancing AVL

Rebalancing AVL

Rebalancing AVL

Insertion completed

Current AVL tree:

5 6

2 4

1

Entered element:

3

Searching for '3' in subtree with root '5'

Current:5

Looking left

Current:2

Looking right

Current:4

Looking left

Not found!

Search completed

Adding element

Inserting element '3' in subtree with root '5'

Current:5

Going left

Current:2

Going right

Current:4

Going left

Insertion place!

Rebalancing AVL

Rebalancing AVL

Rebalancing AVL

Insertion completed

Current AVL tree:

4 5 6

2 3

1

Entered element:

4

Searching for '4' in subtree with root '4'

Current:4

Found!

Search completed

Element already exists!

Current AVL tree:

4 5 6

2 3

1

Выводы.

В результате работы была написана полностью рабочая программа решающая поставленную задачу при использовании изученных теоретических материалов. Реализован рабочий шаблонный класс для хранения и обработки АВЛ-Деревьев. Программа было протестирована, результаты тестов удовлетворительны.

Приложение(листинг программы)

main.cpp

#include <iostream>

#include <fstream>

#include <cstdlib>

bool DEBUG = false;

#define DEFAULT_IFILE_NAME "in"

#define DEFAULT_OFILE_NAME "out"

using namespace std;

istream *inFile = NULL;

bool readFromFile = false;

ostream *outFile = NULL;

bool printToFile = false;

bool repeat = false;

bool awto = false;

int awtoLim = 0;

bool debug = false;

void setIFile(istream* istr){

//cin.rdbuf((*istr).rdbuf());

inFile=istr;

}

void setOFile(ostream* ostr){

//cout.rdbuf((*ostr).rdbuf());

outFile=ostr;

}

int _max(int a, int b){return a>b?a:b;}

int parseArgs(int argc, char** argv, string &iFileName, string &oFileName); //Parses arguments. Returns 1 if program is to be closed

void printStr(string str);

void printInt(int str);

void printChar(char str);

#include "AVLTreeClass.h"

typedef unsigned int unInt;

void _outAVL(AVL<char> b);//Formatter str tree output

void displayAVL(AVL<char> b, int n=1);//Fancy tree graph

void help(){

cout<<"-h\t\thelp\n";

cout<<"-A\t\tAuto reading input line by line\n";

cout<<"-r\t\tchose to repeat input after compliton. Incompatable with \"-i\"!\n";

cout<<"-i [file]\t input from file (\""<<DEFAULT_IFILE_NAME<<"\" by default)\n";

cout<<"-o [file]\t output to file (\""<<DEFAULT_OFILE_NAME<<"\" by default)\n";

cout<<"-d\t\toutput inter-processing data\n";

}

#define INS ( readFromFile?(*inFile):cin )

int main(int argc, char** argv) {

///Variables

string iFileName;

string oFileName;

AVL<char> b;

///WIN setup

#ifdef _WIN32

SetConsoleCP(1251);

SetConsoleOutputCP(1251);

#endif

///Parce argsuments

if(parseArgs(argc,argv,iFileName,oFileName))exit(0);

DEBUG=debug;

ofstream oFile;

ifstream iFile;

///File management

if (printToFile){

oFile.open(oFileName,ios::out);

if(!oFile){

printStr("Cannot open file: "+oFileName+"\n");