CODEWITHSUNDEEP
algorithmrotationred-black-tree
NANDAKUMAR THANGAVELU
NANDAKUMAR THANGAVELU

Reputation: 661

Rules to follow while recoloring after rotation in Red Black Tree

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.

Upvotes: 2

Views: 3972

Answers (2)

templatetypedef
templatetypedef

Reputation: 372764

I've been teaching algorithms and data structures for a couple of years now and my honest advice about red/black trees is the following:

Know where the rotation rules and color flips come from, but don't memorize them.

It's extremely uncommon to actually need to trace through red/black tree rotations by hand or to have to code them up. In those cases, I'd recommend doing what most people do, which is to open up a copy of CLRS and copy whatever pseudocode they've included.

What's more valuable, in my opinion, is to understand where these rules come from the first place and how anyone managed to derive them. Although this isn't often taught, the original rules for red/black trees were derived by using a connection between red/black trees and a related data structure called the 2-3-4 tree. 2-3-4 trees are significantly easier to understand than red/black trees, and once you've seen the connection between them you can actually rederive all the rotations and color flips you'll need to fix up a red/black tree on-the-fly and without too much difficulty. I've put together a set of lecture slides outlining the connection between these data structures and how to use it, and if you're interested, this might be a great way to understand how red/black trees work.

Upvotes: 6

Sumeet
Sumeet

Reputation: 8292

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.

Upvotes: 3

Related Questions