Welcome to Programming and Data Structures

There are different strategies for tracking and maintaining balance in a binary tree. But all of the strategies rely on a fundamental operation called a rotation. A rotation is a local restructuring of a small part of the tree that changes the heights of the left and right subtrees of a node. By performing rotations during insertions and deletions, we can keep the overall tree balanced.

A rotation can be named in multiple ways, but the most common is to name it based on the direction that the subtree is rotated. A right rotation is one where a node is rotated down to the right, and its left child is rotated up to take its place. A left rotation is the opposite: a node is rotated down to the left, and its right child is rotated up to take its place.

This rotation improves the balance of the tree by reducing the height of the left subtree and increasing the height of the right subtree of the rotated node. In the simple example above, the heights of the left and right subtrees of the root node went from 2 and 0 to 1 and 1.

Of course, not every tree is as simple as that one. Often times there will be children below the nodes being rotated. The rotation operation must preserve the binary search tree property, so we need to be careful about where those children end up after the rotation.

When rotating right, the two nodes involved in the rotation are the pivot (the node being rotated down) and its left child (the node being rotated up). The left child may have both left and right children of its own. The pivot may have a right child. We will refer to the left child’s left child as \(A\text{,}\) its right child as \(B\text{,}\) and the pivot’s right child as \(C\text{.}\)

\(A\) and \(C\) can stay where they are in the rotation. \(B\) however presents a problem. The old left child (3 in our diagram) will need to use its right pointer to point at the pivot (the 5 node). So we need to do something with \(B\text{.}\)

Note that whatever value \(B\) has, it must be less than the pivot or it would not have ended up in the left subtree. Also, it must be greater than the left child or it would not have ended up as the right child of the left child. So \(B\) needs to remain between the left child and the pivot after the rotation.

Fortunately, as the pivot rotates down, it no longer needs to use its left pointer. The node it was pointing at is now its parent. So we can have the pivot use its left pointer to point at \(B\text{.}\) This keeps \(B\) in the correct position in the tree and preserves the binary search tree property.

Left rotations are simply a mirror image of right rotations. In a left rotation, the pivot is rotated down to the left, and its right child is rotated up to take its place. The pivot adopts its middle grandchild (the left child of the right child) as a new right child.

The code to do a rotation like this is relatively simple. Given a pointer to the pivot node, we can perform the rotation as follows:

Node* rotateRight(Node* pivot) {
    Node* leftChild = pivot->left;
    Node* middleGrandchild = leftChild->right;  // may be null, doesn't matter
    pivot->left = middleGrandchild;             // Pivot adopts middle grandchild
    leftChild->right = pivot;                   // Left child adopts pivot
    return leftChild;                           // New root of the subtree
}

Note that we return the new root of the subtree after the rotation. We would need to update the parent node’s pointer to point to this new root.

...
// left child of "parent" need to rotate right
parent->left = rotateRight(parent->left);
...