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.
Does Huffman algorithm generate a minimal weight of a tree?
algorithms;algorithm analysis;huffman coding
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.