algorithm - 霍夫曼树与二叉平衡树

Question

给定 n 个正数 A1,A2....An 构建一棵二叉树 T 例如:

1. 每个数字都是一片叶子。
2. T 的权重将尽可能小。树的权重等于每片叶子的总和乘以它的高度。

这个问题是在算法和数据结构的测试中给我的。我的简短回答是构建一棵二叉树，使每个叶子都是 A1 到 An。 T 的权重将是 logn*Ai 的总和。

我没有得到这个答案的分数。获得满分的答案是按频率对数字进行排序并构建霍夫曼树。

我的问题是为什么我的回答被忽略了？

如果A1到An都是非常小的数，比如0到1，那么每片叶子的高度就会成为计算树的权重的主导因素。

我们将不胜感激。

Answer 1

在原始数组 A 中，某些元素的出现次数可能比其他元素多得多。您希望以某种方式构建树，使最常见的元素在树中的位置高于不太常见的元素。

考虑此页面上的示例 - "A quick tutorial on generating a huffman tree" .生成的哈夫曼树权重为228，最优。

对于同一组，您可以获得的最佳完美平衡树的权重为 241(5 和 6 的深度为 2，其他元素的深度为 3)，最差的为 294(将 5 和 6 与 1 和 2 切换)。您的解决方案会在两者之间找到一些东西，而不是最佳的。