3
$\begingroup$

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)$?

$\endgroup$
1
  • $\begingroup$ What is the context where you encountered this task? Can you credit the source where you saw this or the motivation? $\endgroup$
    – D.W.
    Apr 11 at 8:42

1 Answer 1

5
$\begingroup$

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)$.

$\endgroup$
7
  • 1
    $\begingroup$ Thank you for your answer! I have two question. 1. On step 4, when assigning $p=m$ is $m$ the the first middle node found in step 2 or is it the one that is last node to be found in step 3? Also, how can $m=q$ when we are going left from a middle value between $p$ and $q$? 2. Can you give me some explanation runtime of the algorithm? I'm have some trouble proving the runtime of this algorithm. $\endgroup$
    – user149684
    Apr 10 at 5:59
  • $\begingroup$ Your question actually opened some problems with the procedure I presented, which I hope I was able to fix completely. I also changed the way the steps 3 and 4 are presented to hopefully mirror the way binary search selects the subrange that will be considered for further search. Then I added some further discussions. Feel free to ask clarifications if my changes are not enough. $\endgroup$
    – Russel
    Apr 10 at 7:06
  • $\begingroup$ Thank you for improving your answer! Shouldn't $size_{pleft}=1$ on step 4? For example, $9-5=4$ and the numbers between 9 and 5 are three numbers 6,7 and 8 so the algorithm should take step 4 again. Also, one question on runtime. If my understanding is correct, the algorithm will always do step 2 and do step 4 when there is no answer in the left branch and the algorithm will only take a left turn when the answer is in the left branch. So, is the maximum number of visits $\log n$? $\endgroup$
    – user149684
    Apr 10 at 7:55
  • $\begingroup$ I think you're right with setting $size_{p_{left}} $ to 1 in step 4 since at this point $n_p$ will also not be counted under the left subtree of $n_m$. As for the running-time, yes the number of visit is $O(\log n) $. $\endgroup$
    – Russel
    Apr 10 at 8:02
  • $\begingroup$ Actually I think $size_{p_{left}}$ should be -1. Check my update. $\endgroup$
    – Russel
    Apr 10 at 8:23

Your Answer

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