## Rotation

When we perform insert or delete operation on a redblack tree, they modify the tree and the result may violate the red-black properties. To restore these properties, we may have to flip the colors of some of the nodes in the tree and also change the pointer structure through rotation if it violates property 5 (For each node, all simple paths from the node to descendant leaves contain the same number of black nodes).
A rotation is a rearrangement of the nodes which preseves the binary search tree properties.
There are two kinds of rotaions: left rotation and right rotation. When we do a left rotation on a node P, we assume that its right child R is not null. The left rotation “pivots” around the link from P to R. It makes R the new root of the subtree, with P as R’s left child and R’s left child as P’s right child. The letters A and B represent arbitrary subtrees.

### Left Rotation

 Tree Rotations (TreeMap-3)

### P is right to the root

 Tree Rotations (TreeMap-3)

### P is left to the root

 Tree Rotations (TreeMap-3)

### Intermediate Stages

 Tree Rotations (TreeMap-3)
 Tree Rotations (TreeMap-3)

### Right Rotation

 Tree Rotations (TreeMap-3)

### P is left to the root

 Tree Rotations (TreeMap-3)

### P is right to the root

 Tree Rotations (TreeMap-3)
Home
Share.