/***************************************************************************
* 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());
}
}