AVL stromy: Rotace, vkládání, mazání s C++ Příklad

Co jsou stromy AVL?

AVL stromy jsou binární vyhledávací stromy, ve kterých je rozdíl mezi výškou levého a pravého podstromu buď -1, 0 nebo +1.

Stromy AVL se také nazývají samovyrovnávací binární vyhledávací strom. Tyto stromy pomáhají udržovat logaritmickou dobu vyhledávání. Je pojmenován po svých vynálezcích (AVL) Adelsonovi, Velském a Landisovi.

Jak AVL Tree funguje?

Abychom lépe pochopili potřebu AVL stromů, podívejme se na některé nevýhody jednoduchých binárních vyhledávacích stromů.

Zvažte následující klíče vložené v daném pořadí do binárního vyhledávacího stromu.

Výška stromu lineárně roste, když vkládáme klíče v rostoucím pořadí jejich hodnoty. Vyhledávací operace tedy v nejhorším případě zabere O(n).

Hledání prvku trvá lineárně; proto není použití Binární vyhledávací strom struktura. Na druhou stranu, pokud je výška stromu vyrovnaná, získáme lepší čas hledání.

Podívejme se nyní na stejné klíče, ale vložené v jiném pořadí.

Zde jsou klíče stejné, ale protože jsou vkládány v jiném pořadí, zaujímají různé polohy a výška stromu zůstává vyvážená. Hledání tedy nebude trvat déle než O(log n) pro žádný prvek stromu. Nyní je zřejmé, že pokud je vkládání provedeno správně, lze výšku stromu udržet vyváženou.

U AVL stromů kontrolujeme výšku stromu během operace vkládání. Jsou provedeny úpravy, aby byla zachována vyvážená výška bez porušení základních vlastností binárního vyhledávacího stromu.

Faktor rovnováhy ve stromech AVL

Faktor rovnováhy (BF) je základním atributem každého uzlu ve stromech AVL, který pomáhá sledovat výšku stromu.

Vlastnosti bilančního faktoru

Faktor rovnováhy ve stromech AVL — Bilanční faktor AVL strom

Faktor rovnováhy je znám jako rozdíl mezi výškou levého podstromu a pravého podstromu.
Faktor vyvážení (uzel) = výška (uzel->vlevo) – výška (uzel->vpravo)
Povolené hodnoty BF jsou –1, 0 a +1.
Hodnota –1 znamená, že pravý podstrom obsahuje jeden navíc, tj. strom je správně těžký.
Hodnota +1 znamená, že levý podstrom obsahuje jeden navíc, tj. strom je ponechán těžký.
Hodnota 0 ukazuje, že strom obsahuje stejné uzly na každé straně, tj. strom je dokonale vyvážený.

AVL rotace

Aby se AVL Tree vyrovnal sám, při vkládání nebo mazání uzlu ze stromu se provádějí rotace.

Provádíme následující rotaci LL, rotaci RR, rotaci LR a rotaci RL.

Levá – Levá rotace
Pravá – pravá rotace
Rotace vpravo – vlevo
Otočení vlevo – vpravo

Levá – Levá rotace

Tato rotace se provádí, když je nový uzel vložen do levého potomka levého podstromu.

Provede se jediné otočení doprava. Tento typ rotace je identifikován, když má uzel vyvážený faktor +2 a jeho levý potomek má vyvážený faktor +1.

Pravá – pravá rotace

Tato rotace se provádí, když je nový uzel vložen do pravého potomka pravého podstromu.

Provede se jedno otočení doleva. Tento typ rotace je identifikován, když má uzel vyvážený faktor -2 a jeho pravý potomek má vyvážený faktor -1.

Rotace vpravo – vlevo

Tato rotace se provádí, když je nový uzel vložen do pravého potomka levého podstromu.

Tato rotace se provádí, když má uzel faktor rovnováhy –2 a jeho pravý potomek má faktor rovnováhy +1.

Otočení vlevo – vpravo

Tato rotace se provádí, když je nový uzel vložen do levého potomka pravého podstromu.

Tato rotace se provádí, když má uzel vyvážený faktor +2 a jeho levý potomek má vyvážený faktor -1.

Vložení do stromů AVL

