/* Functions for optimizing a binary tree. A tree is optimized with a simple
call to function "optimize(root)".
*/
#include <stdio.h> /* Included only for compiler definition of NULL */
/* Flag values */
#define LEFT 1 /* Depth count/fold/"special" to the left */
#define RIGHT 0 /* Depth count/fold/"special" to the right */
/* Tree struct */
typedef struct tnode { /* Standard binary tree node for storage */
struct tnode *left, *right;
/* Data would go here, but not needed. */
} TREENODE;
static
TREENODE *worstroot, /* Pointer to worst-case root */
*temp_root; /* Traversal pointer */
/* Function prototypes */
void *optimize(void *); /* Optimize a tree */
static
TREENODE *fixbranch(TREENODE *, int), /* "Fix" a branch */
*fold(TREENODE *, int), /* "Fold" a branch */
*special(TREENODE *, int); /* Perform "special" optimization */
static
int depth(TREENOOE *, int); /* Determine depth of a branch */
static
void worstcase(TREENOOE *); /* Rebuild tree into worst-case */
/* Function to initiate the process of optimizing the tree. Optimization is
performed by rearranging a binary tree into its worst-case form and then
folding this new tree and any subtrees in half at any branch of a linear
length of 3 or more nodes.
Usage: void *optimize(opt_root)
void *opt_root; /* Root of a binary tree
Returns: A pointer to the optimized tree.
*/
void *optimize(opt_root)
void *opt_root;
{
int rdepth, ldepth; /* Depth of left & right subtrees */
TREENODE *root; /* Pointer to working root of tree */
if (opt_root == NULL)
return(NULL);
worstroot = temp_root = NULL;
/* Build worst-case tree. Root is in "worstroot" */
worstcase(opt_root);
root = worst_root;
/* Fold worst-case tree in half if three or more nodes */
if (depth(root, RIGHT) > 1)
root = fold(root, RIGHT);
/* Fold left and right subtrees if three or more nodes */
rdepth = depth(root, RIGHT);
ldepth = depth(root, LEFT);
if ((rdepth == 2) && (ldepth == 2))
root = special(root, RIGHT);
else
if ((rdepth > 2) || (ldepth > 2)) {
root = fixbranch(root, RIGHT);
root = fixbranch(root, LEFT);
}
return((void *) root);
}
/* Function to determine the right or left depth of a local root NOT INCLUDING
the local root itself.
Usage: int depth(node, dir)
TREENODE *node; /* Pointer to a local root
int dir; /* Direction (LEFT or RIGHT)
Returns: The depth of the local root.
*/
int depth(node, dir)
TREENODE *node;
int dir;
{
int d = 0; /* Depth count */
switch(dir) {
case RIGHT:
while (node->right != NULL) {
d++;
node = node->right;
}
break;
case LEFT:
while (node->left != NULL) {
d++;
node = node->left;
}
break;
default:
return(0);
}
return(d);
}
/* Function to handle a special optimization case at a local root.
3 4 2
/ \ / \ / \
2 4 changed to 2 5 or 1 4
/ \ / \ / \
1 5 1 3 3 5
Case 1 Case 2
This allows the section of the tree to remain in optimal form in the event
a number is added that is greater than 5 in the first case, or less than 1
in the second case.
Usage: TREENODE *special(node, dir)
TREENODE *node; /* Pointer to a local root
int dir; /* Direction to hang the majority of nodes
Returns: A pointer to the updated local root
*/
TREENODE *special(node, dir)
TREENODE *node;
int dir;
{
TREENODE *temp, /* Temporary pointer */
*newnode; /* Pointer to "specially" optimized subtree */
switch(dir) {
case RIGHT:
node->left->right = node;
temp = node->left;
newnode = node->right;
node->left = NULL;
node->right = NULL;
newnode->left = temp;
break;
case LEFT:
node->right->left = node;
temp = node->right;
newnode = node->left;
node->right = NULL;
node->left = NULL;
newnode->right = temp;
break;
default:
newnode = node;
break;
}
return(newnode);
}
/* Recursive function to initiate the folding of a worst-case local root
into its most optimal form.
Usage: TREENODE *fixbranch(node, dir)
TREENODE *node; /* Pointer to a local root
int dir; /* Direction to fix (LEFT or RIGHT)
Returns: A pointer to an updated local root
*/
TREENODE *fixbranch(node, dir)
TREENODE *node;
int dir;
{
switch(dir) {
case RIGHT:
/* Check for special case */
if ((depth(node, RIGHT) == 2) && (depth(node, LEFT) == 2))
node = special(node, dir);
else
/* Fold right subtree */
node->right = fold(node->right, RIGHT);
/* Fold new right subtree if three or more nodes including the root */
if (depth(node->right, RIGHT) > 1)
node->right = fixbranch(node->right, RIGHT);
/* Fold new left subtree if four or more nodes including the root */
if (depth(node->right, LEFT) > 2)
node->right = fixbranch(node->right, LEFT);
break;
case LEFT:
/* Check for special case */
if ((depth(node, LEFT) == 2) && (depth(node, RIGHT) == 2))
node = special(node, dir);
else
/* Fold left subtree */
node->left = fold(node->left, LEFT);
/* Fold new left subtree if three or more nodes including the root */
if (depth(node->left, LEFT) > 1)
node->left = fixbranch(node->left, LEFT);
/* fold new right subtree if four or more nodes including the root */
if (depth(node->left, RIGHT) > 2)
node->left = fixbranch(node->left, RIGHT);
break;
}
return(node);
}
/* Function to fold a branch of a local root in the direction given.
Usage: TREENODE *fold(node, dir)
TREENODE *node; /* Pointer to a local root
int dir; /* Direction to fold
Returns: A pointer to an updated local root
*/
TREENODE *fold(node, dir)
TREENODE *node;
int dir;
{
TREENODE *newroot, /* Pointer to folded branch */
*temproot; /* Temporary pointer */
int ndepth, /* Node depth */
loop; /* Looping variable */
switch(dir) {
case RIGHT:
ndepth = depth(node, RIGHT);
if (ndepth % 2)
ndepth++; /* Leave any overhang to the left */
ndepth >>= 1;
/* Current parent node becomes left child for all nodes from the first
node in the branch to the middle node */
for (loop = 0; loop < ndepth; loop++) {
node->right->left = node;
temproot = node->right;
node->right = NULL;
node = temproot;
}
break;
case LEFT:
ndepth = depth(node, LEFT);
if (ndepth % 2)
ndepth++; /* Leave any overhang to the left */
ndepth >>= 1;
/* Current parent node becomes right child for all nodes from the first
node in the branch to the middle node */
for (loop = 0; loop < ndepth; loop++) {
node->left->right = node;
temproot = node->left;
node->left = NULL;
node = temproot;
}
break;
default:
return(NULL);
break;
}
return(node);
}
/* Recursive fuction to rebuild a tree into its worst-case form. The root of
the worst-case tree is stored in the global variable "worstroot".
Usage: void worstcase(root)
TREENODE *root; /* Pointer to root of a tree
Returns: Nothing
*/
void worstcase(root)
TREENODE *root;
{
if (root != NULL) {
worstcase(root->left);
if (worstroot == NULL)
temp_root = worstroot = root;
else
temp_root->right = root;
root->left = NULL;
temp_root = root;
worstcase(root->right);
}
}