AVL-bomen: rotaties, invoeging, verwijdering met C++ Voorbeeld
Wat zijn AVL-bomen?
AVL-bomen zijn binaire zoekbomen waarin het verschil tussen de hoogte van de linker en rechter subboom -1, 0 of +1 is.
AVL-bomen worden ook wel een zelfbalancerende binaire zoekboom genoemd. Deze bomen helpen de logaritmische zoektijd in stand te houden. Het is vernoemd naar de uitvinders (AVL) Adelson, Velsky en Landis.
Hoe werkt AVL Tree?
Laten we, om de noodzaak van AVL-bomen beter te begrijpen, eens kijken naar enkele nadelen van eenvoudige binaire zoekbomen.
Beschouw de volgende sleutels in de gegeven volgorde in de binaire zoekboom.

De hoogte van de boom groeit lineair in omvang wanneer we de sleutels in oplopende volgorde van hun waarde invoegen. De zoekbewerking duurt dus in het slechtste geval O(n).
Het kost lineaire tijd om naar een element te zoeken; daarom heeft het geen zin om de Binaire zoekboom structuur. Aan de andere kant, als de hoogte van de boom in evenwicht is, krijgen we een betere zoektijd.
Laten we nu naar dezelfde sleutels kijken, maar in een andere volgorde geplaatst.
Hier zijn de toetsen hetzelfde, maar omdat ze in een andere volgorde worden geplaatst, nemen ze verschillende posities in en blijft de hoogte van de boom in balans. Daarom zal het zoeken naar geen enkel element van de boom meer dan O(log n) vergen. Het is nu duidelijk dat als het inbrengen correct gebeurt, de hoogte van de boom in evenwicht kan worden gehouden.
In AVL-bomen houden we de hoogte van de boom in de gaten tijdens de invoegbewerking. Er worden wijzigingen aangebracht om de gebalanceerde hoogte te behouden zonder de fundamentele eigenschappen van de binaire zoekboom te schenden.
Balansfactor in AVL-bomen
Balansfactor (BF) is een fundamenteel kenmerk van elk knooppunt in AVL-bomen en helpt de hoogte van de boom te bewaken.
Eigenschappen van de balansfactor

- De balansfactor staat bekend als het verschil tussen de hoogte van de linker deelboom en de rechter deelboom.
- Balansfactor(knooppunt) = hoogte(knooppunt->links) – hoogte(knooppunt->rechts)
- Toegestane waarden van BF zijn –1, 0 en +1.
- De waarde –1 geeft aan dat de rechter subboom er één extra bevat, dat wil zeggen dat de boom precies zwaar is.
- De waarde +1 geeft aan dat de linker subboom er één extra bevat, dat wil zeggen dat de boom zwaar blijft.
- De waarde 0 geeft aan dat de boom aan elke kant gelijke knooppunten heeft, dat wil zeggen dat de boom perfect in balans is.
AVL-rotaties
Om de AVL-boom zelf in evenwicht te brengen, worden er bij het invoegen of verwijderen van een knooppunt uit de boom rotaties uitgevoerd.
We voeren de volgende LL-rotatie, RR-rotatie, LR-rotatie en RL-rotatie uit.
- Links – Links draaien
- Rechts – Rechts draaien
- Rechts-links rotatie
- Links-rechts rotatie
Links – Links draaien
Deze rotatie wordt uitgevoerd wanneer een nieuw knooppunt wordt ingevoegd aan het linkerkind van de linker subboom.

Er wordt een enkele rotatie naar rechts uitgevoerd. Dit type rotatie wordt geïdentificeerd wanneer een knooppunt een gebalanceerde factor heeft van +2, en het linkerkind een balansfactor heeft van +1.
Rechts – Rechts draaien
Deze rotatie wordt uitgevoerd wanneer een nieuw knooppunt wordt ingevoegd bij het rechterkind van de rechter subboom.
Er wordt een enkele rotatie naar links uitgevoerd. Dit type rotatie wordt geïdentificeerd wanneer een knooppunt een gebalanceerde factor heeft van -2, en het rechterkind een balansfactor heeft van -1.
Rechts-links rotatie
Deze rotatie wordt uitgevoerd wanneer een nieuw knooppunt wordt ingevoegd aan het rechterkind van de linker subboom.
Deze rotatie wordt uitgevoerd wanneer een knooppunt een balansfactor heeft van –2, en het rechterkind een balansfactor heeft van +1.
Links-rechts rotatie
Deze rotatie wordt uitgevoerd wanneer een nieuw knooppunt wordt ingevoegd aan het linkerkind van de rechter subboom.
Deze rotatie wordt uitgevoerd wanneer een knooppunt een balansfactor heeft van +2, en het linkerkind een balansfactor heeft van -1.
Invoeging in AVL-bomen
De invoegbewerking is bijna hetzelfde als in eenvoudige binaire zoekbomen. Na elke invoeging balanceren we de hoogte van de boom. De invoegbewerking neemt O(log n) slechtste tijdscomplexiteit.

