参考
总结归纳自the-importance-of-knowing-why-part3
问题定义
已知每个字母的使用频数, 现需要找到一个编码, 使得:
- 通信时的编码字符数尽可能少
- 没有二义性, 即没有任何一个字母的编码是另一个编码的前缀.
证明前序
首先, 用反证法, 证明每个编码都在前缀树的叶子节点上:
根据要求2, 使用前缀树来存储这个编码, 如果不是所有编码都在叶子节点, 则某个编码x存在于非叶子节点。对于这个编码x, 其左右子树中一定有另一个编码y(否则他就该是叶子节点), 于是, 编码到y的路径经过x, 则x是y的前缀, 与要求矛盾.
另外，根据要求1，用反证法可以确定，前缀树中每个非叶子节点都有两个孩子。
如果前缀树中有某个节点只有一个孩子，则将其去掉后，cost会更小。
正式证明
现在我们已经得出两个结论:
- 可以用前缀树存储编码, 且编码都在叶子节点上
- 前缀树中每个非叶子节点都有两个孩子。
列出通信时的总消耗:
cost of tree = Σ freq(i) * depth(i)
根据知其所以然提出的思想: 所谓最优解，就是说比其他所有解都要更好，由此可得出一个直接推论——最优解比与它邻近的所有候选解都要好。
上面这个性质究竟意味着什么呢？在该问题中, 最优解的cost一定小于等于任意邻近解.
我们取任意两个叶子节点的频率为f1和f2，深度为d1和d2，互换它们后可得到一个邻近解。互换时，其他叶子节点的cost保持不变，令为常量C。那么互换前总cost为C+f1d1+f2d2，互换后为C+f1d2+f2d1。前者来自最优解，必须小于等于后者，所以(C+f1d1+f2d2)-(C+f1d2+f2d1)=(f1-f2)(d1-d2)<=0。所以若f1>f2, 必有d1<=d2, 若f1<f2, 必有d1>=d2。于是这就引出了结论: 频率最低的叶子节点必然位于树的最底层，频率最高的叶子节点必然位于树的最高层。
那么频率第二低的叶子节点是否在最底层呢？我们同样可用反证法证明。
假设它为n2, 如果它不是最底层，则最低频率的节点的兄弟n3，其一定频率大于n2。将其它节点cost设为C, 则
(C+f2d2+f3d3)-(C+f2d3+f3d2)=(f2-f3)(d2-d3) <0, 将两者交换可以得到更优解，所以n2一定在最底层。
现在我们确定了频率最低的两个节点一定在最底层，但他们不一定是兄弟:
此时用归约的方法，让最低频率的两个节点互为兄弟。
如果当这两个最低频率的叶子不是兄弟的时候，的确存在着某棵最优霍夫曼树，那么通过交换它们各自的兄弟，从而让这两个叶子团聚之后，修改后的树仍然是最优的就可以了。事实情况也的确如此，证明非常直接——既然这里涉及到的所有4个节点都在最底层同一个高度上，那么互相交换的时候不会改变他们任何一个人的深度值，所以总cost不会改变。
现在我们定下了最小两个频率的节点，一个最自然的思路就是考虑第三小的叶子，因为前面说了，元素频率越低就越位于树的底部嘛。第三小的叶子有两种可能的归属:
-
跟最小的两个叶子同样位于最底层, 这个时候第三小的叶子的兄弟叶子在剩下的节点里找, 肯定是第四小的叶子(根据上文推导的"若f1<f2, 必有d1>=d2", 剩下的所有叶子都必须至少在该层上)
-
另一种归属就是往上一层去, (但不会更上一层。用反证可证明, 因为根据上文推导的"若f1<f2, 必有d1>=d2", 剩下的所有叶子都必须至少在该层上。如果它更上一层, 那空出的那一层就有频率更高的节点在, 于是矛盾) 。往上一层去了之后，它的兄弟是谁呢？不妨将它和刚才第一第二叶子的父节点结为兄弟(因为剩下的节点层数一定都在它以上, 用前面证明过的定理, 如果它不是兄弟, 也一定是同层, 同层之间节点互换不会改变编码的cost, 可将它与兄弟交换, 使它和父节点成为兄弟), 如下图：
我们发现, 这无非是选择将第三个与第四个节点"黏"在一起, 或者将第三个与第一二个节点之父"黏"在一起。哪一种更好呢?我们先举个例子看看.
上面这个{1, 2, 3, 4}的例子就是个很好的特例，如图（注：图中节点旁的数字一概为频率值，而非编号）:
多加折腾一番也许我们不难发现，如果将1，2及其父节点跟叶子4进行交换（注意：交换的时候1，2也被一同带走了，因为反正1，2两个节点已确定是好兄弟永远不会分家了，折腾的时候只能作为一个整体移动，所以这里也可以说是交换子树），那么树的编码将会变得更优，因为这样一次交换会将1和2的深度+1，意味着整棵树的代价+3，而同时会将叶子4的深度-1，也就是说整棵树的代价-4，总体上整棵树的代价就是+3-4=-1（注意，在计算的时候我们只需考虑被交换的局部，因为树的其他部分的代价保持不变）。如下图：
这个交换启发了我们，原来前面一开始说的交换两个叶子节点可以推广为交换内部节点和叶子节点，很快我们又意识到其实可以推广到交换任意两个节点(注意，当我们说交换内部节点的时候，其实是连同该内部节点作为局部根节点的整个子树都交换过去)。
对于最优霍夫曼树, 任何其它解都不会更"好", 所以无论互换哪两个节点，得到的树都不会变得"更好"(交换内部节点则是连同该内部节点作为局部根的子树一同带走)。我们记住这个结论，继续证明。
在最优霍夫曼树当中，两个节点n1和n2(n1与n2可能是叶子或子树, 由于叶子也是一种子树, 我们统一视为子树)，深度为d1和d2, 互换后可得到另一个解。互换时,其他节点的cost保持不变, 令为常量C。则互换前后, 子树n1内所有叶子提升距离(d1-d2), 子树n2内左右叶子下沉距离(d1-d2), cost的变化为-(d1-d2)∑n1+(d1-d2)∑n2=(∑n2-∑n1)(d1-d2)(∑n1代表其内所有叶子频数之和), 该值应当≤0, 所以若∑n2<∑n1, 则d1<=d2, 若∑n2>∑n1, 则d1>=d2。 所以, 当有一组子树或叶子时, 如果要组成最优霍夫曼树, 则内部叶子节点频数之和最小的那个子树/叶子, 应当处于最深处。
回到刚才的问题, 所以当n1、n2确定合并后, 我们可以将该子树代替原来的两个节点, 去和剩下的节点比较。{n1与n2子树, n3, n4}中, 哪一个适合放在最深处呢? 我们就选择内部叶子频数和最小的那一个, 然后再选择次小的那一个作为它的兄弟(归约方法)，将它们组合成一个子树，代替原来的节点和剩下的节点比较。于是剩下的问题就可以递归解决了！
证明图谱
所以真正的证明智慧在于
- 反证法, 证明出编码都在前缀树的叶子节点结构
- 通过交换法, 证明内部叶子频数和最小的那个子树/叶子应当在最深处。
- 通过归约法, 选出次小叶子频数和的子树/叶子, 与最小的那个组成兄弟。
- 递归将剩下的依次组成兄弟。
