AVL Trees

# CHAPTER 21

AVL Trees #

1. Introduction #

2. Learning Objectives #

• Define the AVL Balance Factor mathematics.

• Visualize the four structural violations (LL, RR, LR, RL).

• Execute the four geometric Pointer Rotations to restore balance.

• Understand the theoretical Space/Time trade-offs of self-balancing architecture.

3. The Balance Factor #

We calculate this using the Balance Factor (BF) formula: BF = Height(Left Subtree) - Height(Right Subtree)

• If BF is -1, 0, or 1: The node is perfectly legal and balanced.

• If BF is +2 or -2: The node is illegal. The tree is dangerously unbalanced, and an immediate Rotation is mathematically triggered!

4. The Four Structural Violations #

1. 1. Left-Left (LL) Heavy: The tree leans entirely to the left. (Insert 30, 20, 10).

1. 2. Right-Right (RR) Heavy: The tree leans entirely to the right. (Insert 10, 20, 30).

1. 3. Left-Right (LR) Heavy: A left branch suddenly juts to the right. (Insert 30, 10, 20).

1. 4. Right-Left (RL) Heavy: A right branch suddenly juts to the left. (Insert 10, 30, 20).

5. The Geometric Rotations #

#### 5.1 Single Right Rotation (Fixes LL) If the tree is 30 -> 20 -> 10 (Leaning Left), we grab the middle node 20, pull it UP to become the new Root, and push 30 DOWN to become its Right child! Result: 20 is Root. 10 is Left. 30 is Right. Perfectly balanced!

#### 5.2 Single Left Rotation (Fixes RR) If the tree is 10 -> 20 -> 30 (Leaning Right), we grab 20, pull it UP to the Root, and push 10 DOWN to become its Left child!

#### 5.3 Complex Double Rotations (LR and RL) If the tree is shaped like a zig-zag (Left-Right), a single rotation will not fix it. You must do TWO rotations.

1. 1. Rotate the bottom part to straighten the zig-zag into a straight line (turns LR into LL).

1. 2. Rotate the top part to balance the straight line.

6. AVL Node Implementation #

// Java Example: AVL Node Architecture
class AVLNode {
    int data;
    int height; // New! Caches the height for O(1) math.
    AVLNode left;
    AVLNode right;

    public AVLNode(int d) {
        data = d;
        height = 1; // A brand new leaf has a height of 1
    }
}

# Python Example: A Right Rotation Function
def right_rotate(y):
    # y is the unbalanced top node (e.g., 30)
    # x is its left child (e.g., 20)
    x = y.left
    T2 = x.right # Any existing right child of x
    
    # Perform the geometric rotation
    x.right = y # Pull x UP, push y DOWN
    y.left = T2 # Reattach T2 to y's empty left side
    
    # Update cached heights
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    
    return x # x is the brand new Root of this subtree!

7. Complexity Analysis #

8. AVL Trees vs Red-Black Trees #

• AVL Trees: Extremely strict balancing rules. Finding data is blazing fast, but inserting data is slightly slow because it is constantly rotating to stay perfect. (Used for Read-Heavy databases).

• Red-Black Trees: Looser balancing rules. Finding data is slightly slower, but inserting data is blazing fast because it rotates less often. (Used natively in Java's TreeMap and C++ std::map).

9. Common Mistakes #

• Forgetting to update Heights: After a geometric pointer rotation, the physical depths of the nodes have fundamentally changed. If you do not update the node.height variables immediately, the Balance Factor math will corrupt, and the tree will tear itself apart on the next insertion.

10. Best Practices #

• Use standard libraries: You will likely never code an AVL tree from scratch in a production environment. The pointer manipulation is too complex and bug-prone. Use native language implementations (which usually rely on Red-Black Trees). However, FAANG interviews expect you to manually trace rotations on a whiteboard!

11. Exercises #

1. 1. Draw a tree inserting 10, 20, 30. What violation occurs? Draw the tree after the rotation.

1. 2. If the Balance Factor of a Node is calculated as -2, is the tree heavier on the left or the right?

12. MCQs with Answers #

13. Interview Preparation #

• *Conceptual:* "A FAANG interviewer asks: 'Why do we use Red-Black trees in Java's TreeMap instead of AVL trees?'" *(Answer: Because Red-Black trees require fewer rotations during Insertion and Deletion. In a general-purpose programming library where data is constantly being modified, the extreme rotational overhead of an AVL tree degrades performance).*

Common Pitfalls:

• In whiteboard interviews, completely freezing when asked to perform a Double Rotation. Just remember: A Double Rotation is literally just two Single Rotations. Don't try to visualize the entire move at once. Straighten the zig-zag first. Then balance the straight line.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #