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.
Remove from black/red tree subtree with red root, red sibling and black parent in $O(\lg n)$
data structures;binary search trees
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)$).