Albero AVL

Questa voce o sezione sull'argomento informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

L'albero AVL è, in informatica, un albero binario di ricerca bilanciato in cui il coefficiente di bilanciamento per ciascun nodo vale 1, 0 oppure -1 (nel caso di un albero AVL completo tutti i coefficienti di bilanciamento sono uguali a 0).

Il nome AVL viene dai suoi inventori Adelson-Velskij e Landis, che pubblicarono il loro algoritmo nel saggio in russo "Odin algoritm organizacii informacii" ("un algoritmo di organizzazione dell'informazione") del 1962.

Viene definito il coefficiente di bilanciamento come la differenza tra le altezze, rispettivamente, del sottoalbero sinistro e del sottoalbero destro di un nodo:

${\textstyle b(n)=h(n.l)-h(n.r)}$

dove ${\displaystyle n}$ è il nodo di cui si vuole calcolare il coefficiente e ${\displaystyle n.l}$ e ${\displaystyle n.r}$ sono rispettivamente il figlio sinistro e il figlio destro di ${\displaystyle n}$.

${\displaystyle b(n)}$ può quindi assumere solo valori interi sia positivi che negativi.

La condizione per tenere l'albero bilanciato è semplice: per ogni nodo dell'albero, la differenza di altezza dei suoi sottoalberi figli deve differire al massimo di uno ( ${\displaystyle |b(n)|\leq 1}$ ). Grazie a questa restrizione, l'altezza massima dell'albero, ossia la più grande distanza tra la radice e le foglie, è logaritmica nel numero dei nodi. È per questo che questa struttura di dati permette di compiere l'inserimento, la ricerca e l'eliminazione di un elemento in O(log n). Inoltre se si considerano i costi ammortizzati di una serie di inserzioni, questi sono O(1).

Per evitare di dover contare ogni volta l'altezza di un sottoalbero, si salva nel nodo il coefficiente di bilanciamento di un nodo, che è definito come la differenza tra l'altezza del sottoalbero sinistro e quella del sottoalbero destro del nodo considerato.