In competitive programming, you rarely implement balanced BSTs from scratch. Instead: Use language libraries:
- C++:
set,map,multiset(Red-Black trees) - Java:
TreeSet,TreeMap - Python:
sortedcontainers(not built-in, but available)
When you need:
- Ordered iteration: BST gives sorted order naturally
- Range queries: find all elements in
- Predecessor/successor: find closest smaller/larger value
- Rank queries: augment with subtree sizes
When hash tables are better:
- Only need insert/delete/lookup (no ordering)
- Keys aren't naturally comparable
When arrays + sorting is better:
- Static data (no insertions after initial load)
- Binary search on sorted array is simpler