1
$\begingroup$

How can i remove from a red/black tree a subtree whose root and its sibling are red, and their parent is black, in $O(\lg n)$ time, while keeping the red/black properties at the end of the process?

In other words: I have a black/red tree with $n$ nodes, a given black node $y$, and his two red children $x$ and $z$. How can I delete the subtree of $x$ in $O(\lg n)$ time, while keeping the red/black tree properties at the end of the process?

This is an homework question.

$\endgroup$
1
$\begingroup$

The solution is to delete the sub-tree $x$ ($O(\lg n)$), then replace sub-tree $z$ instead of sub-tree $y$ ($O(1)$), then turn $z$ to black ($O(1)$), and finally insert $y$ as usual ($O(\lg n)$).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.