但是這個(gè)只是一顆普通的二叉樹(shù)，由上圖可知，想要IO讀寫(xiě)次數(shù)最少，就要帶權(quán)路徑長(zhǎng)度最優(yōu)，帶權(quán)路徑長(zhǎng)度最優(yōu)時(shí)為哈夫曼樹(shù)

最佳歸并樹(shù)(本質(zhì)是一顆哈夫曼樹(shù)):

當(dāng)歸并樹(shù)為哈夫曼樹(shù)時(shí)，IO次數(shù)最小

所有的初始?xì)w并段一定能構(gòu)造出一顆完美的哈夫曼樹(shù)嗎？

答：不是

我們稱(chēng)這種初始?xì)w并段不夠而補(bǔ)充的段稱(chēng)為虛短

怎么選擇補(bǔ)充虛短的個(gè)數(shù)？

總的節(jié)點(diǎn)個(gè)數(shù) = 孩子節(jié)點(diǎn)總數(shù)+根節(jié)點(diǎn)，即：
度為0的節(jié)點(diǎn)+度為m的節(jié)點(diǎn) = 孩子節(jié)點(diǎn)總數(shù)+根節(jié)點(diǎn)，即：
n₀ + n_m = m * n_m + 1,即：
n₀ = (m-1)n_m + 1

總結(jié)

以上是生活随笔為你收集整理的数据结构之外部排序：最佳归并树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。