2
$\begingroup$

I got an assignment to create a new data structure, with the following rules:

  1. Init - O(1).
  2. Insert x - O(log$_2$n).
  3. Delete x - O(log$_2$n).
  4. Search for x- O(log$_2$n).
  5. Find max difference between two values in the DS - O(1).
  6. Find min difference between two values in the DS - O(1).

I've outlined the basics of the structure to look somewhat like an array/arryaList in which I can complete the tasks using heap-like methods, and that way I'll be able to complete 1-4 in the times given.

Regarding 5 - I need to return the difference between the maxVal and minVal of the array, so it'll be the first number (arr[0]) and I'll change the leaves to be so that the max is the last value (a[n-1]), and then I'll be in O(1).

Regarding 6, and this is where I'm stuck - how can I find the smallest difference between two values in O(1) time? I don't know of any methods that accomplish the task in O(1)...

Thank you!

Improve this question
$\endgroup$
11
  • $\begingroup$ You can "cheat" by really performing 5. and 6. in 2. and 3. [O(log(n)) allowed] and storing the results for later queries. $\endgroup$
    – Yves Daoust
    May 18 at 7:30
  • $\begingroup$ Note that none of 2., 3., 4. can be performed within the required constraints using arrays and "heap-like" methods. $\endgroup$
    – Yves Daoust
    May 18 at 7:31
  • $\begingroup$ @YvesDaoust When inserting a new element, computing the min difference would require $\mathcal{O}(n)$ time in the general case (even if you stored all other differences). $\endgroup$
    – Nathaniel
    May 18 at 8:20
  • $\begingroup$ @Nathaniel: can you justify ? (IMO you are wrong, you can find the two closest neighbors of the new value and compare to the current closest pair.) $\endgroup$
    – Yves Daoust
    May 18 at 8:24
  • 1
    $\begingroup$ @BobAlice A standard min-heap does not support search of any element in log time. $\endgroup$
    – Nathaniel
    May 18 at 15:57

3 Answers 3

Reset to default
4
$\begingroup$

Use an AVL tree with each node having three additional entries $\min,\; \max$, and $\text{closest_pair} = (i,j)$, representing the minimum and maximum values of the tree rooted at that node. At the time of insertion and deletion, these values will be updated (Note that only $O(\log(n))$ node updates are needed per insert/delete operation). Now, this data structure represents your required data structure.

N.B. For a node $i,$ following relation holds. $i$.closest_pair = closest( [ ($i$.left,$i$), ($i$,$i$.right), $i$.left.closest_pair, $i$.right.closest_pair ] )

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice! To implement: - Function runs after insertion of a node. - The base condition is a node with two leaves as children, choosing the smaller of the differences and defining that as closest_pair. - The recursive function compares between the closest_pair values of both children of a node, and takes the smaller as the parent's closest_pair value. - This all happens in O(log(n)) time, which means insert will be O(2*log(n)) = O(log(n)). Correct? $\endgroup$
    – Bob Alice
    May 19 at 7:27
  • $\begingroup$ @BobAlice While inserting you have to do the updation. You have to modify the insert function of AVL tree iin accordance to what you had said. For delete you have to design the code. I just put the sketch of idea, not the entire algorithm. $\endgroup$
    – Subhankar Ghosal
    May 20 at 1:46
1
$\begingroup$

I think this can be done using $(a,b)$-trees storing a bit more information in internal nodes:

  • the minimum difference between two leaves in the subtree;
  • the minimum and maximum values of a leaf in the subtree.

This can yield the wanted complexity:

  1. init is an empty tree
  2. inserting $x$ is first done in the usual way in $(a,b)$-trees, then you need to update all ancestors of the leaf containing $x$. Since each internal node has at most $b$ children, updating a node is done in constant time. Since each internal node has at least $a$ children, $x$ has $\mathcal{O}(\log n)$ ancestors. Note that the minimum difference can either be the minimum difference in a child, or the difference between the maximum and the minimum of two consecutive children ;
  3. deleting is done in a similar way ;
  4. searching is done the usual way in $(a,b)$-trees ;
  5. and 6. are done in $\mathcal{O}(1)$ using the information stored at the root of the tree.

