Tree Rotations (TreeMap-3)

0

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)
Tree Rotations (TreeMap-3)

P is right to the root

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

P is left to the root

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

Intermediate Stages

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

Right Rotation

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

P is left to the root

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

P is right to the root

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

About Author

Ram's expertise lies in test driven development and re-factoring. He is passionate about open source technologies and loves blogging on various java and open-source technologies like spring. You can reach him at [email protected]

Leave A Reply