Rotating a tree is an essential step in the process of balancing binary search trees (Red-Black trees and AVL trees). What makes rotations a special and important tool is that they maintain the binary search property.

Left Rotations

Given a subtree with root \(x\) that has a right subtree \(y\). A left rotation makes \(y\) the new root of the subtree and \(x\) its left subtree. \(y\)’s left subtree \(b\) will be \(x\)’s right subtree. The subtrees $a$ and $c$ remain the same.

x a y c b y x c a b << left rotation



Correctness Proof

We want to prove the following:

a left rotation maintains the binary search property

Proof:
Let \(T\) be a binary search tree and let the right subtree above be in \(T\). Let \(T'\) be the tree resulted after \(T\) has been left rotated at \(x\). We want to prove \(T'\) is a binary search tree. To do so, we need to prove that each node is maintaining the BST property. First, since \(y\) is a right child of \(x\) then we know that \(x.key \leq y.key\). After the rotation is done, \(x\) is a left child of \(y\) maintaining the BST property. Similarly, in T, \(b\) is a left child of \(y\), so this means that \(b.key \leq y.key\) and since the \(b\) in the right subtree of \(x\), we also know that \(b.key \geq x.key\). After the rotation is done, we see that in \(T'\), \(b\) is a right child of \(x\) maintaining the BST property since \(b.key \geq x.key\) and \(b.key \leq y.key\). Finally we see that \(a.key \leq x.key\) and \(x.key \leq y.key\) in \(T\) and so so \(a\) is still maintaining the BST property in \(T'\). Similarly, \(c.key \geq y.key\) and \(y.key \geq x.key\) in \(T\) and so \(c\) is still maintaining the BST property in \(T'\).

Implementation

void left_rotate(Node *root, Node *x) {
    Node *y = x->right; // we are assuming x has a right child

    // as in the example above, y's left child b becomes x's new right child
    x->right = y->left;
    if (y->left != nil) { // if there is a left child, fix up the parent pointer
        y->left->parent = x; // b's parent is x now
    }

    // since y is the new root then we fix up y's parent pointer
    y->parent = x->parent;
	
	// we should now fix the parent link to point to y unless x was the root itself, then y is the new root
    if (x->parent == nil) { // this means x is the root (no parent pointer)
        T->root = y;
    } else if (x == x->parent->left) { // x is a left child, make y the left child of x's parent
        x->parent->left = y;
    } else { // x is a right child, make y the right child of x's parent
        x->parent->right = y;
    }

    // finally, x is now the left child of y and y is its parent
    y->left = x;
    x->parent = y;
}


Right Rotations

Similarly, a rotation rotation takes a node \(y\) with its left child \(x\) and rotate them so that \(x\) is the parent of \(y\) and \(y\) is now a right child of \(x\).

x a y c b y x c a b right rotation >>


Implementation

void right_rotate(Node *root, Node *x) {
    Node *x = y->left; // we are assuming y has a left child x

    // as in the example above,x's right child becomes y's left child
    y->left = x->right;
    if (x->right != nil) { // fix up the parent pointer
        x->right->parent = y;
    }

    // since x is the new root then we fix up x's parent pointer
    x->parent = y->parent;
	
	// we should now fix the parent link to point to x unless y was the root itself, then y is the new root
    if (y->parent == nil) { // this means y is the root (no parent pointer)
        T->root = x;
    } else if (y == y->parent->left) { // y is a left child, make x the left child of y's parent
        y->parent->left = x;
    } else { // y is a right child, make x the right child of y's parent
        y->parent->right = x;
    }

    // finally, y is now the right child of x and x is its parent
    x->right = y;
    y->parent = x;
}


Running Time

Since we’re performing a constant number of link changes then the runtime is \(O(1)\).

Implementation

https://github.com/strncat/algorithms-and-data-structures/blob/master/trees/red-black-tree.cpp

References

CLRS