# sicp-ex-2.71

Exercise 2.71. Suppose we have a Huffman tree for an alphabet of n symbols, and that the relative frequencies of the symbols are 1, 2, 4, ..., 2^n-1. Sketch the tree for n=5; for n=10. In such a tree (for general n) how many bits are required to encode the most frequent symbol? the least frequent symbol?

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.

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.

posxxa

For any n,the most frequent symbol code is 0.It's straightforward.

And the least frequent symbol,if n is infinite,we can simular merge process:

1,2,4,8,16,...,n

3,4,8,16,...,n

7,8,16,...,n

We can discover the merge process is regulation and also straightforward. Imagining tree picture.The least frequent symbol code is (* n 1) (left corresponds 0,right corresponds 1.)