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.

La coppia restituita ha lo stesso ruolo di quella di heightSum (somma, altezza): l'informazione richiesta (la foglia) non basta al padre, serve anche l'altezza. La ricorsione e la sua analisi sono quelle di Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →.

Correttezza (induzione sull'altezza, Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →). 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à.)

Un secondo esempio più profondo: radice $r$ con figlio sinistro $p$ (interno, con figli foglie $c$ e $d$) e figlio destro $q$ (interno, con figlio sinistro foglia $e$ e figlio destro $s$ interno con foglie $f$ e $g$). Dal basso: deepLeaf(f) $=(f,0)$, deepLeaf(g) $=(g,0)$, in $s$: $(g,1)$; deepLeaf(e) $=(e,0)$; in $q$: $h_L=0$, $h_R=1$, quindi $(g,2)$; in $p$: $(d,1)$; in $r$: $h_L=1$, $h_R=2$, si sceglie il destro: $(g,3)$. La foglia più profonda è $g$, a profondità $3$ (altezza dell'albero).

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.