AVL-träd: Rotationer, infogning, radering med C++ Exempelvis
Sarah Chen
Vad är AVL-träd?
AVL-träd är binära sökträd där skillnaden mellan höjden på det vänstra och högra underträdet är antingen -1, 0 eller +1.
AVL-träd kallas också för ett självbalanserande binärt sökträd. Dessa träd hjälper till att upprätthålla den logaritmiska söktiden. Den är uppkallad efter dess uppfinnare (AVL) Adelson, Velsky och Landis.
Hur fungerar AVL Tree?
För att bättre förstå behovet av AVL-träd, låt oss titta på några nackdelar med enkla binära sökträd.
Betrakta följande nycklar infogade i den givna ordningen i det binära sökträdet.
Höjden på trädet växer linjärt i storlek när vi sätter in nycklarna i stigande ordning efter deras värde. Sålunda tar sökoperationen i värsta fall O(n).
Det tar linjär tid att söka efter ett element; därför är det ingen användning att använda Binärt sökträd strukturera. Å andra sidan, om trädets höjd är balanserad får vi bättre söktid.
Låt oss nu titta på samma nycklar men infogade i en annan ordning.
Här är nycklarna desamma, men eftersom de sätts in i en annan ordning tar de olika positioner och trädets höjd förblir balanserad. Därför tar sökningen inte mer än O(log n) för något element i trädet. Det är nu uppenbart att om insättningen görs korrekt kan trädets höjd hållas balanserad.
I AVL-träd håller vi koll på trädets höjd under insättningsoperationen. Ändringar görs för att bibehålla den balanserade höjden utan att bryta mot de grundläggande egenskaperna hos Binary Search Tree.
Balansfaktor i AVL-träd
Balansfaktor (BF) är ett grundläggande attribut för varje nod i AVL-träd som hjälper till att övervaka trädets höjd.
Balansfaktorns egenskaper
- Balansfaktorn är känd som skillnaden mellan höjden på det vänstra underträdet och det högra underträdet.
- Balansfaktor(nod) = höjd(nod->vänster) – höjd(nod->höger)
- Tillåtna värden för BF är –1, 0 och +1.
- Värdet –1 indikerar att det högra underträdet innehåller en extra, dvs trädet är rätt tungt.
- Värdet +1 indikerar att det vänstra underträdet innehåller en extra, dvs trädet lämnas tungt.
- Värdet 0 visar att trädet har lika stora noder på varje sida, dvs trädet är perfekt balanserat.
AVL-rotationer
För att få själva AVL-trädet att balansera, när du infogar eller tar bort en nod från trädet, utförs rotationer.
Vi utför följande LL-rotation, RR-rotation, LR-rotation och RL-rotation.
- Vänster – Vänsterrotation
- Höger – Höger rotation
- Höger – Vänsterrotation
- Vänster – höger rotation
Vänster – Vänsterrotation
Denna rotation utförs när en ny nod infogas vid det vänstra underordnade underträdet i det vänstra underträdet.
En enda högerrotation utförs. Denna typ av rotation identifieras när en nod har en balanserad faktor som +2, och dess vänstra barn har en balansfaktor som +1.
Höger – Höger rotation
Denna rotation utförs när en ny nod infogas vid det högra underordnade underträdet i det högra underträdet.
En enda vänsterrotation utförs. Denna typ av rotation identifieras när en nod har en balanserad faktor som -2, och dess högra underordnade har en balansfaktor som -1.
Höger – Vänsterrotation
Denna rotation utförs när en ny nod infogas vid det högra underordnade underträdet i det vänstra underträdet.
Denna rotation utförs när en nod har en balansfaktor som –2, och dess högra underordnade har en balansfaktor som +1.
Vänster – höger rotation
Denna rotation utförs när en ny nod infogas vid det vänstra barnet i det högra underträdet.
Denna rotation utförs när en nod har en balansfaktor som +2, och dess vänstra barn har en balansfaktor som -1.
Insättning i AVL Trees
Insert-operationen är nästan densamma som i enkla binära sökträd. Efter varje insättning balanserar vi trädets höjd. Insättningsoperationen tar O(log n) värsta tidskomplexitet.
steg 1: Infoga noden i AVL-trädet med samma insättningsalgoritm som BST. I exemplet ovan, infoga 160.
steg 2: När noden har lagts till uppdateras balansfaktorn för varje nod. Efter att 160 har infogats uppdateras balansfaktorn för varje nod.
steg 3: Kontrollera nu om någon nod bryter mot balansfaktorns intervall om balansfaktorn överträds, utför sedan rotationer med fallet nedan. I exemplet ovan bryts balansfaktorn 350 och fall 1 blir tillämpligt där, vi utför LL-rotation och trädet balanseras igen.
- Om BF(nod) = +2 och BF(nod -> vänsterbarn) = +1, utför LL-rotation.
- Om BF(nod) = -2 och BF(nod -> högerbarn) = 1, utför RR-rotation.
- Om BF(nod) = -2 och BF(nod -> högerbarn) = +1, utför RL-rotation.
- Om BF(nod) = +2 och BF(nod -> vänsterbarn) = -1, utför LR-rotation.
Radering i AVL-träd
Borttagning är också väldigt okomplicerad. Vi raderar med samma logik som i enkla binära sökträd. Efter raderingen omstrukturerar vi trädet, om det behövs, för att behålla sin balanserade höjd.
Steg 1: Hitta elementet i trädet.
Steg 2: Ta bort noden enligt BST-borttagningen.
Steg 3: Två fall är möjliga: -
Fallet 1: Tar bort från höger underträd.
- 1A. Om BF(nod) = +2 och BF(nod -> vänsterbarn) = +1, utför LL-rotation.
- IB. Om BF(nod) = +1 och BF(nod -> vänsterbarn) = -2, utför LR-rotation.
- 1C. Om BF(nod) = +2 och BF(nod -> vänsterbarn) = 0, utför LL-rotation.
fallet 2: Tar bort från vänster underträd.
- 2A. Om BF(nod) = -2 och BF(nod -> högerbarn) = -1, utför RR-rotation.
- 2B. Om BF(nod) = -2 och BF(nod -> högerbarn) = +1, utför RL-rotation.
- 2C. Om BF(nod) = -2 och BF(nod -> högerbarn) = 0, utför RR-rotation.
C++ Exempel på AVL-träd
Nedan är C++ som implementerar AVL-träd:
#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);
}
Löpande exempel på ovanstående kod:
- Kopiera koden ovan och klistra in "avl.cpp".
- Kompilera koden:
g++ avl.cpp -o run
- Kör koden.
./run
Fördelar med AVL-träd
- Höjden på AVL-trädet är alltid balanserad. Höjden växer aldrig bortom log N, där N är det totala antalet noder i trädet.
- Det ger bättre söktidskomplexitet jämfört med enkla binära sökträd.
- AVL-träd har självbalanserande förmåga.
Sammanfattning
- AVL-träd är självbalanserande binära sökträd.
- Balansfaktor är den grundläggande egenskapen hos AVL-träd
- Balansfaktorn för en nod definieras som skillnaden mellan höjden på det vänstra och högra underträdet i den noden.
- De giltiga värdena för balansfaktorn är -1, 0 och +1.
- Insättnings- och raderingsoperationen kräver att rotationer utförs efter att balansfaktorn har brutits.
- Tidskomplexiteten för infogning, radering och sökning är O(log N).
- AVL-träd följer alla egenskaper hos Binary Search Trees.
- Det vänstra underträdet har noder som är mindre än rotnoden. Det högra underträdet har noder som alltid är större än rotnoden.
- AVL-träd används där sökoperationer är vanligare jämfört med infoga och radera operationer.
