DSW Algorithm
by Isai Damier, Android Engineer @ Google

/***************************************************************************
 * Author: Isai Damier
 * Title: DSW Algorithm
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Transform the given BST into a perfectly balanced BST so that its
 *   height is log n, where n is the number of nodes on the tree.
 *
 *  Time Complexity: O(n)
 *  Space Complexity: O(1)
 *
 * Details:
 *   While trees are great at depicting hierarchy among objects, the most
 *   important aspect of a binary search tree (BST) is the blazing search
 *   speed that a perfectly balanced BST provides. If a perfectly balanced
 *   BST contains 10,000 objects, it takes at most 14 comparisons to find
 *   an object; a linked list would require 10,000 comparisons: O(n). Does
 *   your BST contain one million objects? Then it would take at most 20
 *   comparisons. One billion objects? Then 30 comparisons. This is because
 *   in a perfectly balanced BST, height = log2(n).
 *
 *   Imagine having to spend $20 to get a million dollars worth of gold;
 *   while everyone else has to spend one million dollars for the same
 *   amount of gold. What would you not do to get that kind of buying power?
 *   That same mindset has fueled a slew of research in Balancing BSTs.
 *   (The members of the US Congress almost had that kind of power: they
 *   used to be allowed to do insider trading; a crime for everyone else.)
 *
 *   The following algorithm was invented by Colin Day and later refined
 *   by Quentin F. Stout and Bette L. Warren: hence, DSW. It takes an
 *   ordinary BST and transforms it into a perfectly balanced BST. A BST
 *   is perfectly balanced if the leaves are on the same level or one
 *   level apart. The algorithm goes as follows:
 *
 *   1] Using right-rotation operations, turn the tree into a linked list
 *      (a.k.a. backbone or vine)
 *   2] Rotate every second node of the backbone about its parent to turn
 *      the backbone into a perfectly balanced BST. Voila!
 *
 **************************************************************************/ 
 public void DSW() {
  if (null != root) {
    createBackbone();// effectively: createBackbone( root)
    createPerfectBST();//effectively: createPerfectBST( root)
  }
}

/**
 * Time complexity: O(n)
 */
private void createBackbone() {
  Node grandParent = null;
  Node parent = root;
  Node leftChild;

  while (null != parent) {
    leftChild = parent.left;
    if (null != leftChild) {
      grandParent = rotateRight(grandParent, parent, leftChild);
      parent = leftChild;
    } else {
      grandParent = parent;
      parent = parent.right;
    }
  }
}

/************************************************************************
 *   Before      After
 *    Gr          Gr
 *     \           \
 *     Par         Ch
 *    /  \        /  \
 *   Ch   Z      X   Par
 *  /  \            /  \
 * X    Y          Y    Z
 ***********************************************************************/
private Node rotateRight(Node grandParent, Node parent, Node leftChild) {
  if (null != grandParent) {
    grandParent.right = leftChild;
  } else {
    root = leftChild;
  }
  parent.left = leftChild.right;
  leftChild.right = parent;
  return grandParent;
}

/**
 * Time complexity: O(n)
 */
private void createPerfectBST() {
  int n = 0;
  for (Node tmp = root; null != tmp; tmp = tmp.right) {
    n++;
  }
  //m = 2^floor[lg(n+1)]-1, ie the greatest power of 2 less than n: minus 1
  int m = greatestPowerOf2LessThanN(n + 1) - 1;
  makeRotations(n - m);

  while (m > 1) {
    makeRotations(m /= 2);
  }
}

/**
 * Time complexity: log(n)
 */
private int greatestPowerOf2LessThanN(int n) {
  int x = MSB(n);//MSB
  return (1 << x);//2^x
}

/**
 * Time complexity: log(n)
 * return the index of most significant set bit: index of
 * least significant bit is 0
 */
public int MSB(int n) {
  int ndx = 0;
  while (1 < n) {
    n = (n >> 1);
    ndx++;
  }
  return ndx;
}

private void makeRotations(int bound) {
  Node grandParent = null;
  Node parent = root;
  Node child = root.right;
  for (; bound > 0; bound--) {
    try {
      if (null != child) {
        rotateLeft(grandParent, parent, child);
        grandParent = child;
        parent = grandParent.right;
        child = parent.right;
      } else {
        break;
      }
    } catch (NullPointerException convenient) {
      break;
    }
  }
}

private void rotateLeft(Node grandParent, Node parent, Node rightChild) {
  if (null != grandParent) {
    grandParent.right = rightChild;
  } else {
    root = rightChild;
  }
  parent.right = rightChild.left;
  rightChild.left = parent;
}
import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

@Test
  public void dswBalanceEmptyBST() {
    BST emptyTree = new BST();
    assertEquals(0, emptyTree.height());
    emptyTree.DSW();
    assertEquals(0, emptyTree.height());
  }

  @Test
  public void dswBalanceForwardSlashTree() {
    BST leftChildren = new BST();
    assertEquals(0, leftChildren.height());
    int[] input = {87, 75, 62, 50, 37, 25, 12};
    for (int i : input) {
      leftChildren.add(i);
    }
    assertEquals(input.length, leftChildren.size());
    assertEquals(input.length, leftChildren.height());
    leftChildren.DSW();
    assertEquals(3, leftChildren.height());
    assertEquals(input.length, leftChildren.size());
  }

  @Test
  public void dswBalanceBackslashTree() {
    BST rightChildren = new BST();
    assertEquals(0, rightChildren.height());
    int[] input = {12, 25, 37, 50, 62, 75, 87};
    for (int i : input) {
      rightChildren.add(i);
    }
    assertEquals(input.length, rightChildren.size());
    assertEquals(input.length, rightChildren.height());
    rightChildren.DSW();
    assertEquals(3, rightChildren.height());
    assertEquals(input.length, rightChildren.size());
  }

  @Test
  public void dswBalancePerfectTree() {
    BST perfectBST = new BST();
    assertEquals(0, perfectBST.height());
    int[] input = {50, 25, 75, 12, 40, 62, 87};
    for (int i : input) {
      perfectBST.add(i);
    }
    assertEquals(input.length, perfectBST.size());
    assertEquals(3, perfectBST.height());
    perfectBST.DSW();
    assertEquals(3, perfectBST.height());
    assertEquals(input.length, perfectBST.size());
  }

  @Test
  public void dswBalanceWeirdTree() {
    BST weirdBST = new BST();
    assertEquals(0, weirdBST.height());
    int[] input = {87, 75, 62, 50, 37, 25, 12, 6, 15, 40};
    for (int i : input) {
      weirdBST.add(i);
    }
    assertEquals(input.length, weirdBST.size());
    assertEquals(8, weirdBST.height());
    weirdBST.DSW();
    assertEquals(4, weirdBST.height());
    assertEquals(input.length, weirdBST.size());

  }
}