Hoffman树Vs，二元平衡树

Question

给定n个实数正数A1，A2....An构建一个二叉树T，如：

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

这个问题是在测试算法和数据结构时给我的。简单地说，我的回答是构建一棵二叉树，这样每一片叶子都是A1到一个。T的权重为logn*之和。

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

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

如果A1到a都是非常小的数字，例如从0到1，那么每片叶子的高度将成为计算树的重量的主要因素。

帮助会很感激的。

Answer 1

在原始数组A中，可能有一些元素发生的次数比其他元素多。您希望以一种方式构造树，即最常见的元素在树中的比例要高于一些比较少见的元素。

考虑一下这个页面上的示例- “生成huffman树的快速教程”。生成的huffman树的权重为228，这是最优的。

在同一组中，你能得到的最完美平衡的树的重量是241 (5和6有深度2，其他元素有深度3)，最差的有294 (用1和2切换5和6)。你的解决方案会在这两者之间找到一些东西，而不是最优的。