AVL stabla: rotacije, umetanje, brisanje sa C++ Primjer
Sarah Chen
Što su AVL stabla?
AVL stabla su binarna stabla pretraživanja u kojima je razlika između visine lijevog i desnog podstabla ili -1, 0 ili +1.
AVL stabla se također nazivaju samobalansirajućim binarnim stablom pretraživanja. Ova stabla pomažu u održavanju logaritamskog vremena pretraživanja. Ime je dobio po svojim izumiteljima (AVL) Adelsonu, Velskyju i Landisu.
Kako radi AVL stablo?
Kako bismo bolje razumjeli potrebu za AVL stablima, pogledajmo neke nedostatke jednostavnih stabala binarnog pretraživanja.
Razmotrite sljedeće ključeve umetnute danim redoslijedom u stablo binarnog pretraživanja.
Visina stabla linearno raste kada umetnemo ključeve rastućim redoslijedom njihove vrijednosti. Dakle, operacija pretraživanja, u najgorem slučaju, traje O(n).
Za traženje elementa potrebno je linearno vrijeme; stoga nema koristi od korištenja Stablo binarnog pretraživanja struktura. S druge strane, ako je visina stabla uravnotežena, dobivamo bolje vrijeme traženja.
Pogledajmo sada iste ključeve, ali umetnute drugačijim redoslijedom.
Ovdje su ključevi isti, ali budući da su umetnuti drugačijim redoslijedom, zauzimaju različite položaje, a visina stabla ostaje uravnotežena. Stoga pretraživanje neće trajati više od O(log n) za bilo koji element stabla. Sada je očito da ako se umetanje pravilno izvede, visina stabla može biti uravnotežena.
U AVL stablima provjeravamo visinu stabla tijekom operacije umetanja. Izmjene su napravljene kako bi se održala uravnotežena visina bez narušavanja osnovnih svojstava stabla binarnog pretraživanja.
Faktor ravnoteže u AVL stablima
Faktor ravnoteže (BF) temeljni je atribut svakog čvora u AVL stablima koji pomaže u praćenju visine stabla.
Svojstva faktora ravnoteže
- Faktor ravnoteže poznat je kao razlika između visine lijevog podstabla i desnog podstabla.
- Faktor ravnoteže (čvor) = visina (čvor->lijevo) – visina (čvor->desno)
- Dopuštene vrijednosti BF su –1, 0 i +1.
- Vrijednost –1 označava da desno pod-stablo sadrži jedno dodatno, tj. da je stablo desno teško.
- Vrijednost +1 označava da lijevo podstablo sadrži jedno dodatno, tj. da je stablo lijevo teško.
- Vrijednost 0 pokazuje da stablo uključuje jednake čvorove sa svake strane, tj. da je stablo savršeno uravnoteženo.
AVL rotacije
Kako bi se AVL stablo samo uravnotežilo, prilikom umetanja ili brisanja čvora iz stabla, izvode se rotacije.
Izvodimo sljedeću LL rotaciju, RR rotaciju, LR rotaciju i RL rotaciju.
- Lijevo – Lijeva rotacija
- Desno – Desna rotacija
- Rotacija desno – lijevo
- Rotacija lijevo – desno
Lijevo – Lijeva rotacija
Ova rotacija se izvodi kada se novi čvor umetne u lijevo dijete lijevog podstabla.
Izvodi se jedna desna rotacija. Ova vrsta rotacije prepoznaje se kada čvor ima faktor ravnoteže +2, a njegov lijevi potomak ima faktor ravnoteže +1.
Desno – Desna rotacija
Ova rotacija se izvodi kada se novi čvor umetne u desno dijete desnog podstabla.
Izvodi se jedna rotacija ulijevo. Ova vrsta rotacije identificira se kada čvor ima faktor ravnoteže -2, a njegov desni potomak ima faktor ravnoteže -1.
Rotacija desno – lijevo
Ova rotacija se izvodi kada se novi čvor umetne u desno dijete lijevog podstabla.
Ova se rotacija izvodi kada čvor ima faktor ravnoteže kao –2, a njegov desni dijete ima faktor ravnoteže kao +1.
Rotacija lijevo – desno
Ova rotacija se izvodi kada se novi čvor umetne u lijevo dijete desnog podstabla.
Ova rotacija se izvodi kada čvor ima faktor ravnoteže kao +2, a njegov lijevi dijete ima faktor ravnoteže kao -1.
Umetanje u AVL stabla
Operacija umetanja gotovo je ista kao kod jednostavnih stabala binarnog pretraživanja. Nakon svakog umetanja balansiramo visinu stabla. Operacija umetanja traje O(log n) najgore vremenske složenosti.
Korak 1: Umetnite čvor u AVL stablo koristeći isti algoritam umetanja kao BST. U gornjem primjeru umetnite 160.
Korak 2: Nakon dodavanja čvora, ažurira se faktor ravnoteže svakog čvora. Nakon umetanja 160, faktor ravnoteže svakog čvora se ažurira.
Korak 3: Sada provjerite krši li bilo koji čvor raspon faktora ravnoteže ako je faktor ravnoteže narušen, zatim izvedite rotacije koristeći donji slučaj. U gornjem primjeru, faktor ravnoteže od 350 je narušen i tu postaje primjenjiv slučaj 1, izvodimo LL rotaciju i stablo je ponovno uravnoteženo.
- Ako je BF(čvor) = +2 i BF(čvor -> lijevo dijete) = +1, izvršite LL rotaciju.
- Ako je BF(čvor) = -2 i BF(čvor -> desno dijete) = 1, izvedite RR rotaciju.
- Ako je BF(čvor) = -2 i BF(čvor -> desno dijete) = +1, izvršite RL rotaciju.
- Ako je BF(čvor) = +2 i BF(čvor -> lijevo dijete) = -1, izvršite LR rotaciju.
Brisanje u AVL stablima
Brisanje je također vrlo jednostavno. Brišemo koristeći istu logiku kao u jednostavnim stablima binarnog pretraživanja. Nakon brisanja, restrukturiramo stablo, ako je potrebno, kako bismo zadržali njegovu uravnoteženu visinu.
Korak 1: Pronađite element u stablu.
Korak 2: Izbrišite čvor u skladu s BST brisanjem.
Korak 3: Moguća su dva slučaja: -
Slučaj 1: Brisanje iz desnog podstabla.
- 1A. Ako je BF(čvor) = +2 i BF(čvor -> lijevo dijete) = +1, izvršite LL rotaciju.
- 1B. Ako je BF(čvor) = +2 i BF(čvor -> lijevo dijete) = -1, izvršite LR rotaciju.
- 1C. Ako je BF(čvor) = +2 i BF(čvor -> lijevo dijete) = 0, izvedite LL rotaciju.
Slučaj 2: Brisanje iz lijevog podstabla.
- 2A. Ako je BF(čvor) = -2 i BF(čvor -> desno dijete) = -1, izvršite RR rotaciju.
- 2B. Ako je BF(čvor) = -2 i BF(čvor -> desno dijete) = +1, izvršite RL rotaciju.
- 2C. Ako je BF(čvor) = -2 i BF(čvor -> desno dijete) = 0, izvedite RR rotaciju.
C++ Primjer AVL stabala
Ispod je C++ koji implementira AVL stabla:
#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);
}
Izvršeni primjer gornjeg koda:
- Kopirajte gornji kod i zalijepite u “avl.cpp”.
- Sastavite kod:
g++ avl.cpp -o run
- Pokrenite kod.
./run
Prednosti AVL stabala
- Visina AVL stabla uvijek je uravnotežena. Visina nikada ne prelazi log N, gdje je N ukupan broj čvorova u stablu.
- Omogućuje bolju složenost vremena pretraživanja u usporedbi s jednostavnim stablima binarnog pretraživanja.
- AVL stabla imaju sposobnost samobalansiranja.
rezime
- AVL stabla su binarna stabla pretraživanja koja se sama balansiraju.
- Faktor ravnoteže temeljni je atribut AVL stabala
- Faktor ravnoteže čvora definiran je kao razlika između visine lijevog i desnog podstabla tog čvora.
- Važeće vrijednosti faktora ravnoteže su -1, 0 i +1.
- Operacije umetanja i brisanja zahtijevaju izvođenje rotacija nakon narušavanja faktora ravnoteže.
- Vremenska složenost operacije umetanja, brisanja i pretraživanja je O(log N).
- AVL stabla slijede sva svojstva stabala binarnog pretraživanja.
- Lijevo podstablo ima čvorove koji su manji od korijenskog čvora. Desno podstablo ima čvorove koji su uvijek veći od korijenskog čvora.
- AVL stabla se koriste tamo gdje je operacija pretraživanja češća u usporedbi s operacijama umetanja i brisanja.
