Learning Functional Data Structures and Algorithms

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. ...