Data Structure For Closest Pair Problem

Question

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.

Answer 1

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