Alberi Avl

Visto che si avvicina il natale è una buona idea iniziare a preparare gli alberelli.
L’albero che ho addobbato è un albero Avl cioè una particolare struttura dati basata su un albero binario semplice ma con una caratteristica in più: la possibilità di ribilanciarsi dopo l’inserimento e la cancellazione di nodi.
Un albero bilanciato è un albero che ha un fattore di bilanciamento in valore assoluto minore o uguale a 1 per ogni nodo,vale a dire che la differenza tra l’altezza del sottoalbero sinistro e quella del sottoalbero destro rispetto al nodo si differenziano di al più una unità.

Questa caratteristica è utilissima perchè un tale albero presenta un’altezza al più logaritmica rispetto al numero dei nodi.
Con una tale struttura le operazioni di ricerca e quindi di inserimento e cancellazione presentano un costo

O(log(n))

rispetto al numero dei nodi.
L’albero Avl non è l’unico ad avere questa proprietà, vi sono anche gli alberi 2-3,i Btrees,i Red Black e tanti altri.

L’albero Avl si serve di rotazioni per ribilanciarsi.
Sostanzialmente viene effettuata una ricerca

del primo nodo “sbilanciato” a partire da quello inserito o cancellato verso la radice e su questo viene effettuata la rotazione necessaria per il ribilanciamento.
A seconda della posizione dell’ultimo nodo inserito o cancellato rispetto al nodo critico,possono essere effettuate due tipi di rotazioni:
Rotazione semplice

Rotazione doppia

Generalizzando il concetto di chiave a stringhe,si può utilizzare un albero Avl per implementare un dizionario.Il dizionario che ho implementato permette l’inserimento,la cancellazione e la ricerca di termini
Per consentire tali operazioni ho fatto uso della libreria libreadline,che troverete sicuramente nel vostro repository di fiducia
.All’interno del tarball vi è un makefile,che consente di compilare anche una versione “debug” del programma con la direttiva

make debug

,con questo eseguibile potrete testare la funzionalità e l’efficienza dell’albero inserendo chiavi numeriche passate come parametro da terminale,nello specifico

+num

vi permette di inserire una chiave e

-num

vi permette di cancellarla.
Vi riporto su questo post solo la parte di codice relativa alle rotazioni,tutto il resto lo trovate in questo tarball.

Aggiungo infine che potete sbizzarrirvi con questa applettina che per fortuna ho trovato in giro.

static void rotate_right(nodo_t *v){
        nodo_t* u=(v->left);             //deve esistere se la funzione è invocata
        if(u->right!=NULL)
                link_l(v,u->right);      //il sottoalbero di u viene eventualmente adottato da v
        else v->left=NULL;

         if(v->paren!=NULL){      //relinking del padre di v
                if(v==v->paren->left)
                        v->paren->left=u;

        else if(v==v->paren->right)
                v->paren->right=u;
         }

        u->paren=v->paren;  //scambio di posizione tra u e v
        v->paren=u;
        u->right=v;

        if(num_sons(v)==0) v->h=0;  //risistemamento dell'altezza di v
        if(num_sons(v)==1){
                nodo_t* figlio_v = ((v->left!=NULL) ? (v->left) : (v->right));
                v->h=figlio_v->h+1;
        }
        if(num_sons(v)==2)
                v->h = 1+(MAX(v->left->h,v->right->h));
}

static void rotate_left(nodo_t *v){ //analogo a rotate_right
        nodo_t* u=(v->right);
        if(u->left!=NULL)
                link_r(v,u->left);
        else v->right=NULL;

        if(v->paren!=NULL){
        if(v==v->paren->right)
                v->paren->right=u;

        else if(v==v->paren->left)
                v->paren->left=u;
        }

        u->paren=v->paren;
        v->paren=u;
        u->left=v;

        if(num_sons(v)==0) v->h=0;
        if(num_sons(v)==1){
                nodo_t* figlio_v = ((v->left!=NULL) ? (v->left) : (v->right));
                v->h=figlio_v->h+1;
        }
        if(num_sons(v)==2)
                v->h = 1+(MAX(v->left->h,v->right->h));

}