-2
$\begingroup$

We want to store a set S of distinct positive integers and support the following operations on S:

Insert(a): insert integer a !∈ S into S.

Delete(a): delete integer a ∈ S from S.

FindNext(a, k), where a ∈ S and k is an integer: if S consists of some elements a1 < a2 < · · · < an, and a = ai (for some i, 1 ≤ i ≤ n), then return ai+k (for simplicity, assume that i + k ≤ n).

The worst-case time complexity of each operation should be O(log n) where n is the size of S. An augmented data structure can be used (without any modification) “as a black box” to achieve the above goal: using the operations that this data structure provides, the algorithms for performing the above three operations are quite simple. Give an algorithm for the FindNext(a, k) operation that uses only the operations of this data structure and consists of at most 5 lines of pseudo-code.

You are allowed to make use of other operations available with this data structure, i.e. everything you can make run in the specified time.

$\endgroup$
  • $\begingroup$ For me, your question is unclear. Do you want to implement the FindNext operation only using insert and delete? This won't be possible since this will always have a worst case of O(n). $\endgroup$ – Benjoyo Mar 5 '15 at 8:16
  • $\begingroup$ I couldnt figure out a O(log n) time operation. Perhaps if Succesor was provided I would be able to have a O(klogn) solution. But that would be incorrect. Thus I am lost $\endgroup$ – anond Mar 5 '15 at 8:22
  • 2
    $\begingroup$ What have you tried? Where did you get stuck? This is not the place to copy-paste your exercise and have us solve it for you. We want to help you with conceptual issues, but as you haven't identified any specific conceptual confusions, it's not clear how to help you. Please edit your question to show in your question what you tried and where you got stuck (what did you try, with a AVL tree? what's the best you were able to achieve? what kinds of augmentations did you consider?), and remember to make a serious effort before asking here. $\endgroup$ – D.W. Mar 5 '15 at 19:27
2
$\begingroup$

You can use the order-statistic tree which is a red-black tree augmented each node $x$ with an additional field $size(x)$. The field contains the number of nodes in the subtree rooted at $x$ (including $x$ itself).

As red-black tree, order-statistic tree supports Query, Insert, and Delete in $O(\lg n)$ time. Further, order-statistic tree provides two new operations:

  1. Select(i): find the element with rank $i$ in $O(\lg n)$ time.
  2. Rank(x): obtain the rank of element $x$ in $O(\lg n)$ time.

Then FindNext(a, k) can be implemented as Select( Rank(x) + k ). The time complexity is obviously $O(\lg n)$.


For more details of order-statistic tree, please refer to CLRS (Section 14.1: Dynamic order statistics, 2nd edition) or this wiki article.

$\endgroup$

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.