AVL Tree

19CSE212 : Data Structures and Algorithms

Dr. Chandan Kumar

Department of Computer Science and Engineering

Jan - Jun 2024

Dr Chandan Kumar Jan - Jun 2024

Contents

1 Introduction to AVL Tree

2 Why AVLTree?
3 Rotations in AVL tree

4 Operations on AVL Tree

Dr Chandan Kumar Jan - Jun 2024

AVL Tree
• AVL tree is a self-balancing binary search tree invented by G.M.
Adelson-Velsky and E.M. Landis in 1962. The tree is named AVL
in honour of its inventors.
• In an AVL tree, the heights of the two sub-trees of a node may
differ by at most one. Due to this property, the AVL tree is also
known as a height-balanced tree.
• The balance factor of a node is calculated by subtracting the
height of its right sub-tree from the height of its left sub-tree.
• Tree is said to be balanced if balance factor of each node is in
between -1 to 1, otherwise, the tree will be unbalanced and need
to be balanced.
Balance factor = Height (left sub-tree) – Height (right sub-tree)

Dr Chandan Kumar Jan - Jun 2024

AVL Tree
• If balance factor of any
node is 1, it means that the
left sub-tree is one level
higher than the right sub-
tree. “left-heavy tree”
• If balance factor of any
node is 0, it means that the
left sub-tree and right sub-
tree contain equal height.
“balanced tree”
• If balance factor of any
node is -1, it means that the
left sub-tree is one level
lower than the right sub-
tree. “right-heavy tree”
Dr Chandan Kumar Jan - Jun 2024
Why AVL Tree

• Guaranteed O(log n) Time Complexity: AVL trees maintain a

strict balance by ensuring the height difference between the left and
right subtrees of any node is at most one. This guarantees that
operations such as search, insert, and delete all have a time
complexity of O(log n).
• Efficient Lookups: The balanced nature of AVL trees ensures that
the path from the root to any leaf is short, making search operations
efficient and predictable.
• Self-Balancing: AVL trees automatically maintain their balance
during insertions and deletions. This is done through rotations
(single or double), which adjust the tree structure without needing
extensive reorganization.

Dr Chandan Kumar Jan - Jun 2024

AVL Tree Rotations
• AVL tree rotations are fundamental operations used to maintain the
balance of an AVL tree after insertions and deletions.
• The goal of these rotations is to restore the AVL property, which
requires that the height difference between the left and right
subtrees of any node is at most one.
• The AVL tree rotations involve rearranging the tree structure
without changing the order of elements. The positions of the nodes
of a subtree are interchanged.
• There are four types of rotations: LL Rotation, RR Rotation, LR
Rotation (Left-Right Rotation), and RL Rotation (Right-Left
Rotation).

Dr Chandan Kumar Jan - Jun 2024

AVL Tree Rotations

Rotations

Double
Single Rotation
Rotation

Right Left (RL) Left Right (LR) Right Rotation Left Rotation
Rotation Rotation (RR Rotation) (LL Rotation)

Dr Chandan Kumar Jan - Jun 2024

LL Rotation
• LL rotation is performed when a newly inserted node is in the left
sub-tree of the left subtree of the particular node.
• LL Rotation is performed when a newly added node violates the
property of the AVL tree which means it changes the balance factor
of a node out of range -1 to 1.
• Here, we have inserted
a new node 10 to the
left of left to node 30.
• To make it balanced
tree we will apply LL
Rotation on the tree.
• We will apply the right rotation and after that, we can see the
resultant tree becomes balanced.

Dr Chandan Kumar Jan - Jun 2024

Example of LL Rotation

Insert 18 into left

of left to node 45.

After performing
LL Rotation

Dr Chandan Kumar Jan - Jun 2024

RR Rotation
• RR rotation is performed when a newly inserted node is in the right
sub-tree of the right subtree of the particular node.
• RR Rotation is performed when a newly added node violates the
property of the AVL tree which means it changes the balance factor
of a node out of range -1 to 1.
• Here, we have inserted
a new node 30 to the
right of right to node
10.
• To make it balanced
tree we will apply RL
Rotation on the tree.
• We will apply the left rotation and after that, we can see the resultant
tree becomes balanced.
Dr Chandan Kumar Jan - Jun 2024
Example of RR Rotation

Insert 89 into it

After performing
RR Rotation

Dr Chandan Kumar Jan - Jun 2024

LR Rotation
• LR rotation is performed when a newly inserted node is in the right
sub-tree of the left subtree of the particular node.
• Here, we have inserted
a new node 20 to the
right of left node 30.
• To make it balanced
tree we will apply LR
Rotation on the tree.

• We will apply the left rotation and after that, we will apply the right
rotation.
• Now again the tree becomes unbalanced like in the first case, so we
have to apply LL Rotation to make it balanced.

Dr Chandan Kumar Jan - Jun 2024

Example of LR Rotation

A new node 37 is inserted

in the right sub-tree of the
left sub-tree of the critical
node 45.

After performing
LR Rotation

Dr Chandan Kumar Jan - Jun 2024

RL Rotation
• RL rotation is performed when a newly inserted node is in the left
sub-tree of the right subtree of the particular node.
• Here, we have inserted
a new node 20 to the
left of right node 30.
• To make it balanced
tree we will apply RL
Rotation on the tree.

• We will apply the right rotation and after that, we will apply the left
rotation
• Now again the tree becomes unbalanced like in the first case, so we
have to apply RR Rotation to make it balanced.

