4

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 ?

2
  • wow, great question. I would really love to see a detailed answer. Dec 17, 2017 at 13:40
  • Thank you so much, but I cannot find a clear answer in any place.
    – Goktug
    Dec 17, 2017 at 13:51

1 Answer 1

3

Remember that nulls are black.

It happens like this:

           Grandparent
            /       \
        x(red)      nil(b)
        /   \     
    nil(b) nil(b) <-- z goes here
2
  • I am grateful for your answer and you. Thank you so much. The tree which you drew negates my theory.
    – Goktug
    Dec 17, 2017 at 14:51
  • The node "U" in the picture of case 4 looks not like a null node...
    – cifer
    Jun 27, 2020 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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