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
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;


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",
}