赫夫曼树的索赔？

Question

我看到了以下说法：

给出了Q={1,2，…，n}和正频率函数f，使得：

f(1) > f(2) >…> f(n) > f(1)/3，

然后在最多3种不同层次的哈夫曼树上有叶。

我一直在找一个反例，但没有运气，有人能帮我吗？

Answer 1

假设对某些树来说，这种说法是错误的，在H深度处有最浅的叶子，最浅的叶子将有频率f(1)。

由于树至少扩展到深度H+3，所以必须在H+1深度处有至少3片叶子的子树。到达H+3的最小子树的形状如下：

   O
  / \
 O   O
    / \
   O   O

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

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