Page 394, Exercise 2 - Huffman Trees

The usual proof involves induction on the number of nodes.   Remember that the Huffman algorithm utilizes the greedy method to determine the merging.  At each instance, it picks the optimal solution given current information.  If the solution is optimal then we should be able to show that exchanging two leaf nodes attached to an internal node in the tree with two leaf nodes that have not been added to the tree produces a tree that has the same
path lengths and  weights as the original tree.  For example, assume that we have two nodes X1 and X2 that are attached to the tree, and two nodes Y1 and Y2 that are not attached to the same internal node as X1 and X2.  We should be able to swap X1 with Y1 and X2 with Y2 and not change the final outcome.  The following figure shows a sample tree.

The tree, after swapping the two sets of nodes, has not changed in either the path length or the total weight.

b) The rule "First add (1-n) mod (m-1) runs of length 0..." is not quite correct.  For m-way Huffman trees the rule, according to Knuth, assumes that n mod (m-1) = 1.  If this is not correct, we add nodes  containing a zero until the assumption is met. 

Example:   Assume that n = 9 and m = 4.  Since 9 mod 3 = 0, we need to add one dummy node.  The tree is constructed, using the same technique discussed for the binary version: on each pass the m smallest elements are merged.  Assuming our n values are 1 .. 9, we would obtain the following tree.

The proof is analogous to the proof given in a.  We simply demonstrate that exchanging two leaf nodes attached to an internal node, and two leaf nodes not yet attached to the tree, produce a tree with the same depth and weight.