Probar un montón binario tiene hojas

Estoy tratando de demostrar que un montón binario con nodos tiene exactamente hojas, dado que el montón se construye de la siguiente manera:$n$$\left\lceil \frac{n}{2} \right\rceil$

Cada nuevo nodo se inserta a través de percolar . Esto significa que cada nuevo nodo debe crearse en el siguiente hijo disponible. Lo que quiero decir con esto es que los niños se llenan de nivel hacia abajo y de izquierda a derecha. Por ejemplo, el siguiente montón:

    0
   / \
  1   2

se tiene que se han construido en este orden: 0, 1, 2. (Los números son sólo índices, no dan ninguna indicación de los datos reales celebradas en ese nodo.)

Esto tiene dos implicaciones importantes:

1. No puede existir ningún nodo en el nivel sin que el nivel esté completamente lleno$k+1$$k$

2. Debido a que los niños se construyen de izquierda a derecha, no puede haber "espacios vacíos" entre los nodos en el nivel , o situaciones como las siguientes: $k+1$

       0
      / \
     1   2
    / \   \
   3  4    6
   

(Esto sería un montón ilegal según mi definición.) Por lo tanto, una buena manera de pensar en este montón es una implementación de matriz de un montón, donde no puede haber ningún "salto" en las indecesiones de la matriz.

Entonces, estaba pensando que la inducción probablemente sería una buena manera de hacer esto ... Tal vez algo que tenga que lidiar incluso con casos extraños para n. Por ejemplo, alguna inducción que utiliza el hecho de que los montones pares construidos de esta manera deben tener un nodo interno con un hijo para un n par, y no tales nodos para un n impar. Ideas?

Si recibo su pregunta correctamente, el montón obtenido es solo un árbol binario ordenado, donde ordenado quiero decir que el nivel solo se puede ocupar después de que el nivel k - 1 se haya llenado por completo, y cada nivel está ocupado desde la izquierda a la derecha, sin saltar.$k$$k-1$

Entonces la prueba es así.

1. Un árbol perfecto de profundidad tiene exactamente 2 k + 1 - 1 nodos.$k$$2^{k+1}-1$
2. Suponga que el montón alcanza la profundidad . Así $k$
   1. hasta el nivel el árbol es perfecto (y tiene 2 k - 1 nodos allí)$k-1$$2^k-1$
   2. en el último nivel, hay exactamente nodos, que son todas hojas.$n-2^k+1$
3. Cada hoja en el nivel tiene un padre. Además, cada dos hojas consecutivas tienen el mismo padre (tal vez a excepción del último nodo, cuyo padre tiene un solo hijo)$k$
4. Por lo tanto, de los nodos en el nivel k - 1 , ⌈ n - 2 k + $2^{k-1}$$k-1$son padres, y el resto2k-1-⌈n-2 k +$\left\lceil \frac{n-2^{k}+1}{2} \right\rceil$son hojas.$2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$
5. La cantidad total de hojas es Que te da lo que necesitas. $$n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$$

Aquí hay una prueba lógica más simple.

Última hoja es índice. Su padre está en el índice ⌊ n / 2 ⌋ y, de manera similar, no hay ningún elemento tal que su padre sea el elemento ( h ⌊ n / 2 + 1 ⌋ ) t h . Por lo tanto, las hojas se indexan de ⌊ n / 2 ⌋ +1 a n.$n^{th}$$\lfloor{n/2}\rfloor$$\lfloor n/2 +1\rfloor)^{th}$$\lfloor{n/2}\rfloor$

$\lfloor(n/2)\rfloor$$\lceil(n/2)\rceil$