¿Cómo puedo demostrar que un árbol binario completo tiene $ \ lceil n / 2 \ rceil $ hojas?

Question

Dado un árbol binario completo con $ n $ nodos. Estoy tratando de probar que un árbol binario completo tiene exactamente $ \ lceil n / 2 \ rceil $ hojas. Creo que puedo hacer esto por inducción.

Por $ h (t) = 0 $, el árbol está vacía. Así que no hay hojas y la demanda se mantiene para un árbol vacío.

Por $ h (t) = 1 $, el árbol tiene 1 nodo, que también es una hoja, por lo que la reclamación se mantiene. Aquí estoy atascado, no sé qué elegir como hipótesis de inducción y cómo hacer el paso de inducción.

Answer 1

Si la instrucción que está tratando de demostrar por inducción es

Para todos los enteros positivos n $ $, un árbol binario completo con $ n $ nodos tiene $ \ lceil {n / 2} \ rceil $ hojas.

entonces la hipótesis de inducción debe ser

Para todos los enteros positivos k $ <$ n, un árbol binario completo con $ k $ nodos tiene $ \ lceil {k / 2} \ rceil $ hojas.

Del mismo modo, si la instrucción que está tratando de demostrar por inducción es

Para todos los enteros positivos n $ $, un hoosegow con $ n $ $ whatsits tiene 2 ^ {\ lfloor \ sqrt {n} \ rceil!} \ Cdot n ^ \ pi $ nubbleframets.

entonces la hipótesis de inducción debe ser

Para todos los enteros positivos k $ <$ n, un hoosegow con k $ $ $ whatsits tiene 2 ^ {\ lfloor \ sqrt {k} \ rceil!} \ Cdot K ^ \ pi $ nubbleframets.

Answer 2

En primer lugar, puede ayudar a ser un poco más específico con su terminología. Vamos a suponer que quiere decir "completo" en la forma en que [CLRS01] define:

Todas las hojas tienen la misma profundidad y todos los nodos internos tener grado 2.

En segundo lugar, es esta tarea?

Se puede demostrar esto mediante la inducción estructural. Mostrar su reclamo es válido para un árbol "base" y luego pensar en cómo otros árboles binarios completos se construyen a partir de éstos.

A medida que construye árboles más grandes de esta manera, ¿cómo el número total de nodos aumento? ¿Cómo aumenta el número de hojas?

Sugerencia:

¿Tiene $ \ lceil n + 1 \ rceil = 2 \ lceil n / 2 \ rceil $?