5

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?

Quanquan Liu
  • 313
  • 1
  • 8
  • 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. – Nicolas Perrin Jan 09 '15 at 11:57
  • Ah correct! I meant to state amortized but I did not. It is changed now. – Quanquan Liu Jan 09 '15 at 15:17
  • Although I don't quite see how solving this problem will allow for merging two BBSTs in $O(\log{n})$ time? – Quanquan Liu Jan 09 '15 at 17:14
  • 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 Jan 09 '15 at 17:53
  • 3
    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 Jan 09 '15 at 17:53
  • But OK, I'm not pretending to be convincing here, it's really more a hunch than anything else. – Nicolas Perrin Jan 09 '15 at 17:54
  • 1
    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ε Jan 11 '15 at 13:07
  • @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 Jan 13 '15 at 21:53
  • 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 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 Jan 13 '15 at 22:16

0 Answers0