DSA · Chapter 22 of 40
Balanced Trees
Self-balancing trees keep their height near log n by rearranging nodes after inserts and deletes. AVL trees keep the height difference of any node's subtrees within 1; red-black trees allow a looser balance with fewer rotations.
You rarely implement these in an interview, but you should know why they exist and what they guarantee.
Rotations
Left and right rotations restructure three nodes locally while preserving BST order; AVL applies them after detecting a balance factor of +/-2.
Where they are used
Language library maps and sets (C++ std::map, Java TreeMap) and database indexes (B-trees, a generalisation for disk).
Example 1 (python)
# balance factor = height(left) - height(right)
def balance_factor(node):
return height(node.left) - height(node.right)
print(balance_factor(bst))Output
0AVL trees rebalance when this value goes outside -1..1.
Example 2 (python)
# In-order gives sorted output for any BST, balanced or not
print(inorder(bst, []))Output
[3, 8, 10]Balancing changes the shape, never the sorted order.
Key points
- Balanced trees guarantee O(log n) operations.
- AVL is strictly balanced; red-black trees rotate less.
- Rotations preserve BST ordering.
- B-trees extend the idea to disk-based indexes.
💡 Note: Say 'a balanced BST guarantees O(log n)' when comparing against a hash map's average O(1).