jump to navigation

Alberi AVL 19 febbraio 2008

Posted by fripp in Algoritmi, C, C++, Informatica, Programmazione.
Tags: , , , , , , ,
trackback

Gli alberi AVL sono degli alberi binari bilanciati in altezza. Un albero binario si dice bilanciato in altezza se, per ciascun nodo dell’albero, l’altezza del sottoalbero sinistro differisce dall’altezza del sottoalbero destro al più di una unità.

Per gli alberi AVL si parla anche di fattore di sbilanciamento di un nodo e lo si definisce come la differenza tra l’altezza del sottoalbero sinistro e l’altezza del sottoalbero destro. Banalmente, in un albero AVL il fattore di sbilanciamento di ciascun nodo è, in valore assoluto, \leq 1.

A differenza di un albero binario “tradizionale”, un albero AVL mantiene la proprietà di bilanciamento in qualsiasi circostanza, sia dopo un inserimento di un nuovo valore che dopo la cancellazione.

Si può dimostrare che l’altezza di un albero AVL di n nodi è sempre O(\log n) e quindi tutte le operazioni di gestione dell’albero (ricerca, inserimento e cancellazione) hanno costo O(\log n).

Per mantenere il bilanciamento dell’albero in seguito a inserimenti o cancellazioni si devono effettuare delle particolari rotazioni, semplici o composte, che permettono di riequilibrare l’albero.

Abbiamo 4 tipi principali di rotazioni, che vengono applicate in base alla tipologia di sbilanciamento che si vuole corregere. Supponiamo di chiamare v il nodo critico, ovvero il nodo più profondo dell’albero che ha un fattore di sbilanciamento in modulo uguale a 2; possiamo trovarci in 4 casi distinti, che necessitano di rotazioni differenti:

  • Rotazione SS: si verifica quando a determinare lo sbilanciamento è il figlio sinistro del sottoalbero sinistro del nodo v
  • Rotazione DD: si verifica quando a determinare lo sbilanciamento è il figlio destro del sottoalbero destro del nodo v
  • Rotazione SD: si verifica quando a determianre lo sbilanciamento è il figlio destro del sottoalbero sinistro del nodo v
  • Rotazione DS: si verifica quando a determianre lo sbilanciamento è il figlio sinistro del sottoalbero destro del nodo v

I 4 casi sono simmetrici a coppie (SS con DD, SD con DS).

Nel caso sia necessaria una rotazione SS, per ribilanciare il nodo v occorrerà applicare una rotazione semplice verso destra su v.

Nel caso sia necessaria una rotazione SD, per ribilanciare il nodo v occorrerà una doppia rotazione: sia z il figlio sinistro di v; l’abero T che sbilancia v è il sottoalbero destro di z, radicato in w. La rotazione SD consiste in una rotazione semplice verso sinistra con perno in z seguita da una rotazione di base verso destra con perno in v.

ss.png

La precedente immagine mostra un’esempio di rotazione semplice verso destra, imperniata sul nodo di etichetta b; la rotazione verso sinistra è perfettamente simmetrica.

Di seguito troverete il codice C per eseguire le 4 rotazioni.


struct node{
    void *data;
    size_t data_size;
    //h è l'ltezza del nodo
    int h;
    struct node *left;
    struct node *right;
    struct node *father;
};

static struct node* ss( struct node* root ){
    printf("Rotazione ss\n");
    struct node* x;

    //effettuiamo la rotazione
    x = root->left;
    root->left = x->right;
    x->right = root;

    //aggiorniamo le altezze dei nodi coinvolti
    root->h = MAX( HEIGHT( root->left ), HEIGHT( root->right ) ) + 1;
    x->h = MAX( HEIGHT( x->left ), x->h ) + 1;

    x->father=x->right->father;
    if(x->father){
        if(x->right->father->left==x->right)
            x->right->father->left=x;
        else if(x->right->father->right==x->right)
            x->right->father->right=x;
    }

    x->right->father=x;
    if(x->right->left)
        x->right->left->father=x->right;

    return x;
}

/*
 * La funzione dd effettua una rotazione semplice verso sinistra.
 * La funzione prende in ingresso il nodo perno
 */

static struct node* dd( struct node* root ){
    printf("Rotazione dd\n");
    struct node* x;

    //effettuiamo la rotazione
    x = root->right;
    root->right = x->left;
    x->left = root;

    //aggiorniamo le altezze dei nodi coinvolti
    root->h = MAX( HEIGHT( root->left ), HEIGHT( root->right ) ) + 1;
    x->h = MAX( HEIGHT( x->right ), root->h ) + 1;

    x->father=x->left->father;
    if(x->father){
        if(x->left->father->left==x->left)
            x->left->father->left=x;
        else if(x->left->father->right==x->left)
            x->left->father->right=x;
    }
    x->left->father=x;
    if(x->left->right)
        x->left->right->father=x->left;

