Practical No.

09 (D-19)
Title: Implementation of Adelson, Velskii, and Landi (AVL) tree.
Aim: A Dictionary stores keywords and its meanings. Provide facility for adding new keywords,
deleting keywords, updating values of any entry. Provide facility to display whole data sorted in
ascending/ Descending order. Also find how many maximum comparisons may require for finding
any keyword. Use Height balance tree and find the complexity for finding a keyword.
Objectives:
• To understand concept of height balance tree.
• To understand the different operations on AVL tree.
Outcomes:
• Apply the operations on AVL tree.
Requirements:
• Software Requirements:
o Operating System recommended: 64-bit Open source Linux or its derivative
o Programming tools recommended: - Text Editor and g++ compiler.
• Hardware Requirements:
o I3 or above processor, 2 GB or above RAM, 512 GB or above Hard-disk etc
Theory:
It is observed that BST's worst-case performance is closest to linear search algorithms, that
is Ο(n). In real-time data, we cannot predict data pattern and their frequencies. So, a need
arises to balance out the existing BST.
AVL Tree:
An AVL (Adelson, Velskii and Lendis) tree is height balanced tree. These trees are binary
search trees in which the height of two siblings are not permitted to differ by more than 1.
i.e. |height of left subtree - height of right subtree| <=1.
Adelsion, Velski and Lendis in 1962 introduced binary tree structure that is balanced with
respect to height of subtrees. The tree can be made balanced and because of this retrieval
of any node can be done in O(log n) times, where n is total number of node. From the
name of these scientists the tree is called AVL tree
Height Balance Tree (AVL):
An empty tree is height balanced.
If T is a non-empty binary tree with TL and TR as its left and right subtrees. The T is
height balanced if and only if
i) TL and TR are height balanced.
ii) |hL — hR| <= 1 where hL and hR are heights of TL and TR
The Idea of balancing a tree is obtained by calculating the balance factor of a tree.
Definition of Balance Factor:
The balance factor BF(T) of a node T in binary tree is defined to be (hL - hR) where hL
and hR are heights of lelt and right subtrees of T.
For any node in AVL tree the balance factor i.e. BF(T) is -1, 0 or +1.
Operations of AVL Trees:
There are three operations that are commonly carried out on AVL tree. And those are
1. Insertion of a node.
2. Deletion of a node at any position.
3. Searching the desired node.
After performing insertion and deletion operations, sometimes the tree structure needs to
be rearranged, because an AVL tree is a height balanced tree in which the balance factor
should always be -1, 0 or +1.
Insertion of a node into an AVL tree:
Insertion of new data into an AVL tree is carried out in two steps.
Insertion algorithm:
1. Insert a new node as new leaf just as in ordinary binary search tree.
2. Now trace the path from insertion point (new node inserted as leaf) towards root.
For each node ‘n’ encountered, check if heights of left (n) and right (n) differ by
at most 1.
a) It yes, move towards parent (n).
b) Otherwise restructure by doing either a single rotation or a double rotation.
Thus once we perform a rotation at node 'n' we do not require to perform any rotation at
any ancestor on ‘n’.
Rebalancing of the tree is carried out through rotation of the deepest node with BF=2 or
BF= -2.
Rotations:
Some modifications done on AVL tree in order to rebalance it is called rotations of AVL
tree. There are two types of rotations:
1. Single rotation:
a. Left-Left (LL rotation)
b. Right-Right (RR rotation)
2. Double rotation
a. Right-Left (RL rotation)
b. Left-Right (LR rotation)
Left Rotation: When a node is added into the right subtree of the right subtree (RR),
if the tree gets out of balance, we do a single left rotation.

Right Rotation: If a node is added to the left subtree of the left subtree (LL), the AVL
tree may get out of balance, we do a single right rotation.
Left-Right Rotation: A left-right rotation is a combination in which first left rotation
takes place after that right rotation executes.

Right-Left Rotation: A right-left rotation is a combination in which first right rotation

Searching:
As AVL tree is basically binary search tree, the algorithm used for searching node from
binary search tree is used for searching a node from AVL tree.
Algorithm for searching:
1. Consider the node to be searched as ‘Key’ node.
2. Compare key with root node. If key < root then go to the left node and call this
left nude as current node. If key > root then go to the right node and call this right
node as current node otherwise the desired node is the root node.
3. Compare key with current node. If key < current node then go to left node and
call this left node as current node. If key > current node then go to right node and
call this right node as current node, Otherwise if key = current node then desired
node is present in an AVL tree. Thus repeat step 3 until the desired node is found
or visiting the entire tree is not over.
For example: Consider an AVL tree as given below

Now if we want to search for node 18 then we will follow the following steps -
1. Compare 18 with root nude 10. As 18 > 10 we will move on right sub-branch.
2. Compare 18 with 14. As 18 > 14, we will move on right sub-branch.
3. Compare 18 with 25. As 18 < 25, we will move on left sub-branch.
4. Compare 18 with 18. As the match is found, we will declare that the desired node
is present in an AVL tree.
Deletion:
Even after deletion of any particular node from AVL tree, the tree has to be restructured
in order to preserve AVL property. And thereby various rotations need to be applied.
Algorithm for deletion:
1. Search the node which is to be deleted
2.
a) if the node to be deleted is a leaf node then simply make it NULL to
remove
b) If the node to be deleted is not a leaf node i.e. node may have one or two
children, then the node must be swapped with its inorder successor. Once
the node is swapped. We can remove this node.
3. Now we have to traverse back up the path towards root, checking the balance
factor of every node along the path. If we encounter unbalancing in some subtree
then balance that subtree using appropriate single or double rotations.
Conclusion: Thus, We have successfully implemented AVL tree and performed different
operations on it.