Table of Contents
- 1 Huffman Tree in Data Structure
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.
- Huffman coding techniques consists of two phase to assign a code for each character in the given input text.
- In first phase of Huffman coding technique we construct the Huffman tree.
- In second phase we assign 0 and 1 label to the edge of Huffman tree to find the code for the character.
Steps of each phase are discussed in next section.
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.
Algorithm to construct Huffman Tree
Algorithm to construct the Huffman Tree consist the following steps.
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.
Algorithm to Assign the Code for Character
To generate the code for each character we the following steps.
Step 1 – Visit the character from root.
Step 2 – For every left edge in the path from root to desired character node assign value 0 to edge and 1 for every right edge in the path.
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
Huffman Coding Example 3
Consider the following characters with the given frequency .
A:12 , B:15, C:7,D:13,E:9
(a) Construct the Huffman Tree.
(b) Find code for each character
Solution
Conclusion and Summary
Huffman Coding is an important technique used for lossless data compression. In this tutorial we have discussed the Huffman Coding Tree in Data Structure with example. Huffman Tree Construction Algorithm is explained in this tutorial with example.
After constructing the Huffman tree a unique code is generated for each character in the text. After getting code for each character we obtained the encoded form of given text. Text in encoded form is the compressed data.
