Alberi AVL: Definizione Corretta, Meccanismo di Auto-bilanciamento e Usi

AVL sta per Adelson-Velsky e Landis — i matematici sovietici che inventarono questo albero binario di ricerca auto-bilanciante nel 1962. Non sta per "Adaptive Variable-Length."

Come Funzionano gli Alberi AVL

• Ogni nodo memorizza un fattore di bilanciamento = altezza(sottoalbero sinistro) – altezza(sottoalbero destro).
• Fattori di bilanciamento ammessi: –1, 0, +1.
• Dopo inserimento/cancellazione, rotazioni (singole/doppie) ripristinano il bilanciamento in tempo O(log n).

Proprietà Chiave

• Altezza sempre O(log n) → ricerca, inserimento, cancellazione garantiti O(log n).
• Più strettamente bilanciati degli alberi rosso-neri → ricerche più veloci, scritture leggermente più lente.

Applicazioni Comuni

• Database e indici in-memory
• Tabelle simboli compilatori
• Sistemi real-time che richiedono latenza prevedibile