An AVL Tree is a special type of Binary Search Tree (BST) that automatically keeps itself balanced after every insertion or deletion. The thing is, if a tree becomes too unbalanced, searching, inserting, and deleting data can become slower.
To prevent this, AVL Trees use rotations whenever the balance factor goes beyond the allowed range. The balance factor is calculated as:
Balance Factor = Height of Left Subtree − Height of Right Subtree
For an AVL Tree, the balance factor should generally remain between -1 and +1.
I think the main reason AVL rotations are needed is to maintain efficiency. Imagine adding nodes continuously to one side of a tree. Instead of looking like a tree, it would start looking like a linked list.
When that happens, operations that should be fast become slower. Rotations help rearrange the nodes and bring the tree back into balance without changing the Binary Search Tree properties.
Types of Rotations
1. LL Rotation (Left-Left Rotation)
This happens when a node is inserted into the left subtree of the left child.
Example:
30
/
20
/
10
The tree becomes left-heavy.
After a right rotation:
20
/ \
10 30
The tree is balanced again.
2. RR Rotation (Right-Right Rotation)
This happens when a node is inserted into the right subtree of the right child.
Example:
10
\
20
\
30
The tree becomes right-heavy.
After a left rotation:
20
/ \
10 30
Balance is restored.
3. LR Rotation (Left-Right Rotation)
This occurs when a node is inserted into the right subtree of the left child.
Example:
30
/
10
\
20
In this case, a single rotation is not enough.
Step 1: Perform a left rotation on 10
30
/
20
/
10
Step 2: Perform a right rotation on 30
20
/ \
10 30
The tree becomes balanced.
4. RL Rotation (Right-Left Rotation)
This occurs when a node is inserted into the left subtree of the right child.
Example:
10
\
30
/
20
Again, two rotations are required.
Step 1: Perform a right rotation on 30
10
\
20
\
30
Step 2: Perform a left rotation on 10
20
/ \
10 30
The AVL Tree becomes balanced again.
Examples
A simple way to remember these rotations is:
-
LL → Right Rotation
-
RR → Left Rotation
-
LR → Left Rotation + Right Rotation
-
RL → Right Rotation + Left Rotation
I personally found AVL rotations confusing when I first learned them because all four names looked similar. But once I understood that the names simply indicate the direction where the imbalance occurs, remembering them became much easier.
So, if you ask me about the four types of AVL Tree rotations, I would say they are techniques used to restore balance whenever the tree becomes unbalanced. LL and RR require a single rotation, while LR and RL require double rotations. These rotations ensure that the balance factor remains within the allowed range, helping the AVL Tree maintain fast search, insertion, and deletion operations.