I'm looking for a data structure that supports efficient:
- Insertion of arbitrary integers.
- Value lookup (given a particular value
needle, return true if it's currently in the structure).
- Removal of all values below a given
I suspect this can be with a self-balancing BST, with insertion and lookup both costing
log(n) time. I think the removal operation can be done by pruning an entire subtree out, but I'm not sure this can be done in
log(n) time while keeping the tree balanced. If we remove a very large subtree (say the left child of the root node), it seems like it would take basically rebuilding the entire tree, which is
O(m log m) with
m being the number of remaining nodes, and at any rate no less than
A cheaper approach would be to use a naturally-ordered self-balancing BST. For removal, we can just start at the smallest node, and keep removing (and rebalancing) until we run out of nodes or hit the
threshold. This will cost
O(m log n) where
m is the number of nodes to be removed.
Bonus question: what if instead of removing below a
threshold, we need to support removal of all nodes in a range between