Albero AVL
Da Wikipedia, l'enciclopedia libera.
L'albero AVL è, in informatica, un particolare tipo di albero bilanciato che contiene, oltre alle caratteristiche tipiche di un albero bilanciato, il coefficiente di bilanciamento definito per ogni nodo (vedi più in basso). In realtà si tratta di un albero approssimativamente bilanciato, cioè tale che i coefficienti di bilanciamento siano 1, 0 oppure -1 (nel caso ideale di albero AVL bilanciato tutti i coefficienti di bilanciamento sono uguali a 0).
La condizione per tenerlo bilanciato è semplice: per ogni nodo dell'albero, la differenza di altezza dei suoi sottoalberi figli deve differire al massimo di uno. Grazie a questa restrizione, l'altezza massima del albero, ossia la più grande distanza tra la radice e le foglie, è logaritmica nel numero dei nodi. È per questo che questa struttura di dati permette di compiere l'inserimento, la ricerca e l'eliminazione di un elemento in O(log n). Inoltre se si considerano i costi ammortizzati di una serie di inserzioni, questi sono O(1).
Il nome AVL viene dai suoi inventori G.M. Adelson-Velsky e E.M. Landis, che pubblicarono il loro algoritmo nel saggio "An algorithm for the organization of information" del 1962.
Per evitare di dover contare ogni volta l'altezza di un sottoalbero, si salva nel nodo il coefficiente di bilanciamento di un nodo, che è definito come la differenza tra l'altezza del sottoalbero destro e quella del sottoalbero sinistro del nodo considerato.
Indice |
[modifica] Rotazioni
Un nodo con il coefficiente di bilanciamento diverso da 1, 0 o -1 è considerato sbilanciato e viene ribilanciato grazie alle rotazioni. Ne esistono tre tipi:
 |
Per approfondire, vedi la voce Rotazione (informatica). |
[modifica] Rotazione a sinistra
Si esegue quando un nodo ha un coefficiente di bilanciamento di +2 ed il suo figlio sinistro un coefficiente di bilanciamento uguale a +1 o 0.
[modifica] Rotazione a destra
Si esegue quando un nodo ha un coefficiente di bilanciamento di -2 e il suo figlio destro un coefficiente di bilanciamento uguale a -1 o 0.
[modifica] Doppia rotazione
[modifica] Sinistra-Destra
Si esegue quando un nodo ha un coefficiente di bilanciamento di -2 e il suo figlio destro un coefficiente di bilanciamento uguale a +1.
[modifica] Destra-Sinistra
Si esegue quando un nodo ha un coefficiente di bilanciamento di +2 e il suo figlio sinistro un coefficiente di bilanciamento uguale a -1
[modifica] Operazioni
[modifica] Ricerca
La ricerca di un elemento in un albero AVL si svolge come quella negli alberi binari di ricerca.
[modifica] Inserimento
Il primo passo dell'inserimento di un elemento in un albero AVL funziona come in quello non bilanciato, si cerca il posto dove deve andare. Se la ricerca finisce su un nodo contenente l'elemento da inserire, l'inserimento è terminato, mentre se finisce in una foglia, la si sostituisce con un nodo contenente l'elemento da inserire. Dopo questa operazione, il giusto bilanciamento dell' albero non è più garantito, è per questo che si controlla se sul percorso, che va dal nuovo nodo alla radice, ci sono nodi dove la condizione di bilanciamento non è soddisfatta e, se è il caso, si applicano le rotazioni.
[modifica] Eliminazione
Anche qui, si cerca l'elemento da eliminare come negli alberi binari di ricerca. Se l'elemento non è presente, non bisogna fare niente. Altrimenti si sostituisce il nodo con il suo predecessore (o successore) simmetrico, se questo non esiste, lo sostituisce con una foglia. Se il nodo è stato eliminato, le condizioni di bilanciamento non sono più garantite, e si ripristina il bilanciamento con delle rotazioni sul percorso che va dal nodo alla radice.
[modifica] Voci correlate
[modifica] Richiami
- G. Adelson-Velskii and E.M. Landis, "An algorithm for the organization of information." Doklady Akademii Nauk SSSR, 146:263–266, 1962 (russo)
