给定 n 个正数 A1,A2....An 构建一棵二叉树 T 例如:
- 每个数字都是一片叶子。
- T 的权重将尽可能小。树的权重等于每片叶子的总和乘以它的高度。
这个问题是在算法和数据结构的测试中给我的。我的简短回答是构建一棵二叉树,使每个叶子都是 A1 到 An。 T 的权重将是 logn*Ai 的总和。
我没有得到这个答案的分数。获得满分的答案是按频率对数字进行排序并构建霍夫曼树。
我的问题是为什么我的回答被忽略了?
如果A1到An都是非常小的数,比如0到1,那么每片叶子的高度就会成为计算树的权重的主导因素。
我们将不胜感激。
最佳答案
在原始数组 A
中,某些元素的出现次数可能比其他元素多得多。您希望以某种方式构建树,使最常见的元素在树中的位置高于不太常见的元素。
考虑此页面上的示例 - "A quick tutorial on generating a huffman tree" . 生成的哈夫曼树权重为228,最优。
对于同一组,您可以获得的最佳完美平衡树的权重为 241(5 和 6 的深度为 2,其他元素的深度为 3),最差的为 294(将 5 和 6 与 1 和 2 切换)。 您的解决方案会在两者之间找到一些东西,而不是最佳的。
关于algorithm - 霍夫曼树与二叉平衡树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21665165/