algorithm - 霍夫曼树的主张？

Question

我看到了以下声明：

给定Q={1,2,...,n}和正频率函数f使得：

f(1) > f(2) > ... > f(n) > f(1)/3 ,

然后在霍夫曼树的最多 3 个不同级别上有叶子。

我一直在寻找一个反例，但没有运气，有人可以帮助我吗？

标签： algorithmtreehuffman-code

Answer 1

假设某棵树的声明是错误的，在深度 H 处具有最浅的叶子。最浅的叶子的频率为 f(1)。

由于树的深度至少为 H+3，因此在深度 H+1 处必须有一个至少有 3 个叶子的子树。到达 H+3 的最小可能子树的形状如下：

   O
  / \
 O   O
    / \
   O   O

子树的总频率大于 f(1)，即最浅叶的频率，但它发生在更深的层次。因此，我们可以通过交换这个子树和最浅叶的位置来改进霍夫曼树。

由于霍夫曼树被证明是最优的，这不可能发生，所以这个说法一定是正确的。