Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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)$).
