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

250 BINARY TREES [CHAP. 10

Fig. 10-18

and RIGHT[ 12 ]=4. The last step tells us that ROOT=15, or we use that fact that ROOT= 2 n−1, where
n=8 is the number of external nodes. Thus all of Fig. 10-19 gives the required treeT.

Fig. 10-19

Remark:During the execution of Huffman’s algorithm we need to keep track of the current weights and to find
two of the minimal weights. This may be efficiently accomplished by maintaining an auxiliary minheap, where
each node contains a weight and its location in the tree. We use a minheap rather than a maxheap since we want
the node with the lowest weight to be on the top of the heap.

Application to Coding

Suppose a collection ofndata itemsA 1 ,A 2 ,...,Anare to be coded by means of strings of bits. Furthermore,
suppose the data items do not occur with the same probability. Then memory space and time may be conserved
by using variable-length strings, where items which occur frequently are assigned shorter strings and items which
occur infrequently are assigned longer strings. For example, country telephone codes use this principle. The
country code for United States is simply 1, for France is 33, and for Finland is 358. This section discusses a
coding using variable length that is based on theHuffman tree Tfor weighted data items, that is, a 2-treeTwith
minimum path lengthP.

Huffman Code:LetTbe the Huffman tree for thenweighted data itemsA 1 ,A 2 ,...An. Each edge inTis
assigned 0 or 1 according as the edge points to a left child or to a right child. The Huffman code assigns to each
external nodeAi, the sequence of bits from the rootRof the treeTto the nodeA. The above Huffman code has
the “prefix” property, that is, the code of any item is not an initial substring of the code of any other item. This
means that there cannot be any ambiguity in decoding any message using a Huffman code.