Membuktikan tumpukan biner memiliki

16

Saya mencoba untuk membuktikan bahwa tumpukan biner dengan n node memiliki tepat n2daun, 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?

varatis
sumber
@DaveClarke: Tidak cukup; pertanyaan terkait adalah hasil dari kesalahpahaman pada bagian kami editor ditinggalkan di sana untuk referensi.
Raphael
Sudahkah Anda mencoba induksi lebih dari nomor simpul resp. jumlah penyisipan?
Raphael
@DaveClarke: Mengapa? Ini adalah pertanyaan yang valid dalam dirinya sendiri, imho.
Raphael
BTW, pertanyaan tidak ada hubungannya dengan tumpukan. Klaim berlaku untuk setiap lengkap biner pohon
Ran G.

Jawaban:

8

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.kk1

Maka bukti seperti ini.

  1. Sebuah pohon yang sempurna dari kedalaman memiliki tepat 2 k + 1 - 1 node.k2k+11
  2. Asumsikan bahwa tumpukan mencapai kedalaman . Jadi k
    1. hingga level pohonnya sempurna (dan memiliki 2 k - 1 node di sana)k12k1
    2. pada level terakhir, ada persis node, yang semuanya daun.n2k+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 + 12k1k1adalah orang tua, dan sisanya2k-1-n-2 k +1n2k+12adalah daun.2k1n2k+12
  5. Jumlah total daun adalah Yang memberi Anda apa yang Anda butuhkan.
    n2k+1+2k1n2k+12
Ran G.
sumber
1
Perhatikan bahwa penuh berbeda lengkap berbeda dari sempurna pohon biner. Disayangkan, ambigu dan tidak konsisten pilihan kata di sana, tapi apa yang dapat Anda lakukan tentang hal itu. Saya kira menempel definisi Wikipedia masuk akal, karena kebanyakan akan terlihat di sana pertama?
Raphael
Oh, wow, saya bahkan tidak tahu istilah-istilah ini. Terima kasih telah menunjukkan ini.
Ran G.
"sampai tingkat k-1 pohon sempurna (dan memiliki 2 ^ k - 1 node di sana)" dan "Dengan demikian, dari 2 ^ (k-1) node pada level k-1" tampaknya bertentangan pernyataan, atau saya melewatkan sesuatu?
adrian h.
@adrianh. ( ) node di seluruh subtree, 2 k - 1 node hanya pada tingkat terakhir (sehingga di seluruh subtree ada 2 k - 1 + 2 k - 2 + . . . Node.)2k12k12k1+2k2+...
Ran G.
Ah kau benar-benar benar, terima kasih banyak untuk klarifikasi!
adrian h.
11

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.nthn/2n/2+1)thn/2

(n/2)(n/2)

Zubin Pahuja
sumber
1
Cukup intuitif dan penjelasan yang jelas. Terima kasih.
whitehat