Remove from black/red tree subtree with red root, red sibling and black parent in $O(\lg n)$

Question

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.

Answer 1

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)$).