Dr Chandan Kumar Jan - Jun 2024

Example of RL Rotation

A new node 92 is inserted

in the left sub-tree of the
right sub-tree of the critical
node 90.
After performing
RL Rotation

Dr Chandan Kumar Jan - Jun 2024

Operation on AVL Tree

• Three basic operations can be performed on the AVL tree: Insert,

Delete and Search.
Insert: Algorithm for Insertion in an AVL Tree
Step 1: START
Step 2: Insert the node using BST insertion logic.
Step 3: Calculate and check the balance factor of each node.
Step 4: If the balance factor follows the AVL criterion, go to step 6.
Step 5: Else, perform tree rotations according to the insertion done.
Once the tree is balanced go to step 6.
Step 6: END

Dr Chandan Kumar Jan - Jun 2024

Example of Insert Operation on AVL Tree
• Let the initial tree be:
• Let the node to be inserted be: 10
 Go to the appropriate leaf node to insert
a newNode using the following recursive
steps. Compare newKey with rootKey of the
current tree.

1. If newKey < rootKey, call the insertion algorithm on the left

subtree of the current node until the leaf node is reached.
2. Else if newKey > rootKey, call the insertion algorithm on the right
subtree of the current node until the leaf node is reached.
3. Else, return leafNode.

Dr Chandan Kumar Jan - Jun 2024

Example of Insert Operation on AVL Tree

 Compare leafKey obtained from the above steps with newKey:

1. If newKey < leafKey, make newNode as the leftChild of leafNode.
2. Else, make newNode as rightChild of leafNode.

Dr Chandan Kumar Jan - Jun 2024

Example of Insert Operation on AVL Tree
 Update balanceFactor of the nodes.

 If the nodes are unbalanced,

then rebalance the node.
1. If balanceFactor > 1, which
means the height of the left
subtree is greater than that of
the right subtree. So, do a right
rotation or left-right rotation
1. If newNodeKey <
leftChildKey do the right
rotation.
2. Else, do left-right rotation.

Dr Chandan Kumar Jan - Jun 2024

Example of Insert Operation on AVL Tree
2. If balanceFactor < -1, it means the height of the right subtree is
greater than that of the left subtree. So, do a right rotation or
right-left rotation
1. If newNodeKey > rightChildKey do a left rotation.
2. Else, do right-left rotation

Dr Chandan Kumar Jan - Jun 2024

Operation on AVL Tree
The final tree is:

Prob: Construct an AVL tree by inserting the following elements in

the given order: 63, 9, 19, 27, 18, 108, 99, 81.

Dr Chandan Kumar Jan - Jun 2024

Operation on AVL Tree
Soln:

Dr Chandan Kumar Jan - Jun 2024

Operation on AVL Tree
The deletion of a node in an AVL tree is similar to that of binary
search trees. Deletion may disturb the AVLness of the tree, so to
rebalance the AVL tree, we need to perform rotations.
Delete: Algorithm for Deletion in an AVL Tree
Step 1: START
Step 2: Find the node. If the element is not found, go to step 7.
Step 3: Delete the node using BST deletion logic.
Step 4: Calculate and check the balance factor of each node.
Step 5: If the balance factor follows the AVL criterion, go to step 7.
Step 6: Else, perform tree rotations to balance the unbalanced nodes.
Once the tree is balanced go to step 7.
Step 7: END
Dr Chandan Kumar Jan - Jun 2024
Example of Delete Operation on AVL Tree
1. Locate node to be Deleted (recursion is used to find node to be
Deleted)
2. There are three cases for deleting a
node:
a) If nodeToBeDeleted is the leaf node
(ie. does not have any child), then
remove leaf node.
b) If nodeToBeDeleted has one child,
then substitute the contents of
nodeToBeDeleted with that of the
child. Remove the child.
c) If nodeToBeDeleted have two
children, find the in-order successor
w of nodeToBeDeleted (ie. node with
a minimum value of key in the right
subtree).
Dr Chandan Kumar Jan - Jun 2024
Example of Delete Operation on AVL Tree
Substitute the contents of nodeToBeDeleted
with that of w.
Remove the leaf
node w.

Dr Chandan Kumar Jan - Jun 2024

Example of Delete Operation on AVL Tree
Update balanceFactor of the nodes.
Rebalance the tree if the balance factor of
any of the nodes is not equal to -1, 0, or 1.

Dr Chandan Kumar Jan - Jun 2024

Example of Delete Operation on AVL Tree
The final tree is:

Prob: Consider the AVL tree

given in below Fig. and delete 72
from it.

Dr Chandan Kumar Jan - Jun 2024

Example of Delete Operation on AVL Tree

Prob: Delete nodes 52, 36, and 61 from the AVL tree given in
below Fig.

Dr Chandan Kumar Jan - Jun 2024

Example of Delete Operation on AVL Tree
Prob: Delete nodes 52, 36, and 61 from the given below AVL tree.

Dr Chandan Kumar Jan - Jun 2024

List of References

https://www.javatpoint.com/
https://www.tutorialspoint.com
https://www.geeksforgeeks.org/
https://www.prepbytes.com/blog/tree/avl-
tree-in-data-structure
https://www.scholarhat.com/tutorial/datastr
uctures/avl-tree-in-data-structures
https://chat.openai.com/

Dr Chandan Kumar Jan - Jun 2024