12.3.2 Representation of Huffman Trees

Let us now consider how the binary tree constructed by the Huffman algorithm should be stored in memory. To this end we consider an example that shows that even though the weighted path length is as small as possible for a given set of weights, the depth of the tree can still be great.

Example 12.1

Suppose that the first n Fibonacci^* numbers are assigned as weights to characters of an alphabet represented as terminal nodes in a tree. The task is to generate a Huffman code. n

^*The Fibonacci sequence is the sequence of integers F₀, F₁, F₂, . . . that starts with F₀ = 0 and F₁ = 1, with each succeeding integer found by adding its two predecessors. Thus the sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . , F_n?, . . . , where F₀ = 0, F₁ = 1, F_n+2 = F_n+1 + F_n, _n ?/FONT> 0.

The Huffman algorithm would construct the tree shown in Figure 12.5. This tree has depth n. Hence the Huffman algorithm may generate trees whose depth is O(n). If a sequential representation were used for such trees, considerable storage would be wasted. For large n, the storage would not even be available. A good alternative is a linked representation of the tree.

Figure 12.5 Tree Constructed by the Huffman Algorithm for Fibonacci Weights