A+DS

AVL Tree

A self-balancing BST — never let it get lopsided!

An AVL tree is a Binary Search Tree that automatically rebalances itself after every insertion or deletion. Each node tracks a "balance factor" (left height minus right height). If any node's balance factor goes beyond -1 or +1, the tree performs rotations to restore balance, guaranteeing O(log n) operations.

  Unbalanced (LL):     After right rotation:
       [30]                 [20]
       /                   /    \
     [20]               [10]   [30]
     /
   [10]

  Balance factors: -1, 0, +1 = OK
                   -2, +2    = ROTATE!

How it works

  1. 1Insert like a normal BST
  2. 2Walk back up, checking each ancestor's balance factor
  3. 3If |balance| > 1, the node is unbalanced
  4. 4Apply the correct rotation: LL, RR, LR, or RL

Loading...