Estoy trabajando en las pruebas del árbol binario completo para un artículo del blog que estoy escribiendo y quiero asegurarme de que no me estoy perdiendo nada. Esta prueba en particular se centra en relacionar el número de nodos totales $N$ al número de hojas $L$ . Me resulta más fácil inducir en $L$ y la siguiente es mi prueba:
El número total de nodos $N$ en un árbol binario completo con $L$ hojas es $N = 2L - 1$
Podemos demostrar $N = 2L - 1$ por inducción.
Caso base
Un árbol con $1$ la hoja tiene $1$ nodo en su totalidad. Un árbol con $2$ hojas tiene $3$ nodos en total. El caso base demuestra el teorema para $L = 1$ & $L = 2$ .
Hipótesis inductiva
Supongamos que cualquier árbol binario completo con $L$ hojas tiene $N = 2L - 1$ total de nodos.
Paso inductivo
Demostrar que todo árbol binario completo con $L+1$ hojas tiene $N = 2(L+1) - 1$ total de nodos.
Dejemos que $T$ sea un árbol binario completo con $L+1$ hojas. Seleccione una hoja $v$ a una profundidad máxima tal que $v$ es también una hoja de máxima profundidad. Elimina ambos $v$ y $v$ 's sibling y dejar que $T'$ sea el árbol resultante. $T'$ es un árbol binario completo con $L$ hojas que por nuestra hipótesis inductiva hipótesis debe tener $2L - 1$ total de nodos $N$ . Nota $v$ es ahora una hoja del árbol $T'$ . Añadir $v$ y $v$ a su padre y observe que el padre se convierte en un nodo interno por lo que el árbol pierde una hoja, pero gana otras dos (que hemos añadido). El número de hojas ha aumentado en un total de de $1 \text{ from } L \Rightarrow L+1$ mientras que el número de nodos aumentó en dos $2L - 1 + 2 = 2L + 1$ . Esto equivale claramente a $2(L+1) - 1$ demostrando así por inducción que el número de nodos totales $N$ en cualquier árbol binario árbol binario con $L$ hojas es $2L - 1 \quad \blacksquare$ .
¿Esta prueba es válida o me estoy dejando algo?
Tengo curiosidad, si fuera a inducir en $N$ en lugar de $L$ obviamente tendría que demostrar que un árbol con $N+2$ Los nodos tienen $\frac{(N+1)+2}{2}$ hojas ya que un árbol con $N+1$ no puede ser un árbol binario completo si un árbol con $N$ nodos es un árbol binario completo. ¿Tengo que hacer algo especial para explicar mi paso de $N \Rightarrow N+1$ . La razón por la que un árbol con $N+2$ nodos es un árbol binario completo si un árbol con $N$ nodos es un árbol binario completo es simplemente debido a la definición recursiva de un árbol binario completo, pero no sé cómo más para articular que (o si necesito). ¿Es esto lo que es la inducción estructural?
Edición: Prueba basada en la división
Caso base
Un árbol con $1$ la hoja tiene $1$ nodo en su totalidad. Un árbol con $2$ hojas tiene $3$ nodos en total. El caso base demuestra el teorema para $L = 1$ & $L = 2$ .
Hipótesis inductiva fuerte
Supongamos que cualquier árbol binario completo con $L$ hojas tiene $N = 2L - 1$ total de nodos para todos $0 \leq L \leq K$ .
Paso inductivo
Dejemos que $T$ sea un árbol binario completo con $K+1$ hojas. Al ver cómo $T$ es un árbol binario completo, sus subárboles $T_{left}$ y $T_{right}$ debe tener al menos $1$ hoja cada uno. Esto significa que $T_{left}$ y $T_{right}$ tienen un número de hojas $< K+1$ . Llame a este número $L_{left}$ y $L_{right}$ respectivamente. Por nuestra fuerte IH, deben tener $2(L_{left}) - 1$ y $2(L_{right}) - 1$ total de nodos, respectivamente. $T$ por tanto, tiene un número de nodos igual a la suma del número de nodos de cada subárbol más su raíz, que no aparece en ninguno de los dos subárboles. Como el único nodo que no aparece en ninguno de los dos $T$ es un nodo interno y no una hoja, el número de hojas en $T = L_{left} + L_{right}$ .
$$2(L_{left}) - 1 + 2(L_{right}) - 1 + 1 = 2(L_{left} + L_{right}) - 2 + 1 = 2(K+1) - 1 = 2(L+1) - 1$$
De este modo se demuestra por inducción que todos los árboles binarios completos con $L$ las hojas tienen $N = 2L - 1$ total de nodos para todos $L \quad \blacksquare$ .
