Un albero AVL è una struttura dati autobilanciante basata sugli alberi di ricerca binaria. E’ stata la prima struttura dati inventata. Il suo nome deriva dai suoi inventori, G.M. Adelson-Velsky e E.M. Landis, fu pubblicato nella ricerca del 1962 intitolata “An algorithm for the organization of information” (un algoritmo per la ricerca delle informazioni).
In un albero AVL le altezze dei due sottoalberi figli di ogni nodo differiscono al massimo di un’ unita, quindi vengono anche detti “bilanciati in altezza”. La ricerca, l’inserimento di un nodo e la cancellazzione impiegano al massimo un tempo O(log n) sia nel caso medio sia in quello peggiore, n è il numero dei nodi dell’albero prima dell’operazione da effettuare.
Inserimenti e cancellazzioni di nodi possono richiedere il ribilanciamento dell’albero con una o più rotazioni.
Il fattore di equilibrio di un nodo è l’altezza del suo sottoalbero destro meno l’altezza del suo sottoalbero sinistro, un nodo con fattore di equlibrio 1,0 o -1 è considerato equilibrato. Un nodo con qualsiasi altro fattore è considerato sbilanciato e richiede il ribilanciamento dell’abero. Il fattore di equilibrio è memorizzato direttamente in ogni nodo oppure calcolato dall’altezza dei suoi sottoalberi figli.
Gli alberi AVL sono spesso paragonati agli alberi rosso- nero (red-black trees) perchè supportano lo stesso insieme di operazioni e perchè i “red-black trees” impiegano anchessi O(log n) per le operazioni di base. Gli alberi AVL risultano migliori rispetto ai cugini red-black nelle applicazioni che richiedono molte ricerche. Glia alberi di ricerca AVL vengono spesso illustrati in molti corsi universitari di algoritmi.
Vediamo le operazioni effettuabili in un albero di ricerca binaria bilanciato (AVL tree):
Ricerca. La ricerca di un elemento in un albero AVL si svolge come quella negli alberi binari di ricerca.
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. 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. 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. 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.
Rotazioni. Un nodo con il coefficiente di bilanciamento diverso da 1, 0 o -1 è considerato sbilanciato e viene ribilanciato grazie alle rotazioni (la rotazione è, in informatica, un procedimento attuato su un albero binario di ricerca per renderlo bilanciato senza intaccare le regole di ordinamento degli elementi o nodi dell’albero). La rotazione opera spostando volta per volta un nodo più sopra e un nodo più sotto nella struttura dell’albero. È usata per cambiare la forma dell’albero e in particolare per diminuirne l’altezza al fine di migliorare il bilanciamento dell’albero stesso. Ciò avviene spostando sottoalberi più piccoli in posizioni più basse e sottoalberi più grandi in posizioni più alte. I benefici di tale procedimento si avvertono in molte operazioni comuni negli alberi binari di ricerca (ad esempio inserimento e rimozione). Le regole di ordinamento sono: “assegnato il valore della radice e dato un nodo contenente un valore x da inserire nell’albero, se i nodi dell’albero contengono numeri le regole di ordinamento di un albero binario di ricerca sono le seguenti: si parte dalla radice e si va a sinistra se x è minore della radice e a destra se x è maggiore della radice. Effettuato questo passaggio, si procede allo stesso modo finché si incontra un nodo che non ha entrambi i figli. A quel punto si posiziona il nodo contenente il dato x e il processo termina.” Di Rotazioni ne esistono tre tipi:
Rotazione a sinistra. 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. 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 suddivisa a sua volta in:
Sinistra-Destra. 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. Si esegue quando un nodo ha un coefficiente di bilanciamento di +2 e il suo figlio destro un coefficiente di bilanciamento uguale a -1.