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

标签 algorithm data-structures binary-tree

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

  1. 每个数字都是一片叶子。
  2. 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/

相关文章:

python - 使用 python 进行二叉树修剪 [postorder 方法不起作用]

python - 判断两行中第一行是否为标题

algorithm - 重新采样一系列点

c++ - 如何对 C++ 代码的性能进行基准测试?

c - 如何反转我在 C 中创建的链接列表

c - 将C二进制搜索树保存到txt文件

c++ - 为什么跳出函数后节点值变了?

regex - 在golang中用零替换数字

arrays - 给定一个有序数组,其中有几个数字是颠倒的。如何排序?

algorithm - 除了对完整性的要求外,B-tree 和 B*-tree 之间有什么区别?