Che cos'è un albero AVL?

Ogni nodo di un albero AVL tiene traccia della propria altezza: il numero di archi sul percorso più lungo che porta a una foglia. Una foglia ha altezza 1 e un sottoalbero vuoto conta come altezza 0. Dall'altezza dei due figli di un nodo puoi calcolare il suo fattore di bilanciamento: height(left) - height(right).

Un nodo è bilanciato quando il suo fattore di bilanciamento è -1, 0 o 1. La regola dell'albero AVL è semplice: ogni singolo nodo deve rimanere bilanciato, sempre. Ogni volta che un inserimento o un'eliminazione porta il fattore di bilanciamento di un nodo a 2 o -2, l'albero esegue una rotazione: un riarrangiamento locale di alcuni puntatori che ripristina il bilanciamento in tempo costante senza compromettere l'ordinamento dell'albero di ricerca.

Esistono quattro casi di rotazione (sinistra-sinistra, destra-destra, sinistra-destra, destra-sinistra), ma si riducono tutti a due elementi di base: una singola rotazione a sinistra e una singola rotazione a destra. Costruirai entrambe da zero nelle prossime lezioni.