Stap 1: Voeg het knooppunt in de AVL-boom in met hetzelfde invoegalgoritme als BST. In het bovenstaande voorbeeld voert u 160 in.
Stap 2: Zodra het knooppunt is toegevoegd, wordt de balansfactor van elk knooppunt bijgewerkt. Nadat 160 is ingevoegd, wordt de balansfactor van elk knooppunt bijgewerkt.
Stap 3: Controleer nu of een knooppunt het bereik van de balansfactor schendt als de balansfactor wordt geschonden, en voer vervolgens rotaties uit met behulp van het onderstaande geval. In bovenstaand voorbeeld wordt de balansfactor van 350 geschonden en wordt geval 1 daar van toepassing, voeren we LL-rotatie uit en is de boom weer in balans.
- Als BF(knooppunt) = +2 en BF(knooppunt -> linkerkind) = +1, voer dan LL-rotatie uit.
- Als BF(knooppunt) = -2 en BF(knooppunt -> rechterkind) = 1, voer dan RR-rotatie uit.
- Als BF(knooppunt) = -2 en BF(knooppunt -> rechterkind) = +1, voer dan RL-rotatie uit.
- Als BF(knooppunt) = +2 en BF(knooppunt -> linkerkind) = -1, voer dan LR-rotatie uit.
Verwijdering in AVL-bomen
Verwijderen is ook heel eenvoudig. We verwijderen met dezelfde logica als bij eenvoudige binaire zoekbomen. Na het verwijderen herstructureren we de boom, indien nodig, om de evenwichtige hoogte te behouden.
Stap 1: Zoek het element in de boom.
Stap 2: Verwijder het knooppunt, volgens de BST-verwijdering.
Stap 3: Er zijn twee gevallen mogelijk: -
Zaak 1: Verwijderen uit de rechter subboom.
- 1A. Als BF(knooppunt) = +2 en BF(knooppunt -> linkerkind) = +1, voer dan LL-rotatie uit.
- 1B. Als BF(knooppunt) = +2 en BF(knooppunt -> linkerkind) = -1, voer dan LR-rotatie uit.
- 1C. Als BF(knooppunt) = +2 en BF(knooppunt -> linkerkind) = 0, voer dan LL-rotatie uit.
Case 2: Verwijderen uit de linker subboom.
- 2A. Als BF(knooppunt) = -2 en BF(knooppunt -> rechterkind) = -1, voer dan RR-rotatie uit.
- 2B. Als BF(knooppunt) = -2 en BF(knooppunt -> rechterkind) = +1, voer dan RL-rotatie uit.
- 2C. Als BF(knooppunt) = -2 en BF(knooppunt -> rechterkind) = 0, voer dan RR-rotatie uit.
C++ Voorbeeld van AVL-bomen
Hieronder staat de C++ dat AVL-bomen implementeert:
#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); }
Lopend voorbeeld van bovenstaande code:
- Kopieer de bovenstaande code en plak deze in “avl.cpp”.
- Compileer de code:
g++ avl.cpp -o run
- Voer de code uit.
./run
Voordelen van AVL Bomen
- De hoogte van de AVL-boom is altijd in evenwicht. De hoogte wordt nooit groter dan log N, waarbij N het totale aantal knooppunten in de boom is.
- Het biedt een betere zoektijdcomplexiteit in vergelijking met eenvoudige binaire zoekbomen.
- AVL-bomen hebben zelfbalancerende eigenschappen.
Samenvatting
- AVL-bomen zijn zelfbalancerende binaire zoekbomen.
- Balansfactor is het fundamentele kenmerk van AVL-bomen
- De balansfactor van een knooppunt wordt gedefinieerd als het verschil tussen de hoogte van de linker- en rechterdeelboom van dat knooppunt.
- De geldige waarden van de balansfactor zijn -1, 0 en +1.
- Voor de invoeg- en verwijderbewerking moeten rotaties worden uitgevoerd nadat de balansfactor is geschonden.
- De tijdcomplexiteit van invoeg-, verwijder- en zoekbewerkingen is O(log N).
- AVL-bomen volgen alle eigenschappen van binaire zoekbomen.
- De linker subboom heeft knooppunten die kleiner zijn dan het hoofdknooppunt. De rechter subboom heeft knooppunten die altijd groter zijn dan het hoofdknooppunt.
- AVL-bomen worden gebruikt wanneer zoekbewerkingen vaker voorkomen dan invoeg- en verwijderbewerkingen.