哈夫曼编码构造贪心解法：贪心选择性质证明疑问

你提到的引理16.2原文为：

设C为字母表，其中每个字符c∈C对应频率c.freq；令x和y为C中频率最低的两个字符，则存在C的最优前缀编码，使得x和y的码字长度相同，仅最后一位存在差异。

证明过程中“将x、y替换到最大深度兄弟叶节点位置”的构造前提完全不会导致证明丧失一般性，核心原因如下：

• 首先要明确引理的证明目标：引理不需要证明「所有最优前缀码都满足x、y的码字仅最后一位不同」，只需要证明「存在至少一个最优前缀码」满足这个性质即可——这也是贪心选择性质证明的标准要求：只要能证明贪心选择是某一个最优解的组成部分，就可以支撑后续贪心算法的正确性，不需要要求所有最优解都包含这个选择。
• 其次，「选取最大深度的两个兄弟叶节点」不是凭空附加的特殊约束，是对任意最优前缀码树都必然成立的结构性质：
  最优前缀码对应的二叉树一定是满二叉树——要是存在只有一个孩子的内部节点，直接把这个节点删掉，将其子节点上提一层，所有经过这个节点的码字长度都减1，总编码代价会严格降低，就和树的最优性矛盾了。同时最大深度位置上不可能存在内部节点，否则内部节点的子节点深度会超过当前最大深度，和“最大深度”的定义矛盾。因此不管取哪一棵最优前缀码树，必然存在至少一对位于最大深度的兄弟叶节点，这个选择对所有最优树通用，不存在“挑特殊情况证明”的问题。
• 再者，将x、y放到最大深度兄弟位只是证明过程中使用的构造技巧，不是引理结论要求的必要条件：
  替换操作的代价计算逻辑非常清晰：设原树中选中的最大深度兄弟节点为a、b，深度为整棵树的最大深度D，原树中x的深度为d_x、y的深度为d_y。由于x、y是全字母表频率最低的两个字符，因此必然满足x.freq ≤ a.freq、y.freq ≤ b.freq，且不管x、y原来在什么位置，深度都不会超过整棵树的最大深度，即d_x ≤ D、d_y ≤ D。交换x和a、y和b的位置后，总代价的变化量为(a.freq - x.freq)*(d_x - D) + (b.freq - y.freq)*(d_y - D)，两个项均小于等于0，因此新树的总代价必然不高于原最优树的代价，即新树也是最优树；同时新树中x和y是深度相同的兄弟节点，对应码字长度一致、仅最后一位不同，刚好满足引理要证明的存在性结论。
• 你观察到的“x、y位于最大深度并非引理结论的必要条件”是完全正确的：实际场景中完全可能存在其他最优前缀码，x、y并不在最大深度位置（比如多字符频率相等时，多种编码树结构总代价一致，都是最优解）。但证明过程从来没有声称“所有满足引理结论的最优树都必须让x、y处于最大深度”，只是构造出了其中一个满足结论的最优树而已，构造过程中用到的特殊位置选择只是为了简化代价差的推导，属于证明技巧的范畴，没有缩小证明的覆盖范围。

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