<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-03-04T00:49:49.990Z
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?
David Eppstein
CC BY-SA 3.0
2013-03-04T01:35:39.740Z
I am sorry, I misread the question. it doesn't seem likely that vED can help here
Sasho Nikolov
CC BY-SA 3.0
2013-03-05T15:11:12.907Z
@Sasho-Could you please delete this answer, as it is misleading
Vk1
CC BY-SA 3.0
2013-03-05T15:18:31.850Z
@DavidEppstein-I have edited the question to make it as clear as possible.Your answer is wrong, since you cant


1.keep height O(logn)


2.make inorder traversal give the original sequence


3.Create a bst...


All three at the same time.


If it were possible, why would someone create cartesian trees.


I am grateful that u answered, but i am not quite convinced that your answer is right.


Try doing all the three above on just the small sample data i have given and you can see that the height is not O(logn).
Vk1
CC BY-SA 3.0
2013-03-05T16:56:08.633Z
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.
David Eppstein
CC BY-SA 3.0
2013-03-05T18:55:01.913Z
...or splay tree, or treap, or skip list, or B-tree, or...
Jeffε
CC BY-SA 3.0
2013-03-06T14:54:55.670Z
@DavidEppstein--I am sorry but I am not able to understand how you are able to do it.Could you just implement it on the sample data given above, on a piece of paper,take its pic and post it here,with some sample queries worked out.THanks
Vk1
CC BY-SA 3.0
2013-03-06T15:51:39.367Z
Did you read the chapter I told you to read?
David Eppstein
CC BY-SA 3.0
2013-03-06T23:14:12.087Z
Yes,I have read it, but I am not able to make the connection.Could you please solve for the above small sample data,So that it can be useful to everyone reading this thread.
Thanks
Vk1
CC BY-SA 3.0
2013-03-07T05:03:16.727Z
Look. It's really easy. Just imagine a balanced binary search tree whose keys are the numbers from 1 to n, representing the positions in the sequence. Then take away those numbers and store the other information stated in my answer. Giving you worked examples of how balanced binary search trees work is freshman-level computer science; it doesn't belong on this board.
David Eppstein
CC BY-SA 3.0
2013-03-07T13:01:06.073Z
I am asking becoz, your idea doesnt work.I tried doing and i cant answer the query of nearest smaller neighbour in O(logn) time.You are just going round and round.Try to work it out.Your answer is definitely wrong until u give a small concrete example.or theoretical proof.
Vk1
CC BY-SA 3.0
2013-03-07T16:20:17.563Z
I give up. If you don't want to learn, I can't make you. But insisting that it's wrong is neither a good way to understand nor a good way to convince me to help unconfuse you.
David Eppstein
CC BY-SA 3.0
2013-03-07T23:43:15.037Z
Okay I have done what you have asked for.
I have attached it as an image.
The first number at each node is the data and the second number is the min of its descendants.
The in-order traversal gives back the original data.It is a balanced tree.Every thing is as you asked for,but the queries dont give the exact result.To see the difference, try solving on the sample array given above and then on the image I have attached. they will give different results.
Do let me know if i have constructed the tree wrong.
http://s12.postimage.org/4sg42k0wt/DSC_0363.jpg
Vk1
CC BY-SA 3.0
2013-03-08T03:57:31.677Z
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?
David Eppstein
CC BY-SA 3.0
2013-03-08T18:06:40.420Z
Hmm.. Seems right now.
Thanks.
The example seems to clarify the doubts.
Interesting and elegant solution.
Pardon my censure,but I do not accept any answer unless I am absolutely sure it is right.
Vk1
CC BY-SA 3.0
2013-03-03T17:38:55.087Z
2013-03-05T02:07:01.793Z
2013-03-05T02:07:01.793Z
David Eppstein
<p>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 (<em>not</em> the value or the memory address of that item).</p>

<ul>
<li><p>$\mathtt{NearestSmaller}(i)$: Return the <em>value</em> of the last item in the sequence that occurs before position $i$ and whose value is less than the value at position $i$.</p></li>
<li><p>$\mathtt{InsertBefore}(x, i)$: Insert a new item with value $x$ into the sequence just before the item with position $i$.</p></li>
<li><p>$\mathtt{Delete}(i)$: Delete item at position $i$ from the sequence.</p></li>
</ul>

<p>In short, my question is whether there is a dynamic version of the <a href="http://en.wikipedia.org/wiki/All_nearest_smaller_values" rel="nofollow">all nearest smaller neighbors</a> algorithm.</p>

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

