Esercizio 10albero binario bilanciato

Idea

Per il nodo $v$ servono: (1) $T_L$ e $T_R$ bilanciati, (2) $\lvert h(T_L) - h(T_R) \rvert \le 1$ (il valore assoluto, Valore assoluto (modulo)Il valore assoluto è la distanza di un numero da zero: definizione, proprietà, disuguaglianza triangolare e disequazioni con i moduli.Valore assoluto (modulo) →, perché non si sa quale dei due sottoalberi sia più alto). Un albero bilanciato in questo senso ha altezza $O(\log n)$ (è la condizione degli alberi AVL, citati in Alberi binari di ricercaAlbero binario di ricerca come albero binario proprio con entry nei nodi interni e foglie vuote; inorder crescente; TreeSearch; get, put e remove (due casi, con predecessore inorder) in Theta(h); altezza fino a n-1; esempi di inserimenti; alberi aumentati con campi size e max e algoritmi di conteggio e interrogazione in O(h).Alberi binari di ricerca →). L'altezza dei figli è l'informazione extra suggerita: se ogni chiamata la restituisce insieme al booleano, il padre non deve ricalcolarla. Si usa la convenzione: altezza di un sottoalbero vuoto $= -1$, altezza di una foglia $= 0$ (vedi AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).Alberi →). È un postorder.

(a) Pseudocodice

Algoritmo isBalanced(T)
Input: albero binario T (eventualmente vuoto)
Output: true se T è bilanciato, false altrimenti
return check(T.root())[0]

Algoritmo check(v)
Input: nodo v oppure null (sottoalbero vuoto)
Output: coppia (balanced, height): balanced = T_v bilanciato; height = altezza di T_v
        (se balanced = false il valore di height è irrilevante)
if v = null then return (true, -1)
(bL, hL) <- check(left(v))
if bL = false then return (false, 0)
(bR, hR) <- check(right(v))
if bR = false then return (false, 0)
if |hL - hR| > 1 then return (false, 0)
return (true, 1 + max(hL, hR))

Il controllo anticipato (return (false, 0) appena un sottoalbero è sbilanciato) non cambia la complessità asintotica: la risposta false si propaga fino alla radice senza ulteriori calcoli.

Correttezza (induzione sull'altezza). Sottoalbero vuoto: bilanciato per definizione, altezza $-1$ ✓. Nodo $v$: per ipotesi induttiva check sui figli restituisce correttamente (bilanciato, altezza). $T_v$ è bilanciato se e solo se lo sono entrambi i figli e le altezze differiscono al più di $1$, che è esattamente ciò che si controlla; l'altezza di $v$ è $1 + \max(h_L, h_R)$ per definizione.

(b) Complessità

Ogni nodo (e ogni puntatore nullo) genera al più una chiamata di check: $n$ nodi più al più $n + 1$ sottoalberi vuoti. Il costo locale di una chiamata (confronti, un valore assoluto, un massimo, assegnazioni) è $\Theta(1)$, escluse le chiamate figlie. Quindi:

• Limite superiore: $O(n)$, perché il numero di chiamate è $\le 2n + 1$ e ognuna è $O(1)$.
• Limite inferiore: $\Omega(n)$ se l'albero è bilanciato (nessuna uscita anticipata: si visitano tutti i nodi, ognuno una volta), quindi nel caso pessimo la complessità è $\Theta(n)$. (Non si può fare meglio di $\Omega(n)$: per dire che un albero è bilanciato bisogna guardare tutti i nodi.)

Confronto con la soluzione ingenua (calcolare height ad ogni nodo e poi chiamarsi ricorsivamente sui figli): ogni height costa $\Theta(\lvert T_v \rvert)$ e il totale è $O(\sum_v \lvert T_v \rvert) = O(n \cdot h)$ (ogni nodo è contato una volta per ciascun antenato), cioè più di $\Theta(n)$ appena l'albero ha altezza non costante (in un albero bilanciato $O(n \log n)$). Esempio: in un albero perfetto di altezza $h$ ogni livello $i$ ha $2^i$ nodi ciascuno con un sottoalbero di dimensione circa $2^{h-i+1}$, quindi height chiamata su ogni nodo costa circa $2^h$ per livello, $h\cdot2^h\approx n\log_2 n$ in totale (SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →, Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →).

Esempio

Albero $A \to (B \to (D, E),\ C)$: check(D) $= (\text{true}, 0)$, check(E) $= (\text{true}, 0)$; in $B$: $\lvert 0 - 0 \rvert = 0 \le 1$, restituisce $(\text{true}, 1)$; check(C) $= (\text{true}, 0)$; in $A$: $\lvert 1 - 0 \rvert = 1 \le 1$, restituisce $(\text{true}, 2)$ $\Rightarrow$ bilanciato. Tabella dell'esempio bilanciato (altezza vuoto $=-1$):

Albero a catena $A \to B \to C$ (solo figli sinistri): in $C$ le altezze dei due vuoti sono $-1, -1$: $(\text{true}, 0)$; in $B$: $h_L = 0$, $h_R = -1$, differenza $1$: $(\text{true}, 1)$; in $A$: $h_L = 1$, $h_R = -1$, differenza $2 > 1$: $(\text{false}, 0)$ $\Rightarrow$ non bilanciato. (Controllato su 3000 alberi casuali confrontando con la definizione.)

Errori comuni

• Usare l'altezza $0$ per l'albero vuoto: confonde il vuoto con una foglia e fa dichiarare bilanciato un nodo con un solo figlio che a sua volta ha un figlio (altezze $1$ e $0$, differenza $1$), mentre le altezze corrette sono $1$ e $-1$ (differenza $2$).
• Controllare il bilanciamento solo alla radice: la definizione vale per ogni nodo.
• Calcolare height ad ogni nodo con una funzione separata: $O(n h)$.
• Non specificare input e output della procedura ausiliaria (richiesto dal testo).