0
$\begingroup$

Consider the weights: 10, 12, 13, 16, 17, 17.

(a) Construct an optimal coding scheme for the weights given by using a tree.

(b) What is the total weight of the tree you found in part (a)?

  • 0
    @Rick: You just reminded me that I’d not upvoted your answer; fixed.2012-12-11

2 Answers 2

1

I presume that you can construct the tree, given the hints you've been offered. Once that's done, at each non-leaf node, arbitrarily assign a $0$ and a $1$ to each branch, Then the code for each leaf node is just the sequence of these branch values, reading from the top to the bottom. For example, if the leaf nodes contain 10, 12, 13, 16, 17, 17, reading from left to right, then assigning $0$ to each left branch and $1$ to each right branch gives you the codes $ \begin{align} 10 &: 000 \\ 12 &: 001 \\ 13 &: 010 \\ 16 &: 011 \\ 17 &: 10 \\ 17 &: 11 \\ \end{align} $ along with 31 other equally good codes.

1

This is the tree that Rick Decker used in his answer. Each node of the tree that isn’t a leaf has two edges leading down from it; the one to the left is labelled with a red $0$ and the one to the right with a red $1$. Think of the tree as a road map; a string of red numbers can be used to describe how to get from the root ($85$) to one of the leaves. To get from the root to the leaf $13$, for instance, you must go left ($0$), then right ($1$), then left ($0$) again, so the route is $010$, and that’s the code assigned to the weight $13$ leaf.

Notice that the most heavily weighted leaves $-$ the two $17$’s $-$ are closest to the root and so have the shortest codes; this is what makes the Huffman encoding efficient.

enter image description here