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