Operace vkládání je téměř stejná jako v jednoduchých binárních vyhledávacích stromech. Po každém zasunutí vyrovnáme výšku stromu. Operace vložení trvá O(log n) nejhorší časovou složitost.

Krok 1: Vložte uzel do stromu AVL pomocí stejného vkládacího algoritmu jako BST. Ve výše uvedeném příkladu vložte 160.

Krok 2: Jakmile je uzel přidán, faktor vyvážení každého uzlu se aktualizuje. Po vložení 160 se aktualizuje faktor vyvážení každého uzlu.

Krok 3: Nyní zkontrolujte, zda některý uzel nenarušuje rozsah faktoru vyvážení, pokud je faktor vyvážení narušen, a poté proveďte rotace pomocí níže uvedeného případu. Ve výše uvedeném příkladu je porušen rovnovážný faktor 350 a uplatní se zde případ 1, provedeme rotaci LL a strom je znovu vyvážen.

Pokud BF(uzel) = +2 a BF(uzel -> levé dítě) = +1, proveďte rotaci LL.
Pokud BF(uzel) = -2 a BF(uzel -> pravé dítě) = 1, proveďte rotaci RR.
Pokud BF(uzel) = -2 a BF(uzel -> pravé dítě) = +1, proveďte rotaci RL.
Pokud BF(uzel) = +2 a BF(uzel -> levé dítě) = -1, proveďte rotaci LR.

Odstranění ve stromech AVL

Mazání je také velmi přímočaré. Odstraňujeme pomocí stejné logiky jako v jednoduchých binárních vyhledávacích stromech. Po smazání strom v případě potřeby restrukturalizujeme, abychom zachovali jeho vyváženou výšku.

Krok 1: Najděte prvek ve stromu.

Krok 2: Odstraňte uzel podle odstranění BST.

Krok 3: Jsou možné dva případy: -

Případ 1: Mazání z pravého podstromu.

1A. Pokud BF(uzel) = +2 a BF(uzel -> levé dítě) = +1, proveďte rotaci LL.
1B. Pokud BF(uzel) = +2 a BF(uzel -> levé dítě) = -1, proveďte rotaci LR.
1C. Pokud BF(uzel) = +2 a BF(uzel -> levé dítě) = 0, proveďte rotaci LL.

případ 2: Mazání z levého podstromu.

2A. Pokud BF(uzel) = -2 a BF(uzel -> pravé dítě) = -1, proveďte rotaci RR.
2B. Pokud BF(uzel) = -2 a BF(uzel -> pravé dítě) = +1, proveďte rotaci RL.
2C. Pokud BF(uzel) = -2 a BF(uzel -> pravé dítě) = 0, proveďte rotaci RR.

C++ Příklad AVL stromů

Níže je C++ který implementuje AVL stromy:

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

Spuštěný příklad výše uvedeného kódu:

Zkopírujte výše uvedený kód a vložte jej do „avl.cpp“.
Zkompilujte kód:

g++ avl.cpp -o run

Spusťte kód.

./run

Výhody AVL Trees

Výška stromu AVL je vždy vyrovnaná. Výška nikdy nepřesáhne log N, kde N je celkový počet uzlů ve stromu.
Ve srovnání s jednoduchými binárními vyhledávacími stromy poskytuje lepší časovou složitost vyhledávání.
AVL stromy mají schopnost samovyvažování.

Shrnutí

AVL stromy jsou samovyvažující binární vyhledávací stromy.
Faktor rovnováhy je základním atributem AVL stromů
Faktor rovnováhy uzlu je definován jako rozdíl mezi výškou levého a pravého podstromu tohoto uzlu.
Platné hodnoty vyvažovacího faktoru jsou -1, 0 a +1.
Operace vkládání a mazání vyžaduje, aby byly rotace provedeny po porušení faktoru vyvážení.
Časová složitost operace vkládání, mazání a vyhledávání je O(log N).
Stromy AVL sledují všechny vlastnosti binárních vyhledávacích stromů.
Levý podstrom má uzly, které jsou menší než kořenový uzel. Pravý podstrom má uzly, které jsou vždy větší než kořenový uzel.
Stromy AVL se používají tam, kde je operace vyhledávání častější ve srovnání s operacemi vkládání a mazání.

Máš rád: