Dimostrando un albero binario ha al massimo $ \ lceil n / 2 \ rceil $ foglie

Question

sto cercando di dimostrare che un albero binario con $ n $ nodi ha a la maggior parte dei $ \ left \ lceil \ frac {n} {2} \ right \ rceil $ foglie. Come potrei fare per fare questo con l'induzione?

Per le persone che seguivano nella domanda iniziale su cumuli, è stato spostato qui .

Answer 1

presumo ora che la domanda è la seguente:

Dato un albero binario con $ n $ nodi, dimostrare che esso contiene al massimo $ \ left \ lceil \ frac {n} {2} \ right \ rceil $ foglie.

Cerchiamo di lavorare con l'albero di definizione $ \ mathrm {Albero} = \ mathrm {vuoto} \ metà \ mathrm {Foglia} \ metà \ mathrm {Node} (\ mathrm {Albero}, \ mathrm {Albero}) $ . Per $ T $ tale albero, lasciate $ n_T $ il numero di nodi in $ T $ e $ l_T $ il numero di foglie in $ T $.

Hai ragione a farlo per induzione, ma sarà necessario strutturale di induzione che segue la struttura ad albero. Per gli alberi, questo è spesso fatto come induzione completo sul Altezza $ h (T) $ degli alberi.

L'ancora di induzione ha due parti. In primo luogo, per $ h (t) = 0 $ abbiamo $ T = \ mathrm {vuoto} $ con $ l_T = n_T = 0 $; la domanda tiene chiaramente per l'albero vuoto. Per $ h (t) = 1 $, vale a dire $ T = \ mathrm {Foglia} $, che allo stesso modo sono $ l_T = 1 = \ left \ lceil \ frac {n_T} {2} \ right \ rceil $, in modo che il reclamo vale per le foglie.

L'ipotesi di induzione è: Si supponga che l'affermazione vale per tutti (binario) alberi $ T $ con $ h (T) \ leq k $, $ k \ geq 1 $ arbitrario ma fisso

.

Per il passo induttivo, si consideri un albero binario arbitrario $ T $ con $ h (t) = k + 1 $. Come $ k \ geq 1 $, $ T = \ mathrm {Node} (L, R) $ e $ n_T = n_L + n_R + 1 $. Come $ L $ e $ R $ sono anche alberi binari (altrimenti $ T $ non sarebbe) e $ h (L), h (R) \ leq k $, vale ipotesi induttiva e Hai

$ \ qquad \ displaystyle l_l \ leq \ left \ lceil \ frac {n_L} {2} \ right \ rceil \ text {e} L_R \ leq \ left \ lceil \ frac {n_R} {2} \ right \ rceil. $

Come tutte le foglie di $ T $ sono o in $ L $ o $ R $, si ha che

$ \ qquad \ begin {* align} l_T & = l_l + L_R \\ & \ Leq \ left \ lceil \ frac {n_L} {2} \ right \ rceil + \ left \ lceil \ frac {n_R} {2} \ right \ rceil \\ & \ Leq \ left \ lceil \ frac {n_L + n_R + 1} {2} \ right \ rceil \ qquad (*) \\ & = \ Left \ lceil \ frac {n_T} {2} \ right \ rceil \ End {align *} $

La disuguaglianza contrassegnati con $ (*) $ può essere controllato da (a quattro vie) caso distinzione sul fatto $ n_L, n_R \ in 2 \ mathbb {N} $. Per il potere di induzione, questo conclude la dimostrazione.

---

Come esercizio, è possibile utilizzare la stessa tecnica per dimostrare le seguenti dichiarazioni:

• Ogni albero binario perfetto di altezza $ h $ ha $ di 2 ^ H-1 $ nodi.
• Ogni albero binario completo ha un numero dispari di nodi.

Answer 2

Sono un po 'confuso dalla domanda. Se siete interessati in alberi con grado al massimo di $ 3 $, che è ciò che Wikipedia dice che si desidera, poi ci imbattiamo nel problema che un singolo bordo ha $ n = 2 $ nodi e $ n = 2 $ foglie, ma $ n / 2 = 1 $. In ogni caso, qui è qualcosa di simile che ha un argomento facile.

Sia $ T $ un tale albero con $ n $ nodi e $ L $ foglie. Dal momento che $ T $ è un albero, ci sono $ n-1 $ bordi e fare doppio loro conteggio, vediamo che $$ 2n - 2 \ le L + 3 (n - L) $$ che dice che $$ 2L \ le n + 2 $$ e questo è stretto nell'esempio due vertici sopra. Credo che se si vuole assumere che non ci una radice di grado due e $ n \ ge 3 $, allora si può definire questa argomentazione per dare $$ 2L \ le n + 1 $$ che è quello che stai cercando, e questo è stretto quando l'albero è completo.