AVL Trees

# CHAPTER 11

AVL Trees #

1. Introduction #

2. Learning Objectives #

• Understand the algorithmic trigger mechanism for AVL rebalancing.

• Calculate the exact Balance Factor for any isolated node.

• Execute the 4 fundamental Geometric Rotations (LL, RR, LR, RL).

• Trace the pointer surgery required to flatten a Degenerate branch.

3. The Balance Factor Trigger #

$$ BF = \text{Height}(Left) - \text{Height}(Right) $$

• Valid states: $+1$, $0$, or $-1$.

• Trigger states: $+2$ (Heavily Left-Skewed) or $-2$ (Heavily Right-Skewed).

4. The 4 Geometric Rotations #

1. Right Rotation (LL Imbalance)

• *Scenario:* The tree is skewed heavily to the Left ($BF = +2$), and the new node was inserted on the Left child's Left side (LL).

• *Action:* Grab the Left Child. Pull it UP to become the new Root. Push the old Root DOWN to become the Right Child.

2. Left Rotation (RR Imbalance)

• *Scenario:* The tree is skewed heavily to the Right ($BF = -2$), and the new node was inserted on the Right child's Right side (RR).

• *Action:* Grab the Right Child. Pull it UP to become the new Root. Push the old Root DOWN to become the Left Child.

3. Left-Right Rotation (LR Imbalance)

• *Scenario:* The tree is skewed Left ($BF = +2$), but the new node was inserted on the Left child's *Right* side (LR). A single rotation won't fix it (it just creates a zigzag).

• *Action:* Execute a Left Rotation on the *Child* node first to straighten the line. Then, execute a Right Rotation on the Parent.

4. Right-Left Rotation (RL Imbalance)

• *Scenario:* The tree is skewed Right ($BF = -2$), but the new node was inserted on the Right child's *Left* side (RL).

• *Action:* Execute a Right Rotation on the Child to straighten the line, then a Left Rotation on the Parent.

5. Step-by-Step Rotation Walkthrough #

  [10] (Root) -> BF = 0 - 2 = -2! (CRITICAL IMBALANCE)
    \
    [20] -> BF = 0 - 1 = -1
      \
      [30] -> BF = 0 - 0 = 0

The Fix (Left Rotation):

1. 1. The engine detects Node 10 has a BF of $-2$. The heavy line is on the Right-Right side.

1. 2. The engine grabs the middle node (20) and pulls it UP.

1. 3. Node 10 is forced down to the Left.

       [20] (New Root)
      /    \
   [10]    [30]

*The tree is perfectly balanced! The Space Complexity remains $O(1)$ and the height is minimized!*

6. Pointer Surgery (Left Rotation Code) #

// Execute Left Rotation anchored on node X
Node leftRotate(Node x) {
    Node y = x.right;      // Grab the heavy right child (y)
    Node T2 = y.left;      // Temporarily store y's left orphaned branch
    
    // Perform rotation (Surgery)
    y.left = x;            // Push X down to the left of Y
    x.right = T2;          // Reattach the orphaned branch to X
    
    // Update Heights mathematically here...
    
    return y; // Return the new Root!
}

7. Complexity Analysis #

• Time Complexity (Insertion/Deletion/Search): A mathematically flawless $O(\log N)$. By constantly enforcing rotations, the AVL tree mathematically guarantees the height will never exceed $1.44 \log_2 N$. Degeneration is physically impossible!

• Space Complexity: $O(N)$ for nodes, plus extra integer variables stored inside each node tracking its exact localized Height.

8. Common Mistakes #

• Forgetting to update Heights: After executing a rotation, the heights of the twisted nodes have drastically changed! If your algorithm does not manually recalculate and update node.height = max(height(left), height(right)) + 1, subsequent inserts will trigger the wrong rotations and destroy the geometry!

9. Exercises #

1. 1. Draw the exact geometric pointer states before and after executing an LL (Right Rotation) to fix a tree containing 30 $\rightarrow$ 20 $\rightarrow$ 10.

1. 2. Why is an LR Imbalance physically impossible to fix using only a single Right Rotation? Draw it out!

10. MCQs with Answers #

11. Interview Preparation #

• *Data Structure Selection:* "You are building the dictionary database for a spell-check application. It is populated once with 500,000 words, and then read billions of times a day without being updated. Do you use an AVL Tree or a Red-Black Tree?" *(Answer: AVL Tree! AVL trees strictly enforce tighter geometric balancing than Red-Black trees. Because the database is "Read-Heavy" and never updated, you don't care about the slow insertion rotational overhead. You only care about achieving the absolute fastest, shallowest $O(\log N)$ extraction speed possible!)*

12. Summary #

13. Next Chapter Recommendation #