5
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 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$
    – Nicolas Perrin
    Jan 9, 2015 at 11:57
  • $\begingroup$ Ah correct! I meant to state amortized but I did not. It is changed now. $\endgroup$
    – Quanquan Liu
    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$
    – Quanquan Liu
    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$
    – Nicolas Perrin
    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

0

Reset to default

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.