Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 10] BINARY TREES 249

Huffman’s Algorithm

The general problem we want to solve is the following. Suppose a list ofnweights is given:

W 1 ,W 2 ,...,Wn

Among all the 2-trees withnexternal nodes and with the givennweights, find a treeTwith a minimum weighted
path length. (Such a treeTis seldom unique.) Huffman gave an algorithm to find such a treeT.
Huffman’s algorithm, which appears in Fig. 10-17, is recursively defined in terms of the numbernof weights.
In practice, we use an equivalent iterated form of the Huffman algorithm which constructs the desired treeTfrom
the bottom up rather than from the top down.

Fig. 10-17

EXAMPLE 10.12 LetA,B,C,D,E,F,G,Hbe eight data items with the following assigned weights:

Data item: ABC DEF GH

Weight: 22 5 11 19 2 11 25 5

Construct a 2-treeTwith a minimum weighted path lengthPusing the above data as external nodes.
Apply the Huffman algorithm. That is, repeatedly combine the two subtrees with minimum weights into a
single subtree as shown in Fig. 10-18(a). For clarity, the original weights are underlined, and a circled number
indicates the root of a new subtree. The treeTis drawn from Step (8) backward yielding Fig. 10-18(b). (When
splitting a node into two parts, we have drawn the smaller node on the left.) The path lengthPfollows:

P= 22 ( 2 )+ 11 ( 3 )+ 11 ( 3 )+ 25 ( 2 )+ 5 ( 4 )+ 2 ( 5 )+ 5 ( 5 )+ 19 ( 3 )= 280

Computer Implementation of Huffman’s Algorithm

Consider again the data in Example 10.12. Suppose we want to implement the algorithm using the computer.
Since some of the nodes in our binary tree are weighted, our tree can be maintained by four parallel arrays: INFO,
WT, LEFT, and RIGHT. The first eight columns in Fig. 10-19 show how the data may be stored in the computer
initially.
Each step in Huffman’s algorithm assigns values to WT, LEFT, and RIGHT in columns 9 through 15, which
correspond, respectively, to steps (2) through (8) in Fig. 10-18. Specifically, each step finds the current two
minimal weights and their locations, and then enters the sum in WT and their locations in LEFT and RIGHT. For
example, the current minimal weights after assigning values to column 11, which corresponds to step (4), are
12 and 19 appearing in WT[10] and WT[4].Accordingly, we assign WT[ 12 ]= 12 + 19 =31 and LEFT[ 12 ]= 10