Membuktikan tumpukan biner memiliki

Saya mencoba untuk membuktikan bahwa tumpukan biner dengan $n$ node memiliki tepat $\left\lceil \frac{n}{2} \right\rceil$daun, mengingat bahwa tumpukan dibangun dengan cara berikut:

Setiap node baru dimasukkan melalui meresap sampai . Ini berarti bahwa setiap node baru harus diciptakan di anak berikutnya yang tersedia. Apa yang saya maksudkan dengan ini adalah bahwa anak-anak diisi tingkat-bawah, dan kiri ke kanan. Sebagai contoh, berikut tumpukan:

    0
   / \
  1   2

akan memiliki telah dibangun dalam urutan ini: 0, 1, 2. (Jumlahnya hanya indeks, mereka tidak memberikan indikasi data aktual yang diselenggarakan di simpul tersebut.)

Ini memiliki dua implikasi penting:

1. Tidak ada simpul pada level $k+1$ tanpa level $k$ yang terisi penuh

2. Karena anak-anak dibangun kiri ke kanan, tidak ada "ruang kosong" antara node pada tingkat $k+1$ , atau situasi seperti berikut:

       0
      / \
     1   2
    / \   \
   3  4    6
   

(Ini akan menjadi tumpukan ilegal menurut definisi saya.) Jadi, cara yang baik untuk memikirkan tumpukan ini adalah implementasi array tumpukan, di mana tidak ada "lompatan" di indeces array.

Jadi, aku berpikir induksi mungkin akan menjadi cara yang baik untuk melakukan hal ini ... Mungkin sesuatu yang harus berurusan dengan bahkan kasus aneh untuk n. Sebagai contoh, beberapa induksi menggunakan fakta bahwa tumpukan bahkan membangun dalam mode ini harus memiliki simpul internal dengan satu anak untuk lebih n, dan tidak ada node tersebut untuk n ganjil. Ide ide?

Jika saya mendapatkan pertanyaan Anda dengan benar, tumpukan yang diperoleh hanyalah pohon biner yang terurut, di mana dalam urutan saya maksudkan bahwa level hanya dapat ditempati setelah level k - 1 telah terisi penuh, dan setiap level ditempati dari kiri ke kanan, tanpa melewatkan.$k$$k-1$

Maka bukti seperti ini.

1. Sebuah pohon yang sempurna dari kedalaman memiliki tepat 2 k + 1 - 1 node.$k$$2^{k+1}-1$
2. Asumsikan bahwa tumpukan mencapai kedalaman . Jadi $k$
   1. hingga level pohonnya sempurna (dan memiliki 2 k - 1 node di sana)$k-1$$2^k-1$
   2. pada level terakhir, ada persis node, yang semuanya daun.$n-2^k+1$
3. Setiap daun pada tingkat th memiliki orangtua. Selain itu, setiap dua daun berturut-turut memiliki ayah yang sama (mungkin kecuali untuk simpul terakhir, yang ayahnya hanya memiliki satu anak)$k$
4. Jadi, dari node pada level k - 1 , ⌈ n - 2 k + $2^{k-1}$$k-1$adalah orang tua, dan sisanya2k-1-⌈n-2 k +$\left\lceil \frac{n-2^{k}+1}{2} \right\rceil$adalah daun.$2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$
5. Jumlah total daun adalah Yang memberi Anda apa yang Anda butuhkan. $$n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$$

Berikut adalah bukti logis sederhana.

Daun terakhir adalah indeks. Induknya berada pada indeks ⌊ n / 2 ⌋ dan demikian pula, tidak ada elemen sedemikian sehingga induknya adalah ( ⌊ n / 2 + 1 ⌋ ) t h elemen. Jadi daun diindeks dari ⌊ n / 2 ⌋ 1 ke 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$