赫夫曼树-尽可能高的频率，给出完美的树

Question

假设你的字母表有4个字符: A，B，C，D。在赫夫曼树是完美的情况下，最频繁的字符的最高频率是多少？

我们有一个理论，它是总长度的2/5，但我们希望看到更具体的证据或解释。

Answer 1

在不失去一般性的情况下，我们假设p(A) <= p(B) <= p(C) <= p(D)Huffman算法将A和B合并成一个分支。(同样，如果某些概率相等，则不会失去一般性。)为了使生成的树平坦，我们必须将C和D组合成一个分支。最后一步是将这两个分支结合起来。

为了保证C和D结合成一个分支，p(C)和p(D)都必须小于p(A) + p(B)。所以p(D) < p(A) + p(B)。注意，如果p(C) = p(D) = p(A) + p(B)，那么Huffman算法可以选择下一步中的任意对，其中两种情况都会导致树的倾斜。因此，p(D)必须严格小于p(A) + p(B)。

剩下的留给读者做练习。

(你的猜测接近了。它必须小于2/5。SO2/5-ϵ，其中ϵ是允许从频率(大概是整数)计算的概率小于2/5的最小数。达到最大值的概率集合是{1/5，1/5，1/5+ϵ，2/5-ϵ})。