霍夫曼樹Vs的二進制平衡樹

鑑於ň真正正數A1，A2 ....一個建立二叉樹牛逼如：霍夫曼樹Vs的二進制平衡樹

每一個數字是葉。
重量的T將盡可能最小。樹的重量等於每片葉子的總和乘以它的高度。

這個問題在算法和數據結構測試中給了我。我簡短的回答是建立一個二叉樹，使每個葉子是A1到An。 * T的總和將爲logn * Ai的總和。

我沒有得到這個答案的積分。獲得滿分的答案是按頻率對數字進行排序並構建霍夫曼樹。

我的問題是爲什麼我的回答被忽略？

如果A1至An都是非常小的數字，例如範圍從0到1，則每個葉的HIGHT將成爲計算樹的重量dominent因子。

幫助會被重視。

來源

2014-02-09 Illya Broder

最好在http://programmers.stackexchange.com/上詢問這個問題，因爲這是針對該網站的專題討論。參考：http://programmers.stackexchange.com/help/on-topic乾杯。 –

第二個條件是我不明白，難道你乘葉深入時候，它存儲了數數字本身（頻率。在原始數組A），或深度次的頻率是多少？ – pepo

在原始陣列A可能有許多比其他多個正好某些元素。你想以某種方式構建樹，樹中最常見的元素比較少見的樹更高。

請考慮本頁上的示例 - "A quick tutorial on generating a huffman tree"。生成的哈夫曼樹的權重爲228，這是最優的。

你可以得到同一組合的最佳平衡樹有241（5和6與深度2，其他元素與深度3），最差的一個294（切換5和6與1和2）。你的解決方案會找到這些之間的東西，而不是最佳。

來源

2014-02-09 21:45:22 pepo

如果數組A由非常小的數字組成，該怎麼辦？霍夫曼樹仍然存在？ –

我假設樹的權重是'freq（Ai）* depth（Ai）'的總和，現在我看到權重是'Ai * depth（Ai）'的總和。因此，而不是頻率，使用數字本身來建立霍夫曼樹。因此，小數字比大數字更深，對整體重量的貢獻大致相同。爲了回答你的問題，小數字不是問題，它們只會降低樹的重量。問題是數字有很大的差異 - 這就是哈夫曼樹最優解決的問題。 – pepo

霍夫曼樹Vs的二進制平衡樹

回答

相關問題