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?

  • 1
    $\begingroup$ 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. $\endgroup$ Jan 9, 2015 at 11:57
  • $\begingroup$ Ah correct! I meant to state amortized but I did not. It is changed now. $\endgroup$ Jan 9, 2015 at 15:17
  • $\begingroup$ Although I don't quite see how solving this problem will allow for merging two BBSTs in $O(\log{n})$ time? $\endgroup$ Jan 9, 2015 at 17:14
  • 3
    $\begingroup$ 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. $\endgroup$ Jan 9, 2015 at 17:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Jan 11, 2015 at 13:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.