Huffman Trees

Fun with Bits

Huffman Trees

• Each node has 0 or 2 children
• Only leaf nodes contain data
• Data in each leaf node is unique

Huffman Coding

• Basic compression
• Performs compression on characters (not entire words)
• Represent most frequent characters using shortest bit-length

Building a Huffman Tree

1. Create a table of values mapping characters to their frequencies
2. Create a priority queue where the key is the frequency and the data is the character (minimum values have higher priority)
3. Insert all of the values from the table into the priority queue
4. If the priority queue has a single element, you're done, this is the root of the tree
5. Poll the priority queue twice and create a binary tree with those nodes
6. Add the frequencies of the newly created tree and offer back to the priority queue
7. Return to step 4

Example / In Lab Discussion

• Create a Huffman tree for the data humuhumunukunukuapuaa

Character	Frequency
u	9
p	1
a	3
n	2
m	2
k	2
h	2