Mengapa ketinggian minimum

10

Di kelas Java saya, kami belajar tentang kompleksitas berbagai jenis koleksi.

Segera kita akan membahas pohon biner, yang telah saya baca. Negara-negara buku yang tinggi minimal pohon biner adalah log2(n+1)1 , tetapi tidak menawarkan penjelasan lebih lanjut.

Adakah yang bisa menjelaskan mengapa?

CodyBugstein
sumber
Saya jelaskan di sini stackoverflow.com/a/13093274/550393
2cupsOfTech

Jawaban:

11

Pohon biner memiliki 1 atau 2 anak di simpul non-daun dan 0 simpul di simpul daun. Biarkan ada node di pohon dan kita harus mengaturnya sedemikian rupa sehingga mereka masih membentuk pohon biner yang valid.n

Tanpa membuktikan, saya menyatakan bahwa untuk memaksimalkan ketinggian, diberikan node harus diatur secara linier, yaitu setiap node non-daun harus hanya memiliki satu anak:

                              O 1
                              |
                              O 2
                              |
                              O 3
                              |
                              O 4
                              |
                              O 5
                              |
                              O 6
                              |
                              O 7
                              |
                              O 8

Di sini, rumus untuk menghitung hubungan ketinggian dalam hal jumlah node adalah lurus ke depan. Jika adalah ketinggian pohon, maka h = n - 1 .hh=n1

Sekarang, jika kita mencoba untuk membangun pohon biner dari node dengan tinggi minimum (selalu dapat direduksi menjadi pohon biner lengkap), kita harus mengemas sebanyak mungkin simpul di tingkat atas, sebelum pindah ke tingkat berikutnya. Jadi, pohon itu berbentuk pohon berikut:n

                              O
                              |1
                              |
                       O------+-----O
                       |2           |3
                       |            |
                   O---+---O    O---+----O
                   |4      |5    6        7
                   |       |
               O---+--O    O
                8      9    10

Mari kita mulai dengan kasus tertentu, .n=2m1

Kita tahu itu,

20+21+22+...+2m1=2m1

Juga, mudah untuk membuktikan bahwa, level yang dapat memiliki paling banyak 2 i node di dalamnya.i2saya

Dengan menggunakan hasil ini dalam jumlah di atas, kami menemukan bahwa untuk setiap level , dari 0 hingga m , terdapat istilah 2 i - 1 yang sesuai dalam perluasan 2 m - 1 . Ini menyiratkan, bahwa pohon biner lengkap 2 m - 1 node diisi penuh dan memiliki tinggi, h ( 2 m - 1 ) = m - 1 , di mana h ( n ) = tinggi pohon biner lengkap dengan n node.saya0m2i12m12m-1h(2m-1)=m-1h(n)=n

Dengan menggunakan hasil ini, , karena pohon dengan 2 m - 1 node terisi penuh dan dengan demikian pohon dengan ( 2 m - 1 ) + 1 = 2 m node harus mengakomodasi node tambahan di level berikutnya m , menambah tinggi 1 dari m - 1 ke m .h(2m)=m2m-1(2m-1)+1=2mmm-1m

Sampai sekarang kita telah membuktikan, h ( 2 m + 1 ) = m + 1 dan juga, h ( 2 m + 1 - 1 ) = m

h(2m)=m,
h(2m+1)=m+1
h(2m+1-1)=m

Jadi, m h ( n ) < m + 1nZ,2mn<2m+1

mh(n)<m+1

Tetapi, dengan mengambil log (basis 2) di kedua sisi, m = log 2 ( n )

mcatatan2(n)<m+1
m=catatan2(n)

Jadi, h ( n ) = m = log 2 ( n ) n,n[2m,2m+1)

h(n)=m=log2(n)

Dan kita dapat menggeneralisasi hasil ini menggunakan induksi.nZ

log2(n+1)1nlog2(n)n

Anurag Kalia
sumber
18

n

41+12+122+12223

nodes=1+2+22+23+...+2depth=k=0depth2k=12depth+112.

nodes=2depth+11,
nodes+1=2depth+1log2(nodes+1)=log2(2depth+1)=depth+1log2(nodes+1)1=depth.
MikeDan
sumber
4

Untuk menjaga ketinggian minimum, mudah untuk melihat bahwa kita perlu mengisi semua level kecuali mungkin yang terakhir. Mengapa? jika tidak, kita bisa memindahkan node level terakhir ke slot kosong di level atas.

Sekarang, bayangkan saya memiliki sejumlah kacang yang tidak ditentukan dan saya beri Anda satu kacang sekaligus dan meminta Anda untuk membangun pohon biner dengan ketinggian seminimal mungkin. Saya mungkin kehabisan kacang pada saat Anda mengisi tingkat terakhir sepenuhnya atau setidaknya memiliki satu kacang di tingkat terakhir. Katakanlah, Anda memiliki tinggi pohon h pada saat ini.

20+21+22+23++2h=2h+11n.
h=lg(n+1)1.
pengguna1234
sumber