Esercizio 11massimo beneficio lungo un cammino radice-foglia

Richiami

Visita ricorsiva in postorder: il risultato di un nodo dipende da quello dei figli (vedi Visite di alberiVisite in preorder e postorder come schemi generali (template) da adattare; complessità Theta(n + somma dei costi di visita) perché la somma dei figli è n-1; esempi (indice di un libro, spazio occupato in un file system); profondità con il preorder, altezza con il postorder; antenato comune più basso.Visite di alberi → e 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 →).

(a) Idea

Il miglior piano che parte da un nodo $v$ prende il valore di $v$ e poi sceglie il sottoalbero migliore tra i due. Se $v$ è una foglia, c'è un solo piano e vale v.value. Quindi, indicando con $B(v)$ il massimo beneficio dei cammini da $v$ a una foglia di $T_v$:

$$B(v) = \begin{cases} v.\text{value} & v \text{ foglia} \\ v.\text{value} + \max\{B(\text{left}(v)),\, B(\text{right}(v))\} & \text{altrimenti.} \end{cases}$$

Si noti che non basta sommare i valori positivi: il cammino deve arrivare a una foglia, anche attraversando valori negativi.

Esempio: radice $5$, figli $2$ e $7$; $2$ ha figli (foglie) $4$ e $1$; $7$ ha figli (foglie) $3$ e $-2$. I quattro piani valgono $5+2+4 = 11$, $5+2+1 = 8$, $5+7+3 = 15$, $5+7+(-2) = 10$. In basso: $B(2) = 2 + \max(4, 1) = 6$, $B(7) = 7 + \max(3, -2) = 10$; in radice $B = 5 + \max(6, 10) = 15$ ✓.

(b) Pseudocodice

Algoritmo bestClimatePlan(v)
Input: nodo v di un albero binario non vuoto; ogni nodo ha un campo intero value
Output: massimo, tra i cammini da v a una foglia di T_v, della somma dei value
if v è una foglia then return v.value
best <- -infinito
if v ha il figlio sinistro then best <- max(best, bestClimatePlan(left(v)))
if v ha il figlio destro  then best <- max(best, bestClimatePlan(right(v)))
return v.value + best

Chiamata: bestClimatePlan(root). (Se tutti i nodi interni hanno due figli, come nel testo, i due if sono sempre veri; la versione generale gestisce anche un solo figlio.)

Correttezza (induzione sull'altezza). Foglia: l'unico cammino ha somma v.value ✓. Nodo interno: ogni cammino da $v$ a una foglia è $v$ seguito da un cammino da un figlio a una foglia; la somma è v.value più la somma del sottocammino, quindi il massimo si ottiene con il massimo sottocammino di un figlio, che per ipotesi induttiva restituiscono le chiamate ricorsive.

(c) Complessità

È una visita in postorder: l'albero della ricorsione ha esattamente un nodo per ogni nodo di $T$ (ogni nodo è visitato una sola volta, indipendentemente dai valori) e il costo locale di ogni chiamata, escluse le figlie, è $\Theta(1)$ (confronti, un massimo, una somma). Quindi

$$t(n) \in O(n) \quad \text{e} \quad t(n) \in \Omega(n) \implies t(n) \in \Theta(n).$$

Non si può evitare di guardare tutti i nodi: un valore molto grande nascosto in una foglia qualsiasi può cambiare il risultato.

Errori comuni

• Sommare solo i valori positivi o fermarsi quando il beneficio parziale scende: un valore negativo può essere seguito da uno molto positivo.
• Scegliere ad ogni nodo il figlio col valore più grande (algoritmo greedy): sbagliato. Nell'esempio da $5$ il figlio $7 > 2$ è quello giusto, ma con foglie $3, -2$ sotto $7$ e $100, 100$ sotto $2$ la scelta golosa ($7$) darebbe $15$ contro $5 + 2 + 100 = 107$.
• Confondere il cammino fino a una foglia con un cammino qualunque dalla radice (il testo chiede la foglia).
• Restituire una struttura più complicata del necessario (ad esempio il cammino intero): l'output richiesto è il solo beneficio massimo.