Assignment No. 5: AVL Trees & Huffman Encoding
Subject: Data Structures
Management
Assigned: 3/7/2016
Assignment Marks: 30
Instructor: CS301 Team
Due Date: 3/7/2016
Attached Files: Non
Objective:
1- The objective of this assignment is to give you some practice exercise of AVL Trees and
Huffman encoding scheme.
Instructions:
1234-
This is an individual assignment. You will submit your work individually through your logins.
Write your name and roll number at the start of the assignment.
Do not copy and paste any thing from the internet. Your work must be original.
Please note that you must do your own work. If any one found copying from another
Student, no marks will be given to him/ her.
5- Deadline for this assignment is 3/7/2016This deadline will not be extended.
6- No assignment will be accepted through email before and after the due date.
7- If you have any problems, feel free to mail at.
Problems
Question 1:
Make an AVL tree for the following input.
79, 47, 76, 53, 75, 56, 90, 48, 63, 59
Show all the necessary rotations where possible
Question 2:
Consider the following AVL tree.
Show the tree after deleting the node 80.
Show the AVL tree after deleting the node 50.
Show the AVL tree after inserting the node 79.
Question 3:
Given Letters A, B, C, D, E with following frequencies.
Frequency Table
Character
Frequency Huffman Codes
A20
—————-B
11
—————-C
8
—————-D
12
—————-E
49
—————-A) Create a Huffman tree to determine the binary codes for each character.
B) Fill the codes into the table above.
C) Encode the following sequence ABCDE.
