What are AVL Tree Rotations? Explain LL, RR, LR, and RL cases with examples in Data Structures

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:

1. Single Rotation
2. 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:

• 1. First, perform a Left Rotation on the bottom two nodes to make it a straight left line (converts it to an LL case).

  2. 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:

• 1. First, perform a Right Rotation on the bottom two nodes to make it a straight right line (converts it to an RR case).

  2. 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.

AVL tree rotations are operations used to keep an AVL tree balanced after insertion or deletion. An AVL tree is a self-balancing binary search tree where the difference between the heights of left and right subtrees (called balance factor) should not be more than 1. When this balance is disturbed, rotations are applied to restore it.

There are four types of rotations: LL, RR, LR, and RL.

LL (Left-Left) Rotation: This case occurs when a node is inserted into the left subtree of the left child, making the tree left-heavy. To fix this, a single right rotation is performed. For example, if values are inserted in decreasing order like 30, 20, 10, the tree becomes unbalanced, and a right rotation makes 20 the new root with 10 as left child and 30 as right child.

RR (Right-Right) Rotation: This happens when a node is inserted into the right subtree of the right child, making the tree right-heavy. A single left rotation is used to fix it. For example, inserting 10, 20, 30 causes imbalance, and after left rotation, 20 becomes the root with 10 and 30 as its children.

LR (Left-Right) Rotation: This occurs when a node is inserted into the right subtree of the left child. It requires two rotations: first a left rotation on the left child, then a right rotation on the unbalanced node. For example, inserting 30, 10, 20 leads to this case, and after rotations, 20 becomes the root.

RL (Right-Left) Rotation: This happens when a node is inserted into the left subtree of the right child. It also requires two rotations: first a right rotation on the right child, then a left rotation on the unbalanced node. For example, inserting 10, 30, 20 results in this case, and 20 becomes the root after balancing.

These rotations ensure the AVL tree remains balanced, maintaining efficient search, insertion, and deletion operations.