AVL-trær: Rotasjoner, Innsetting, Sletting med C++ Eksempel
Sarah Chen
Hva er AVL-trær?
AVL trær er binære søketrær der forskjellen mellom høyden til venstre og høyre deltre er enten -1, 0 eller +1.
AVL-trær kalles også et selvbalanserende binært søketre. Disse trærne bidrar til å opprettholde den logaritmiske søketiden. Den er oppkalt etter oppfinnerne (AVL) Adelson, Velsky og Landis.
Hvordan fungerer AVL Tree?
For bedre å forstå behovet for AVL-trær, la oss se på noen ulemper ved enkle binære søketrær.
Tenk på følgende nøkler satt inn i gitt rekkefølge i det binære søketreet.
Høyden på treet vokser lineært i størrelse når vi setter inn tastene i økende rekkefølge etter verdien. Dermed tar søkeoperasjonen i verste fall O(n).
Det tar lineær tid å søke etter et element; derfor er det ingen bruk for å bruke Binært søketre struktur. På den annen side, hvis høyden på treet er balansert, får vi bedre søketid.
La oss nå se på de samme tastene, men satt inn i en annen rekkefølge.
Her er nøklene de samme, men siden de settes inn i en annen rekkefølge, tar de forskjellige posisjoner, og høyden på treet forblir balansert. Derfor vil søk ikke ta mer enn O(log n) for noe element i treet. Det er nå tydelig at hvis innsettingen gjøres riktig, kan treets høyde holdes balansert.
I AVL-trær holder vi sjekk på høyden på treet under innsettingsoperasjon. Modifikasjoner er gjort for å opprettholde den balanserte høyden uten å krenke de grunnleggende egenskapene til Binary Search Tree.
Balansefaktor i AVL-trær
Balansefaktor (BF) er en grunnleggende egenskap for hver node i AVL-trær som hjelper til med å overvåke treets høyde.
Egenskaper til balansefaktor
- Balansefaktoren er kjent som forskjellen mellom høyden på venstre undertre og høyre undertre.
- Balansefaktor(node) = høyde(node->venstre) – høyde(node->høyre)
- Tillatte verdier for BF er –1, 0 og +1.
- Verdien –1 indikerer at høyre undertre inneholder en ekstra, dvs. at treet er riktig tungt.
- Verdien +1 indikerer at det venstre undertreet inneholder en ekstra, dvs. at treet er tungt igjen.
- Verdien 0 viser at treet inkluderer like noder på hver side, dvs. at treet er perfekt balansert.
AVL-rotasjoner
For å få AVL-treet til å balansere seg selv, utføres rotasjoner når du setter inn eller sletter en node fra treet.
Vi utfører følgende LL-rotasjon, RR-rotasjon, LR-rotasjon og RL-rotasjon.
- Venstre – Venstre rotasjon
- Høyre – Høyre rotasjon
- Høyre – Venstre rotasjon
- Venstre – Høyre rotasjon
Venstre – Venstre rotasjon
Denne rotasjonen utføres når en ny node settes inn ved venstre underordnede av det venstre undertreet.
En enkelt høyrerotasjon utføres. Denne typen rotasjon identifiseres når en node har en balansert faktor som +2, og dens venstre barn har en balansefaktor som +1.
Høyre – Høyre rotasjon
Denne rotasjonen utføres når en ny node settes inn ved høyre underordnet av høyre undertre.
En enkelt venstrerotasjon utføres. Denne typen rotasjon identifiseres når en node har en balansert faktor som -2, og dens høyre barn har en balansefaktor som -1.
Høyre – Venstre rotasjon
Denne rotasjonen utføres når en ny node settes inn ved høyre underordnet av det venstre undertreet.
Denne rotasjonen utføres når en node har en balansefaktor som –2, og dens høyre underordnede har en balansefaktor som +1.
Venstre – Høyre rotasjon
Denne rotasjonen utføres når en ny node settes inn ved venstre underordnede av høyre undertre.
Denne rotasjonen utføres når en node har en balansefaktor som +2, og dens venstre barn har en balansefaktor som -1.
Innsetting i AVL-trær
Innsettingsoperasjonen er nesten den samme som i enkle binære søketrær. Etter hver innsetting balanserer vi høyden på treet. Innsettingsoperasjon tar O(log n) verste tidskompleksitet.
Trinn 1: Sett inn noden i AVL-treet ved å bruke den samme innsettingsalgoritmen til BST. I eksemplet ovenfor setter du inn 160.
Trinn 2: Når noden er lagt til, oppdateres balansefaktoren for hver node. Etter at 160 er satt inn, oppdateres balansefaktoren for hver node.
Trinn 3: Sjekk nå om en node bryter med balansefaktorens område hvis balansefaktoren brytes, og utfør rotasjoner ved å bruke tilfellet nedenfor. I eksemplet ovenfor blir balansefaktoren på 350 brutt og tilfelle 1 blir aktuelt der, vi utfører LL-rotasjon og treet balanseres igjen.
- Hvis BF(node) = +2 og BF(node -> venstre-barn) = +1, utfør LL-rotasjon.
- Hvis BF(node) = -2 og BF(node -> høyre-barn) = 1, utfør RR-rotasjon.
- Hvis BF(node) = -2 og BF(node -> høyre-barn) = +1, utfør RL-rotasjon.
- Hvis BF(node) = +2 og BF(node -> venstre-barn) = -1, utfør LR-rotasjon.
Sletting i AVL-trær
Sletting er også veldig rett frem. Vi sletter ved å bruke samme logikk som i enkle binære søketrær. Etter sletting omstrukturerer vi treet, om nødvendig, for å opprettholde dens balanserte høyde.
Trinn 1: Finn elementet i treet.
Trinn 2: Slett noden i henhold til BST-slettingen.
Trinn 3: To tilfeller er mulige:
Sak 1: Sletter fra høyre undertre.
- 1A. Hvis BF(node) = +2 og BF(node -> venstre-barn) = +1, utfør LL-rotasjon.
- 1B. Hvis BF(node) = +2 og BF(node -> venstre-barn) = -1, utfør LR-rotasjon.
- 1C. Hvis BF(node) = +2 og BF(node -> venstre-barn) = 0, utfør LL-rotasjon.
Sak 2: Sletter fra venstre undertre.
- 2A. Hvis BF(node) = -2 og BF(node -> høyre-barn) = -1, utfør RR-rotasjon.
- 2B. Hvis BF(node) = -2 og BF(node -> høyre-barn) = +1, utfør RL-rotasjon.
- 2C. Hvis BF(node) = -2 og BF(node -> høyre-barn) = 0, utfør RR-rotasjon.
C++ Eksempel på AVL-trær
Nedenfor er C++ som implementerer AVL-trær:
#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);
}
Kjørende eksempel på koden ovenfor:
- Kopier koden ovenfor og lim inn "avl.cpp".
- Kompiler koden:
g++ avl.cpp -o run
- Kjør koden.
./run
Fordeler med AVL-trær
- Høyden på AVL-treet er alltid balansert. Høyden vokser aldri utover log N, hvor N er det totale antallet noder i treet.
- Det gir bedre søketidskompleksitet sammenlignet med enkle binære søketrær.
- AVL-trær har selvbalanserende evner.
Sammendrag
- AVL-trær er selvbalanserende binære søketrær.
- Balansefaktor er den grunnleggende egenskapen til AVL-trær
- Balansefaktoren til en node er definert som forskjellen mellom høyden til venstre og høyre undertre til den noden.
- De gyldige verdiene for balansefaktoren er -1, 0 og +1.
- Innsetting og sletting krever at rotasjoner utføres etter brudd på balansefaktoren.
- Tidskompleksiteten for innsetting, sletting og søk er O(log N).
- AVL-trær følger alle egenskapene til Binary Search Trees.
- Det venstre undertreet har noder som er mindre enn rotnoden. Det høyre undertreet har noder som alltid er større enn rotnoden.
- AVL-trær brukes der søkeoperasjoner er hyppigere sammenlignet med inn- og sletteoperasjoner.
