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.

Denk eens aan het volgendewing sleutels ingevoegd in de gegeven volgorde in de binaire zoekboom.


AVL Boomwerk
AVL-boomvisualisatie

De hoogte van de boom groeit lineair in omvang wanneer we de sleutels in oplopende volgorde van hun waarde invoegen. De zoekoperatie 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 balans is, krijgen we een betere zichtbaarheidarching tijd.

Laten we nu naar dezelfde sleutels kijken, maar in een andere volgorde geplaatst.

AVL Boomwerk

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.

Bij AVL-bomen controleren wij tijdens het insteken de hoogte van de boom. 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


Balansfactor in AVL-bomen

Evenwichtsfactor AVL-boom
  • 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.

Wij voeren het volgende uitwing LL-rotatie, RR-rotatie, LR-rotatie en RL-rotatie.

  • 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.


AVL-boom links – linksom draaien

AVL-boom links – linksom draaien

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.

AVL-boom rechts – Rechts draaien

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.

AVL Boom Rechts – Links Rotatie

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.

AVL Boom Links – Rechts Rotatie

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 bij eenvoudige binaire zoekbomen. Na elke plaatsing balanceren we de hoogte van de boom. Invoegbewerking kost O(log n) slechtste tijd complexheid.


Invoeging in AVL-bomen

Implementatie van AVL-boominvoeging

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.

  1. Als BF(knooppunt) = +2 en BF(knooppunt -> linkerkind) = +1, voer dan LL-rotatie uit.
  2. Als BF(knooppunt) = -2 en BF(knooppunt -> rechterkind) = 1, voer dan RR-rotatie uit.
  3. Als BF(knooppunt) = -2 en BF(knooppunt -> rechterkind) = +1, voer dan RL-rotatie uit.
  4. 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.

Verwijdering in AVL-bomen

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.

Verwijdering in AVL-bomen

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:

  1. Kopieer de bovenstaande code en plak deze in “avl.cpp”.
  2. Compileer de code:
g++ avl.cpp -o run
  1. Voer de code uit.
./run

C++ Voorbeeld van AVL-bomen

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 geeft een betere zoektijd complexvergeleken met eenvoudige binaire zoekbomen.
  • AVL-bomen hebben zelfbalancerende eigenschappen.

Samengevat

  • 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 verwijderbewerkingen moeten rotaties worden uitgevoerd na het overtreden van de balansfactor.
  • De tijd complexDe kwaliteit van de invoeg-, verwijder- en zoekbewerking 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 waar zoekbewerkingen vaker voorkomen dan invoeg- en verwijderbewerkingen.