A data structure that supports efficient insertion of arbitrary integers, value lookup, and removal of all integers smaller than a given threshold?

Question

I'm looking for a data structure that supports efficient:

1. Insertion of arbitrary integers.
2. Value lookup (given a particular value needle, return true if it's currently in the structure).
3. Removal of all values below a given threshold integer.

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 O(m).

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 upper_bound and lower_bound?

Answer 1

If you accept randomized algorithms you could use TREAP. This data structure is BST where each node is augmented with priority, a random number. The only one invariant over normal normal BST is that parent's priority must be greater than children's. This results in a very simple implementation of Insert and Delete functions (recursive variant is 10-15 lines of clean C code). The complexity of basic operations is $O(\log N)$ on average.

It is possible to cut-off all nodes below threshold in $O(\log n)$ time assuming that nodes below the threshold are not disposed.

Node cut(Node node, int threshold) {
   if (node->key < threshold) {
      // optionally dispose node, and subtree at node->left
      return cut(node->right, threshold);
   }
   node->left = cut(node->left, threshold);
   return node;
}

root = cut(root, threshold);

Note, that there is no rebalancing because the node is replaced by one of its children (or subchildren). As result the priority invariant in satisfied.

Disposal of nodes with a key below the threshold will increase complexity to $O(k + \log n)$, where $k$ is a number of disposed nodes. Cost of disposal will be amortized to $O(1)$ over multiple operations because each node is created and disposed only once.

Removal of nodes above a given threshold will require symmetrical functions.