Двоичные деревья поиска
Выполнил студент группы ПМИб-2301-01-00 ________________/ Д. А. Смирнов /
Проверил преподаватель кафедры ФИиПМ ________________/ Т.Г. Прозорова /
Киров 2017
Цель работы
Изучить особенности работы с динамической структурой данных – двоичным деревом поиска.
Задание на лабораторную работу
Написать программу, которая должна выполнять следующие функции:
1. хранение данных в виде двоичного дерева поиска;
2. добавление элемента;
3. удаление элемента;
4. вывод всех элементов дерева;
5. поиск элементов.
Программа должна обеспечивать диалог с пользователем с помощью меню и контроль ошибокпри вводе данных пользователем.
Описание алгоритмов работы программы
Добавление элемента в дерево осуществляется следующим образом.
Если дерево пусто, то есть если указатель, указывающий на корневой элемент дерева, имеет значение NULL, то под новый элемент выделяется память, и указателю, указывающему на корневой элемент дерева, присваивается значение указателя, указывающего на участок памяти, выделенный под новый элемент. Метод добавления элемента завершается.
Иначе осуществляется спуск вниз по дереву от корневого элемента. Назовём указатель, указывающий на текущий элемент, currentnode. Изначальноcurrentnodeуказывает на корневой элемент дерева. Далее, пока следующий элемент, к которому предстоит перейти, существует (то есть указатель на соответствующее поддерево элемента, на который указывает currentnode, не равен NULL), осуществляется спуск вниз. Если ключ добавляемого элемента больше ключа элемента, на который указывает currentnode, то спуск идёт в правое поддерево, если меньше – в левое поддерево. Если же ключ добавляемого элемента равен ключу элемента, на который указывает currentnode, то добавлять элемент не надо, так как элемент с таким ключом уже есть в дереве – метод добавления нового элемента завершается.
После спуска вниз в дерево добавляется элемент – в качестве правого поддерева элемента, на который указывает currentnode, если ключ добавляемого элемента больше ключа элемента, на который указывает currentnode, и в качестве левого поддерева элемента, на который указывает currentnode, если ключ добавляемого элемента меньше ключа элемента, на который указывает currentnode.
Далее осуществляется балансировка дерева - подъём вверх по дереву и определённое вращение каждого узла в зависимости от высоты левого и правого поддеревьев.
Типы вращений
Малое левое вращение. Используется, когда высота поддерева bбольше высоты поддерева Lна два, а высота поддерева R не меньше высоты поддерева C.
Большое левое вращение. Используется, когда высота поддерева b больше высоты поддерева Lна два, а высота поддерева cбольше высоты поддерева R.
Малое правое вращение. Используется, когда высота поддерева bбольше высоты поддерева Rна два, а высота поддерева L не меньше высоты поддерева C.
Большое правое вращение. Используется, когда высота поддерева b больше высоты поддерева Rна два, а высота поддерева cбольше высоты поддерева L.
Поиск элемента с ключом keyосуществляется следующим образом.
Указателю currentnodeприсваивается адрес корневого элемента дерева. И пока указатель currentnodeимеет ненулевое значение, то есть пока указывает на существующий элемент, осуществляется спуск – если ключ key больше ключа элемента, на который указывает currentnode, то в правое поддерево, если меньше – в левое. Если же ключ элемента, на который указывает currentnode, равен ключу key, то это означает, что необходимый элемент найден, метод поиска элемента завершается.
Если же было выполнено условие выхода из цикла, то элемент не был найден в дереве.
Алгоритм удаления элемента дерева рекурсивный.
Для удаления элемента дерева, во-первых, осуществляется поиск удаляемого элемента. Если элемент не был найден, то метод удаления элемента завершается. Если элемент был найден, то если удаляемый элемент являлся листом, то освобождается память, занимаемая этим элементом, и указатель родителя (в случае, если он есть, то есть если удаляемый элемент – не корень) на это поддерево становится равным NULL. Далее осуществляется балансировка дерева - подъём от удалённого элемента вверх по дереву и вращение каждого узла в зависимости от высоты левого и правого поддеревьев.
Если же удаляемый элемент не является листом, то осуществляется замена удаляемого элемента и наибольшего его потомка. Если глубина левого поддерева удаляемого элемента больше глубины правого его поддерева, то замена происходит с наибольшим потомком левого поддерева, иначе – с наибольшим потомком правого поддерева.
Листинг
Файл.h, содержащий реализацию АВЛ-дерева
#pragmaonce
template<classValueT>
structResult
{
boolisFind;
ValueT result;
Result()
{
}
Result(constboolisFind, constValueTresult)
{
this->isFind = isFind;
this->result = result;
}
};
template<typenameKeyT, classValueT>
classNode
{
public:
Node<KeyT, ValueT>* LeftTree;
Node<KeyT, ValueT>* RightTree;
Node<KeyT, ValueT>* Ancestor;
KeyT Key;
ValueT Value;
int Depth;
Node(KeyTkey, ValueTvalue)
{
Key = key;
Value = value;
Depth = 1;
LeftTree = nullptr;
RightTree = nullptr;
Ancestor = nullptr;
}
};
template<typenameKeyT, classValueT>
classAVLtree
{
private:
Node<KeyT, ValueT>* Root;
public:
AVLtree()
{
Root = nullptr;
}
~AVLtree()
{
while (Root!= nullptr) { RemoveNode(Root); }
}
// Добавляет узел со значением value и с ключом key
void Add(constKeyTkey, constValueTvalue)
{
if (Root == nullptr)
{
Root = newNode<KeyT, ValueT>(key, value);
return;
}
Node<KeyT, ValueT>* currentNode = Root;
while (true)
{
// Определение того, куда двигаться:
Node<KeyT, ValueT>* nextNode;
if (key>currentNode->Key) { nextNode = currentNode->RightTree; }
elseif (key<currentNode->Key) { nextNode = currentNode->LeftTree; }
else { return; }
if (nextNode == nullptr) { break; }
else { currentNode = nextNode; }
}
Node<KeyT, ValueT>* newNode = newNode<KeyT, ValueT>(key, value);
newNode->Ancestor = currentNode;
if (key>currentNode->Key) { currentNode->RightTree = newNode; }
else { currentNode->LeftTree = newNode; }
// Подъёмвверхдокорняибалансировкаузлов:
while (currentNode!= nullptr)
{
FindDepth(currentNode);
Balancing(currentNode);
currentNode = currentNode->Ancestor;
}
}
// Удаляет узел, ключ которого равен key
void Remove(constKeyTkey)
{
Node<KeyT, ValueT>* removingNode = FindNode(key);
if (removingNode!= nullptr)
{
RemoveNode(removingNode);
}
}
// Возвращает значение узла, ключ которого равен key
Result<ValueT>Find(constKeyTkey)
{
Node<KeyT, ValueT>* node = FindNode(key);
Result<ValueT> result;
if (node!= nullptr) { result = Result<ValueT>(true, node->Value); }
else { result = Result<ValueT>(false, NULL); }
returnresult;
}
// Обход дерева в глубину
void DFS(void(*ptFunc)(Node<KeyT, ValueT>))
{
DFSRecursive(ptFunc, Root);
}
// Возвращаетвысотудерева
int Height()
{
return Root->Depth;
}
private:
voidDFSRecursive(void(*ptFunc)(Node<KeyT, ValueT>), Node<KeyT, ValueT>* node)
{
if (node!= nullptr)
{
DFSRecursive(ptFunc, node->LeftTree);
ptFunc(*node);
DFSRecursive(ptFunc, node->RightTree);
}
}
voidRemoveNode(Node<KeyT, ValueT>* removingNode)
{
int left = 0; int right = 0;
if (removingNode->LeftTree!= nullptr) { left = removingNode->LeftTree->Depth; }
if (removingNode->RightTree!= nullptr) { right = removingNode->RightTree->Depth; }
if (left == 0 &&right == 0)
{
// В случае, если удаляемый элемент - лист:
if (removingNode!= Root)
{
if (removingNode->Ancestor->LeftTree == removingNode) { removingNode->Ancestor->LeftTree = nullptr; }
else { removingNode->Ancestor->RightTree = nullptr; }
}
else { Root = nullptr; }
Node<KeyT, ValueT>* currentNode = removingNode->Ancestor;
deleteremovingNode;
// Подъём вверх до корня и балансировка узлов:
while (currentNode!= nullptr)
{
FindDepth(currentNode);
Balancing(currentNode);
currentNode = currentNode->Ancestor;
}
}
else
{
Node<KeyT, ValueT>* currentNode;
if (left>right)
{
// Поиск в левом поддереве
currentNode = removingNode->LeftTree;
while (currentNode->RightTree!= nullptr) { currentNode = currentNode->RightTree; }
}
else
{
// Поисквправомподдереве
currentNode = removingNode->RightTree;
while (currentNode->LeftTree!= nullptr) { currentNode = currentNode->LeftTree; }
}
removingNode->Key = currentNode->Key;
removingNode->Value = currentNode->Value;
RemoveNode(currentNode);
}
}
Node<KeyT, ValueT>* FindNode(constKeyTkey)
{
Node<KeyT, ValueT>* currentNode = Root;
while (currentNode!= nullptr)
{
if (key>currentNode->Key) { currentNode = currentNode->RightTree; }
elseif (key<currentNode->Key) { currentNode = currentNode->LeftTree; }
else { returncurrentNode; }
}
returnnullptr;
}
int max(constinta, constintb)
{
if (a>b) { returna; }
else{ returnb; }
}
// Переопределение значения глубины поддерева с корнем node
voidFindDepth(Node<KeyT, ValueT>* node)
{
int left = 0; int right = 0;
if (node->LeftTree!= nullptr) { left = node->LeftTree->Depth; }
if (node->RightTree!= nullptr) { right = node->RightTree->Depth; }
node->Depth = max(left, right) + 1;
}
// При вращениях пересчитываются глубины только тех поддеревьев, которые непосредственно вращались
// Для всех элементов "выше" балансируемого элемента необходим также пересчёт глубины
// Малоелевоевращение
voidSmallLeftRotation(Node<KeyT, ValueT>* node)
{
Node<KeyT, ValueT> *a, *b;
Node<KeyT, ValueT> *L, *C, *R;
a = node;
b = a->RightTree;
L = a->LeftTree;
C = b->LeftTree;
R = b->RightTree;
if (node->Ancestor!= nullptr)
{
if (node->Ancestor->LeftTree == node) { node->Ancestor->LeftTree = b; }
else { node->Ancestor->RightTree = b; }
}
else { Root = b; }
b->Ancestor = node->Ancestor;
b->LeftTree = a;
b->RightTree = R;
a->Ancestor = b;
R->Ancestor = b;
a->LeftTree = L;
a->RightTree = C;
if (L!= nullptr) { L->Ancestor = a; }
if (C!= nullptr) { C->Ancestor = a; }
FindDepth(a);
FindDepth(b);
}
// Большоелевоевращение
voidLargeLeftRotation(Node<KeyT, ValueT>* node)
{
Node<KeyT, ValueT> *a, *b, *c;
Node<KeyT, ValueT> *L, *R, *M, *N;
a = node;
b = a->RightTree;
c = b->LeftTree;
L = a->LeftTree;
M = c->LeftTree;
N = c->RightTree;
R = b->RightTree;
if (node->Ancestor!= nullptr)
{
if (node->Ancestor->LeftTree == node) { node->Ancestor->LeftTree = c; }
else { node->Ancestor->RightTree = c; }
}
else { Root = c; }
c->Ancestor = node->Ancestor;
c->LeftTree = a;
c->RightTree = b;
a->Ancestor = c;
b->Ancestor = c;
a->LeftTree = L;
a->RightTree = M;
if (L!= nullptr) { L->Ancestor = a; }
if (M!= nullptr) { M->Ancestor = a; }
b->LeftTree = N;
b->RightTree = R;
if (N!= nullptr) { N->Ancestor = b; }
if (R!= nullptr) { R->Ancestor = b; }
FindDepth(a);
FindDepth(b);
FindDepth(c);
}
// Малоеправоевращение
voidSmallRightRotation(Node<KeyT, ValueT>* node)
{
Node<KeyT, ValueT> *a, *b;
Node<KeyT, ValueT> *L, *C, *R;
a = node;
b = a->LeftTree;
L = b->LeftTree;
C = b->RightTree;
R = a->RightTree;
if (node->Ancestor!= nullptr)
{
if (node->Ancestor->LeftTree == node) { node->Ancestor->LeftTree = b; }
else { node->Ancestor->RightTree = b; }
}
else { Root = b; }
b->Ancestor = node->Ancestor;
b->LeftTree = L;
b->RightTree = a;
L->Ancestor = b;
a->Ancestor = b;
a->LeftTree = C;
a->RightTree = R;
if (C!= nullptr) { C->Ancestor = a; }
if (R!= nullptr) { R->Ancestor = a; }
FindDepth(a);
FindDepth(b);
}
// Большое правое вращение
voidLargeRightRotation(Node<KeyT, ValueT>* node)
{
Node<KeyT, ValueT> *a, *b, *c;
Node<KeyT, ValueT> *L, *R, *M, *N;
a = node;
b = a->LeftTree;
c = b->RightTree;
L = b->LeftTree;
M = c->LeftTree;
N = c->RightTree;
R = a->RightTree;
if (node->Ancestor!= nullptr)
{
if (node->Ancestor->LeftTree == node) { node->Ancestor->LeftTree = c; }
else { node->Ancestor->RightTree = c; }
}
else { Root = c; }
c->Ancestor = node->Ancestor;
c->LeftTree = b;
c->RightTree = a;
b->Ancestor = c;
a->Ancestor = c;
b->LeftTree = L;
b->RightTree = M;
if (L!= nullptr) { L->Ancestor = b; }
if (M!= nullptr) { M->Ancestor = b; }
a->LeftTree = N;
a->RightTree = R;
if (N!= nullptr) { N->Ancestor = a; }
if (R!= nullptr) { R->Ancestor = a; }
FindDepth(a);
FindDepth(b);
FindDepth(c); }
// Типывращенийподдеревьев
enumRotationType { LEFT, RIGHT, LARGE, SMALL };
// БалансировкаузлаunbalancedNode
void Balancing(Node<KeyT, ValueT>* node)
{
int left = 0; int right = 0;
if (node->LeftTree!= nullptr) { left = node->LeftTree->Depth; }
if (node->RightTree!= nullptr) { right = node->RightTree->Depth; }
RotationType type1;
if (left - right >= 2) { type1 = RIGHT; }
elseif (right - left >= 2) { type1 = LEFT; }
else { return; }
int center = 0; int side = 0;
if (type1 == RIGHT)
{
if (node->LeftTree->LeftTree!= nullptr) { side = node->LeftTree->LeftTree->Depth; }
if (node->LeftTree->RightTree!= nullptr) { center = node->LeftTree->RightTree->Depth; }
}
else
{
if (node->RightTree->LeftTree!= nullptr) { center = node->RightTree->LeftTree->Depth; }
if (node->RightTree->RightTree!= nullptr) { side = node->RightTree->RightTree->Depth; }
}
RotationType type2;
if (center > side) { type2 = LARGE; }
else { type2 = SMALL; }
// Вращение
if (type1 == LEFT && type2 == SMALL) { SmallLeftRotation(node); }
elseif (type1 == RIGHT && type2 == SMALL) { SmallRightRotation(node); }
elseif (type1 == LEFT && type2 == LARGE) { LargeLeftRotation(node); }
elseif (type1 == RIGHT && type2 == LARGE) { LargeRightRotation(node); }
}
};
Файл.cpp, содержащий метод main
#include"stdafx.h"
#include"AVLtree.h"
#include"Menu.h"
#include<iostream>
usingnamespacestd;
AVLtree<int, int> avltree1 = AVLtree<int, int>();
voidfuncForDFS(constNode<int, int>node)
{
intnSpace;
if (node.Ancestor == nullptr) { nSpace = 0; }
else
{
intleftDepth;
if (node.Ancestor->LeftTree == nullptr) { leftDepth = 0; }
else { leftDepth = node.Ancestor->LeftTree->Depth; }
intrightDepth;
if (node.Ancestor->RightTree == nullptr) { rightDepth = 0; }
else { rightDepth = node.Ancestor->RightTree->Depth; }
if (leftDepth>rightDepth) { nSpace = leftDepth; }
else { nSpace = rightDepth; }
nSpace = avltree1.Height() - nSpace;
}
for (inti = 0; i<nSpace * 1; i++)
{
cout<<" ";
}
cout<<node.Value;
cout<<endl;
}
void add()
{
int key, value;
cout<<"Введите значение добавляемого элемента:"<<endl;
cin>> value;
if (!cin.fail())
{
cout<<"Введите значение ключа добавляемого элемента:"<<endl;
cin>> key;
}
if (cin.fail())
{
cout<<"Некорректныйввод."<<endl;
cin.clear();
cin.ignore(32767, '\n');
_getch();
}
else
{
avltree1.Add(key, value);
}
}
voidremove()
{
intkey;
cout<<"Введите значения ключа, по которому необходимо удалить элемент:"<<endl;
cin>> key;
if (cin.fail())
{
cout<<"Некорректныйввод."<<endl;
cin.clear();
cin.ignore(32767, '\n');
_getch();
}
else
{
avltree1.Remove(key);
}
}
void find()
{
intkey;
cout<<"Введите значения ключа, по которому необходимо найти элемент:"<<endl;
cin>> key;
if (cin.fail())
{
cout<<"Некорректныйввод."<<endl;
cin.clear();
cin.ignore(32767, '\n');
}
else
{
Result<int> result = avltree1.Find(key);
if (result.isFind) { cout<<"Значениеэлементасключом "<< key <<" равно "<<result.result<<"."<<endl; }
else { cout<<"Элементсключом "<< key <<" ненайден."; }
}
_getch();
}
voidwriteOnScreen()
{
avltree1.DFS(funcForDFS);
cout<<endl;
_getch();
}
int main()
{
setlocale(LC_ALL, "Russian");
Menu menu1 = Menu();
menu1.AddWindow(nullptr); // 0
menu1.AddWindow(add); // 1
menu1.AddWindow(remove); // 2
menu1.AddWindow(find); // 3
menu1.AddWindow(writeOnScreen); // 4
menu1.AddWindow(nullptr); // 5
menu1.AddJunction(0, 1, "Добавить элемент в дерево.");
menu1.AddJunction(0, 2, "Удалить элемент дерева.");
menu1.AddJunction(0, 3, "Найти элемент дерева.");
menu1.AddJunction(0, 4, "Вывести на экран все элементы дерева в соответствии с порядком обхода в глубину, начиная с корня.");
menu1.AddJunction(0, 5, "Закончить работу с деревом.");
menu1.AddJunction(1, 0, "");
menu1.AddJunction(2, 0, "");
menu1.AddJunction(3, 0, "");
menu1.AddJunction(4, 0, "");
menu1.Start();
}
Выводы
В ходе лабораторной была изучена структура данных АВЛ-дерево, сохраняющая балансировку при удалении и добавлении элементов. Сбалансированность дерева позволяет осуществлять поиск, удаление и добавление элементов за время O(log(n)), что является огромным плюсом перед линейными структурами данных.