1
$\begingroup$

Suppose I have a list of distinct integers. I'm looking for a data structure that will support the operations search, insert, delete and closest_pair in $O(\log n)$ time.

I know that a sorted array supports search, insert and delete in $O(\log n)$ time. So, all we need to do is maintain information about the closest pair during the insert and delete operations.

The only problem is that the closest_pair would perform in better than $O(\log n)$ time since information about the closest pair would already be available. So, I'm stuck at this point.

$\endgroup$
  • $\begingroup$ Note that "better than $O(\log n)$" has little meaning. But how would the operation being fast be a problem, anyway? I fail to understand what you are asking. $\endgroup$ – Raphael Jan 26 '14 at 15:58
  • $\begingroup$ Better than $O(\log n)$ means $o(\log n)$. $\endgroup$ – Yuval Filmus Jan 26 '14 at 16:54
  • $\begingroup$ @Raphael I had interpreted the requirement to be that all operations had to be in O(log n) time and that they could not be better. As FrankW pointed out, my interpretation is incorrect. $\endgroup$ – EggHead Jan 26 '14 at 18:40
  • $\begingroup$ @YuvalFilmus: Every function from $o(\log n)$ is also in $O(\log n)$. (I know you know that.) EggHead, you want to use $\Omega$ or $\Theta$ when talking about lower bounds. $\endgroup$ – Raphael Jan 26 '14 at 21:23
6
$\begingroup$

Your confusion appears to arise from a misunderstanding: $O(\log n)$ means "proportional to $\log n$ or better". So being able to get the closest pair in constant time is not a problem.

While you seem to already have found a solution to the original problem, I'll still give hints towards a solution, in order to make this answer helpful for other people stuck with that problem.

Hint 1: Basic data structure to start from: (Contrary to the claim in the current version of the question, a sorted array does not work, since you can not insert or delete in an array in $O(\log n)$.)

A height balanced binary search tree (e.g. AVL tree) works.

Hint 2: What additional information should be stored:

Each node stores: the smallest and largest value in the subtree below this node and the closest pair in that subtree.

Hint 3: How to update the information in a single node:

  • The smallest value is the smallest value in the left subtree (or the value of the node itself, if no left subtree is present).
  • The largest value is the largest value in the right subtree (or the value of the node itself, if no right subtree is present).
  • There is no closest pair in a leaf.
  • In an inner node there are at most 4 candidates for the closest pair:
    1. The closest pair in the left subtree,
    2. the closest pair in the right subtree,
    3. the pair (largest value in the left subtree, value of the node) and
    4. the pair (value of the node, smallest value in the right subtree).
    Simply compute minimum of these.

Finally: How to do the operations:

  • $\text{search}$ just ignores the additional information.
  • $\text{closest_pair}$ reads the required information from the root node.
  • $\text{insert}$:
    1. perform a normal AVL-insert
    2. update all nodes on the path from the inserted leaf to the root and all nodes affected by rotations (starting at the leaf)
  • $\text{delete}$:
    1. perform a normal AVL-delete
    2. update all nodes on the path from the deleted leaf to the root and all nodes affected by rotations (starting at the leaf)

    If the descent into the tree in insert and delete is done via recursion, the updates can --just as the rotations -- be done when returning from the recursive calls.
    Of course, once a node is unchanged, the nodes above it will remain unchanged as well (unless affected by a rotation).

  • $\endgroup$
    • $\begingroup$ Just to clarify, it needs to be a height balanced BST, since otherwise we cannot guarantee O(log n). $\endgroup$ – EggHead Jan 26 '14 at 20:37
    • $\begingroup$ Of course, thanks. I should have spotted this myself. --- At least it was easy to fix. $\endgroup$ – FrankW Jan 26 '14 at 21:39
    • $\begingroup$ I think the delete needs more work. When a node is deleted, if the node is not one of the nodes in the closest pair then no issue. Otherwise, we will have to figure out what the "new" closest pair is. Since I've already accepted your answer, I'm going to post a new question to discuss this. You can try answering that if you'd like 8-) $\endgroup$ – EggHead Jan 27 '14 at 4:08
    • $\begingroup$ It does work. See my answer to the followup question (Link included for others that get stuck on the same problem.) $\endgroup$ – FrankW Jan 27 '14 at 7:55

    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.