Confused about Huffman Trees

Question

A quick tutorial on generating a huffman tree

Confused about Huffman Trees. Near the end of that link above, it shows the tree with 2 elements left, and then the completed tree. I'm confused about the way that it is branched. Is there a specific way a huffman tree needs to be branched?

For example, 57:* with its right child 35:* is branched off to the right. Could it have been 35 branched to the left with 22 branched to the right? Also, why wasn't 22:* paired up with 15:4 - it just paired with 20:5 to create a new tree.

From initial obersvations it seems the tree does not need to be balanced or have any specific order other than that the frequencies of a leaf add up to the value of the parent node. Could two people creating a huffman tree with the same data end up with different encoding values?

Answer 1

The key to Huffman trees is this:

Sort this list by frequency and make the two-lowest elements into leaves

If you have more than two elements that have the lowest frequency (e.g. 3,4,4...), any two will do (3 and either of 4s - not two 4s). Also, it is not important which of these lowest elements is assigned 0 and which is 1. These two facts allow different yet valid Huffman encodings to arise from the same data.

The Huffman tree is supposed to be balanced by frequencies, not by the number of nodes. Thus the following is balanced:

(100 (50 (25 (12 (12 1)))))

and this is not:

(((100 50) 25) ((12 12) 1)))

Specifically in your question, 15 is paired with 20 and not 22 because 15 and 20 are the two lowest remaining values (both lower than 22). Either branching (left or right) would have been fine, as long as it's consistent (always smaller-left, or always smaller-right, within the same algorithm, so that the encoding can be reconstructed at the other end).

Answer 2

The posts so far are wrong and misleading: the choice of leaves with equal weights does matter and they do change how well they compress data.

Here's a counter example that demonstrates how different choices lead to different compression rates: ABBBCCCDDDDEEEEEEEE

A:1, B:3, C:3, D:4, E:8. First step: take A and B to form a node with weight 4. Second step:

If you take the newly created node in the first step with C, then you get (19 (11 (7 (4 (1-A) (3-B)) (3-C)) (4-D)) (8-E)) which gives 37-bits compressed data.

If, on the other hand, you take D, which also has the weight 4, instead of the newly created node, you get (19 (11 (4 (1-A) (3-B)) (7 (3-C) (4-D))) (8-E)) which gives 41-bits compressed data.

Answer 3

Everything is explained on the page. 22:* wasn't paired up with 15:4 because in each step, two nodes with the lowest elements are combined. This creates an unique order.

Huffman codes can be different (if you have multiple values with the same frequency or exchange 0 and 1 representation of left/right), but huffman lengths can't be.

Branching left/right is just a matter of how to draw the tree or represent it graphical, so this doesn't matter.