it-swarm-id.com

Berapa jumlah total node dalam pohon k-ary penuh, dalam hal jumlah daun?

Saya melakukan bentuk unik pengkodean Huffman, dan saya sedang membangun pohon k-ary (dalam kasus khusus ini, 3-ary) yang penuh (setiap simpul akan memiliki 0 atau k anak-anak), dan saya tahu berapa banyak daun yang akan dihasilkan miliki sebelum saya membangunnya. Bagaimana cara menghitung jumlah total node dalam pohon dalam hal jumlah daun?

Saya tahu bahwa dalam kasus pohon biner penuh (2-ary), rumus untuk ini adalah 2L - 1, di mana L adalah jumlah daun. Saya ingin memperluas prinsip ini pada kasus pohon k-ary.

28
Andrew

Pikirkan tentang bagaimana membuktikan hasil untuk pohon biner penuh, dan Anda akan melihat bagaimana melakukannya secara umum. Untuk pohon biner penuh, misalkan tinggi h, jumlah node N adalah

N = 2^{h+1} - 1

Mengapa? Karena level pertama memiliki node 2^0, level kedua memiliki node 2^1, dan, secara umum, level kth memiliki node 2^{k-1}. Menambahkan ini untuk total tingkat h+1 (begitu tinggi h) berikan

N = 1 + 2 + 2^2 + 2^3 + ... + 2^h = (2^{h+1} - 1) / (2 - 1) = 2^{h+1} - 1

Jumlah total daun L hanya jumlah node di tingkat terakhir, jadi L = 2^h. Karena itu, dengan substitusi, kita dapatkan

N = 2*L - 1

Untuk pohon k- ary, tidak ada yang berubah selain 2. Begitu 

N = 1 + k + k^2 + k^3 + ... + k^h = (k^{h+1} - 1) / (k - 1)

L = k^h

jadi sedikit aljabar bisa membawa Anda langkah terakhir untuk mendapatkannya

N = (k*L - 1) / (k-1)
33
PengOne

Rumus untuk 2L-1 yang Anda sebutkan berasal dari melihat pohon biner penuh, lengkap dan seimbang: pada tingkat terakhir Anda memiliki 2 ^ h daun, dan di tingkat lain: 1 + 2 + 4 + .... + 2 ^ (h-1) = 2 ^ h -1 daun. Ketika Anda "mengacaukan" level di pohon dan membuat yang tidak seimbang, maka jumlah node internal yang Anda miliki tidak berubah.

Dalam pohon 3-ary ini logika yang sama: pada tingkat terakhir Anda memiliki 3 ^ h daun, dan di tingkat lain: 1 + 3 + 9 + .... + 3 ^ (h-1) = (3 ^ h -1)/2, itu berarti bahwa pada pohon 3-ary Anda memiliki 1,5 * L - 0,5 daun (dan ini masuk akal - karena derajatnya lebih besar Anda memerlukan lebih sedikit node internal). Saya kira itu juga di sini, ketika Anda mengacaukan level di pohon Anda masih akan membutuhkan jumlah node internal yang sama.

Semoga ini bisa membantu Anda 

0
Bartolinio

Untuk setiap pohon k-ary, jumlah total node n = [(k ^ (h + 1)) - 1]/(h-1) dengan h adalah ketinggian pohon k-ary.

Mis: - Untuk pohon biner lengkap (k = 2) total no. dari node = [(2 ^ (h + 1)) - 1]/(h-1). 

Jadi untuk tinggi 3, total no. node akan menjadi 15.

Untuk pohon pohon ternary lengkap (k = 3) total no. dari node = [(3 ^ (h + 1)) - 1]/(h-1).

Jadi untuk tinggi 3, total no. node akan menjadi 40.

0
Kishan