sicp-ex-2.71


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.


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


meteorgan

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.