<< Previous exercise (2.70) | Index | Next exercise (2.72) >>

NB: We will use letters from the alphabet to represent the symbols.

Example with n=5:

{a b c d e} 31 / \ {a b c d} 15 e 16 / \ {a b c} 7 d 8 / \ {a b} 3 c 4 / \ a 1 b 2

The tree for n=10 looks similar, only larger.

The minimum number of bits to construct a symbol (i.e. the minimum depth to reach a leaf) for such trees is 1, for the symbol of weight 2^n-1.

The maximum number of bits will be n-1, for the two symbols of least weight.

In this problem, the shapes of huffman trees are same. Every node's left/right branch only have one node. That's because 1 + 2^2 + 2^3 + ... + 2^(n-2) = 2^(n-1)-1 < 2^(n-1). so every time we add a symbol into the Huffman tree, we make the symbol be the brother of the root node of the Huffman tree.