An AVL Tree is a self balancing tree and in normal binary search tree, inserting data in sequently can create an sekwed tree (an single long line) tree which increases the search time.
What are AVL Tree Rotations?
When an new node is inserted or an existing node is deleted the height of subtress changes. If the balance of tree changes to 2 or -2 then its clearly voilets the AVL tree properties and becomes an unblanced tree and AVL Tree should be an Balanced Tree. in which Balance Should be 1, 0, or -1.
If Balance is not 1,0 or -1 then need to makes unbalance tree into an balancd tree through shifting the nodes up or down and the process of shifing nodes of unbalanced tree to make an balanced tree is called AVL Tree Rotation.
There are mailnly 2 catgories to perform this task are:
- Single Rotation
- Double Rotation
Types of AVL Tree Rotation
Case1. LL Rotation
Tree became unblance when an new node is insert in the left subtree of the left child.
To fix this issue we perform Single right rotation. Due to this the middle node is pulled up to become the new root and the old unbalanced root is pushed down to right and became an new parent.
For eg.
-
Example:
-
Insert nodes: 30, 20, 10
-
Problem: Node 30 has a BF of +2 (Left height 2 - Right height 0). The nodes 30 $\rightarrow$ 20 $\rightarrow$ 10 form a left-leaning line.
-
Solution: Rotate Right. Node 20 becomes the new root. Node 10 stays on its left, and Node 30 goes to its right. The tree is now balanced (BF of 20 becomes 0).
-
Case 2: RR Rotation (Right-Right Case)
The tree becomes unbalanced when a new node is inserted into the right subtree of the right child. (The structure looks like a straight line leaning to the right).
We perform a Single Left Rotation. The middle node is pulled up to become the new root, and the old unbalanced root is pushed down to the left.
-
Example:
-
Insert nodes: 10, 20, 30
-
Problem: Node 10 has a BF of -2 (Left height 0 - Right height 2). The nodes 10 $\rightarrow$ 20 $\rightarrow$ 30 form a right-leaning line.
-
Solution: Rotate Left. Node 20 becomes the new root. Node 10 goes to its left, and Node 30 stays on its right. The tree is balanced.
-
Case 3: LR Rotation (Left-Right Case)
The tree becomes unbalanced when a new node is inserted into the right subtree of the left child. (The structure looks like a bent elbow or zig-zag: Left then Right).
Because it is a zig-zag, a single rotation won't work. We need a Double Rotation:
-
-
First, perform a Left Rotation on the bottom two nodes to make it a straight left line (converts it to an LL case).
-
Then, perform a Right Rotation on the top nodes to balance the tree.
-
-
Example:
-
Insert nodes: 30, 10, 20
-
Step 1 (Left Rotation on 10 and 20): Node 20 moves up, and 10 moves down to its left. The tree is now 30 $\rightarrow$ 20 $\rightarrow$ 10 (which is an LL case).
-
Step 2 (Right Rotation on 30 and 20): Node 20 becomes the root, 10 is on the left, 30 is on the right.
-
Case 4: RL Rotation (Right-Left Case)
The tree becomes unbalanced when a new node is inserted into the left subtree of the right child. (The structure is zig-zag: Right then Left).
We need a Double Rotation:
-
-
First, perform a Right Rotation on the bottom two nodes to make it a straight right line (converts it to an RR case).
-
Then, perform a Left Rotation on the top nodes.
-
-
Example:
-
Insert nodes: 10, 30, 20
-
Step 1 (Right Rotation on 30 and 20): Node 20 moves up, and 30 moves down to its right. The tree is now 10 $\rightarrow$ 20 $\rightarrow$ 30 (which is an RR case).
-
Step 2 (Left Rotation on 10 and 20): Node 20 becomes the root, 10 is on the left, 30 is on the right.
-