Esercizio 7dimostrazioni sulle foglie di un albero binario proprio

---

Richiami

Un albero binario è proprio se ogni nodo interno ha esattamente due figli (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 →). L'altezza di un nodo è $0$ per le foglie e $1 + \max$ delle altezze dei figli altrimenti. La relazione nota: il numero di nodi interni è $n - m = m - 1$ (le foglie sono una in più dei nodi interni).

1. $m \le 2^h$

Induzione sull'altezza $h \ge 0$. Si fissa la proprietà $P(h)$: ogni albero binario proprio di altezza $h$ ha al più $2^h$ foglie.

• Base $h = 0$: l'albero è una sola foglia (la radice), $m = 1 = 2^0$ ✓.
• Passo. Sia $h \ge 0$ e si assuma $P(h')$ per ogni $h' \le h$. Sia $T$ di altezza $h + 1 \ge 1$: la radice è un nodo interno con sottoalberi propri $T_1, T_2$ di altezze $h_1, h_2$, con $h + 1 = \max\{h_1, h_2\} + 1$, quindi $h_1, h_2 \le h$. Per ipotesi induttiva $m_1 \le 2^{h_1} \le 2^h$ e $m_2 \le 2^{h_2} \le 2^h$. Le foglie di $T$ sono quelle di $T_1$ e $T_2$, quindi $m = m_1 + m_2 \le 2 \cdot 2^h = 2^{h+1}$ ✓.

2. $m \ge h + 1$

Induzione sull'altezza. $P(h)$: ogni albero proprio di altezza $h$ ha almeno $h + 1$ foglie.

• Base $h = 0$: $m = 1 = h + 1$ ✓.
• Passo. $T$ di altezza $h + 1$ con sottoalberi $T_1, T_2$: uno dei due, diciamo $T_1$, ha altezza esattamente $h$ (perché $h + 1 = \max\{h_1, h_2\} + 1$). Per ipotesi $m_1 \ge h + 1$. Il sottoalbero $T_2$, essendo non vuoto, ha almeno una foglia, $m_2 \ge 1$. Quindi $m = m_1 + m_2 \ge (h + 1) + 1 = h + 2$, che è il valore richiesto per l'altezza $h + 1$ ✓.

3. $n \ge 2h + 1$

Dalla relazione nota, il numero di nodi interni è $n - m = m - 1$, quindi $n = 2m - 1$. Con il punto 2: $n = 2m - 1 \ge 2(h + 1) - 1 = 2h + 1$. $\square$

Dimostrazione diretta alternativa. Un cammino dalla radice a una foglia di profondità $h$ contiene $h$ nodi interni e una foglia. Ogni nodo interno ha due figli, e uno solo sta sul cammino: l'altro è un nodo fuori dal cammino, e questi $h$ nodi sono tutti distinti. Quindi $n \ge (h + 1) + h = 2h + 1$.

Il limite è raggiunto da un albero "a pettine" in cui ogni nodo interno ha una foglia come figlio (esempio: $h = 4$, $m = 5$, $n = 9$).

4. Altezza e massima profondità delle foglie (albero qualsiasi)

Induzione su $n \ge 1$. Si usa l'induzione "forte": $P(n)$ vale se per ogni albero con $n$ nodi $\text{height}(T) = \max_{f \text{ foglia}} \text{depth}(f)$.

• Base $n = 1$: la sola radice è anche l'unica foglia, altezza $0$ e profondità $0$ ✓.
• Passo. $T$ con $n + 1 \ge 2$ nodi ha radice $r$ con $k \ge 1$ figli e sottoalberi $T_1, \dots, T_k$ con meno di $n + 1$ nodi ciascuno. Le foglie di $T$ sono le foglie dei $T_i$ e per ognuna $\text{depth}_T(f) = 1 + \text{depth}_{T_i}(f)$. Per ipotesi induttiva la massima profondità delle foglie di $T_i$ in $T_i$ è $\text{height}(T_i)$. Quindi $\max_f \text{depth}_T(f) = 1 + \max_i \text{height}(T_i) = \text{height}(r) = \text{height}(T)$ per definizione di altezza ✓.

Errori comuni

• Nella base mettere $h = 1$ senza dimostrare il caso $h = 0$.
• Nel passo scrivere $m = 2 \cdot 2^h$ senza specificare che le due altezze sono $\le h$ (non necessariamente uguali).
• Nel punto 2 dimenticare di usare che un sottoalbero ha altezza esattamente $h$ (serve per applicare l'ipotesi con $h + 1$ foglie).
• Applicare le relazioni ad alberi non propri.