авл деревья поиска ответы на вопросы vkclub152685050
.pdfBigRightRotate(MainTree);
}
if (MainTree->Prev) MainTree = MainTree->Prev; else break;
}
Root = MainTree;
}
void AddTreeElem(Tree *&Root, Tree *NewElem)
{
Tree *MainTree = Root; if (!Root)
{
Root = new |
Tree; |
|
Root->elem |
= |
NewElem->elem; |
Root->height |
= 1; |
|
Root->Prev |
= |
NULL; |
Root->Left |
= |
NULL; |
Root->Right = NULL; |
||
MainTree = |
Root; |
|
}
else
{
while (true)
{
if (NewElem->elem < MainTree->elem)
{
if (MainTree->Left) MainTree = MainTree->Left; else
{
MainTree->Left = NewElem;
NewElem->Prev = MainTree; break;
}
}
else
{
if (MainTree->Right) MainTree = MainTree->Right; else
{
MainTree->Right = NewElem;
NewElem->Prev = MainTree; break;
}
}
}
BalanceTree(Root, MainTree);
}
}
vk.com/club152685050
vk.com/id446425943
Функция удаления элемента из дерева:
6
void DeleteTreeElem(Tree *&Root, Tree *&DeleteElem)
{
Tree *MainTree = Root;
Tree *TmpElem = NULL; Tree *OneMoreTmp = NULL; int counter = 0;
while (true)
{
if (MainTree)
{
if (DeleteElem->elem == MainTree->elem)
{
if (MainTree->Prev || GetHeight(MainTree) > 1)
{
OneMoreTmp = MainTree;
if (MainTree->Left || MainTree->Right)
{
if (MainTree->Right) MainTree = MainTree->Right; TmpElem = OneMoreTmp->Prev; while (MainTree->Left) MainTree = MainTree->Left; if (MainTree->Prev)
{
if (MainTree->Prev->Right == MainTree) MainTree->Prev->Right = NULL;
else
MainTree->Prev->Left = NULL;
}
if (TmpElem)
{
if (TmpElem->Right)
{
if (TmpElem->Right == OneMoreTmp) TmpElem->Right = MainTree;
else
TmpElem->Left = MainTree;
}
else
TmpElem->Left = MainTree;
}
if (MainTree->Prev != OneMoreTmp) TmpElem = MainTree->Prev;
else TmpElem = MainTree; MainTree->Prev = OneMoreTmp->Prev; if (OneMoreTmp->Right != MainTree)
{
MainTree->Right = OneMoreTmp->Right; if (MainTree->Right)
MainTree->Right->Prev = MainTree;
}
else
7
MainTree->Right = NULL;
if (OneMoreTmp->Left != MainTree)
{
MainTree->Left = OneMoreTmp->Left; if (MainTree->Left)
MainTree->Left->Prev = MainTree;
}
else
MainTree->Left = NULL; BalanceTree(Root, TmpElem);
}
else
{
TmpElem = MainTree->Prev; if (TmpElem)
{
if (TmpElem->Right)
{
if (TmpElem->Right == MainTree) TmpElem->Right = NULL;
else
TmpElem->Left = NULL;
}
else
TmpElem->Left = NULL;
}
BalanceTree(Root, TmpElem);
}
cout << "elem was deleted" << endl; ShowTree(counter, Root, 0);
cout << "Num of elements = " << counter<<endl; _getch();
return;
}
else
{
Root = NULL;
cout << "Tree is Empty Now" << endl; _getch();
return;
}
}
else if (DeleteElem->elem > MainTree->elem) MainTree = MainTree->Right;
else
MainTree = MainTree->Left;
}
else
{
cout << "No such elem in tree!" << endl; _getch();
return;
}
8
}
}
Таким образом, реализуется два первых пункта задания на лабораторную работу. Осталось реализовать функцию поиска в дереве и функцию, заданную вариантом задания.
Поиск в дереве осуществляется классическим способом. Единственным отличием здесь будет добавлением в функцию поиска операции подсчета количества вершин дерева, по которым проходим в процессе поиска, и вывода этого количества по окончанию поиска.
Задание по варианту реализуется с помощью указанного метода обхода. Обход можно реализовывать рекурсивным или нерекурсивным способом по выбору.
1.6 Контрольные вопросы
1)Что такое дерево? Что такое высота и степень дерева?
2)Назовите способы реализации бинарного дерева. Сравните их.
3)Какие способы обхода бинарного дерева существуют?
4)Что такое дерево поиска?
5)Какова временная сложность алгоритма поиска в дереве поиска?
6)Что такое идеально сбалансированное дерево?
7)Что такое дерево, сбалансированное по АВЛ?
8)Какие операции применяют для восстановления сбалансированности дерева?
9