Construction of the Tree

The Huffman algorithm generates the most efficient binary code tree at given frequency distribution. Prerequisite is a table with all symbols and their frequency. Any symbol represents a leaf node within the tree.

The following general procedure has to be applied:

• search for the two nodes providing the lowest frequency, which are not yet assigned to a parent node
• couple these nodes together to a new interior node
• add both frequencies and assign this value to the new interior node

The procedure has to be repeated until all nodes are combined together in a root node.

Example: "abracadabra"

   Symbol   Frequency
     a       5
     b       2
     r       2
     c       1
     d       1

According to the outlined coding scheme the symbols "d" and "c" will be coupled together in a first step. The new interior node will get the frequency 2.

 <   ^   >