Cheap and Secure Web Hosting Provider : See Now

# Does Huffman algorithm generate a minimal weight of a tree?

, ,
Problem Detail:

Does Huffman algorithm generate a minimal weight of a tree?

I noticed that by trying to make two different trees with the same frequencies of letters, I get different weights of the trees.

We defined the weight of the tree as $\displaystyle\sum_{c\in C}f(c)d(c)$ where $C$ is all the letters, $f()$ is the frequency of the letter, $d()$ is the depth in the tree of that letter.

#### Answered By : Yuval Filmus

If you normalize the frequencies so that they add to 1, then the weight of the tree is just the average codeword length, which is exactly what Huffman's algorithm tries to minimize. Check this section of the Wikipedia article you link to.