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?

  • $\begingroup$ Is there a bound on (the absolute values of) all numbers? Have you considered (lazy) segment tree? Do you require an online algorithm? $\endgroup$ – John L. Mar 21 at 15:50
  • $\begingroup$ @JohnL. let's say all numbers are 32-bit unsigned ints. This needs to be an online algorithm. I don't know about segment trees but I'll read up on them if they are the best solution here. $\endgroup$ – Goh Mar 21 at 16:27
  • $\begingroup$ you can try using a splay tree with amortized logn complexity perhaps $\endgroup$ – jjohn Mar 21 at 17:32

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.

  • $\begingroup$ What do you mean by "assuming that excluding disposal of the nodes"? $\endgroup$ – Yuval Filmus Mar 31 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.