Why Balance Matters

BST operations are $O(h)$, but $h$ depends on insertion order:

• Insert $[4, 2, 6, 1, 3, 5, 7]$: balanced tree, $h = 2$
• Insert $[1, 2, 3, 4, 5, 6, 7]$: right-skewed, $h = 6$

In the worst case, BST operations become $O(n)$.

No better than a linked list. Self-balancing BSTs solve this by automatically adjusting structure after insertions and deletions:

• AVL trees: strictly balanced (heights of subtrees differ by at most 1)
• Red-Black trees: relaxed balance (guarantees $h \leq 2 \log n$)
• Splay trees: move recently accessed nodes to root

Most languages use Red-Black trees for their ordered map/set implementations.