Binary Trees - Data Structures and Algorithm Analysis - page 183

/ ** AHuffmancodingtree * /
classHuffTree<E>implementsComparable<HuffTree<E>>{
privateHuffBaseNode<E>root;//Rootofthetree

/ ** Constructors * /
publicHuffTree(Eel,intwt)
{root=newHuffLeafNode<E>(el,wt);}
publicHuffTree(HuffBaseNode<E>l,
HuffBaseNode<E>r,intwt)
{root=newHuffInternalNode<E>(l,r,wt);}

publicHuffBaseNode<E>root(){returnroot;}
publicintweight()//Weightoftreeisweightofroot
{returnroot.weight();}
publicintcompareTo(HuffTree<E>that){
if(root.weight()<that.weight())return-1;
elseif(root.weight()==that.weight())return0;
elsereturn1;

}

}

Figure5.28 Class declarations for the Huffman tree.

and IntlNode . This implementation reflects the fact that leaf and internal nodes
contain distinctly different information.
Figure 5.28 shows the implementation for the Huffman tree. Figure 5.29 shows
the Java code for the tree-building process.
Huffman tree building is an example of a greedy algorithm. At each step, the
algorithm makes a “greedy” decision to merge the two subtrees with least weight.
This makes the algorithm simple, but does it give the desired result? This sec-
tion concludes with a proof that the Huffman tree indeed gives the most efficient
arrangement for the set of letters. The proof requires the following lemma.

Lemma5.1 For any Huffman tree built by function buildHuff containing at
least two letters, the two letters with least frequency are stored in siblings nodes
whose depth is at least as deep as any other leaf nodes in the tree.

Proof: Call the two letters with least frequency l 1 and l 2 . They must be siblings
because buildHuff selects them in the first step of the construction process.
Assume that l 1 and l 2 are not the deepest nodes in the tree. In this case, the Huffman
tree must either look as shown in Figure 5.30, or in some sense be symmetrical
to this. For this situation to occur, the parent of l 1 and l 2 , labeled V, must have
greater weight than the node labeled X. Otherwise, function buildHuff would
have selected node V in place of node X as the child of node U. However, this is
impossible because l 1 and l 2 are the letters with least frequency. 2

Theorem5.3 Function buildHuff builds the Huffman tree with the minimum
external path weight for the given set of letters.