CODEWITHSUNDEEP
algorithmtreerotationred-black-tree
JimBelushi2
JimBelushi2

Reputation: 285

How to rotate in red black tree

I'm trying to solve this exercise with red black tree: I need to insert 2, 1, 4, 5, 9 in this order. After the last input I need to balance it with the Insert-Fixup algorithm: enter image description here

The part of the algorithm I need to follow is:

if z == z.p.right
   z = z.p
   LEFT-ROTATE (T, z)
z.p.color = BLACK
z.p.p.color = RED
RIGHT-ROTATE (T, z.p.p)

(Z is the node I want to insert) and z.p is its father. So I tried to follow the steps until the left rotation and this is the result: is it right? enter image description here

I searched on internet and I read that there are double rotation algorithm, but I cannot figure out if I can use them here instead of using the single rotation (for example I don't know hot to right rotate the node with the 4).

Upvotes: 2

Views: 2014

Answers (1)

Deepak Tatyaji Ahire
Deepak Tatyaji Ahire

Reputation: 5309

You are following the wrong case. I have explained the answer in the following steps. In the last step, i.e. inserting 9, we have to do left-rotate(4) and recoloring.

Following is the pic in which I have explained the steps:

enter image description here

Upvotes: 3

Related Questions