Assume I have an order-statistic tree, $T$, which is a red-black tree where every node $x$ also has the attribute $x.size$. How can I compute the worst-case running time of an arbitrary sequence of $n$ insertions/deletions and $m$ calls to SELECT($x, i$), which returns a pointer to the node containing the $i$th smallest key in the subtree rooted at $x$.

I know that insertion, deletion and SELECT is done in $O(\lg k)$ time where $k$ is the number of nodes in the tree $T$.

Any hints would be greatly appreciated.


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.