4
$\begingroup$

I need a data structure that stores a sequence of numbers and supports the following operations. The input to each operation includes the position of an item in the current sequence (not the value or the memory address of that item).

  • $\mathtt{NearestSmaller}(i)$: Return the value of the last item in the sequence that occurs before position $i$ and whose value is less than the value at position $i$.

  • $\mathtt{InsertBefore}(x, i)$: Insert a new item with value $x$ into the sequence just before the item with position $i$.

  • $\mathtt{Delete}(i)$: Delete item at position $i$ from the sequence.

In short, my question is whether there is a dynamic version of the all nearest smaller neighbors algorithm.

For example, if the current sequence is $X = [9,7,3,1,8,12,10,20,15,5]$, then

  • $\mathtt{NearestSmaller}(6)$ should return $8 = X[5]$, and

  • $\mathtt{NearestSmaller}(10)$ should return $1 = X[4]$.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Edited for clarity. Please verify that I haven't changed the question. In particular, I wasn't sure what you actually intended as the input to the insertion and deletion functions. (Direct pointer? Rank? Value? Something else?) $\endgroup$
    – Jeffε
    Commented Mar 3, 2013 at 16:58
  • $\begingroup$ Thank you,my dear friend,I will re-edit to make it more clear. $\endgroup$
    – Vk1
    Commented Mar 4, 2013 at 17:40
  • 1
    $\begingroup$ Re-edited for precision and consistency. Again, it's unclear whether the intended input is the position or the address of the item in the sequence. It's also unclear whether the ambiguous term "nearest" is supposed to mean "furthest to the right" or "closest in value". $\endgroup$
    – Jeffε
    Commented Mar 5, 2013 at 6:55
  • $\begingroup$ Now it is pretty clear. If it is still not clear,I request you to refer to this link en.wikipedia.org/wiki/All_nearest_smaller_values and try to find a datastructure to implement its dynamic version. $\endgroup$
    – Vk1
    Commented Mar 5, 2013 at 15:09
  • $\begingroup$ Edited for concision. "Position smaller than and closest to $i$" is the same as "last before position $i$". $\endgroup$
    – Jeffε
    Commented Mar 5, 2013 at 18:53

1 Answer 1

Reset to default
7
$\begingroup$

If you modify a balanced binary search tree (whose inorder traversal is the sequence order) so that each node stores the minimum value of its descendants (and if you know the path to x) then you can easily find the nearest smaller value: it must either be on the path to x, or in a left subtree descending from the path. In the first case, you have a logarithmic number of nodes to check, and in the second case you can use the extra information to find the closest left subtree with a value smaller than x and then descend through it along the rightmost path that still has a value smaller than x. So the time per query or update is logarithmic.

Edited to add: Now that you have clarified that you want to identify items in the sequence by their position, you should also augment the search tree so that each node stores its number of descendants. With this information, it is straightforward to find the path to the item at position $i$, in logarithmic time, matching the time described above for the NearestSmaller query.

Improve this answer
$\endgroup$
15
  • $\begingroup$ vEB can maintain sets of numbers and tell you the largest value in the set that is smaller than a query value (as can standard binary search trees) but how do you modify it to handle nearest smaller values in a sequence? $\endgroup$
    – David Eppstein
    Commented Mar 4, 2013 at 0:49
  • $\begingroup$ I am sorry, I misread the question. it doesn't seem likely that vED can help here $\endgroup$
    – Sasho Nikolov
    Commented Mar 4, 2013 at 1:35
  • 6
    $\begingroup$ Sure you can. Use a red-black tree (or AVL, etc) but where the nodes are in sequence order rather than sorted by value. See the chapter on augmented binary trees in CLRS. $\endgroup$
    – David Eppstein
    Commented Mar 5, 2013 at 16:56
  • 1
    $\begingroup$ ...or splay tree, or treap, or skip list, or B-tree, or... $\endgroup$
    – Jeffε
    Commented Mar 5, 2013 at 18:55
  • 1
    $\begingroup$ Ok, so e.g. to find the nearest smaller value to 10, you would look at its ancestors that are earlier than it (12 and 1, but not 20), and the left subtrees on the path from it to the root (rooted at nodes 8 and 7). Of these, 8, 7, and 1 are smaller than it, and 8 is the closest (along the path to the root as well as in the sequence order). If you search inside the subtree labeled 8 you will find the nearest smaller value to 10. What values do you think this gets wrong? $\endgroup$
    – David Eppstein
    Commented Mar 8, 2013 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.