Rules to follow while recoloring after rotation in Red Black Tree

Question

I am just newbie to RB Tree. I just got hanged in doing re-coloring the tree after the rotation.

Lets Consider the following case:-

Order of insertion: 34,32,56,30,31

            34 (B)

        32 (B)      56 (B)

    30 (R)

        31 (R)

In the above case the color conflict occurs in the insertion of 31, to the parent of 30 and also the height instability occurs.

So for the tree 32,30,31 we are doing the Left Right rotation which is same as doing in the AVL tree.

Upto this rotation, it seems fine for me.

But after the rotation, the tree will become like,

            34 (B)

        31 (R)      56 (B)

    30 (R)      32 (B)

So here, the red-red conflict occurs at 31 and 30. And also the blackness of the left sub tree got affected.

May I kindly know, what are the steps of formula/conditions, that I have to apply to correct this coloring and blackness problem.

Thanks in advance.

Answer 1

The invariants to be kept in mind while inserting keys in RED BLACK tree are:

1.The root is always black.

2.No two red nodes can be consecutive.

3.The number of black nodes visited from every root to null path must be equal.

Keeping the above points in mind, let us do the insertions:

insert(34)

34(B)

insert(32)

    34(B)
   /
  32(R)

insert(56)

    34(B)
   /    \
  32(R)  56(R)

insert(30)

    34(B)
   /    \
 32(R)  56(R)
 /
30(R)

Violation of invariant 2.

To handle this we do the recolouring of nodes 32 and 56 to be black and make their parent red.

But by making thier parent red Violation of invariant 1 occurs, so we keep their parent black and we have the following tree.

    34(B)
   /    \
 32(B)  56(B)
 /
30(R)

The above tree satisfies all the invariants and we continue with insertions.

insert(31)

        34(B)
       /    \
     32(B)  56(B)
     /
    30(R)
       \
       31(R)

Violation of invariant 2.

To handle this violation, we perform Left Rotation on the node 32 and node 31 (its a single rotation affecting these 2 nodes).

        34(B)
       /    \
     32(B)  56(B)
     /
    31(R)
    /
  30(R)

Now we perform Right Rotation on the node 31 and node 32

        34(B)
       /    \
     31(R)  56(B)
     /  \ 
  30(R) 32(B)

Now we perform Right Rotation on the node 31 and node 34

        31(R)
       /    \
     30(R)  34(B)
            /   \
          32(B) 56(B)

Now we recolour the node 31 and node 30 to be black and node 32 and node 56 to be red. We get the following tree:

        31(B)
       /    \
     30(B)  34(B)
            /   \
          32(R) 56(R)

Our final tree satisfies all the properties of RED BLACK tree and is also balanced.