Albero AVL

Da Wikipedia, l'enciclopedia libera.
Esempio di un albero non-AVL: il nodo contenente il numero 9 ha un coefficiente di bilanciamento +2, quello contenente il numero 76 di -3 e quello contenente il numero 54 di +2
Lo stesso albero, adesso AVL (dopo essere stato bilanciato: rotazione a sinistra sul nodo contenente il numero 9 e una rotazione a destra sul nodo contenente il numero 54, seguita da una rotazione a destra sul nodo contenente il numero 72)

L'albero AVL è, in informatica, un particolare tipo di albero bilanciato che possiede, 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 dell'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 Georgij Adelson-Velskij e Evgenij Landis, che pubblicarono il loro algoritmo nel saggio in russo "Odin algoritm organizacii informacii" ("un algoritmo di organizzazione dell'informazione") 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 SINISTRO e quella del sottoalbero DESTRO del nodo considerato.

Rotazioni[modifica | modifica sorgente]

Rotazione a destra; la rotazione a sinistra è simmetrica

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:

Exquisite-kfind.png Per approfondire, vedi Rotazione (informatica).

Rotazione a sinistra[modifica | modifica sorgente]

Si esegue quando un nodo ha un coefficiente di bilanciamento di +2 ed il suo figlio destro un coefficiente di bilanciamento uguale a +1 o 0.

Rotazione a destra[modifica | modifica sorgente]

Si esegue quando un nodo ha un coefficiente di bilanciamento di -2 e il suo figlio sinistro un coefficiente di bilanciamento uguale a -1 o 0.

Doppia rotazione[modifica | modifica sorgente]

Un esempio di doppia rotazione (sinistra destra)

Sinistra-Destra[modifica | modifica sorgente]

Si esegue quando un nodo ha un coefficiente di bilanciamento di -2 e il suo figlio sinistro un coefficiente di bilanciamento uguale a +1.

Destra-Sinistra[modifica | modifica sorgente]

Si esegue quando un nodo ha un coefficiente di bilanciamento di +2 e il suo figlio destro un coefficiente di bilanciamento uguale a -1

Operazioni[modifica | modifica sorgente]

Ricerca[modifica | modifica sorgente]

La ricerca di un elemento in un albero AVL si svolge come quella negli alberi binari di ricerca.

Inserimento[modifica | modifica sorgente]

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. L'algoritmo quindi aggiorna i coefficienti di bilanciamento e controlla se sul percorso dal nuovo nodo alla radice ci siano nodi dove la condizione di bilanciamento non è soddisfatta. In questo caso viene applicata una serie di rotazioni che ripristina tale invariante.

Eliminazione[modifica | modifica sorgente]

Anche qui, si cerca l'elemento da eliminare come negli alberi binari di ricerca. Se l'elemento non è presente, non bisogna fare niente. Se è una foglia o ha un solo figlio, il nodo viene rimosso e l'unico figlio agganciato al padre del nodo rimosso; altrimenti si sostituisce il nodo con una foglia che ne costituisce il suo diretto predecessore o successore[1]. A questo punto le condizioni di bilanciamento non sono più garantite sul percorso che va dalla radice al nodo rimosso fino eventualmente alla foglia che lo ha sostituito; l'algoritmo quindi procede ripristinando il bilanciamento su questi nodi tramite una serie di rotazioni.

Voci correlate[modifica | modifica sorgente]

Richiami[modifica | modifica sorgente]

  • G. Adelson-Velskii and E.M. Landis, "Odin algoritm organizacii informacii" Doklady Akademii Nauk SSSR, 146:263–266, 1962 (russo)

Note[modifica | modifica sorgente]

  1. ^ La scelta dell'uno o dell'altro è indifferente.

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]