AVL дървета: ротации, вмъкване, изтриване с C++ Пример
Сара Чен
Какво представляват AVL дърветата?
AVL дървета са двоични дървета за търсене, в които разликата между височината на лявото и дясното поддърво е -1, 0 или +1.
AVL дърветата се наричат още самобалансиращо се двоично дърво за търсене. Тези дървета помагат да се поддържа логаритмичното време за търсене. Той е кръстен на своите изобретатели (AVL) Аделсън, Велски и Ландис.
Как работи AVL Tree?
За да разберем по-добре необходимостта от AVL дървета, нека разгледаме някои недостатъци на простите бинарни дървета за търсене.
Помислете за следните ключове, вмъкнати в дадения ред в двоичното дърво за търсене.
Височината на дървото нараства линейно по размер, когато вмъкваме ключовете в нарастващ ред на тяхната стойност. По този начин операцията за търсене в най-лошия случай отнема O(n).
Отнема линейно време за търсене на елемент; следователно няма полза от използването на Двоично дърво за търсене структура. От друга страна, ако височината на дървото е балансирана, получаваме по-добро време за търсене.
Нека сега разгледаме същите ключове, но вмъкнати в различен ред.
Тук ключовете са еднакви, но тъй като са поставени в различен ред, те заемат различни позиции и височината на дървото остава балансирана. Следователно търсенето няма да отнеме повече от O(log n) за всеки елемент от дървото. Сега е очевидно, че ако вмъкването е направено правилно, височината на дървото може да се поддържа балансирана.
В AVL дървета, ние поддържаме проверка на височината на дървото по време на операцията по вмъкване. Правят се модификации, за да се поддържа балансираната височина, без да се нарушават основните свойства на дървото за двоично търсене.
Фактор на баланс в AVL дървета
Коефициентът на баланс (BF) е основен атрибут на всеки възел в AVL дървета, който помага да се наблюдава височината на дървото.
Свойства на фактора на баланса
- Коефициентът на баланс е известен като разликата между височината на лявото поддърво и дясното поддърво.
- Коефициент на баланс (възел) = височина (възел->ляво) – височина (възел->дясно)
- Позволените стойности на BF са –1, 0 и +1.
- Стойността –1 показва, че дясното поддърво съдържа едно допълнително, т.е. дървото е дясно тежко.
- Стойността +1 показва, че лявото поддърво съдържа едно допълнително, т.е. дървото е ляво тежко.
- Стойността 0 показва, че дървото включва равни възли от всяка страна, т.е. дървото е перфектно балансирано.
AVL ротации
За да се балансира самото AVL дърво, при вмъкване или изтриване на възел от дървото се извършват ротации.
Извършваме следната LL ротация, RR ротация, LR ротация и RL ротация.
- Ляво – ляво завъртане
- Надясно – завъртане надясно
- Завъртане надясно – наляво
- Завъртане наляво – надясно
Ляво – ляво завъртане
Това завъртане се извършва, когато се вмъкне нов възел в лявото дете на лявото поддърво.
Извършва се едно завъртане надясно. Този тип ротация се идентифицира, когато възел има балансиран коефициент като +2, а лявото му дете има балансиран коефициент като +1.
Надясно – завъртане надясно
Това завъртане се извършва, когато се вмъкне нов възел в дясното дете на дясното поддърво.
Извършва се едно завъртане наляво. Този тип ротация се идентифицира, когато възел има балансиран коефициент като -2, а дясното дете има балансиран коефициент като -1.
Завъртане надясно – наляво
Това завъртане се извършва, когато се вмъкне нов възел в дясното дете на лявото поддърво.
Тази ротация се извършва, когато възел има коефициент на баланс като –2, а неговото дясно дете има коефициент на баланс като +1.
Завъртане наляво – надясно
Това завъртане се извършва, когато се вмъкне нов възел в лявото дете на дясното поддърво.
Това завъртане се извършва, когато възел има коефициент на баланс като +2, а лявото дете има коефициент на баланс като -1.
Вмъкване в AVL дървета
Операцията за вмъкване е почти същата като при обикновените двоични дървета за търсене. След всяко вмъкване балансираме височината на дървото. Операцията за вмъкване отнема O(log n) най-лошата времева сложност.
Стъпка : Вмъкнете възела в AVL дървото, като използвате същия алгоритъм за вмъкване на BST. В горния пример въведете 160.
Стъпка : След като възелът бъде добавен, коефициентът на баланс на всеки възел се актуализира. След вмъкване на 160 коефициентът на баланс на всеки възел се актуализира.
Стъпка : Сега проверете дали някой възел нарушава обхвата на фактора на баланс, ако факторът на баланс е нарушен, след това извършете ротации, като използвате случая по-долу. В горния пример факторът на баланс от 350 е нарушен и случай 1 става приложим там, извършваме LL ротация и дървото отново се балансира.
- Ако BF(възел) = +2 и BF(възел -> ляво-дете) = +1, извършете LL ротация.
- Ако BF(възел) = -2 и BF(възел -> дясно дете) = 1, извършете RR ротация.
- Ако BF(възел) = -2 и BF(възел -> дясно дете) = +1, извършете RL ротация.
- Ако BF(възел) = +2 и BF(възел -> ляво-дете) = -1, извършете LR ротация.
Изтриване в AVL дървета
Изтриването също е много ясно. Ние изтриваме, използвайки същата логика, както при простите двоични дървета за търсене. След изтриването ние преструктурираме дървото, ако е необходимо, за да запазим балансираната му височина.
Стъпка 1: Намерете елемента в дървото.
Стъпка 2: Изтрийте възела, съгласно BST Изтриване.
Стъпка 3: Възможни са два случая: -
Дело 1: Изтриване от дясното поддърво.
- 1А. Ако BF(възел) = +2 и BF(възел -> ляво-дете) = +1, извършете LL ротация.
- 1Б. Ако BF(възел) = +2 и BF(възел -> ляво-дете) = -1, извършете LR ротация.
- 1C. Ако BF(възел) = +2 и BF(възел -> ляво-дете) = 0, извършете LL ротация.
Дело 2: Изтриване от ляво поддърво.
- 2А. Ако BF(възел) = -2 и BF(възел -> дясно дете) = -1, извършете RR ротация.
- 2B. Ако BF(възел) = -2 и BF(възел -> дясно дете) = +1, извършете RL ротация.
- 2C. Ако BF(възел) = -2 и BF(възел -> дясно дете) = 0, извършете RR ротация.
C++ Пример за AVL дървета
По-долу е C++ който имплементира AVL дървета:
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct node {
struct node *left;
int data;
int height;
struct node *right;
};
class AVL
{
private:
public:
struct node * root;
AVL(){
this->root = NULL;
}
int calheight(struct node *p){
if(p->left && p->right){
if (p->left->height < p->right->height)
return p->right->height + 1;
else return p->left->height + 1;
}
else if(p->left && p->right == NULL){
return p->left->height + 1;
}
else if(p->left ==NULL && p->right){
return p->right->height + 1;
}
return 0;
}
int bf(struct node *n){
if(n->left && n->right){
return n->left->height - n->right->height;
}
else if(n->left && n->right == NULL){
return n->left->height;
}
else if(n->left== NULL && n->right ){
return -n->right->height;
}
}
struct node * llrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->left;
p->left = tp->right;
tp->right = p;
return tp;
}
struct node * rrrotation(struct node *n){
struct node *p;
struct node *tp;
p = n;
tp = p->right;
p->right = tp->left;
tp->left = p;
return tp;
}
struct node * rlrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->right;
tp2 =p->right->left;
p -> right = tp2->left;
tp ->left = tp2->right;
tp2 ->left = p;
tp2->right = tp;
return tp2;
}
struct node * lrrotation(struct node *n){
struct node *p;
struct node *tp;
struct node *tp2;
p = n;
tp = p->left;
tp2 =p->left->right;
p -> left = tp2->right;
tp ->right = tp2->left;
tp2 ->right = p;
tp2->left = tp;
return tp2;
}
struct node* insert(struct node *r,int data){
if(r==NULL){
struct node *n;
n = new struct node;
n->data = data;
r = n;
r->left = r->right = NULL;
r->height = 1;
return r;
}
else{
if(data < r->data)
r->left = insert(r->left,data);
else
r->right = insert(r->right,data);
}
r->height = calheight(r);
if(bf(r)==2 && bf(r->left)==1){
r = llrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==-1){
r = rrrotation(r);
}
else if(bf(r)==-2 && bf(r->right)==1){
r = rlrotation(r);
}
else if(bf(r)==2 && bf(r->left)==-1){
r = lrrotation(r);
}
return r;
}
void levelorder_newline(){
if (this->root == NULL){
cout<<"\n"<<"Empty tree"<<"\n";
return;
}
levelorder_newline(this->root);
}
void levelorder_newline(struct node *v){
queue <struct node *> q;
struct node *cur;
q.push(v);
q.push(NULL);
while(!q.empty()){
cur = q.front();
q.pop();
if(cur == NULL && q.size()!=0){
cout<<"\n";
q.push(NULL);
continue;
}
if(cur!=NULL){
cout<<" "<<cur->data;
if (cur->left!=NULL){
q.push(cur->left);
}
if (cur->right!=NULL){
q.push(cur->right);
}
}
}
}
struct node * deleteNode(struct node *p,int data){
if(p->left == NULL && p->right == NULL){
if(p==this->root)
this->root = NULL;
delete p;
return NULL;
}
struct node *t;
struct node *q;
if(p->data < data){
p->right = deleteNode(p->right,data);
}
else if(p->data > data){
p->left = deleteNode(p->left,data);
}
else{
if(p->left != NULL){
q = inpre(p->left);
p->data = q->data;
p->left=deleteNode(p->left,q->data);
}
else{
q = insuc(p->right);
p->data = q->data;
p->right = deleteNode(p->right,q->data);
}
}
if(bf(p)==2 && bf(p->left)==1){ p = llrotation(p); }
else if(bf(p)==2 && bf(p->left)==-1){ p = lrrotation(p); }
else if(bf(p)==2 && bf(p->left)==0){ p = llrotation(p); }
else if(bf(p)==-2 && bf(p->right)==-1){ p = rrrotation(p); }
else if(bf(p)==-2 && bf(p->right)==1){ p = rlrotation(p); }
else if(bf(p)==-2 && bf(p->right)==0){ p = llrotation(p); }
return p;
}
struct node* inpre(struct node* p){
while(p->right!=NULL)
p = p->right;
return p;
}
struct node* insuc(struct node* p){
while(p->left!=NULL)
p = p->left;
return p;
}
~AVL(){
}
};
int main(){
AVL b;
int c,x;
do{
cout<<"\n1.Display levelorder on newline";
cout<<"\n2.Insert";
cout<<"\n3.Delete\n";
cout<<"\n0.Exit\n";
cout<<"\nChoice: ";
cin>>c;
switch (c)
{
case 1:
b.levelorder_newline();
// to print the tree in level order
break;
case 2:
cout<<"\nEnter no. ";
cin>>x;
b.root = b.insert(b.root,x);
break;
case 3:
cout<<"\nWhat to delete? ";
cin>>x;
b.root = b.deleteNode(b.root,x);
break;
case 0:
break;
}
} while(c!=0);
}
Работен пример на горния код:
- Копирайте горния код и го поставете в „avl.cpp“.
- Компилирайте кода:
g++ avl.cpp -o run
- Изпълнете кода.
./run
Предимства на AVL дървета
- Височината на AVL дървото винаги е балансирана. Височината никога не надвишава log N, където N е общият брой възли в дървото.
- Той осигурява по-добра времева сложност за търсене в сравнение с обикновените двоични дървета за търсене.
- AVL дърветата имат способности за самобалансиране.
Oбобщение
- AVL дърветата са самобалансиращи се двоични дървета за търсене.
- Факторът на баланс е основният атрибут на AVL дърветата
- Коефициентът на баланс на възел се определя като разликата между височината на лявото и дясното поддърво на този възел.
- Валидните стойности на баланс фактора са -1, 0 и +1.
- Операциите за вмъкване и изтриване изискват завъртания да се извършват след нарушаване на балансиращия фактор.
- Времевата сложност на операциите по вмъкване, изтриване и търсене е O(log N).
- AVL дърветата следват всички свойства на двоичните дървета за търсене.
- Лявото поддърво има възли, които са по-малки от основния възел. Дясното поддърво има възли, които винаги са по-големи от основния възел.
- AVL дървета се използват там, където операцията за търсене е по-честа в сравнение с операциите за вмъкване и изтриване.
