Huffman Tree Algorithm Assignment Help Online

• Binary tree along with every non-terminal node possessing two children.
• Gives optimal (min average code length) prefix free binary code in order to every ‘ai∈Σo’ for any provided probabilities ‘p(ai )>0’.

Huffman’s Algorithm:

Step-1: Create a terminal node for every ‘ai∈Σo’, along with probability ‘p(ai)’ and let ‘S’= the set of terminal nodes.

Step-2: Choose nodes ‘x’ and ‘y’ in ‘S’ using the two smallest probabilities.

Step-3: Substitute ‘x’ and ‘y’ in ‘S’ with a node along with probability ‘p(x)+ p(y)’. Also, create a node in the tree that is the actual parent associated with ‘x’ and ‘y’.

Step-4: Repeat ‘Step2-Step3’ untill ‘|S|=1’.

Example.

Σ0 =(A,B,…,E) and

The nodes in S are shown shaded.

Step1:

Step2:

Step3:

Step4:

Step5:

Step6: After redrawing the tree

Important topics in Huffman Tree

• Huffman Tree Example
• Steps to build Huffman Tree