According to my lecture notes, adding a red child to a red node with a black sibling in a red-black tree, is equivalent to changing a 3-node into a 4-node in a 2-3-4 tree. I've built several red-black trees with different values to try to get to this situation, but I never seem to get to the situation where I have a red node with a black sibling, and where the value to be inserted will be inserted below the red node. I'm starting to ask myself if this situation could ever happen in a red-black tree?
1 Answer
$\begingroup$ $\endgroup$
Assume we have a black node $N$ with black child $L$ and red child $R$. Thus we have a red and black sibling. Recall that in a red-black tree all paths from root to leaf must have the same number of black nodes. The path $N-L$ contains two black nodes, the path $N-R$ just one. That means that both children of $R$ must be present, and must be black. So indeed, we can not add a new red child to $R$ because it already has black children. However, what can happen is that one of these black children turns red as consequence of a flag-flip. We then are in the situation you describe.
