Arbore AVL: rotații, inserare, ștergere cu C++ Exemplu
Sarah Chen
Ce sunt arborii AVL?
arbori AVL sunt arbori binari de căutare în care diferența dintre înălțimea subarborelui din stânga și din dreapta este fie -1, 0 sau +1.
Arborii AVL mai sunt numiți și arbore de căutare binar cu auto-echilibrare. Acești arbori ajută la menținerea timpului de căutare logaritmic. Este numit după inventatorii săi (AVL) Adelson, Velsky și Landis.
Cum funcționează arborele AVL?
Pentru a înțelege mai bine necesitatea arborilor AVL, să ne uităm la câteva dezavantaje ale arborilor de căutare binari simpli.
Luați în considerare următoarele chei introduse în ordinea dată în arborele de căutare binar.
Înălțimea copacului crește liniar în dimensiune atunci când introducem cheile în ordinea crescătoare a valorii lor. Astfel, operația de căutare, în cel mai rău caz, ia O(n).
Este nevoie de timp liniar pentru a căuta un element; prin urmare, nu are rost să folosești Arborele de căutare binar structura. Pe de altă parte, dacă înălțimea copacului este echilibrată, obținem un timp de căutare mai bun.
Să ne uităm acum la aceleași chei, dar introduse într-o ordine diferită.
Aici, cheile sunt aceleași, dar din moment ce sunt introduse într-o ordine diferită, ele ocupă poziții diferite, iar înălțimea copacului rămâne echilibrată. Prin urmare, căutarea nu va dura mai mult de O(log n) pentru orice element al arborelui. Acum este evident că dacă inserarea se face corect, înălțimea copacului poate fi menținută echilibrată.
În arborii AVL, ținem o verificare a înălțimii arborelui în timpul operației de inserare. Se fac modificări pentru a menține înălțimea echilibrată fără a încălca proprietățile fundamentale ale Arborelui de căutare binar.
Factorul de echilibru în arbori AVL
Factorul de echilibru (BF) este un atribut fundamental al fiecărui nod din arborii AVL care ajută la monitorizarea înălțimii arborelui.
Proprietățile factorului de echilibru
- Factorul de echilibru este cunoscut ca diferența dintre înălțimea subarborelui din stânga și a subarborelui din dreapta.
- Factorul de echilibru (nod) = înălțime (nod-> stânga) – înălțime (nod-> dreapta)
- Valorile permise ale BF sunt –1, 0 și +1.
- Valoarea –1 indică faptul că sub-arborele din dreapta conține unul suplimentar, adică arborele este foarte greu.
- Valoarea +1 indică faptul că sub-arborele din stânga conține un plus, adică arborele este lăsat greu.
- Valoarea 0 arată că arborele include noduri egale pe fiecare parte, adică arborele este perfect echilibrat.
Rotații AVL
Pentru ca arborele AVL să se echilibreze în sine, la inserarea sau ștergerea unui nod din arbore se efectuează rotații.
Efectuăm următoarea rotație LL, rotație RR, rotație LR și rotație RL.
- Stânga – Rotire stânga
- Rotație dreapta – dreapta
- Rotație dreapta – stânga
- Rotire stânga – dreapta
Stânga – Rotire stânga
Această rotație este efectuată atunci când un nou nod este inserat la copilul din stânga subarborele din stânga.
Se efectuează o singură rotație la dreapta. Acest tip de rotație este identificat atunci când un nod are un factor echilibrat ca +2, iar copilul său din stânga are un factor de echilibru ca +1.
Rotație dreapta – dreapta
Această rotație este efectuată atunci când un nou nod este inserat în copilul din dreapta al subarborelui din dreapta.
Se efectuează o singură rotație la stânga. Acest tip de rotație este identificat atunci când un nod are un factor echilibrat ca -2, iar copilul său drept are un factor de echilibru ca -1.
Rotație dreapta – stânga
Această rotație este efectuată atunci când un nou nod este inserat în copilul din dreapta al subarborelui din stânga.
Această rotație este efectuată atunci când un nod are un factor de echilibru ca –2, iar copilul său din dreapta are un factor de echilibru ca +1.
Rotire stânga – dreapta
Această rotație este efectuată atunci când un nou nod este inserat la copilul din stânga subarborelui din dreapta.
Această rotație este efectuată atunci când un nod are un factor de echilibru ca +2, iar copilul său din stânga are un factor de echilibru ca -1.
Inserarea în arbori AVL
Operația de inserare este aproape aceeași ca în arborii de căutare binari simpli. După fiecare inserție, echilibrăm înălțimea copacului. Operația de inserare ia O(log n) cea mai proastă complexitate de timp.
Etapa 1: Inserați nodul în arborele AVL utilizând același algoritm de inserare al BST. În exemplul de mai sus, introduceți 160.
Etapa 2: Odată ce nodul este adăugat, factorul de echilibru al fiecărui nod este actualizat. După ce 160 este inserat, factorul de echilibru al fiecărui nod este actualizat.
Etapa 3: Acum verificați dacă vreun nod încalcă intervalul factorului de echilibru dacă factorul de echilibru este încălcat, apoi efectuați rotații folosind cazul de mai jos. În exemplul de mai sus, factorul de echilibru de 350 este încălcat și cazul 1 devine aplicabil acolo, efectuăm rotația LL și arborele este echilibrat din nou.
- Dacă BF(nod) = +2 și BF(nod -> stânga-copil) = +1, efectuați rotația LL.
- Dacă BF(nod) = -2 și BF(nod -> dreapta-copil) = 1, efectuați rotația RR.
- Dacă BF(nod) = -2 și BF(nod -> dreapta-copil) = +1, efectuați rotația RL.
- Dacă BF(nod) = +2 și BF(nod -> stânga-copil) = -1, efectuați rotația LR.
Ștergerea în arbori AVL
Ștergerea este, de asemenea, foarte simplă. Ștergem folosind aceeași logică ca în arborii de căutare binari simpli. După ștergere, restructuram arborele, dacă este necesar, pentru a-și menține înălțimea echilibrată.
Pasul 1: Găsiți elementul din arbore.
Pasul 2: Ștergeți nodul, conform ștergerii BST.
Pasul 3: Sunt posibile două cazuri: -
Caz 1: Ștergerea din subarborele din dreapta.
- 1A. Dacă BF(nod) = +2 și BF(nod -> stânga-copil) = +1, efectuați rotația LL.
- 1B. Dacă BF(nod) = +2 și BF(nod -> stânga-copil) = -1, efectuați rotația LR.
- 1C. Dacă BF(nod) = +2 și BF(nod -> stânga-copil) = 0, efectuați rotația LL.
Cauza 2: Se șterge din subarborele din stânga.
- 2A. Dacă BF(nod) = -2 și BF(nod -> dreapta-copil) = -1, efectuați rotația RR.
- 2B. Dacă BF(nod) = -2 și BF(nod -> dreapta-copil) = +1, efectuați rotația RL.
- 2C. Dacă BF(nod) = -2 și BF(nod -> dreapta-copil) = 0, efectuați rotația RR.
C++ Exemplu de arbori AVL
Mai jos este C++ care implementează arbori 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);
}
Exemplu de rulare a codului de mai sus:
- Copiați codul de mai sus și inserați în „avl.cpp”.
- Compilați codul:
g++ avl.cpp -o run
- Rulați codul.
./run
Avantajele arborilor AVL
- Înălțimea arborelui AVL este întotdeauna echilibrată. Înălțimea nu crește niciodată dincolo de log N, unde N este numărul total de noduri din arbore.
- Oferă o complexitate mai bună a timpului de căutare în comparație cu arborii simpli de căutare binară.
- Arborii AVL au capacități de auto-echilibrare.
Rezumat
- Arborii AVL sunt arbori de căutare binari cu auto-echilibrare.
- Factorul de echilibru este atributul fundamental al arborilor AVL
- Factorul de echilibru al unui nod este definit ca diferența dintre înălțimea subarborelui din stânga și din dreapta acelui nod.
- Valorile valide ale factorului de echilibru sunt -1, 0 și +1.
- Operația de inserare și ștergere necesită efectuarea de rotații după încălcarea factorului de echilibru.
- Complexitatea de timp a operațiunii de inserare, ștergere și căutare este O(log N).
- Arborii AVL urmează toate proprietățile Arborilor de căutare binare.
- Subarborele din stânga are noduri mai mici decât nodul rădăcină. Subarborele din dreapta are noduri care sunt întotdeauna mai mari decât nodul rădăcină.
- Arborii AVL sunt utilizați acolo unde operațiunile de căutare sunt mai frecvente în comparație cu operațiunile de inserare și ștergere.