0
$\begingroup$

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.

$\endgroup$

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.