<p>Given a balanced binary search tree, suppose I have an operation decrease-right-keys(k, s) that operates as follows: when I call this operation on a tree $T$, I decrease all keys by $s$ in the right subtrees along the path created by searching for $k$. </p>

<p>For example, suppose I call decrease-right-keys(1, 3). I would search for $1$. Along the search path, I would decrease the key of every element of every right subtree along this path by $3$.</p>

<p>My question is, is there a way to create a balanced binary search tree with this operation operating in $O(\log{n})$ time or $O(\log{n})$ amortized time? I realize that I can't actually decrease all keys in all the right subtrees because that would require $O(n)$ time potentially. But maybe there's a way to implement the operation without having to physically decrease all the keys?  </p>

CC BY-SA 3.0
2015-01-09T11:57:31.197Z
Such a data structure is likely to give the ability to merge two arbitrary balanced BSTs of size $n$ in $O(log(n))$ time. Maybe an efficient time complexity in the amortized sense is a more realistic objective.
Nicolas Perrin
CC BY-SA 3.0
2015-01-09T15:17:08.360Z
Ah correct! I meant to state amortized but I did not. It is changed now.
Quanquan Liu
CC BY-SA 3.0
2015-01-09T17:14:10.880Z
Although I don't quite see how solving this problem will allow for merging two BBSTs in $O(\log{n})$ time?
Quanquan Liu
CC BY-SA 3.0
2015-01-09T17:53:22.547Z
It's quite hypothetical, but consider two BBSTs of size $n$, $T_1$ and $T_2$. It shouldn't be difficult to use a variant of your operation to decrease all the keys in $T_1$ (maybe with an additional construction) by a huge value $l$, so that all the keys in $T_2$ are greater than the ones in $T_1$. Then it shouldn't be difficult to join the two trees, maybe with a new key $k$ at the root, so that you have $T_1$ at the left of $k$ and $T_2$ at the right of $k$ (although the data structure required might not allow that).
Nicolas Perrin
CC BY-SA 3.0
2015-01-09T17:53:39.647Z
Then you use decrease-right-keys($k$,$l$), which would decrease all the keys in $T_2$ by $l$. The result obtained should essentially behave like a merging of $T_1$ and $T_2$ (after deleting $k$). The decrease of all the keys by $l$ does not really matter.
Nicolas Perrin
CC BY-SA 3.0
2015-01-09T17:54:06.277Z
But OK, I'm not pretending to be convincing here, it's really more a hunch than anything else.
Nicolas Perrin
CC BY-SA 3.0
2015-01-11T13:07:12.713Z
What other operations do you need to support? (If the _only_ operation you need is decrease-right-keys, I can solve it in O(1) worst-case time!) if you really need to maintain a binary search tree (as opposed to a data structure that supports the same operations as a binary search tree), then @NicolasPerrin's argument seems to imply that O(log n) time is impossible.
Jeffε
CC BY-SA 3.0
2015-01-13T21:53:23.113Z
@Jeff, it should support search, insertion, deletion of keys, and decrease-right-keys in $O(\log{n})$ amortized time. The data structure may be of any form so long as it supports the aforementioned operations. Sorry if this wasn't clear before.
Quanquan Liu
CC BY-SA 3.0
2015-01-13T22:16:10.200Z
NicolasPerrin, your argument does indeed make this a very useful operation...@JeffE, I was looking at your post about merging two binary search trees [Merging Two Binary Search Trees](http://cstheory.stackexchange.com/questions/10407/merging-two-binary-search-trees) in $O(\log{n})$ amortized time. Based on this, NicholasPerrin's argument does make it seem like the operation is possible in the time bound given in the question.
Quanquan Liu
<ds.algorithms><ds.data-structures>
Rebalancing balanced binary search tree when decreasing all keys to the right of a path?
Quanquan Liu
# Rebalancing balanced binary search tree when decreasing all keys to the right of a path?

(Asked by: username_0 on 2015-01-04)

Given a balanced binary search tree, suppose I have an operation decrease-right-keys(k, s) that operates as follows: when I call this operation on a tree $T$, I decrease all keys by $s$ in the right subtrees along the path created by searching for $k$.

For example, suppose I call decrease-right-keys(1, 3). I would search for $1$. Along the search path, I would decrease the key of every element of every right subtree along this path by $3$.

My question is, is there a way to create a balanced binary search tree with this operation operating in $O(\log{n})$ time or $O(\log{n})$ amortized time? I realize that I can't actually decrease all keys in all the right subtrees because that would require $O(n)$ time potentially. But maybe there's a way to implement the operation without having to physically decrease all the keys?

**Tags:** ds.algorithms, ds.data-structures

> **Comments:**
> **username_1**: Such a data structure is likely to give the ability to merge two arbitrary balanced BSTs of size $n$ in $O(log(n))$ time. Maybe an efficient time complexity in the amortized sense is a more realistic objective.  
> **username_0**: Ah correct! I meant to state amortized but I did not. It is changed now.  
> **username_0**: Although I don't quite see how solving this problem will allow for merging two BBSTs in $O(\log{n})$ time?  
> **username_1**: It's quite hypothetical, but consider two BBSTs of size $n$, $T_1$ and $T_2$. It shouldn't be difficult to use a variant of your operation to decrease all the keys in $T_1$ (maybe with an additional construction) by a huge value $l$, so that all the keys in $T_2$ are greater than the ones in $T_1$. Then it shouldn't be difficult to join the two trees, maybe with a new key $k$ at the root, so that you have $T_1$ at the left of $k$ and $T_2$ at the right of $k$ (although the data structure required might not allow that).  
> **username_1**: Then you use decrease-right-keys($k$,$l$), which would decrease all the keys in $T_2$ by $l$. The result obtained should essentially behave like a merging of $T_1$ and $T_2$ (after deleting $k$). The decrease of all the keys by $l$ does not really matter.  
> **username_1**: But OK, I'm not pretending to be convincing here, it's really more a hunch than anything else.  
> **username_2**: What other operations do you need to support? (If the _only_ operation you need is decrease-right-keys, I can solve it in O(1) worst-case time!) if you really need to maintain a binary search tree (as opposed to a data structure that supports the same operations as a binary search tree), then @NicolasPerrin's argument seems to imply that O(log n) time is impossible.  
> **username_0**: @Jeff, it should support search, insertion, deletion of keys, and decrease-right-keys in $O(\log{n})$ amortized time. The data structure may be of any form so long as it supports the aforementioned operations. Sorry if this wasn't clear before.  
> **username_0**: NicolasPerrin, your argument does indeed make this a very useful operation...@JeffE, I was looking at your post about merging two binary search trees [Merging Two Binary Search Trees](http://cstheory.stackexchange.com/questions/10407/merging-two-binary-search-trees) in $O(\log{n})$ amortized time. Based on this, NicholasPerrin's argument does make it seem like the operation is possible in the time bound given in the question.  

---

## 0 answers

