Esercizio 9foglia più profonda di un albero binario proprio

Idea

Il suggerimento del testo: l'altezza di $T_v$ è la massima profondità delle sue foglie (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 →). Quindi la foglia più profonda di $T_v$ è, tra le foglie più profonde dei due sottoalberi figli, quella del sottoalbero più alto. Per decidere serve conoscere l'altezza dei due figli: si restituisce una coppia (foglia, altezza), come in heightSum (vedi Alberi binariAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.Alberi binari →): conviene calcolare un'informazione più ricca di quella richiesta. È una visita in postorder.

(a) Pseudocodice

Algoritmo deepLeaf(T, v)
Input: albero binario proprio T, nodo v di T
Output: coppia (w, h) con w = una foglia più profonda di T_v e h = altezza di T_v
if T.isExternal(v) then return (v, 0)
(wL, hL) <- deepLeaf(T, T.left(v))
(wR, hR) <- deepLeaf(T, T.right(v))
if hL > hR then return (wL, hL + 1)
else return (wR, hR + 1)

Chiamata: (w, h) <- deepLeaf(T, T.root()); $w$ è la foglia cercata e $h$ l'altezza dell'albero.

Correttezza (induzione sull'altezza). Foglia: l'unica foglia di $T_v$ è $v$ stesso, a profondità $0$ = altezza. Nodo interno: le foglie di $T_v$ sono quelle di $T_L$ e $T_R$ con profondità aumentata di $1$ rispetto ai sottoalberi; per ipotesi $w_L$ e $w_R$ sono le più profonde nei rispettivi sottoalberi, quindi la più profonda di $T_v$ è quella con altezza maggiore, a profondità $1 + \max(h_L, h_R)$ in $T_v$, che è l'altezza di $v$.

(b) Complessità

L'albero della ricorsione ha esattamente un nodo per ogni nodo di $T$; ogni chiamata, escluse le figlie, fa un numero costante di operazioni (un test, un confronto, una coppia restituita). Dunque $$t(n) \in \Theta(n),$$ come una visita in postorder in cui la visita di un nodo costa $\Theta(1)$.

Esempio

Albero: radice $r$ con figli $x$ e $y$; $x$ ha figli (foglie) $a$ e $b$; $y$ è foglia. deepLeaf(a) $= (a, 0)$, deepLeaf(b) $= (b, 0)$; in $x$: $h_L = 0 \not> h_R = 0$, quindi si restituisce $(b, 1)$ (con la parità si sceglie il destro; si poteva scegliere $a$, che è ugualmente profonda). deepLeaf(y) $= (y, 0)$. In $r$: $h_L = 1 > h_R = 0$, quindi $(b, 2)$: la foglia più profonda è $b$, a profondità $2$. (Controllato su 500 alberi casuali: profondità della foglia restituita = massima profondità.)

Alternative (peggiori)

• Calcolare la profondità di ogni foglia con depth (risalendo dalla foglia) e scegliere la massima: corretto, ma ogni depth costa $\Theta(\text{depth})$ e nel caso peggiore il totale è $\Omega(n^2)$ (vedi heightBad in 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 →).
• Memorizzare in ogni nodo un campo v.height e poi cercare la foglia: due visite, ancora $\Theta(n)$ ma più codice.

Errori comuni

• Restituire solo la foglia: senza l'altezza il padre non può confrontare i due figli, e si finisce a ricalcolare le altezze (quadratico).
• Restituire solo l'altezza: si risponde a un problema diverso.
• Scrivere hL >= hR e hL > hR indifferentemente ma non indicare cosa succede alla parità: il testo accetta una qualsiasi delle foglie più profonde, va però dichiarato.