完美哈夫曼树问题：4字符集下最高频字符的最大可能频率求解

你的猜想是正确的，4个字符的哈夫曼树为完美满二叉树时，出现频率最高的字符的最大可能频率为总频率的$\frac{2}{5}$。 #

为了简化计算，我们将总频率归一化为1，设四个字符的频率满足 $w_1 \ge w_2 \ge w_3 \ge w_4 >0$，且 $w_1+w_2+w_3+w_4=1$，我们的目标是在约束「构造出的哈夫曼树为完美满二叉树（所有叶子节点深度相同，均为2）」下最大化 $w_1$。

核心约束推导 #

完美满二叉树的本质是：哈夫曼树根节点的两个子节点均为非叶子节点，没有任何原始字符直接作为根节点的子节点（否则该字符的编码长度为1，和其他字符长度不同）。
结合哈夫曼树的构造规则，可以推导出唯一的硬性约束：最大频率 $w_1$ 不能超过最小两个频率的和，即 $w_1 \le w_3 +w_4$。
原因是：如果 $w_1 > w_3 +w_4$，那么前两次合并后，会出现一个包含三个小频率字符的中间节点，最终会和 $w_1$ 作为根节点的两个子节点，此时 $w_1$ 为根节点的直接子节点，编码长度为1，不满足完美树要求。

极值计算 #

我们要最大化 $w_1$，因此取约束的等号边界：$w_1 = w_3 +w_4$，代入总频率公式可得：
$$w_1 + w_2 + w_1 = 1 \implies 2w_1 +w_2 =1$$
另外根据频率的大小关系 $w_2 \ge w_3$、$w_2 \ge w_4$，可得 $w_3 +w_4 \le 2w_2$，代入 $w_1 =w_3 +w_4$ 可得：
$$w_1 \le 2w_2 \implies w_2 \ge \frac{w_1}{2}$$
将上述不等式代入总频率公式：
$$2w_1 + \frac{w_1}{2} \le 1 \implies \frac{5w_1}{2} \le1 \implies w_1 \le \frac{2}{5}$$ #

当 $w_1 = \frac{2}{5}$ 时，等号成立的频率组合为 $w_1=\frac{2}{5}$，$w_2=w_3=w_4=\frac{1}{5}$，我们按哈夫曼规则构造树：

1. 第一次合并任意两个 $\frac{1}{5}$ 的节点，得到中间节点频率 $\frac{2}{5}$，剩余节点：$\frac{2}{5}$、$\frac{2}{5}$、$\frac{1}{5}$
2. 第二次合并剩余的 $\frac{1}{5}$ 和任意一个 $\frac{2}{5}$ 节点，得到中间节点频率 $\frac{3}{5}$，剩余节点：$\frac{2}{5}$、$\frac{3}{5}$
3. 第三次合并两个中间节点得到根节点，最终所有原始字符的深度均为2，符合完美树要求。

内容的提问来源于stack exchange，提问作者aydee45