AVL Tree Rotations: LL, RR, LR, and RL Rotations

Jab AVL tree me naya node insert karne par balance factor +2 ya -2 ho jata hai, toh balance restore karne ke liye 4 standard rotational techniques use ki jati hain: do Single Rotations (LL aur RR) aur do Double Rotations (LR aur RL).

The 4 Imbalance Cases and Rotations

1. LL Imbalance (Left-Left Case) -> Single Right Rotation

Yeh tab hota hai jab node A ke Left child ke Left subtree me insertion hui ho (BF of A = +2, BF of Child = +1).

     [ C ] (+2)                      [ B ] (0)
     /                               /     \
   [ B ] (+1)   == Right Rotate ==> [ A ]   [ C ]
   /                                 (0)     (0)
 [ A ] (0)

2. RR Imbalance (Right-Right Case) -> Single Left Rotation

Jab node A ke Right child ke Right subtree me insertion hui ho (BF of A = -2, BF of Child = -1).

3. LR Imbalance (Left-Right Case) -> Double Rotation (Left then Right)

Jab node A ke Left child ke Right subtree me insertion hui ho (BF of A = +2, BF of Child = -1). Pehle left child par Left Rotate karte hain (yeh LL me convert ho jata hai), fir parent par Right Rotate karte hain.

4. RL Imbalance (Right-Left Case) -> Double Rotation (Right then Left)

Jab node A ke Right child ke Left subtree me insertion hui ho (BF of A = -2, BF of Child = +1). Pehle right child par Right Rotate karte hain, fir parent par Left Rotate karte hain.

Complexity of AVL Tree

Search, Insertion, aur Deletion sabhi operations ki Worst-case Time Complexity strictly O(log n) hoti hai.

Agli post me hum cover karenge Binary Heap: Min-Heap and Max-Heap Properties.