Albero AVL
Da Wikipedia, l'enciclopedia libera.
Nell'informatica l'albero AVL è un albero bilanciato. 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. È 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, che è definito come l'altezza del sottoalbero destro meno quella del sottoalbero sinistro.
Indice |
[modifica] Le 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:
[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 contentente 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 bilanciameno 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)
