Red Black Tree Insertion Cases

Question

This may be a very easy question, but I could not find a satisfying answer. After a node is inserted into the red-black tree, three different cases can be encountered :

newly added node = z

Case 1 : z = red, parent of z = red, uncle of z = red

Case 2 : z = red, parent of z = red, z = right child, uncle of z = black

Case 3 : z = red, parent of z = red, z = left child, uncle of z = black

However, I think that we cannot directly enter into case 2 or case 3 because assume that x and y are siblings and red and black respectively. When we insert z under the node x, case 2 or case 3 can be observed without entering into case 1. However, this means that before adding node z, the red-black tree is not balanced because the black-height rule is already broken.

            Grandparent
             /       \
        x(red)       y(black)
        /   \         /   \
    nil(b) nil(b)  nil(b)  nil(b)

The node z can be added into one of the nil pointers of node x, but it is impossible that the tree is like this. After each insertion, the red-black tree must be balanced.

However, my algorithm professor rejected this theory; hence, I cannot ensure this situation. Is it possible to be involved in case 2 or case 3 without case 1 ?

wow, great question. I would really love to see a detailed answer. — Shihab Shahriar Khan
Thank you so much, but I cannot find a clear answer in any place. — Goktug

Matt Timmermans Matt Timmermans · Accepted Answer · 2017-12-17T14:36:48

Remember that nulls are black.

It happens like this:

           Grandparent
            /       \
        x(red)      nil(b)
        /   \     
    nil(b) nil(b) <-- z goes here

Red Black Tree Insertion Cases

1 Answers