Table of Contents
Huffman Tree in Data Structure
- Huffman Tree in Data Structure is used in Huffman Coding.
- In this tutorial we will learn about Huffman coding tree in data structure.
- Questions based on Huffman tree are generally asked in different university examination of Data Structure subject and also in GATE and UGC NET exam.
Frequently Asked Questions
Some frequently asked questions based on Huffman Tree in Data Structure are given below. After reading this tutorial students can answer these questions.
- What is Huffman Coding ?
- What is Huffman tree ?
- How Huffman Coding Works ?
- What is Huffman Coding Complexity ?
- What are Huffman Coding Applications ?
- Write Huffman Coding Algorithm.
Let’s start with introduction of Huffman Coding.
What is Huffman Coding ?
- Huffman Coding is a Data Compression Techniques which is used to compress the data without loosing the data.
- In Huffman Coding algorithm, code of variable length is assigned to various input characters.
- The code length represents that how frequently characters are used.
- Most frequent used characters have the smallest codes and least frequently used characters have longer codes.
What is Huffman Tree ?
- Huffman Tree is a Full Binary Tree in which beach leaf of the tree corresponds to a letter in the given alphabet.
- Huffman tree is treated as the Binary Tree associated with minimum external path weight.
- So goal is to construct the minimum external path weight.
- Huffman Coding Tree is built during Huffman coding data compression technique.
How Huffman Coding Works ?
Huffman coding provides the code to character such that the length of code depends on the relative frequency or weight of corresponding character.
In Huffman Coding algorithm at first Huffman Tree is constructed to encode a given character in the text.
In Huffman Coding following steps are used to construct the Huffman Coding Tree.
Step 1 – Create leaf node for each character of the text.
Step 2 – Leaf node of character contains the occurring frequency of that character.
Step 3 – Arrange all nodes in increasing order of their frequency.
Step 4 – Consider first two nodes having minimum frequencies and create a internal node from these nodes. The frequency of the created node will be the sum of frequencies of these two nodes.
Step 5- Make the first node as left left child of created node and second node as right child of created node.
Step 6- Keep repeating step 3 to step 5 until all characters form a single tree. Finally obtained tree is the desired Huffman Tree.
Huffman Coding Tree Example
Two examples or problems based on Huffman Tree in Data Structure are explained in the picture.
Question 1. Construct Huffman Tree for the following characters with given frequencies and write code for each character.
a:5 , b:9, c:12, d:13, e:16, f:45
Question 2. Construct the Huffman Coding Tree for the word MAHARASHTRA
Step wise step solution of these question is explained in following pictures
Conclusion and Summary
In this tutorial we have discussed the Huffman Coding Tree in Data Structure with example.
