Rotations Keep the Height

The rotations are the last operations that can leave a cached height out of date.

The only addition to rightRotation is two updateHeight calls:

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

After the pointer changes, root and child are the only nodes whose children changed, so they are the only two whose heights can be wrong. The subtrees A, B, and C from the rotation pictures kept their shape, so their heights are still correct, and two $O(1)$ updates are enough.

This is the bottom-up rule: root is now below child, and child’s new height is computed from root’s, so updateHeight(root) comes first.

leftRotation is the mirror, with the same two lines in the same order:

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

The double rotations need no change at all. We wrote each one as two single rotations in a row. Each single rotation now updates the two heights it changes, so when a double rotation finishes, every node it moved already has a correct height.