home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_09_06 / 9n06071a < prev    next >
Text File  |  1990-11-12  |  9KB  |  275 lines
  1.  
  2. /* Functions for optimizing a binary tree.  A tree is optimized with a simple
  3.    call to function "optimize(root)".
  4. */
  5.  
  6. #include <stdio.h>      /* Included only for compiler definition of NULL */
  7.  
  8. /* Flag values */
  9. #define LEFT    1       /* Depth count/fold/"special" to the left */
  10. #define RIGHT   0       /* Depth count/fold/"special" to the right */
  11.  
  12. /* Tree struct */
  13. typedef struct tnode {          /* Standard binary tree node for storage */
  14.   struct tnode *left, *right;
  15.   /* Data would go here, but not needed. */
  16. } TREENODE;
  17.  
  18. static
  19. TREENODE *worstroot,            /* Pointer to worst-case root */
  20.          *temp_root;            /* Traversal pointer */
  21.  
  22.  
  23. /* Function prototypes */
  24. void *optimize(void *);                 /* Optimize a tree                  */
  25.  
  26. static
  27. TREENODE *fixbranch(TREENODE *, int),   /* "Fix" a branch                   */
  28.          *fold(TREENODE *, int),        /* "Fold" a branch                  */
  29.          *special(TREENODE *, int);     /* Perform "special" optimization   */
  30.  
  31. static
  32. int depth(TREENODE *, int);             /* Determine depth of a branch      */
  33.  
  34. static
  35. void worstcase(TREENODE *);             /* Rebuild tree into worst-case     */
  36.  
  37. /* Function to initiate the process of optimizing the tree.  Optimization is
  38.    performed by rearranging a binary tree into its worst-case form and then
  39.    folding this new tree and any subtrees in half at any branch of a linear
  40.    length of 3 or more nodes.
  41.    Usage:   void *optimize(opt_root)
  42.               void *opt_root;           /* Root of a binary tree
  43.    Returns: A pointer to the optimized tree.
  44. */
  45. void *optimize(opt_root)
  46.   void *opt_root;
  47. {
  48.   int rdepth, ldepth;           /* Depth of left & right subtrees */
  49.   TREENODE *root;               /* Pointer to working root of tree */
  50.  
  51.   if (opt_root == NULL)
  52.     return(NULL);
  53.  
  54.   worstroot = temp_root = NULL;
  55.   /* Build worst-case tree.  Root is in "worstroot" */
  56.   worstcase(opt_root);
  57.   root = worstroot;
  58.  
  59.   /* Fold worst-case tree in half if three or more nodes */
  60.   if (depth(root, RIGHT) > 1)
  61.     root = fold(root, RIGHT);
  62.  
  63.   /* Fold left and right subtrees if three or more nodes */
  64.   rdepth = depth(root, RIGHT);
  65.   ldepth = depth(root, LEFT);
  66.   if ((rdepth == 2) && (ldepth == 2))
  67.     root = special(root, RIGHT);
  68.   else
  69.     if ((rdepth > 2) || (ldepth > 2)) {
  70.       root = fixbranch(root, RIGHT);
  71.       root = fixbranch(root, LEFT);
  72.     }
  73.   return((void *) root);
  74. }
  75.  
  76.  
  77. /* Function to determine the right or left depth of a local root NOT INCLUDING
  78.    the local root itself.
  79.    Usage:  int depth(node, dir)
  80.              TREENODE *node;    /* Pointer to a local root
  81.              int dir;           /* Direction (LEFT or RIGHT)
  82.    Returns:  The depth of the local root.
  83. */
  84. int depth(node, dir)
  85.   TREENODE *node;
  86.   int dir;
  87. {
  88.   int d = 0;    /* Depth count */
  89.   switch(dir) {
  90.     case RIGHT:
  91.       while (node->right != NULL) {
  92.         d++;
  93.         node = node->right;
  94.       }
  95.       break;
  96.     case LEFT:
  97.       while (node->left != NULL) {
  98.         d++;
  99.         node = node->left;
  100.       }
  101.       break;
  102.     default:
  103.       return(0);
  104.   }
  105.   return(d);
  106. }
  107.  
  108.  
  109. /* Function to handle a special optimization case at a local root.
  110.  
  111.          3                           4             2
  112.         / \                         / \           / \
  113.        2   4      changed to       2   5   or    1   4
  114.       /     \                     / \               / \
  115.      1       5                   1   3             3   5
  116.                                  Case 1          Case 2
  117.    This allows the section of the tree to remain in optimal form in the event
  118.    a number is added that is greater than 5 in the first case, or less than 1
  119.    in the second case.
  120.    Usage:  TREENODE *special(node, dir)
  121.              TREENODE *node;    /* Pointer to a local root
  122.              int dir;           /* Direction to hang the majority of nodes
  123.    Returns:  A pointer to the updated local root
  124. */
  125. TREENODE *special(node, dir)
  126.   TREENODE *node;
  127.   int dir;
  128. {
  129.   TREENODE *temp,       /* Temporary pointer */
  130.            *newnode;    /* Pointer to "specially" optimized subtree */
  131.   switch(dir) {
  132.     case RIGHT:
  133.       node->left->right = node;
  134.       temp = node->left;
  135.       newnode = node->right;
  136.       node->left = NULL;
  137.       node->right = NULL;
  138.       newnode->left = temp;
  139.       break;
  140.     case LEFT:
  141.       node->right->left = node;
  142.       temp = node->right;
  143.       newnode = node->left;
  144.       node->right = NULL;
  145.       node->left = NULL;
  146.       newnode->right = temp;
  147.       break;
  148.     default:
  149.       newnode = node;
  150.       break;
  151.   }
  152.   return(newnode);
  153. }
  154.  
  155.  
  156. /* Recursive function to initiate the folding of a worst-case local root
  157.    into its most optimal form.
  158.    Usage:  TREENODE *fixbranch(node, dir)
  159.              TREENODE *node;    /* Pointer to a local root
  160.              int dir;           /* Direction to fix (LEFT or RIGHT)
  161.    Returns:  A pointer to an updated local root
  162. */
  163. TREENODE *fixbranch(node, dir)
  164.   TREENODE *node;
  165.   int dir;
  166. {
  167.   switch(dir) {
  168.  
  169.     case RIGHT:
  170.       /* Check for special case */
  171.       if ((depth(node, RIGHT) == 2) && (depth(node, LEFT) == 2))
  172.         node = special(node, dir);
  173.       else
  174.         /* Fold right subtree */
  175.         node->right = fold(node->right, RIGHT);
  176.         /* Fold new right subtree if three or more nodes including the root */
  177.         if (depth(node->right, RIGHT) > 1)
  178.           node->right = fixbranch(node->right, RIGHT);
  179.         /* Fold new left subtree if four or more nodes including the root */
  180.         if (depth(node->right, LEFT) > 2)
  181.           node->right = fixbranch(node->right, LEFT);
  182.       break;
  183.  
  184.     case LEFT:
  185.       /* Check for special case */
  186.       if ((depth(node, LEFT) == 2) && (depth(node, RIGHT) == 2))
  187.         node = special(node, dir);
  188.       else
  189.         /* Fold left subtree */
  190.         node->left = fold(node->left, LEFT);
  191.         /* Fold new left subtree if three or more nodes including the root */
  192.         if (depth(node->left, LEFT) > 1)
  193.           node->left = fixbranch(node->left, LEFT);
  194.         /* fold new right subtree if four or more nodes including the root */
  195.         if (depth(node->left, RIGHT) > 2)
  196.           node->left = fixbranch(node->left, RIGHT);
  197.       break;
  198.   }
  199.   return(node);
  200. }
  201.  
  202.  
  203. /* Function to fold a branch of a local root in the direction given.
  204.    Usage:  TREENODE *fold(node, dir)
  205.              TREENODE *node;    /* Pointer to a local root
  206.              int dir;           /* Direction to fold
  207.    Returns:  A pointer to an updated local root
  208. */
  209. TREENODE *fold(node, dir)
  210.   TREENODE *node;
  211.   int dir;
  212. {
  213.   TREENODE *newroot,    /* Pointer to folded branch */
  214.            *temproot;   /* Temporary pointer */
  215.   int ndepth,           /* Node depth */
  216.       loop;             /* Looping variable */
  217.   switch(dir) {
  218.     case RIGHT:
  219.       ndepth = depth(node, RIGHT);
  220.       if (ndepth % 2)
  221.         ndepth++;   /* Leave any overhang to the left */
  222.       ndepth >>= 1;
  223.       /* Current parent node becomes left child for all nodes from the first
  224.          node in the branch to the middle node */
  225.       for (loop = 0; loop < ndepth; loop++) {
  226.         node->right->left = node;
  227.         temproot = node->right;
  228.         node->right = NULL;
  229.         node = temproot;
  230.       }
  231.       break;
  232.  
  233.     case LEFT:
  234.       ndepth = depth(node, LEFT);
  235.       if (ndepth % 2)
  236.         ndepth++;   /* Leave any overhang to the left */
  237.       ndepth >>= 1;
  238.       /* Current parent node becomes right child for all nodes from the first
  239.          node in the branch to the middle node */
  240.       for (loop = 0; loop < ndepth; loop++) {
  241.         node->left->right = node;
  242.         temproot = node->left;
  243.         node->left = NULL;
  244.         node = temproot;
  245.       }
  246.       break;
  247.     default:
  248.       return(NULL);
  249.       break;
  250.   }
  251.   return(node);
  252. }
  253.  
  254.  
  255. /* Recursive fuction to rebuild a tree into its worst-case form.  The root of
  256.    the worst-case tree is stored in the global variable "worstroot".
  257.    Usage:  void worstcase(root)
  258.              TREENODE *root;    /* Pointer to root of a tree
  259.    Returns:  Nothing
  260. */
  261. void worstcase(root)
  262.   TREENODE *root;
  263. {
  264.   if (root != NULL) {
  265.     worstcase(root->left);
  266.     if (worstroot == NULL)
  267.       temp_root = worstroot = root;
  268.     else
  269.       temp_root->right = root;
  270.     root->left = NULL;
  271.     temp_root = root;
  272.     worstcase(root->right);
  273.   }
  274. }
  275.