Prouver un tas binaire a

J'essaie de prouver qu'un tas binaire avec nœuds a exactement , étant donné que le tas est construit de la manière suivante:$n$$\left\lceil \frac{n}{2} \right\rceil$

Chaque nouveau nœud est inséré via percoler vers le haut . Cela signifie que chaque nouveau nœud doit être créé au prochain enfant disponible. Ce que je veux dire par là, c'est que les enfants sont remplis de haut en bas et de gauche à droite. Par exemple, le segment de mémoire suivant:

    0
   / \
  1   2

aurait dû être construit dans cet ordre: 0, 1, 2. (Les nombres ne sont que des index, ils ne donnent aucune indication sur les données réelles contenues dans ce nœud.)

Cela a deux conséquences importantes:

1. Il ne peut exister de nœud au niveau sans que le niveau soit complètement rempli$k+1$$k$

2. Parce que les enfants sont construits de gauche à droite, il ne peut y avoir aucun "espace vide" entre les nœuds au niveau , ou des situations comme les suivantes: $k+1$

       0
      / \
     1   2
    / \   \
   3  4    6
   

(Ce serait un tas illégal selon ma définition.) Ainsi, une bonne façon de penser à ce tas est une implémentation de tableau d'un tas, où il ne peut pas y avoir de "sauts" dans les indéces du tableau.

Donc, je pensais que l'induction serait probablement un bon moyen de le faire ... Peut-être quelque chose devant traiter même des cas étranges pour n. Par exemple, une induction utilisant le fait que même les tas construits de cette façon doivent avoir un nœud interne avec un enfant pour un n pair, et aucun de ces nœuds pour un n impair. Des idées?

Si je comprends bien votre question, le tas obtenu n'est qu'un arbre binaire ordonné, où dans l'ordre je veux dire que le ème niveau ne peut être occupé qu'après que le niveau k - 1 a été complètement rempli, et chaque niveau est occupé de gauche à droite, sans sauter.$k$$k-1$

Ensuite, la preuve va comme ça.

1. Un arbre parfait de profondeur a exactement 2 k + 1 - 1 nœuds.$k$$2^{k+1}-1$
2. Supposons que le tas atteint la profondeur . Donc $k$
   1. jusqu'au niveau l'arbre est parfait (et contient 2 k - 1 nœuds)$k-1$$2^k-1$
   2. au dernier niveau, il y a exactement nœuds, qui sont tous des feuilles.$n-2^k+1$
3. Chaque feuille du ème niveau a un parent. De plus, chacun des deux congés consécutifs a le même père (peut-être à l'exception du dernier nœud, dont le père n'a qu'un enfant)$k$
4. Ainsi, sur les nœuds au niveau k - 1 , ⌈ n - 2 k + $2^{k-1}$$k-1$sont parents, et le reste2k-1-⌈n-2 k +$\left\lceil \frac{n-2^{k}+1}{2} \right\rceil$sont des feuilles.$2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$
5. La quantité totale de feuilles est qui vous donne ce que vous avez besoin. $$n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$$

Voici une preuve logique plus simple.

$n^{th}$$\lfloor{n/2}\rfloor$$\lfloor n/2 +1\rfloor)^{th}$$\lfloor{n/2}\rfloor$

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