<aside> ℹ️

Un albero è bilanciato in altezza se le altezze dei sottoalberi sinistro e destro di ogni suo nodo differiscono al più di uno

</aside>

<aside> ℹ️

Il fattore di bilanciamento $\beta(v)$ di un nodo $v$ è la differenza tra l’altezza del suo sottoalbero sinistro e quella del suo sottoalbero destro

$$ \beta (v)=altezza[left[v]]-altezza[right[v]] $$

</aside>

Il fattore di bilanciamento è tanto migliore quanto più piccolo è il suo valore assoluto

• alberi completi: il fattore di bilanciamento di ogni nodo è 0
• alberi bilanciati (AVL): $|\beta(v)|\le 1$ per ogni nodo $v$
• alberi degenerati in una lista: il fattore di bilanciamento è uguale all’altezza dell’albero, $\beta(root)=h=n-1$ dove $n$ è il numero di nodi dell’albero

<aside> ℹ️

Un albero è bilanciato in altezza se, per ogni nodo $v$, $|\beta(v)|\le 1$

</aside>

Altezza → $h=\Theta(log_2n)$

• $n\le 2^{h+1}-1$, cioè il numero di nodi di un albero AVL è minore del numero di nodi di un albero binario completo di altezza $h$, pertanto fornisce un limite inferiore al numero di nodi di albero di altezza $h$.
• $n\ge N(h)$, dove $N(h)$ denota il minimo numero di nodi che un albero bilanciato di altezza $h$ deve avere (limite superiore al valore di $h)$

Rotazioni

Gli alberi binari consentono la ricerca di un dato elemento in un tempo logaritmico

<aside> ⚠️

Problema: l’inserimento o la cancellazione di un nodo potrebbero far perdere il bilanciamento di un albero AVL

</aside>

Il bilanciamento deve essere ripristinato attraverso delle opportune operazioni sui nodi: rotazioni

• Rotazioni SS: inserimento a sinistra nel sottoalbero sinistro
• Rotazioni SD: inserimento a sinistra nel sottoalbero destro
• Rotazioni DD: inserimento a destra nel sottoalbero destro
• Rotazioni DS: inserimento a destra nel sottoalbero sinistro