Rotations

Rotations are common to all balanced search trees. The idea is to locally rebalance subtrees at a node in O(1) time without violating the search tree property. When you invoke a rotation, it is always on a parent-child node pair. If it is a right child, you need a left rotation and vice-versa for a left child.

Here is a diagram.

We want to rotate the pair (x,y) so that Y is the new child of P. Since X is less than Y, X must be Y's left child. Since C is greater than Y, it must be Y's right child. Since A is greater than X, it must be X's left child. Now we know X<B<Y so B will be X's right child. This also satisfies that B is on Y's left subtree.

A right rotation is very similar to this.