# Rebalancing balanced binary search tree when decreasing all keys to the right of a path?

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?

• 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 9 '15 at 11:57
• Ah correct! I meant to state amortized but I did not. It is changed now. – Quanquan Liu Jan 9 '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 9 '15 at 17:14
• 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 9 '15 at 17:53
• 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