O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

The concept of rotation

Before we jump headlong into the nitty-gritty of Red-Black tree implementation, let's look at a fundamental concept: rotation. Rotations are used in Red-Black trees to restore balance.

Let's look at left rotation first. Rotate the tree counterclockwise so the node 19, which was earlier a parent of 12, becomes its right child.

It is always okay to do this as the parent of a node can be made its right child to preserve the BST invariant, namely the right child value should be greater that the parent node. The parent 95 of 12 has now become the parent of 19. The original left child of 19 was 17, which is now the right child of 12. Lastly, 12 is now the new left child of 19.

Note that we just changed a fixed number of pointers. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required