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