Red-Black-Tree algorithm: About the RB-INSERT-FIXUP(T, z)

 The insertion procedure in red-black-tree, the insertion algorithm is something like,

1. hey, here is the newbie z!

2. are you smaller than this newbie? (z) 

    yes -> okay, next (smaller guy)

    no -> okay, next (bigger guy)

then finally, find the correct location on which a < z < b. 

plus, since does not have it's children, z.left and z.right is assigned nil, plus it's color is assigned as RED.

However, this is not the end of insertion. Actually, the insertion procedure of the red-black-tree causes the corruption of the color pattern rule that red -> black -> red -> black so that we need to fix the color pattern corruption with the function called

RB-INSERT-FIXUP(T,z)

Okay, let' have a look:

So, I do not provide the code details here (if you are interested, please have a look at this) 

Initially, we have node z and it's parent Q, it's grand pa A. then:

secondly, we confirm if the z.grandpa's right child (y) is RED, then Q (its bro) should be black as well (since the child nodes of the red node should always be black), and y should be BLACK as well, and A should be converted to BLACK. then we move the pointer of Z to A, so now A is going to be Z.

The other case: if Z is position at the right of its daddy (Q), then we move Z pointer to Q and Left-rotate.

Left rotate, as explained earlier brings the straight line(BLUE) part (W-O) part and leave the others (P-D: yellow as GARBAGE). So it is transformed like this:

Then, we make W as black and A as red, then right-rotate for A:

here is right rotate:

Yeah it's bit complicated but if you understand well on the rotation, this function is not that intimidating.

thanks