1

I am trying to figure out the rotation in a Red Black tree while its rebalancing is done. I understand why rotation is occurring but I don't get how it is being done. Also, what intermediate rotations like LL, RR , LR and RL are done to reach till the result and I would also appreciate if someone tells me any rule of thumb as to when to do any one of these rotation. Here is the rotation:

enter image description here

Rr(2) is the case when black node deficiency is in right child of "py" i.e. 
"y" and grandchild of "v" are 2 red nodes i.e. "b" and "x"
java_doctor_101
  • 3,287
  • 4
  • 46
  • 78

1 Answers1

1

You can try to understand rotations in Red Black Trees in a better way by breaking down the operation into different rotations. There are only 3 basic operations for a Left Leaning Red Black BST. The operations are performed in order as listed in this slide.

Image demonstrating the rotations.

Moreover, the Red Black Tree that you have shown is not correct as it violates the condition for a Red Black Tree. ie. Every path from the root to the leaf must have equal number of black edges. But in your final tree, the path from x to c has 2 black edges, while the path from x to a has 1 black edge. I recommend you to read more about self balancing BSTs and Red-Black BSTs from here.

PS. I do not own the slide. It has been taken from Robert Sedgewick's course on Algorithms from coursera.

Nikunj Banka
  • 11,117
  • 16
  • 74
  • 112