A common usage context is query on some data set after pre-processing . In these contexts, BST competes with sorted vector and priority queue.
- Killer app against vector: incremental insert or live updates
- Killer app against vector: if there’s even occasional delete(), then sorted vector would suffer
- Killer app against vector: update on one item can be implemented as delete/reinsert. Vector requires binary search -> mid-stream insert
- minor advantage over sorted vector: vector sorting requires swapping, so value-semantics is problematic
- Killer app against priority queue: range query, approximate query,
- Killer app against priority queue: both max() and min()
- Application: if each BST node needs additional data. Binary heap doesn’t expose those nodes(?)
It’s important to remember the advantages of vector
- cache efficiency
- runtime malloc cost
Java, c++ and c# all provide self-balancing BST in their standard libraries, from the very beginning. In my projects, I use these containers on an everyday basis. However, after talking to a few friends I now agree that most coding problems don’t need self-balancing BST because
- These problems have no incremental insertion/deletion, so we can simply sort an array of items at O(N logN) as pre-processing
- In some cases, priorityQ is a viable alternative
- Python doesn’t have this container at all and all coding problems must support python.