Introduzione

Un albero di ricerca binario mantiene i valori ordinati: il sottoalbero sinistro di ogni nodo contiene valori più piccoli, mentre quello destro contiene valori più grandi. Questo ordinamento rende la ricerca veloce, ma solo se l’albero rimane più o meno bilanciato. Se inserisci valori in ordine in un normale albero di ricerca binario, questo degenera in una linea retta, trasformando ogni ricerca in una lenta scansione lineare.

Un albero AVL risolve il problema mantenendosi bilanciato automaticamente. Dopo ogni inserimento o eliminazione, controlla se un nodo è diventato sbilanciato e, in tal caso, esegue una piccola correzione locale chiamata rotazione per ripristinare l’equilibrio. Indipendentemente da come lo costruisci, un albero AVL non degenera mai in una linea.

In questo corso costruirai da zero un albero AVL nel linguaggio che preferisci: nodi con un’altezza registrata, controlli del bilanciamento, i quattro casi di rotazione e un inserimento e un’eliminazione con bilanciamento automatico. Poi userai la classe completata per risolvere una serie di sfide pratiche.