Alberi Avl

Visto che si avvicina il natale è una buona idea iniziare a preparare gli alberelli.
L’albero che ho addobbato è un albero Avl cioè una particolare struttura dati basata su un albero binario semplice ma con una caratteristica in più: la possibilità di ribilanciarsi dopo l’inserimento e la cancellazione di nodi.
Un albero bilanciato è un albero che ha un fattore di bilanciamento in valore assoluto minore o uguale a 1 per ogni nodo,vale a dire che la differenza tra l’altezza del sottoalbero sinistro e quella del sottoalbero destro rispetto al nodo si differenziano di al più una unità.

Questa caratteristica è utilissima perchè un tale albero presenta un’altezza al più logaritmica rispetto al numero dei nodi.
Con una tale struttura le operazioni di ricerca e quindi di inserimento e cancellazione presentano un costo

O(log(n))

rispetto al numero dei nodi.
L’albero Avl non è l’unico ad avere questa proprietà, vi sono anche gli alberi 2-3,i Btrees,i Red Black e tanti altri.

L’albero Avl si serve di rotazioni per ribilanciarsi.
Sostanzialmente viene effettuata una ricerca