PDF

The paper describe about DSW algorithm, a \(O(N)\) time and \(O(1)\) space transformation of binary search tree to rebalance it.

Day’s algorithm

Given an unbalanced search tree, first convert the tree into a linked list (tree with only right child on each node), then compress the tree in several iteration to convert the linked list into a balanced search tree.

Day’s original paper is on Fortran with no support to recusion and pointers. It uses a threaded binary tree to work around that.

ILB(K) = pointer to left child to node K
IRB(K) = pointer to right child to node K

Threaded binary tree: back-pointers to control the traversal, so as to workaround Fortran’s lack of recursion

  • IRB(k) is positive (array index) to point to the right child
  • IRB(k) is negative to point to the next node to backtrack in traversal

The algorithm. First phase: transform the binary search tree into a linked list (the “backbone”, or “vine”)

/* Create the "degenerated tree"
 * make node has no left child but only right child, and right child is a linked list
 * head will hold the beginning node of the linked list,
 * and size will tell how many nodes in it
 */
void DSW::Strip( BasePtr node, BasePtr &head, int &size )
{
    if ( node == NULL ) return; // empty, nothing shall be done
    BasePtr left = node->left;  // remember left child
    node->left = NULL;          // degenerated tree has all left == NULL
	// recursively degenerate the right branch first
	Strip( node->right, head, size );
	// whatever becomes the head of the right branch will become right child
	// of this node. If this node has no right child, the head will remain
	// to be what's passed in
	node->right = head;
	head = node;                // this node will become the new linked list head
	size++;
	Strip ( left, head, size ); // recursively do the left branch
}

// Usage:
int size = 0;
BasePtr head = NULL;
Strip(bst_root, head, size);

Second phase: Convert degenerated tree into balanced tree, using repeated leftward rotations. Tree has a single “pseudo-root” node, which only has the right child. That child is the root of the actual tree.

%                %
 \                \
  B*               D
 / \              / \
A   D     -->    B   E
   / \          / \ 
  C   E        A   C

/* Perform a number of count of leftward rotation on the tree identified by its root node
 */
void DSW::compression ( BasePtr root, int count )
{
    BasePtr scanner = root;
    for ( int j = 0; j < count; j++ ) {   // leftward rotations on scanner's right child
        BasePtr newleft = scanner->right; // newroot = D
		scanner->right = newleft->right;  // B.right = E
		scanner = scanner->right;         // scanner = E (shift down scanner)
		newleft->right = scanner->left;   // D.right = E.left
		scanner->left = newroot;          // E.left = D
		/* original scanner node and its left child are not changed:
		    A[scanner]      A
		   / \             / \
		      C               E[scanner]
		     / \     ->      / \
		    B   E           C
		       / \         / \
		      D           B   D
		*/
	}
	/* The for-loop above make 2*count nodes down on the right from the root into only
	   count nodes down, with the other count nodes move to left branch of some other
	   nodes
	*/
}

// Loop structure taken directly from Day’s code
void DSW::vine_to_tree ( BasePtr root, int size )
{
	int NBack = size - 1;
	for ( int M = NBack / 2; M > 0; M = NBack / 2) {
		compression ( root, M );
		NBack = NBack - M - 1;
	}
	/* From linked list of N nodes to tree with depth N/2 and each node carrying
	   one left child, then each loop double the depth of each node's left branch
	   and halfed the depth of the right branch
	*/
}

Illustration of each loop in vine_to_tree() with % as the pseudo-root:

%                %                 %
 \                \                 \
  A                B                 D
   \              / \               / \
    B      ->    A   D     ->     B     F
     \              / \          / \   / \
      C            C   F        A   C E   G
       \              / \
        D            E   G
         \
          E
           \
            F
             \
              G

Stout and Warren’s algorithm

Improvement over Day’s algorithm. On the first phase, a rightward rotation is used instead to get rid of recursion structure.

// Tree to Vine algorithm: “pseudo-root” is passed
// comparable with a dummy header for a linked list.
void DSW::tree_to_vine ( BasePtr root, int &size )
{
    BasePtr vineTail, remainder, tempPtr;
    vineTail = root;
    remainder = vineTail->right;
    size = 0;
    while ( remainder != NULL )	{
		if ( remainder->left == NULL ) {
		    // no left subtree, remainder move to right
			vineTail = remainder;
			remainder = remainder->Right;
			size++;
		} else {
		    // elimate left subtree by rightward rotation
		    // one node moved to parent of remainder and remainder move up one node
			tempPtr = remainder->left;
			remainder->left = tempPtr->right;
			tempPtr->right = remainder;
			remainder = tempPtr;
			vineTail->right = tempPtr;
		}
	}
}

On the second phase, not only a balanced tree, but also a complete tree (one with the bottom-most level filled from left to right) can be generated.

int FullSize ( int size )
{
	// Full portion of a complete tree
	int Rtn = 1;
	while ( Rtn <= size )     // One step PAST FULL
		Rtn = Rtn + Rtn + 1;  // next pow(2,k)-1
	return Rtn/2;
}
void DSW::vine_to_tree ( BasePtr root, int size )
{
	int full_count = FullSize (size); // find the expected depth of result tree
	compression(root, size - full_count);
	for ( size = full_count ; size > 1 ; size /= 2 )
	    // instead of compress by half of size, compress by a correct depth
		compression ( root, size / 2 );
}

Reference

The original Stout and Warren (1986) paper: Tree Rebalancing in Optimal Time and Space

Bibliographic data

@article{
   title = "One-Time Binary Search Tree Balancing: The Day/Stout/Warren (DSW) Algorithm",
   author = "Timothy J. Rolfe",
   journal = "SIGCSE Bulletin",
   volume = "34",
   number = "4",
   pages = "85--88",
   month = "December",
   year = "2002",
}