AVL Trees

An AVL Tree is a self-balancing Binary Search Tree. Imagine a BST that automatically stays balanced — like a seesaw that always levels itself.

After every insert or delete, it checks the balance factor (left height − right height). If the difference exceeds 1, it performs a rotation to restore balance.

This guarantees O(log n) for all operations, even in the worst case.

• Right rotation — left side is too heavy
• Left rotation — right side is too heavy
• Left-Right (LR) — left child is right-heavy
• Right-Left (RL) — right child is left-heavy

| Operation | Time | Space | |-----------|----------|-------| | Insert | O(log n) | O(n) | | Delete | O(log n) | O(n) | | Search | O(log n) | O(n) |

A plain BST can degrade to O(n) if you insert sorted data. AVL trees never do.