Balanced Binary Search Trees

We can think about a balanced binary search tree as a dynamic sorted array. If we have a sorted array, what kinds of operations can we perform on it?

1. Binary search in O(logn) time.
2. Select element given ith order statistic in O(1)
3. Computing min/max of array - O(1)
4. Predecessor/Successor - O(1), just find that element and return one before/after it
5. Rank - how many keys stored are less than or equal to the key - O(logn)
6. Output in sorted order - O(n)

Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time. This is where the binary search tree comes in! A BST is like a sorted array, but with logarithmic insertion and deletion. Now, the operations:

1. Binary search - O(log n)
2. Select - O(log n)
3. Min/max - O(log n)
4. Pred/succ - O(log n)
5. Rank - O(log n)
6. Output in sorted order - O(n)
7. Insert/Deletion - O(log n)

If you only need min/max, you should use a heap instead. If you only need fast insertion and lookup, use a hash table instead.