<ul>
<li><p>$\mathtt{NearestSmaller}(6)$ should return $8 = X[5]$, and </p></li>
<li><p>$\mathtt{NearestSmaller}(10)$ should return $1 = X[4]$.</p></li>
</ul>

CC BY-SA 3.0
2013-03-03T16:58:27.077Z
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?)
Jeffε
CC BY-SA 3.0
2013-03-04T17:40:41.357Z
Thank you,my dear friend,I will re-edit to make it more clear.
Vk1
CC BY-SA 3.0
2013-03-05T06:55:53.820Z
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".
Jeffε
CC BY-SA 3.0
2013-03-05T15:09:40.147Z
Now it is pretty clear. If it is still not clear,I request you to refer to this link
http://en.wikipedia.org/wiki/All_nearest_smaller_values
and try to find a datastructure to implement its dynamic version.
Vk1
CC BY-SA 3.0
2013-03-05T18:53:46.530Z
Edited for concision.  "Position smaller than and closest to $i$" is the same as "last before position $i$".
Jeffε
<ds.data-structures><dynamic-algorithms>
Dynamic Data structure for All nearest smaller values
Vk1
# Dynamic Data structure for All nearest smaller values

(Asked by: username_0 on 2013-03-03)

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](http://en.wikipedia.org/wiki/All_nearest_smaller_values) 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]$.

**Tags:** ds.data-structures, dynamic-algorithms
> **Comments:**
> **username_1**: 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?)  
> **username_0**: Thank you,my dear friend,I will re-edit to make it more clear.  
> **username_1**: 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".  
> **username_0**: Now it is pretty clear. If it is still not clear,I request you to refer to this link http://en.wikipedia.org/wiki/All_nearest_smaller_values and try to find a datastructure to implement its dynamic version.  
> **username_1**: Edited for concision.  "Position smaller than and closest to $i$" is the same as "last before position $i$".  

---

## 1 answers

### Answer by username_2 on 2013-03-03. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_2**: 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?  
> **username_3**: I am sorry, I misread the question. it doesn't seem likely that vED can help here  
> **username_0**: @Sasho-Could you please delete this answer, as it is misleading  
> **username_0**: @DavidEppstein-I have edited the question to make it as clear as possible.Your answer is wrong, since you cant   1.keep height O(logn)   2.make inorder traversal give the original sequence   3.Create a bst...   All three at the same time.   If it were possible, why would someone create cartesian trees.   I am grateful that u answered, but i am not quite convinced that your answer is right.   Try doing all the three above on just the small sample data i have given and you can see that the height is not O(logn).  
> **username_2**: 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.  
> **username_1**: ...or splay tree, or treap, or skip list, or B-tree, or...  
> **username_0**: @DavidEppstein--I am sorry but I am not able to understand how you are able to do it.Could you just implement it on the sample data given above, on a piece of paper,take its pic and post it here,with some sample queries worked out.THanks  
> **username_2**: Did you read the chapter I told you to read?  
> **username_0**: Yes,I have read it, but I am not able to make the connection.Could you please solve for the above small sample data,So that it can be useful to everyone reading this thread. Thanks  
> **username_2**: Look. It's really easy. Just imagine a balanced binary search tree whose keys are the numbers from 1 to n, representing the positions in the sequence. Then take away those numbers and store the other information stated in my answer. Giving you worked examples of how balanced binary search trees work is freshman-level computer science; it doesn't belong on this board.  
> **username_0**: I am asking becoz, your idea doesnt work.I tried doing and i cant answer the query of nearest smaller neighbour in O(logn) time.You are just going round and round.Try to work it out.Your answer is definitely wrong until u give a small concrete example.or theoretical proof.  
> **username_2**: I give up. If you don't want to learn, I can't make you. But insisting that it's wrong is neither a good way to understand nor a good way to convince me to help unconfuse you.  
> **username_0**: Okay I have done what you have asked for. I have attached it as an image. The first number at each node is the data and the second number is the min of its descendants. The in-order traversal gives back the original data.It is a balanced tree.Every thing is as you asked for,but the queries dont give the exact result.To see the difference, try solving on the sample array given above and then on the image I have attached. they will give different results. Do let me know if i have constructed the tree wrong. http://s12.postimage.org/4sg42k0wt/DSC_0363.jpg  
> **username_2**: 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?  
> **username_0**: Hmm.. Seems right now. Thanks. The example seems to clarify the doubts. Interesting and elegant solution. Pardon my censure,but I do not accept any answer unless I am absolutely sure it is right.  

---