    return x;
}

/*
 * La funzione sd effettua una rotazione composta, prima verso sinistra con perno nel figlio sinistro del nodo crtico,
 * poi verso destra con perno nel nodo critico stesso.
 * La funzione prende in ingresso il nodo critico
 */

static struct node* sd( struct node* root ){
    printf("Rotazione sd\n");

    root->left = dd( root->left );

    return ss( root );
}

static struct node* ds( struct node* root ){
    printf("Rotazione sd\n");

    root->right = ss( root->right );

    return dd( root );
}

Le 4 funzioni prendono in ingresso il “nodo critico”, ovvero il più profondo nodo con fattore di sbilanciamento in modulo uguale a 2. Le funzioni mantengono pure i “rapporti di paternità” tra i nodi e aggiornano l’altezza dei nodi coivolti nella rotazione.La funzione di inserimento è semplice da implementare. Il criterio su cui si basa è lo stesso su cui si basa la funzione di inserimento ricorsivo per un normale albero binario; l’unica aggiunta sta nel controllo dello sbilanciamento dopo l’inserimento.Ecco il codice:


inline struct node* avl_insert(struct node* root, void *data, size_t s,compare_function compare){

    if(!root){

        root=node_alloc(data,s);
        root->father=0;

    }else if(compare(data,root->data)<0){
        root->left=avl_insert(root->left,data,s,compare);
        root->left->father=root;

        /*
         * Dopo l'inserimento del nuovo nodo controlliamo se si verifica uno sbilanciamento.
         * Se si, controlliamo le caratteristiche dello sbilanciamento per decidere che tipo di rotazione effettuare
         */
        if((HEIGHT(root->left) - HEIGHT(root->right)) == 2){

            if(compare(data,root->left->data)<0){

                //effettuaiamo una rotazione ss
                root=ss(root);

            }else{
                //rotazione sd
                root=sd(root);

            }
        }
    }else if(compare(data,root->data)>0){
        root->right=avl_insert(root->right,data,s,compare);
        root->right->father=root;

        //Stesse considerazioni fatte sopra
        if((HEIGHT(root->right) - HEIGHT(root->left))==2){

            if(compare(data,root->right->data)>0){
                root=dd(root);

            }else{
                root=ds(root);

            }
        }
    }

    //Aggiorniamo l'altezza del nodo dopo l'inserimento
    root->h=MAX(HEIGHT(root->left),HEIGHT(root->right))+1;

    return root;
}

Ho implementato pure la funzione di cancellazione. Il codice di quest’ultima funzione e di tutte le altre lo potrete scaricare dal mio repository a questo link.Occorre sottolineare che, mentre nel caso degli inserimenti al più si effettua una sola rotazione, nel caso della cancellazione di un nodo si posson fare O(\log n) rotazioni consecutive.Per approfondimenti, cliccate qui.

Annunci

Commenti»

1. Usare Graphviz e DOT per stampare un albero binario « frammenti di razionalità - 20 febbraio 2008

[…] DOT che mi ha permesso di realizzare l’immagine della rotazione di un albero, presente nel post sugli alberi AVL, è il […]

2. rief - 14 luglio 2008

I miei complimenti, davvero un bell’articolo, ben scritto e ben fatto.

3. antonio - 23 gennaio 2010

Grazie per quest’articolo.
Però come molti altri è incompleto, o meglio non alla portata di tutti. se ti riesce, se hai tempo voglia, per me sarebbe utilissimo :
1) dopo la spiegazione della rotazione sd, (dove parli di nodi v,z,w) mostri una figura dove non sono riportati i nodi v,z,w ma etichette del tipo a, b….e questo ad un novizio come me scatena domande del tipo…chi è il nodo v ed il nodo z?
2) se ti è possibile fare una figura per tutte e 4 le rotazioni…non basta dire sono simmetriche…credimi! uno vuole avere una riferimento sicuro…
ciao ciao e grazie davvero per quest’articolo
P.S
sto preparando l’esame di algoritmi e strutture dati e mi faresti veramente una gran cortesia
ciao

4. Marco - 28 gennaio 2011

ciao…
ho scaricato il tuo programma ma ho qualche problema…
se provo a caricare un albero inserendo 1-2-3-4-5-6-7-8-9-10 il risultato è 5-10…nelle varie rotazioni si perde dei pezzi per strada…
nella cancellazione di un elemento…
se cancello un nodo che ha 2 figli idem…
potrasti per caso aiutarmi?
grazie mille!!

fripp - 28 gennaio 2011

Attualmente sono impegnato full time con la tesi, quindi non posso veramente guardare il codice. Ricordo che quando lo misi online era stato debuggato abbastanza bene……


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: