Probar un árbol binario tiene como máximo

14

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?nn2

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

varatis
fuente
3
Primero, tenga en cuenta que podemos usar LaTeX aquí. Haga clic en "editar" para ver cómo lo hice. En segundo lugar, no veo una inducción. Está arrojando algunos números por allí, pero no hay una estructura de prueba ni relación con los montones. ¿Puedes mejorarlo? Y, por último, el reclamo es incorrecto: una lista ordenada cumple la propiedad del montón y solo tiene una hoja. ¿Has omitido algunas suposiciones?
Raphael
¿Es la edición de @ Kaveh lo que tenía en mente, es decir, "como mucho"?
Raphael
@Raphael, al leer la pregunta nuevamente, creo que podría tratarse de montones donde cada nodo interno tiene exactamente dos hijos (en cuyo caso la pregunta original tiene sentido y la afirmación es correcta, o algo similar).
Kaveh
1
@Kaveh Ah sí, veo tu confusión. Los nodos del montón tienen como máximo dos hijos (de ahí la etiqueta del árbol binario)
varatis
1
Veo. Con el reclamo formulado con precisión, de hecho no hay necesidad de más suposiciones. La propiedad es válida para todos los árboles binarios.
Raphael

Respuestas:

7

Supongo ahora que la pregunta es la siguiente:

Dado un árbol binario con nodos, demuestre que contiene como máximo nnn2 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 enTree=EmptyLeafNode(Tree,Tree)TnTTlT .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 Th(t)=0T=EmptylT=nT=0h(t)=1T=Leaf, por lo que el reclamo es válido para las hojas.lT=1=nT2

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.Th(T)kk1

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 (Th(T)=k+1k1T=Node(L,R)nT=nL+nR+1LRT , la hipótesis de inducción se aplica y tieneh(L),h(R)k

lLnL2 and lRnR2.

Como todas las hojas de están en L o R , tenemos queTLR

lT=lL+lRnL2+nR2nL+nR+12()=nT2

La desigualdad marcado con se puede comprobar (de cuatro vías) distinción caso sobre si n L , n R2 N . Por el poder de la inducción, esto concluye la prueba.()nL,nR2N


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

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

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. 3n=2n=2n/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 LTnLTn1

2n2L+3(nL)
2Ln+2
n3 que es lo que estás buscando, y esto es ajustado cuando el árbol está lleno.
2Ln+1
Louis
fuente
Supongo que aquí asumimos silenciosamente árboles enraizados aquí; Wikipedia también lo hace.
Raphael
1
Wikipedia se equivoca, diciendo: "Fuera del árbol, a menudo hay una referencia al nodo" raíz "(el antepasado de todos los nodos), si existe". De todos modos, parece valioso escribir este argumento, ya que es diferente y bastante fácil.
Louis
Si sigue leyendo, todos los bordes están dirigidos, hablan de "niños" y "padres". Eso no tiene sentido en árboles sin raíces. En consecuencia, una hoja sería un nodo con un grado 0.
Rafael