What is a Huffman Tree?
Consider an extended binary tree (2-tree) discussed earlier in previous articles. In an extended binary tree, every node has either zero or two children. The nodes with two children are called internal nodes and the nodes with no children are called external nodes or terminal nodes.
In an extended binary tree, the total number of external nodes (E) is equal to one more than the number of internal nodes.
Also check: Bellman ford algorithm in data structure
The path length for any node is the number of minimum nodes traverse from the root node to that node.
The total path length for internal nodes is –
P1 = 0 + 1 + 2 + 1 = 4
The total path length for external nodes is –
P1 = 2 + 3 + 3 + 2 + 2 = 12
The formula given below can also be used to find the total path length of external nodes if the total path length of internal nodes is known.
Pₑ = p1 + 2n
Also check: Keywords in C Programming
Where n is the total number of internal nodes.
Let us suppose every external node, i, has some weight W, assigned to it. Then the weighted path length of external nodes P is found by the following formula –
P = w1p1 + w2p2 + ………………..wnpn
Where w1 denotes the weight and p1 denotes the path length of the ith external node.
Consider the following extended binary tree with the weights 7, 5, 3, and 6 assigned to their external nodes.
The total weighted path length of the first tree is –
P1 = 7*2 + 3*3 + 6*3 + 5*1 = 14 + 9 + 18 + 5 = 46
The total weighted path length of the second tree is –
P1 = 5*2 + 3*3 + 6*3 + 7*1 = 10+9+18+7 = 44
The total weighted path length of the second tree is –
P1 = 3*2 + 5*3 + 7*3 + 6*1 = 6+15+21+6 = 48.
Also check: max heap deletion algorithm
The total weighted path lengths of the above trees are different. The extended binary tree with the least weighted path length is called a Huffman tree.
Therefore, the second tree with the least weighted path length on its external nodes is a Huffman tree.
Huffman Algorithm in Data Structures
Huffman’s algorithm gives a method to construct an extended binary tree with a weighted path length from a set of given weights. Suppose N nodes with their weights W1, W2,……., Wn are given, Create a list L of those nodes –
Also check: spanning tree in data structure
Huffman Tree Algorithm
Given below is the algorithm for Huffman Tree –
- Choose two nodes with the least weights assigned to them, say, w1 and w2.
- Construct an extended binary tree by creating a new node as wi = w1 + s2.
- Discard w1 and w2 from the list and include wi.
- Repeat steps 1,2 and 3 until the list is exhausted.
So, in this article, we learned about the Huffman Tree and Huffman Algorithm.
Attempt Free Data Structures Online Test
