Efficient data structure for insertion, deletion and smallest-not-in-range query on an array of integers

Question

I'm trying to make a data structure $A$ that has the following features:

• insert($a$) operation : insert given integer $a$ to $A$. It is assured that all integers are unique.
• delete($b$) operation : delete $b$ from $A$.
• smallestNotInRange($p$,$q$) : returns the smallest value $k$ such that $k\in [p,q]$ and $k \notin A$.
• Each operation should take $O(\log{n})$ time and should use $O(n)$ space. $n$ is the number of integers in $A$.

Because of the last function the first thing I thought of was using segment trees. However, it was not the right choice because it uses $O(n \log n)$ space.
The next thing I thought of was using a balanced binary search tree. Everything is good for insert and delete operations because insertion and deletion of a balanced binary search tree take worst-case runtime of $O(\log n)$ and the data structure use $O(n)$ space. The problem is with the smallestNotInRange operation. When the number of integers in range $[p,q]$ is less than $\log n$ the operation will take $O(\log n)$, however, when the number of integers in range $[p,q]$ is greater than $\log n$ the operation will take $O(n)$. How can I resolve this problem and get this to work at worst-case runtime of $O(\log n)$?

Answer 1

You can use a balanced BST. For each node $n$, let $n.lsize$ be the size of the left subtree of $n$. Insert and delete is just standard BST add and remove with size updating. To implement smallestNotInRange do the following:

1. Find node $n_p$ containing $p$. If it does not exist, then $k =p$, else let $size_{p_{left}} = n_p.lsize$.

2. Starting from the root, find the shallowest node $n_m$ such that $p \le m \le q$. To do this, check the value of the current node. If the value is less than $p$ move down to its right subtree. Else, if the value is greater than $q$ move down to its left subtree. Otherwise, the current node is $n_m$. If at some point, the visited subtree is empty, then $k = p + 1$.

3. If $n_m.lsize - size_{p_{left}} \lt m - p$ and $n_m$ is the parent of $n_p$, then $k = p + 1$. Otherwise, let $q = m - 1$ and repeat step 2, but this time starting at the left child of $n_m$, instead of the root.

4. If $n_m.lsize - size_{p_{left}} = m - p$ and $m = q$ then there is no such $k$. Otherwise, set $size_{p_{left}} = -1$, $n_p = n_m$, and $p = m$ and repeat step 2, but this time starting at the right child of $n_m$, instead of the root.

For step 1, it is self-explanatory why $k=p$ when $n_p$ does not exist. The variable $size_{p_{left}}$ is initially set to the number of elements in the left subtree of $n_p$, which are elements not in $[p,q]$.

The idea behind steps 2 to 4 is like doing a binary search to find the subrange in $[p,q]$ closest to $p$, that contains an element not in $A$. Step 2 is like the "finding the middle" part of the binary search.

Step 3 checks if there is a missing element in the subrange $[p,m]$. If there is, it continues the search in that subrange. There is a missing element when $m-p$, the expected number of elements in the range, is greater than $n_m.lsize - size_{p_{left}}$. The subtraction ensures that when $n_p$ is in the left subtree of $n_m$, we do not count the elements in the left subtree of $n_p$ since they are not in $[p,m]$.

If there is no missing element in $[p,m]$, step 4 performs the search in the subrange $[m,q]$ instead. When going to this subrange, the new $n_p$ will never appear as subtree of the $n_m$ hence, the left subtree of $n_m$ will also not contain elements that are not in $[p, m]$. Therefore, we set $size_{p_{left}} = -1$. This will effectively add 1 to $n_m.lsize$ when comparing it to $m - p$, since $m-p$ takes into account $p$ but $n_m.lsize$ doesn't.

As for the running-time, step one takes $O(\log n)$ in the worst-case if it happens that $n_p$ is a leaf of a balanced BST. For steps 2-4, this is just modified BST search. Choosing the node to visit is controlled by the result of comparing $n_m.lsize - size_{p_{left}} $ and $m - p$. Each time a node is visited, only constant amount of work is done, thus the running-time for the entire steps 2-4 is also $O(\log n)$ because the tree is balanced. Therefore, the entire procedure is $O(\log n)$.