4.1 Problemi degli alberi sbilanciati
Con gli alberi normali (sbilanciati) durante l'aggiunta di elementi possono verificarsi effetti indesiderati.
1. Aumento dell'altezza dell'albero:
Negli alberi sbilanciati l'altezza può raggiungere n (dove n è il numero di nodi), il che porta a una degrado delle prestazioni.
Il tempo di esecuzione delle operazioni principali (ricerca, inserimento, eliminazione) nel peggior caso diventa O(n).
2. Distribuzione non uniforme dei nodi:
Negli alberi sbilanciati alcuni sottoalberi possono contenere significativamente più nodi di altri, il che porta a un utilizzo inefficiente della memoria e all'aumento del tempo di elaborazione.
3. Peggioramento del tempo di esecuzione delle operazioni:
Negli alberi sbilanciati le operazioni di ricerca, inserimento e eliminazione richiedono più tempo a causa dell'aumentata altezza dell'albero.
Esempio di albero sbilanciato:
In questo esempio l'albero di fatto si trasforma in una lista collegata e il tempo di esecuzione delle operazioni diventa lineare.
4.2 Definizione di albero AVL e sue proprietà
Un albero AVL (chiamato così dai suoi inventori, Adel'son-Vel'skii e Landis) è un tipo di albero binario di ricerca bilanciato, in cui per ogni nodo la differenza delle altezze del suo sottoalbero sinistro e destro non supera 1.
Proprietà dell'albero AVL:
1. Bilanciamento:
La differenza delle altezze del sottoalbero sinistro e destro di ogni nodo non supera 1.
Questo assicura un'altezza dell'albero di O(log n), dove n è il numero di nodi, garantendo un'esecuzione efficiente delle operazioni di ricerca, inserimento e eliminazione.
2. Albero binario di ricerca:
L'albero AVL possiede tutte le proprietà dell'albero binario di ricerca: per ogni nodo tutte le chiavi nel suo sottoalbero sinistro sono minori della chiave del nodo, e tutte le chiavi nel suo sottoalbero destro sono maggiori della chiave del nodo.
3. Bilanciamento automatico:
Dopo ogni operazione di inserimento o eliminazione viene eseguito un bilanciamento dell'albero per mantenerne le proprietà.
4.3 Esempi di bilanciamento degli alberi
Le rotazioni sono operazioni che vengono eseguite per ripristinare l'equilibrio in un albero AVL dopo l'inserimento o l'eliminazione di nodi. Esistono quattro tipi di rotazioni: sinistra, destra, sinistra-destra e destra-sinistra.
1. Rotazione a sinistra (Left Rotation):
Nella rotazione a sinistra il nodo x viene spostato verso l'alto e il suo nodo figlio destro y diventa il suo genitore. Il sottoalbero sinistro di y diventa il sottoalbero destro di x.
2. Rotazione a destra (Right Rotation):
Nella rotazione a destra il nodo x viene spostato verso l'alto e il suo nodo figlio sinistro y diventa il suo genitore. Il sottoalbero destro di y diventa il sottoalbero sinistro di x.
3. Rotazione sinistra-destra (Left-Right Rotation):
Si esegue prima una rotazione a sinistra sul nodo figlio sinistro, e poi una rotazione a destra sul nodo stesso.
4. Rotazione destra-sinistra (Right-Left Rotation):
Si esegue prima una rotazione a destra sul nodo figlio destro, e poi una rotazione a sinistra sul nodo stesso.
4.4 Operazioni principali negli alberi AVL
Le operazioni principali negli alberi AVL comprendono l'inserimento, l'eliminazione e la ricerca.
Inserimento (Insertion)
È necessario inserire un nuovo nodo nell'albero AVL e bilanciarlo, se necessario.
Passaggi:
- Inserimento del nodo:
- Si inizia dalla radice dell'albero e ricorsivamente si trova il posto giusto per il nuovo nodo, confrontando il suo valore con i nodi esistenti.
- Si inserisce il nuovo nodo nel posto trovato, come in un normale albero binario di ricerca.
- Aggiornamento delle altezze:
- Dopo l'inserimento si aggiornano le altezze di tutti i nodi lungo il percorso dal nuovo nodo alla radice.
- Bilanciamento dell'albero:
- Si controlla il bilanciamento di ogni nodo lungo il percorso dal nuovo nodo alla radice.
- Se il bilanciamento di un qualsiasi nodo è compromesso (la differenza di altezza tra il sottoalbero sinistro e destro è maggiore di 1), si esegue la rotazione appropriata per ripristinare il bilanciamento.
Esempio:
2. Eliminazione (Deletion)
È necessario eliminare un nodo dall'albero AVL e bilanciarlo, se necessario.
Passaggi:
1. Ricerca e eliminazione del nodo:
- Si inizia dalla radice dell'albero e ricorsivamente si trova il nodo da eliminare.
- Si elimina il nodo come in un normale albero binario di ricerca:
- Se il nodo è una foglia, basta eliminarlo.
- Se il nodo ha un figlio, si sostituisce il nodo con il suo figlio.
- Se il nodo ha due figli, si trova il nodo più piccolo nel sottoalbero destro (o il più grande nel sinistro), si copia il suo valore nel nodo da eliminare e si elimina ricorsivamente il nodo più piccolo nel sottoalbero destro.
2. Aggiornamento delle altezze:
- Dopo l'eliminazione si aggiornano le altezze di tutti i nodi lungo il percorso dal nodo eliminato alla radice.
3. Bilanciamento dell'albero:
- Si controlla il bilanciamento di ogni nodo lungo il percorso dal nodo eliminato alla radice.
- Se il bilanciamento di un qualsiasi nodo è compromesso, si esegue la rotazione appropriata per ripristinare il bilanciamento.
Esempio:
3. Ricerca (Search)
È necessario trovare un nodo con un valore specifico nell'albero AVL.
Passaggi:
1. Ricerca ricorsiva:
- Si inizia dalla radice dell'albero e ricorsivamente si confronta il valore cercato con i nodi esistenti.
- Se il valore è minore del nodo corrente, si passa al sottoalbero sinistro.
- Se il valore è maggiore del nodo corrente, si passa al sottoalbero destro.
- Se il valore corrisponde al nodo corrente, si ritorna questo nodo.
Esempio:
GO TO FULL VERSION