Note: this wiki is now retired and will no longer be updated!
The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.
SICP 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 may bits are required to encode the most frequent symbol? the least frequent symbol?
The tree for n=5:
+ / \ 16 \ \ + / \ 8 \ \ + / \ 4 \ \ + / \ 2 1
The encodings for this tree are 0, 10, 110, 1110, and 1111.
The tree for n=10 is similar. For each such tree, 1 bit is required to encode the most frequent symbol (as 0), and n-1 bits are required to encode the least frequent symbol.