AVL Træer: Rotationer, Indsættelse, Sletning med C++ Eksempel

Hvad er AVL-træer?

AVL træer er binære søgetræer, hvor forskellen mellem højden af venstre og højre undertræ er enten -1, 0 eller +1.

AVL-træer kaldes også et selvbalancerende binært søgetræ. Disse træer hjælper med at opretholde den logaritmiske søgetid. Den er opkaldt efter dens opfindere (AVL) Adelson, Velsky og Landis.

Hvordan virker AVL Tree?

For bedre at forstå behovet for AVL-træer, lad os se på nogle ulemper ved simple binære søgetræer.

Overvej følgende nøgler indsat i den givne rækkefølge i det binære søgetræ.

Træets højde vokser lineært i størrelse, når vi indsætter nøglerne i stigende rækkefølge efter deres værdi. Således tager søgeoperationen i værste fald O(n).

Det tager lineær tid at søge efter et element; derfor er der ingen brug af at bruge Binært søgetræ struktur. På den anden side, hvis træets højde er afbalanceret, får vi bedre søgetid.

Lad os nu se på de samme nøgler, men indsat i en anden rækkefølge.

Her er tasterne de samme, men da de er indsat i en anden rækkefølge, indtager de forskellige positioner, og træets højde forbliver afbalanceret. Derfor vil søgning ikke tage mere end O(log n) for noget element i træet. Det er nu tydeligt, at hvis indsættelsen udføres korrekt, kan træets højde holdes afbalanceret.

I AVL-træer holder vi øje med træets højde under indsætningsoperationen. Ændringer er lavet for at opretholde den afbalancerede højde uden at krænke de grundlæggende egenskaber ved Binary Search Tree.

Balancefaktor i AVL-træer

Balancefaktor (BF) er en grundlæggende egenskab for hver knude i AVL-træer, der hjælper med at overvåge træets højde.

Balancefaktorens egenskaber

Balancefaktor i AVL-træer — Balancefaktor AVL træ

Balancefaktoren er kendt som forskellen mellem højden af venstre undertræ og højre undertræ.
Balancefaktor(node) = højde(node->venstre) – højde(node->højre)
Tilladte værdier for BF er –1, 0 og +1.
Værdien –1 angiver, at det højre undertræ indeholder en ekstra, dvs. træet er ret tungt.
Værdien +1 angiver, at det venstre undertræ indeholder en ekstra, dvs. træet er efterladt tungt.
Værdien 0 viser, at træet indeholder lige store noder på hver side, dvs. træet er perfekt afbalanceret.

AVL rotationer

For at få AVL-træet til at balancere selv, udføres der rotationer, når du indsætter eller sletter en node fra træet.

Vi udfører følgende LL-rotation, RR-rotation, LR-rotation og RL-rotation.

Venstre – Venstre rotation
Højre – Højre rotation
Højre – Venstre rotation
Venstre – Højre rotation

Venstre – Venstre rotation

Denne rotation udføres, når en ny node indsættes i venstre underordnede undertræ.

En enkelt højredrejning udføres. Denne type rotation identificeres, når en node har en balanceret faktor som +2, og dens venstre-barn har en balancefaktor som +1.

Højre – Højre rotation

Denne rotation udføres, når en ny node indsættes ved det højre underordnede af det højre undertræ.

En enkelt venstredrejning udføres. Denne type rotation identificeres, når en node har en balanceret faktor som -2, og dens højre underordnede har en balancefaktor som -1.

Højre – Venstre rotation

Denne rotation udføres, når en ny node indsættes ved højre underordnede af det venstre undertræ.

Denne rotation udføres, når en node har en balancefaktor som –2, og dens højre underordnede har en balancefaktor som +1.

Venstre – Højre rotation

Denne rotation udføres, når en ny node indsættes ved det venstre underordnede underordnede undertræ.

Denne rotation udføres, når en node har en balancefaktor som +2, og dens venstre-barn har en balancefaktor som -1.

