关于满足特定频率条件的哈夫曼树(Huffman Tree)命题的反例寻求
这个命题是成立的,不存在你要找的反例,以下是推导过程:
我们用反证法验证:假设存在符合条件的频率序列对应的哈夫曼树有至少4个不同层级的叶子节点:
- 先把所有节点权重按从大到小排序为 $f(1) > f(2) > ... > f(n),题设条件满足最小的权重 $f(n) > f(1)/3$
- 哈夫曼树的构造规则决定了深度最深的叶子一定是权重最小的节点。如果存在第4层的叶子(约定根节点为第1层),那么至少有两个权重最小的节点a、b位于第4层,两者满足 $a \geq b > f(1)/3$
- 合并a、b得到的父节点权重为 $a+b > 2f(1)/3$,这个父节点下一步需要和剩余节点中权重最小的节点c合并,c同样满足 $c>f(1)/3$,因此合并后得到的新节点权重为 $(a+b)+c > f(1)$
- 哈夫曼树中权重越大的节点深度越浅,此时新节点的权重已经超过了最大权重$f(1)$,因此$f(1)$的深度最多和这个新节点持平,最多是第2层,而a、b的深度为第4层,中间最多存在第3层的叶子,不可能出现第5层的叶子,因此所有叶子最多分布在3个不同层级。
符合题设条件的哈夫曼树最多只会出现3个层级的叶子,比如$f(1)=10, f(2)=9, f(3)=8, f(4)=7, f(5)=4, f(6)=3.5的实例中,叶子分别分布在第2、3、4三个层级,不存在超过3个层级的情况。
内容的提问来源于stack exchange,提问作者user16138525
相关产品推荐
相关产品推荐

