AVL Trees: Height Balancing, Rotations & Minimal Node Bounds
“Balance factors, single and double rotations (LL, RR, LR, RL), Fibonacci recurrence for minimal nodes, and height bounds.”
1.The AVL Invariant & The Four Rotation Types
§ 3.1.An AVL Tree (Adelson-Velsky and Landis) is a self-balancing binary search tree.
Balance Factor (BF):
text{BF}(u) = text{Height}(text{LeftSubtree}(u)) - text{Height}(text{RightSubtree}(u)).
For every node in an AVL tree, text{BF}(u) in {-1, 0, +1}.
When an insertion causes text{BF} to become +2 or -2 at a critical node A:
1. LL Case (Inserted in Left of Left): Right rotation at A.
2. RR Case (Inserted in Right of Right): Left rotation at A.
3. LR Case (Inserted in Right of Left): Left rotation at A.left, then Right rotation at A.
4. RL Case (Inserted in Left of Right): Right rotation at A.right, then Left rotation at A.
Every rotation takes O(1) time, guaranteeing O(log n) insertion and deletion.
2.The Fibonacci Recurrence for Minimum AVL Nodes
§ 3.2.To maximize height with the minimum number of nodes, one subtree of the root must have height h - 1 and the other must have height h - 2.
Recurrence for Minimum Nodes N(h):
N(h) = N(h - 1) + N(h - 2) + 1
With base cases (height of single node = 0):
- h = 0: N(0) = 1
- h = 1: N(1) = 2
- h = 2: N(2) = 2 + 1 + 1 = 4
- h = 3: N(3) = 4 + 2 + 1 = 7
- h = 4: N(4) = 7 + 4 + 1 = 12
- h = 5: N(5) = 12 + 7 + 1 = 20
- h = 6: N(6) = 20 + 12 + 1 = 33
Notice N(h) = F_{h+3} - 1, where F_k is the k-th Fibonacci number. Since Fibonacci numbers grow as phi^h (where phi approx 1.618), h approx log_phi n = 1.44 log_2 n = O(log n).
3. Worked Problem: Maximum Height of an AVL Tree Given Node Count
If n falls strictly between N(h) and N(h+1), the maximum possible height is h, NOT h+1.
Problem: What is the maximum possible height of an AVL tree containing n = 30 nodes (where a single-node tree has height 0)?
Step 1: Compute minimum node thresholds N(h):
N(0) = 1
N(1) = 2
N(2) = 4
N(3) = 7
N(4) = 12
N(5) = 20
N(6) = 33
Step 2: Compare given n = 30 with thresholds:
N(5) = 20 <= 30 < N(6) = 33.
Step 3: Deduce maximum height:
To achieve height 6, an AVL tree requires at least 33 nodes.
Since we only have 30 nodes (< 33), a height of 6 is impossible.
Height 5 requires at least 20 nodes, which is satisfied (30 >= 20).
Final Answer: The maximum possible height is 5.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Visual thinkers who want to see each algorithm step animated clearly.
GATE-targeted coverage with step-by-step GATE PYQ walkthroughs.