Balanced trees
Trees where heights of subtrees differ by at most a constant factor, maintaining O(log n) operations. Balancing ensures worst-case logarithmic complexity for search, insertion, deletion. Rebalancing operations maintain balance after modifications.
Formula
Height = O(log n); All operations (search, insert, delete) = O(log n)
Real World
Database engines like MySQL's InnoDB use balanced B-trees to index millions of rows — without balancing, searching a skewed tree of 1 million records could take 1 million comparisons instead of 20.
Exam Focus
When asked why balancing matters, always contrast O(log n) balanced performance with O(n) worst-case for an unbalanced (degenerate) tree.
How well did you know this?