# DSW Algorithmby 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) {
}
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) {
}
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) {
}
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) {