Probar un árbol binario tiene como máximo

Estoy tratando de demostrar que un árbol binario con nodos tiene como máximo hojas. ¿Cómo haría para hacer esto con inducción?$n$$\left\lceil \frac{n}{2} \right\rceil$

Para las personas que seguían la pregunta original sobre montones, se ha movido aquí .

Supongo ahora que la pregunta es la siguiente:

Dado un árbol binario con nodos, demuestre que contiene como máximo ⌈ $n$$\left\lceil \frac{n}{2} \right\rceil$ hojas.

Trabajemos con la definición de árbol . Para T tal árbol, deje n T el número de nodos en T y l T el número de hojas en$\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$$T$$n_T$$T$$l_T$ .$T$

Es correcto hacer esto por inducción, pero necesitará una inducción estructural que siga la estructura del árbol. Para los árboles, esto a menudo se realiza como una inducción completa sobre la altura de los árboles.$h(T)$

El ancla de inducción tiene dos partes. Primero, para tenemos T = E m p t y con l T = n T = 0 ; el reclamo se cumple claramente para el árbol vacío. Para h ( t ) = 1 , es decir, T = L e a f , también tenemos l T = 1 = ⌈ n $h(t)=0$$T=\mathrm{Empty}$$l_T=n_T=0$$h(t)=1$$T = \mathrm{Leaf}$, por lo que el reclamo es válido para las hojas.$l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$

La hipótesis de inducción es: Suponga que la afirmación es válida para todos los árboles (binarios) con h ( T ) ≤ k , k ≥ 1 arbitraria pero fija.$T$$h(T)\leq k$$k\geq 1$

Para el paso inductivo, considere un árbol binario arbitrario con h ( T ) = k + 1 . Como k ≥ 1 , T = N o d e ( L , R ) y n T = n L + n R + 1 . Como L y R también son árboles binarios (de lo contrario, T no lo sería) y 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$ , la hipótesis de inducción se aplica y tiene$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 las hojas de están en L o R , tenemos 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*}$

La desigualdad marcado con se puede comprobar (de cuatro vías) distinción caso sobre si n L , n R ∈ 2 N . Por el poder de la inducción, esto concluye la prueba.$(*)$$n_L,n_R\in 2\mathbb{N}$

Como ejercicio, puede usar la misma técnica para probar las siguientes afirmaciones:

• Cada árbol binario perfecto de altura tiene 2 h - 1 nodos.$h$$2^h-1$
• Cada árbol binario completo tiene un número impar de nodos.

Estoy un poco confundido por la pregunta. Si está interesado en árboles con un grado máximo de , que es lo que Wikipedia dice que quiere, entonces nos encontramos con el problema de que un solo borde tiene n = 2 nodos yn = 2 hojas, pero n / 2 = 1 . De todos modos, aquí hay algo cercano que tiene un argumento fácil. $3$$n=2$$n=2$$n/2 = 1$

Deje que sea ​​tal árbol con n nodos y L hojas. Como T es un árbol, hay n - 1 aristas, y contando dos veces, vemos que 2 n - 2 ≤ L + 3 ( n - L ) que dice que 2 L ≤ n + 2 y esto es apretado en los dos -vertex ejemplo anterior. Supongo que si quieres asumir que hay una raíz de grado dos yn ≥ 3 , entonces puedes refinar este argumento para dar 2 $T$$n$$L$$T$$n-1$