3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.