sicp每日一题[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, . . . ,2n 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?

这道题挺简单的，只要明白了霍夫曼编码的逻辑，自己画一下就可以了，这会是一种非常不平衡的树，除了权重最低的两个符号构成了一个完整的子树，其他的子树都只有一个叶子，n=5 时如下图所示，n=10太多了就不画了，跟这个类似。

可以看出，当有 n 个符号时，使用频率最高的符号只需要1位就可以表示，频率最低的则需要 n-1 位。