DSW Algorithm
by Isai Damier

  #=======================================================================
  # 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!
  #
  #=======================================================================
 
 
class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def DSW( self ):
    if None != self.root:
      self.createBackbone() #  effectively: createBackbone( self.root)
      self.createPerfectBST() # effectively: createPerfectBST( self.root)

  #=====================================================================
  # Time complexity: O(n)
  #=====================================================================
  def createBackbone( self ):
    grandParent = None
    parent = self.root
    leftChild = None

    while None != parent:
      leftChild = parent.left
      if None != leftChild:
        grandParent = self.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
  #=======================================================================
  def rotateRight( self, grandParent, parent, leftChild ):
    if None != grandParent:
      grandParent.right = leftChild
    else:
      self.root = leftChild

    parent.left = leftChild.right
    leftChild.right = parent
    return grandParent

  #=======================================================================
  # Time complexity: O(n)
  #=======================================================================
  def createPerfectBST( self ):
    n = self.size()

    # m = 2^floor[lg(n+1)]-1, ie the greatest power of 2 less than n: minus 1
    m = self.greatestPowerOf2LessThanN( n + 1 ) - 1
    self.makeRotations( n - m )

    while m > 1:
      m /= 2
      self.makeRotations( m )


  #=======================================================================
  # Time complexity: log(n)
  #=======================================================================
  def greatestPowerOf2LessThanN( self, n ):
    x = self.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
  #=======================================================================
  def MSB( self, n ):
    ndx = 0
    while 1 < n:
      n = ( n >> 1 )
      ndx += 1
    return ndx


  def makeRotations( self, bound ):
    grandParent = None
    parent = self.root
    child = self.root.right
    while bound > 0:
      try:
        if None != child:
          self.rotateLeft( grandParent, parent, child );
          grandParent = child;
          parent = grandParent.right;
          child = parent.right;
        else:
          break
      except AttributeError: # TypeError
        break
      bound -= 1


  def rotateLeft( self, grandParent, parent, rightChild ):
    if None != grandParent:
      grandParent.right = rightChild
    else:
      self.root = rightChild

    parent.right = rightChild.left
    rightChild.left = parent
import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):

  def testDswBalanceEmptyBST( self ):
    emptyTree = BST()

    self.assertEquals( 0, emptyTree.height() )
    emptyTree.DSW()
    self.assertEquals( 0, emptyTree.height() )



  def testDswBalanceForwardSlashTree( self ):
    leftChildren = BST()

    self.assertEquals( 0, leftChildren.height() )
    tape = [87, 75, 62, 50, 37, 25, 12]
    for i in tape:
      leftChildren.add( i )

    self.assertEquals( len( tape ), leftChildren.size() )
    self.assertEquals( len( tape ), leftChildren.height() )
    leftChildren.DSW()
    self.assertEquals( 3, leftChildren.height() )
    self.assertEquals( len( tape ), leftChildren.size() )


  def testDswBalanceBackslashTree( self ):
    rightChildren = BST()

    self.assertEquals( 0, rightChildren.height() )
    tape = [12, 25, 37, 50, 62, 75, 87]
    for i in tape:
      rightChildren.add( i )

    self.assertEquals( len( tape ), rightChildren.size() )
    self.assertEquals( len( tape ), rightChildren.height() )
    rightChildren.DSW()
    self.assertEquals( 3, rightChildren.height() )
    self.assertEquals( len( tape ), rightChildren.size() )



  def testDswBalancePerfectTree( self ):
    perfectBST = BST()

    self.assertEquals( 0, perfectBST.height() )
    tape = [50, 25, 75, 12, 40, 62, 87]
    for i in tape:
      perfectBST.add( i )

    self.assertEquals( len( tape ), perfectBST.size() )
    self.assertEquals( 3, perfectBST.height() )
    perfectBST.DSW()
    self.assertEquals( 3, perfectBST.height() )
    self.assertEquals( len( tape ), perfectBST.size() )

  def testDswBalanceWeirdTree( self ):
    weirdBST = BST()

    self.assertEquals( 0, weirdBST.height() )
    tape = [87, 75, 62, 50, 37, 25, 12, 6, 15, 40]
    for i in tape:
      weirdBST.add( i )

    self.assertEquals( len( tape ), weirdBST.size() )
    self.assertEquals( 8, weirdBST.height() )
    weirdBST.DSW()
    self.assertEquals( 4, weirdBST.height() )
    self.assertEquals( len( tape ), weirdBST.size() )