Rotations in Code

A rotation happens at one node and changes only the subtree rooted there. So the method takes that node and returns the subtree’s new root. Let’s take a look at the single right rotation. Here is the general picture, with A, B, and C standing for whole subtrees, each one possibly empty:

       ╭──────╮
       │ root │
       ╰──┬───╯
      ┌───┴────┐
  ╭───┴───╮  ╭─┴─╮
  │ child │  │ C │
  ╰───┬───╯  ╰───╯
   ┌──┴───┐
 ╭─┴─╮  ╭─┴─╮
 │ A │  │ B │
 ╰───╯  ╰───╯

The node we lift is child, the left child of root. After the rotation, child is on top. root has come down to become its right child, and the subtree B in the middle has moved over to root’s left:

     ╭───────╮
     │ child │
     ╰───┬───╯
    ┌────┴─────┐
  ╭─┴─╮     ╭──┴───╮
  │ A │     │ root │
  ╰───╯     ╰──┬───╯
           ┌───┴───┐
         ╭─┴─╮   ╭─┴─╮
         │ B │   │ C │
         ╰───╯   ╰───╯

The method changes two links:

private Node<K, V> rightRotation(Node<K, V> root) {
  Node<K, V> child = root.left;
  root.left = child.right;
  child.right = root;
  return child;
}

root.left = child.right moves the middle subtree B from child’s right to root’s left. It has to run first, while child.right still points at B.

Left rotation

The left rotation is the mirror. This time child is root’s right child, and the middle subtree B moves from child’s left to root’s right. The code is rightRotation with every left and right swapped:

private Node<K, V> leftRotation(Node<K, V> root) {
  Node<K, V> child = root.right;
  root.right = child.left;
  child.left = root;
  return child;
}

Double rotations

A double rotation is two single rotations in a row: first rotate the child to straighten the bend, then rotate the root. Here is the right-left double:

private Node<K, V> rightLeftRotation(Node<K, V> root) {
  root.right = rightRotation(root.right);
  return leftRotation(root);
}

The first line right-rotates root’s right child and stores the result back as root.right, the same way a caller reattaches any rotated subtree.

The left-right double is the mirror:

private Node<K, V> leftRightRotation(Node<K, V> root) {
  root.left = leftRotation(root.left);
  return rightRotation(root);
}