Rotation :
Rotation Is a rearrangement of the nodes that hopefully leaves the tree more balanced.
In essence, were designed to do following:
Raise some nodes & lower others to help balance the tree.
Ensure that the characteristics of a binary search tree are not violated.
Red-Black Tree :
Red-Black Tree Rotation doesn’t rotate the nodes themselves but the relationships between them changes.
One node is chosen as the “top” of the rotation.
If were doing a right rotation, this “top” node will move down and to the right, into the position of it’s right child .
Its left child will move up to take its place.
Note: that the “top” node is not the center of the rotation. Also you must be sure that when your doing the right rotation, the top node has a left child.
Red-Black Tree :
Red-Black Tree Otherwise, there’s nothing to rotate in to the “top” spot. Similarly, when doing the left rotation, the top node must have the right child.
Red-Black Tree :
Red-Black Tree A B C D E G F H I J K L K