Demostrando un árbol binario tiene como máximo $ \ lceil n / 2 \ rceil $ hojas

Question

Estoy tratando de probar que un binaria árbol con $ n $ nodos tiene por lo la mayoría de los $ \ left \ lceil \ frac {n} {2} \ right \ rceil hojas $. ¿Cómo voy a ir haciendo esto con la inducción?

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

Answer 1

Asumo ahora que la cuestión es la siguiente:

Dado un árbol binario con $ n $ nodos, prueba que contiene a lo sumo $ \ left \ lceil \ frac {n} {2} \ right \ rceil $ hojas.

Vamos a trabajar con el árbol de definición $ \ mathrm {Árbol} = \ mathrm {Vacío} \ mid \ mathrm {Hoja} \ mid \ mathrm {nodo} (\ mathrm {Árbol}, \ mathrm {Árbol}) $ . Por $ T $ tal árbol, dejó $ $ n_T el número de nodos en $ T $ y $ $ l_T el número de hojas en $ T $.

Estás correcta de hacer esto por inducción, pero se necesita estructural inducción que sigue la estructura de árbol. Para los árboles, esto se hace a menudo como la inducción completa sobre el altura $ h (t) $ de los árboles.

El ancla de inducción tiene dos partes. En primer lugar, por $ h (t) = 0 tenemos $ $ T = \ mathrm {Vacío} $ con $ l_T = n_T = 0 $; la reclamación tiene claramente para el árbol vacío. Por $ h (t) = 1 $, es decir, $ T = \ mathrm {Hoja} $, que de manera similar tenemos $ l_T = 1 = \ left \ lceil \ frac {n_T} {2} \ right \ rceil $, por lo que la reclamación se cumple para las hojas.

La hipótesis de inducción es: Supongamos que la reclamación se mantiene para todos (binario) árboles $ T $ con $ h (T) \ leq k $, $ k \ geq 1 $ arbitrario pero fijo

.

Para la etapa inductiva, considere un árbol binario arbitrario $ T $ con $ h (T) = k + 1 $. Como $ k \ geq 1 $, $ T = \ mathrm {Node} (L, R) $ y $ n_T = n_L + n_R + 1 $. Como $ L $ y $ R $ son también árboles binarios (de lo contrario $ T $ no sería) y $ h (L), H (R) \ leq k $, se aplica la hipótesis de inducción y tienen

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

Como todas las hojas de $ T $ son ya sea en $ L $ o $ R $, tenemos que

$ \ qquad \ begin {align *} l_T & = l_L + L_r \\ Y \ leq \ left \ lceil \ frac {n_L} {2} \ right \ rceil + \ left \ lceil \ frac {n_R} {2} \ right \ rceil \\ Y \ leq \ left \ lceil \ frac {+ n_L n_R + 1} {2} \ right \ rceil \ qquad (*) \\ Y = \ left \ lceil \ frac {n_T} {2} \ right \ rceil \ End {align *} $

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

---

A modo de ejercicio, puede utilizar la misma técnica para demostrar las siguientes declaraciones:

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

Answer 2

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

Let $ T $ sea un árbol de este tipo con $ n $ nodos y $ L $ hojas. Desde $ T $ es un árbol, hay $ $ n-1 aristas, y el doble cómputo ellos, vemos que $$ 2n - 2 \ le L + 3 (n - L) $$ que dice que $$ 2L \ le n + 2 $$ y esto es apretado en el ejemplo de dos vértice anteriormente. Creo que si se quiere suponer que hay una raíz de grado dos y $ n \ ge $ 3, entonces se puede refinar este argumento para dar $$ 2L \ le n + 1 $$ que es lo que está buscando, y esto es apretado cuando el árbol está lleno.