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

From Drewiki
Jump to: navigation, search

Problem

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?

Solution

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.

Personal tools