Provar que uma árvore binária tem no máximo

Estou tentando provar que uma árvore binária com nós tem no máximo leaves. Como eu faria isso com indução?$n$$\left\lceil \frac{n}{2} \right\rceil$

Para as pessoas que estavam seguindo a pergunta original sobre pilhas, ela foi movida para aqui .

Suponho agora que a pergunta seja a seguinte:

Dada uma árvore binária com nós, prove que ela contém no máximo leaves.⌈ $n$$\left\lceil \frac{n}{2} \right\rceil$

Vamos trabalhar com a definição de árvore . Para árvore tal, vamos o número de nós em e o número de folhas em .T N T T G T$\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$$T$$n_T$$T$$l_T$$T$

Você está correto ao fazer isso por indução, mas precisará de indução estrutural que segue a estrutura em árvore. Para as árvores, isso geralmente é feito como uma indução completa sobre a altura das árvores.$h(T)$

A âncora de indução possui duas partes. Primeiro, para , temos T = E m p t y com l T = n T = 0 ; a reivindicação claramente vale para a árvore vazia. Para h ( t ) = 1 , isto é, T = L um e um f , que têm semelhante l T = 1 = ⌈ n $h(t)=0$$T=\mathrm{Empty}$$l_T=n_T=0$$h(t)=1$$T = \mathrm{Leaf}$, então a reivindicação é válida para folhas.$l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$

A hipótese de indução é: Suponha que a reivindicação seja válida para todas as árvores (binárias) com h ( T ) ≤ k , k ≥ 1 arbitrário, mas fixo.$T$$h(T)\leq k$$k\geq 1$

Para a etapa indutiva, considere uma árvore binária arbitrária com h ( T ) = k + 1 . Como k ≥ 1 , T = N o d e ( L , R ) e n t = n L + n R + 1 . Como L e R também são árvores binárias (caso contrário, T não seria) e h ( L ) , h $T$$h(T)=k+1$$k\geq 1$$T=\mathrm{Node}(L,R)$$n_T = n_L+ n_R+1$$L$$R$$T$ , a hipótese de indução se aplica e tem$h(L),h(R)\leq k$

$\qquad \displaystyle l_L \leq \left\lceil \frac{n_L}{2} \right\rceil \text{ and } l_R \leq \left\lceil \frac{n_R}{2} \right\rceil.$

Como todas as folhas de estão em L ou R , temos que$T$$L$$R$

$\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*}$

A desigualdade marcado com pode ser verificada por (quatro vias) caso distinção sobre se n G , N R ∈ 2 N . Pelo poder da indução, isso conclui a prova.$(*)$$n_L,n_R\in 2\mathbb{N}$

Como exercício, você pode usar a mesma técnica para provar as seguintes afirmações:

• Toda árvore binária perfeita de altura tem 2 h - 1 nós.$h$$2^h-1$
• Toda árvore binária completa possui um número ímpar de nós.

Estou um pouco confuso com a pergunta. Se você está interessado em árvores com grau máximo de , que é o que a Wikipedia diz que deseja, encontramos o problema de que uma única aresta tem n = 2 nós en = 2 folhas, mas n / 2 = 1 . Enfim, aqui está algo próximo que tem um argumento fácil. $3$$n=2$$n=2$$n/2 = 1$

Seja uma árvore com n nós e L folhas. Como T é uma árvore, existem n - 1 arestas, e as conta duas vezes, vemos que 2 n - 2 ≤ L + 3 ( n - L ) que diz que 2 L ≤ n + 2 e isso é apertado nas duas Exemplo -vertex acima. Eu acho que se você quiser assumir que existe uma raiz de grau dois en = 3 , então você pode refinar esse argumento para dar 2 $T$$n$$L$$T$$n-1$