TreeRotation.cpp

/*
 * Perform a single rotation in the given direction around a given root
 * tree and return the new root.
 * 3           4
 *  \         / \
 *   4   ==> 3   5
 *    \
 *     5
 *
 * The comments will follow with an example of performing a left rotation
 * on this tree.  The root is 3 with a direction of 0.
 */
Tree * SingleRotation(Tree *root, int dir) {
  Tree *pivot = root->children[!dir];

  root->children[!dir] = pivot->children[dir]; // e.g. 3 takes 4's left child as its right child.
  pivot->children[dir] = root;                 // e.g. 4 takes 3 as its left child.
  return pivot;                                // e.g. 4 becomes the new root.
}

/*
 * Perform a double rotation in the given direction around a given root
 * tree and return the new root.
 * 3         4
 *  \       / \
 *   5 ==> 3   5
 *  /
 * 4
 *
 * The comments will follow with an example of performing a double rotation
 * on the given tree and returning the new root.
 */
Tree * DoubleRotation(Tree *root, int dir) {
  // e.g. Perform a right rotation on 5, effectively swapping 4 and 5's 
  // position.  It is required that we assign the new root to where 5 was.
  root->children[!dir] = SingleRotation(root->children[!dir], !dir);

  // e.g. Now that our structure is like the previous example tree from
  // SingleRotation, we can perform a left rotation on 3 creating our
  // properly balanced tree.
  return SingleRotation(root, dir);
}