Experiment # 11.
AVL Tree Implementation
Objectives: To familiarize students with AVL Tree implementation i.e. insertion for single and double
rotation in AVL Tree
Tools: Eclipse IDE
Procedure: Writing C++ language program to perform the following tasks
Create a node class for AVL tree
Create a function to insert elements in an AVL tree
AVL tree – identical to a BST, barring the following possible differences:
Height of the left and right subtrees may differ by at most 1.
Height of an empty tree is defined to be (–1).
We can calculate the height of a subtree by counting its levels from the bottom. At some node,
we calculate the height of its left subtree and right subtree and get the difference between them.
AVL tree is given in figure 41 as shown below
An AVL
Leve
Tree
l
5 0
2 8 1
1 4 7 2
3 3
Figure 1: AVL Tree
In figure 1: the root of the tree is 5. At next level, we have 2 and 8, followed by 1, 4 and 7 at next
level where 1, 4 are left and right subtrees of node 2 and 7 is the left subtree of node 8. At the
level three, we have 3. The root is at level 0, followed by the levels 1, 2 and 3. The height of the
left subtree of 5. It is 3.
Similarly the height of the right subtree is 2. The difference of the height of left subtree and right
subtree of 5. The height of left subtree of 5 is 3 and height of right subtree of 5 is 2. So the
difference is
1. Similarly, we can have a tree in which right subtree is deeper than left subtree. The condition
in the AVL tree is that at any node the height of left subtree can be one more or one less than
the height of right subtree. These heights, of course, can be equal. The difference of heights
can not be more than 1. This difference can be -1 if we subtract the height of left subtree from
right subtree where the height of left subtree is one less than the height of right subtree. This
condition is not at the root. It should satisfy at any level at any node. Let’s analyze the height of
left subtree and right subtree of node 2. This should be -1, 0 or 1. The height of left subtree of
node 2 is 1 while that of right subtree of the node 2 is 2. Therefore the absolute difference
between them is 1. Similarly at node 8, the height of left subtree is 1 and right subtree does not
exist so its height is zero. Therefore the difference is 1. At leaves, the height is zero, as there is
no left or right subtree.
The figure 2 below is not an AVL Tree.
Not an AVL
tree Leve
l
6 0
1 8 1
1 4
2
3 5
3
Figure 2: Not an AVL Tree
The height of the left subtree of node 6 is three whereas the height of the right subtree is one.
Therefore the difference is 2. The balanced condition is not satisfactory. Therefore, it is not an AVL tree.
Algorithm: Steps to follow for insertion (Single Rotations and Double
Rotation) Let the newly inserted node be w
1. Perform standard BST insert for w.
2. Starting from w, travel up and find the first unbalanced node. Let z be the first
unbalanced node, y be the child of z that comes on the path from w to z and x be the
grandchild of z that comes on the path from w to z.
3. Re-balance the tree by performing appropriate rotations on the subtree rooted with z.
There can be 4 possible cases that needs to be handled as x, y and z can be
arranged in 4 ways. Following are the possible 4 arrangements:
a. y is left child of z and x is left child of y (Left Left Case)
b. y is left child of z and x is right child of y (Left Right Case)
c. y is right child of z and x is right child of y (Right Right Case)
d. y is right child of z and x is left child of y (Right Left Case)
Step 1: Create New C++ Program File and save it as [Link]
Step 2: Create a New class and save it as [Link]
Step 3: Write the following code as shown in figure below
Figure 3 (a): AVL Node Class
Figure 3 (b): AVL Node Class
Step 4: Create a New class and save it as [Link]
Step 5: Write the following code in it as shown in figures below
Figure 4 (a): AVL Class
Figure 4 (b): AVL Class
Figure 4 (c): AVL Class
Figure 4 (d): AVL Class
Figure 4 (e): AVL Class
Figure 4 (f): AVL Class
Step 6: Write the following code in main class such as [Link]
Figure 5 (a): AVL Main Class
Figure 5 (b): AVL Main Class
Lab Task(s): Perform the following
Task 1: Write a C++ program to implement AVL Tree and the code must contain following
functions.
insert(); for insertion of nodes in tree
balance(); for balancing of AVL Tree
height(); to find out height of AVL Tree
diff(); for finding height difference
ll_rotation(); left-left rotation
rr_rotation(); right-right rotation
rl_rotation(): right-left rotation
lr_rotation(); left-right rotation
inorder(); For inorder traversal of a tree. Provide snapshots of 4 outputs and
describe the achievement of all 4 rotation cases through key values of
various nodes.
Task 2: using the same logic for AvlInsert function, Develop code for an AvlDelete function
which will delete a specific node based on the provided key and then take care of any
imbalance in the tree. Include the delete option in the main menu as shown in the lab tutorial.