Actually, I think this can also be done with any kind of balanced binary search tree, storing the same kind of information:

  • the min of a node $N(l, x, r)$ is either the min of $l$ or $x$ if $l$ is empty (and it is similar for the max);
  • the min difference of $N(l, x, r)$ is one of the following:
    • the min difference of $l$;
    • the min difference of $r$;
    • the difference between $x$ and the maximum of $l$;
    • the difference between the minimum of $r$ and $x$.
Improve this answer
$\endgroup$
1
$\begingroup$

I'm assuming that the sets of functions in big-Oh notation refer to the desired worst-case time complexity of the operations.

A possible data structure consists of an AVL tree $T$ plus a priority queue $H$ that supports insertions, deletions, and lookup of the minimum in time $O(\log n)$, $O(\log n)$, and $O(1)$ (respectively). The tree $T$ stores your collection and also keeps track of the minimum element $m$ and the maximum element $M$ in it. The priority queue $H$ stores all the differences between adjacent elements in the sorted version of the collection, and is allowed to contain multiple copies of the same value ($H$ can be implement using a min-heap and suitably managing pointers to elements to allow for fast deletions, or using another AVL tree).

The operations are implemented as follows:

  • Init: create an empty tree $T$ and an empty priority queue $H$.
  • Search $x$: search for $x$ in $T$ as usual.
  • Insert $x$: insert $x$ in $T$ as usual. Update $m$ and $M$ by searching for the minimum and maximum element in $T$. Find the successor $y$ of $x$ in $T$ (if any). If $y$ exists add $y-x$ to $H$. Find the predecessor $z$ of $x$ in $T$ (if any). If $z$ exists add $x-z$ to $H$. If both $y$ and $z$ exist, delete $y-z$ from $H$.
  • Delete $x$: delete $x$ from $T$ as usual. Update $m$ and $M$ by searching for the minimum and maximum element in $T$. Find the successor $y$ of $x$ in $T$ (if any). If $y$ exists delete $y-x$ from $H$. Find the predecessor $z$ of $x$ in $T$ (if any). If $z$ exists delete $x-z$ from $H$. If both $y$ and $z$ exist, add $y-z$ to $H$.
  • Find max difference between two values: return $M-m$.
  • Find min difference between two values in the dataset. Return the minimum in $H$.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Maybe you should point out that a node in $T$ will have a pointer to the $y-x$ entry in $H$ to efficiently perform delete. But my question is how can you guarantee that $y-z$ entry in $H$ does not appear many times in $H$. Because every time you insert and delete a key $x$ whose value lies between $y$ and $z$, such that they are always the successor and predecessor of $x$, you will insert $y-z$. Wouldn't it be possible that the size of $H$ be too large than $T$? $\endgroup$
    – Russel
    May 18 at 13:57
  • $\begingroup$ Upon reviewing the question I fixed the insert operation that didn't consider $x$'s predecessor. That said, a key can appear many times in $H$ but the size of $H$ is always $n-1$ (i.e., the number of adjacent pairs of elements in the sorted version of the collection). You can see that, for $n \ge 1$, an insert operation increases the size of $H$ by $1$ (if two elements are added to $H$, then one is removed), while a delete operation decreases the size of $H$ by at least $1$ when $n \ge 2$ (if $y-z$ is added to $H$, then two elements are removed, otherwise one element is removed). $\endgroup$
    – Steven
    May 18 at 15:12
  • 1
    $\begingroup$ I added a remark about managing pointers. Also $H$ can be any data structure that supports fast insertions deletions and lookup of the minimum. For example another AVL tree. $\endgroup$
    – Steven
    May 18 at 15:17

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.