Indsættelse i AVL Træer

Indsættelsesoperationen er næsten den samme som i simple binære søgetræer. Efter hver indsættelse afbalancerer vi træets højde. Indsæt operation tager O(log n) værste tidskompleksitet.

Trin 1: Indsæt noden i AVL-træet ved hjælp af den samme indsættelsesalgoritme som BST. I ovenstående eksempel skal du indsætte 160.

Trin 2: Når noden er tilføjet, opdateres balancefaktoren for hver node. Efter at 160 er indsat, opdateres balancefaktoren for hver knude.

Trin 3: Tjek nu, om en node overtræder balancefaktorens område, hvis balancefaktoren overtrædes, og udfør derefter rotationer ved at bruge nedenstående tilfælde. I ovenstående eksempel er balancefaktoren på 350 overtrådt, og tilfælde 1 bliver gældende der, vi udfører LL-rotation og træet balanceres igen.

Hvis BF(node) = +2 og BF(node -> venstre-barn) = +1, udfør LL-rotation.
Hvis BF(node) = -2 og BF(node -> højre-barn) = 1, udfør RR-rotation.
Hvis BF(node) = -2 og BF(node -> højre-barn) = +1, udfør RL-rotation.
Hvis BF(node) = +2 og BF(node -> venstre-barn) = -1, udfør LR-rotation.

Sletning i AVL-træer

Sletning er også meget ligetil. Vi sletter ved at bruge samme logik som i simple binære søgetræer. Efter sletning omstrukturerer vi træet, hvis det er nødvendigt, for at bevare dets afbalancerede højde.

Trin 1: Find elementet i træet.

Trin 2: Slet noden i henhold til BST-sletningen.

Trin 3: To tilfælde er mulige:

Sag 1: Sletter fra højre undertræ.

1A. Hvis BF(node) = +2 og BF(node -> venstre-barn) = +1, udfør LL-rotation.
1B. Hvis BF(node) = +2 og BF(node -> venstre-barn) = -1, udfør LR-rotation.
1C. Hvis BF(node) = +2 og BF(node -> venstre-barn) = 0, skal du udføre LL-rotation.

Sag 2: Sletter fra venstre undertræ.

2A. Hvis BF(node) = -2 og BF(node -> højre-barn) = -1, udfør RR-rotation.
2B. Hvis BF(node) = -2 og BF(node -> højre-barn) = +1, udfør RL-rotation.
2C. Hvis BF(node) = -2 og BF(node -> højre-barn) = 0, udfør RR-rotation.

C++ Eksempel på AVL-træer

Nedenfor er C++ der implementerer AVL-træer:

#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);
  
}

Kørende eksempel på ovenstående kode:

Kopier koden ovenfor og indsæt "avl.cpp".
Kompiler koden:

g++ avl.cpp -o run

Kør koden.

./run

Fordele ved AVL Træer

Højden på AVL-træet er altid afbalanceret. Højden vokser aldrig ud over log N, hvor N er det samlede antal knudepunkter i træet.
Det giver bedre søgetidskompleksitet sammenlignet med simple binære søgetræer.
AVL-træer har selvbalancerende egenskaber.

Resumé

AVL-træer er selvbalancerende binære søgetræer.
Balancefaktor er den grundlæggende egenskab ved AVL-træer
Balancefaktoren for en node er defineret som forskellen mellem højden af venstre og højre undertræ af den node.
De gyldige værdier af balancefaktoren er -1, 0 og +1.
Indsæt- og sletningsoperationen kræver, at der udføres rotationer efter at have overtrådt balancefaktoren.
Tidskompleksiteten for indsættelse, sletning og søgning er O(log N).
AVL-træer følger alle egenskaber for binære søgetræer.
Det venstre undertræ har noder, der er mindre end rodknuden. Det højre undertræ har noder, der altid er større end rodknuden.
AVL-træer bruges, hvor søgeoperationer er hyppigere sammenlignet med indsætnings- og sletningsoperationer.