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). Il metodo è quello dell'induzione (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 →, Dimostrazioni, induzione e invariantiTecniche di dimostrazione (esempio, controesempio, assurdo), induzione con casi base multipli, invarianti di ciclo (inizializzazione, conservazione, uso alla fine), schema generale per provare la correttezza; esempi svolti su arrayMax, sequenza di bit e numeri di Fibonacci.Dimostrazioni, induzione e invarianti →): si dimostra il caso più piccolo (base) e si mostra che, se la proprietà vale per alberi più piccoli, vale per l'albero costruito aggiungendo una radice sopra due sottoalberi; il confronto tra potenze di $2$ usa 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 →. Piccoli casi per orientarsi (alberi propri di altezza $h$): $h=0$ una foglia ($m=1$); $h=1$ radice e due foglie ($m=2=2^1$); $h=2$ da $m=3$ (pettine) a $m=4$ (perfetto).

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$ (la seconda disuguaglianza perché $h_i\le h$ e la funzione $2^x$ è crescente). 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$ ✓. Controllo con $h=1$: radice con due foglie ha $m=2=h+1$; con $h=2$ il pettine (radice con una foglia e un sottoalbero di altezza $1$) ha $m=1+2=3=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 cammino ha $h+1$ nodi, e i fratelli fuori dal cammino sono altri $h$: uno per ognuno degli $h$ nodi interni del cammino).

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. L'"induzione forte" assume la proprietà per tutti gli alberi con meno nodi (non solo per quello con $n$ nodi), perché i sottoalberi $T_i$ hanno numeri di nodi diversi e non fissati. 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.