AVL Tree: Concept and Balance Factor

AVL Tree (invented by Adelson-Velsky and Landis in 1962) pehla Self-Balancing Binary Search Tree hai. Standard BST me jab sorted inputs aate hain toh tree skewed ho jata hai aur search performance degrade hokar O(n) ban jaati hai. AVL Tree ensure karta hai ki tree ki height hamesha O(log n) rahe.

Balance Factor (BF) Definition

AVL Tree ke har node par ek Balance Factor calculate kiya jata hai:

Strict AVL Property: Ek BST tabhi valid AVL Tree kehlata hai agar uske har ek node ka Balance Factor strictly in me se ek ho:

BF ∈ { -1, 0, +1 }

• BF = 0: Perfectly balanced node.
• BF = +1: Left-heavy node (left subtree 1 level deeper hai).
• BF = -1: Right-heavy node (right subtree 1 level deeper hai).
• Agar kisi insertion ya deletion ke baad kisi node ka |BF| > 1 (jaise +2 ya -2) ho jaye, toh tree Unbalanced ho jata hai aur use balance karne ke liye Rotations perform karni padti hain.

Balanced AVL Node:               Unbalanced AVL Node (Violation):
      (50) [BF = 1-1 = 0]                     (50) [BF = 2 - 0 = +2] <-- VIOLATION!
     /    \                                  /
   (30)   (70)                             (30) [BF = 1 - 0 = +1]
   [0]    [0]                              /
                                         (20) [BF = 0]

Agli post me hum cover karenge AVL Tree Rotations: LL, RR, LR, and RL Rotations with Solved Numericals.