哈夫曼树的主张？
Claim of Huffman Tree?
我看到了以下声明：
Given Q={1,2,...,n}, and positive frequency function f such that:
f(1) > f(2) > ... > f(n) > f(1)/3,
Then there are leafs at maximum 3 different levels of Huffman tree.
我一直在寻找反例但没有找到，有人可以帮助我吗？
假设某些树的声明是错误的，最浅的叶子在深度 H。最浅的叶子将有频率 f(1)。
既然这棵树至少延伸到深度H+3，那么在深度H+1一定有一颗至少有3片叶子的子树。到达 H+3 的最小可能子树的形状如下：
O
/ \
O O
/ \
O O
子树的总频率大于最浅叶子的频率f(1)，但出现在更深的层次。因此，我们可以通过交换这棵子树和最浅叶子的位置来改进哈夫曼树。
由于哈夫曼树被证明是最优的，所以这不可能发生，所以这个说法一定是正确的。
我看到了以下声明：
Given Q={1,2,...,n}, and positive frequency function f such that:
f(1) > f(2) > ... > f(n) > f(1)/3,
Then there are leafs at maximum 3 different levels of Huffman tree.
我一直在寻找反例但没有找到，有人可以帮助我吗？
假设某些树的声明是错误的，最浅的叶子在深度 H。最浅的叶子将有频率 f(1)。
既然这棵树至少延伸到深度H+3，那么在深度H+1一定有一颗至少有3片叶子的子树。到达 H+3 的最小可能子树的形状如下：
O
/ \
O O
/ \
O O
子树的总频率大于最浅叶子的频率f(1)，但出现在更深的层次。因此，我们可以通过交换这棵子树和最浅叶子的位置来改进哈夫曼树。
由于哈夫曼树被证明是最优的，所以这不可能发生，所以这个说法一定是正确的。