nノードのバイナリヒープにceil（n/2）の葉があることをどのように証明しますか？

Question

nノードを持つバイナリヒープが正確に⌈ n/2 ⌉リーフノードであることを証明しますか？

Answer 1

これについての直感は、これを誘導的に考えることです。 n = 0の場合、葉はなく、n = 1の場合、根は唯一の葉である。その後に追加された各ノードについて、（1）以前にリーフであったノードに子を追加し、リーフノードの数を変更しないで1つの子を持つ、または（2）既に存在するノードに子を追加する1人の子供が、葉の数を1つ増やします。帰納法を使用すると、これを形式化して、バイナリヒープの葉数が⌈ n/2 ⌉であることを証明できます。

Answer 2

Let x be the height of tree in which case 2^x = no of leaves 
=> 2^0 + 2^1+ 2^2 + 2^3 +...2^x = n 
=> 2^(x+1) - 1 = n (By sum series power of 2 formula) 
=>2^(x+1)= n+1 
=> log(n+1) = x+1 
=>log(n+1)-1 = x; 
=>log(n+1)- log2 =x 
x =log(n+1/2) 

=> no of leaves = (n+1)/2 (which is 2^(log(n+1/2)) 

Answer 3

0-level 
1-level 
... 
d-level       // Total 2^d nodes at this level. #ofLeafNodes at this level depends on how many nodes are there at below level. 
last-level-containing-X-nodes // All leaf nodes 

リーフノードは、最後の二つのレベルからのみ来ることができるように、我々はnノードを持っているとしましょう。

最終レベルはxリーフノードです。 最後の2番目のレベルは合計2^d個のノードと⌈ x/2 ⌉のリーフノードを持ちます。

したがって、総リーフノードに=バイナリヒープツリー内

= (Leaf nodes at bottom-most level) + (Leaf nodes at second bottom-most level) 
= (x + (2^d - ⌈x/2⌉))     //Equation 1 

---

合計ノードは=>

n  = (2^(d + 1) - 1) + x 
2*(2^d) = n-x+1 
2^d  = (n-x+1)/2 

次に、上記EQ＃1に2^dを代入

(x + (2^d - ⌈x/2⌉)) 
=(x + (n-x+1)/2 - ⌈x/2⌉) 
= n/2 + x/2 + 1/2 - ⌈x/2⌉ 

---

でも nについては

、xが奇数になります：奇数nについては

= n/2 + x/2 + 1/2 - (x/2 + 1/2) 
= n/2 + x/2 + 1/2 - x/2 - 1/2 
= n/2 
= ⌈n/2⌉  /*Since n is even*/ 

、xはさらに次のようになります。

= n/2 + x/2 + 1/2 - (x/2 + 1/2) 
= n/2 + x/2 + 1/2 - x/2 
= n/2 + 1/2 
= ⌈n/2⌉