Self-Balancing

AVL Tree

A self-balancing Binary Search Tree maintaining O(log n) height boundaries.

What is AVL Tree?

An AVL Tree (Adelson-Velsky and Landis) is a self-balancing Binary Search Tree (BST). In an AVL tree, the heights of the two child subtrees of any node differ by at most one (Balance Factor = height(left) - height(right) is -1, 0, or 1). If an insertion or deletion causes the balance factor to go outside this range, one of four rotations (LL, RR, LR, RL) is executed to rebalance the tree.

Key Characteristics:

  • Strictly balanced: height difference <= 1
  • Maintains BST search properties
  • Auto-balances on insert/delete via single or double rotations
  • Guarantees O(log n) performance for all lookups

Complexity Analysis

Avg Time Complexity: O(log n) for Search, Insert, and Delete
Space Complexity: O(n) storage node allocation
Best Case: O(1) (operating at root node)
Worst Case: O(log n) (traversing entire depth)

How it Works Step-by-Step

  1. Insert: Run standard BST insertion recursively.
  2. Calculate Height: Update height of ancestor nodes during return path.
  3. Check Balance Factor: Compute Balance Factor for ancestors.
  4. Perform Rotation: If Balance Factor > 1 (left-heavy) or < -1 (right-heavy), apply rotations.

Code Implementation

Worked Trace Example

Inserting 10, 20, 30 sequentially (LL imbalance):
1. Insert 10: [10]
2. Insert 20: [10] -> right [20]
3. Insert 30: [10] -> right [20] -> right [30]
4. Node 10 has Balance Factor -2. Apply Left Rotation around 10.
Result: 20 becomes root, 10 is left child, 30 is right child.