util/grind/avl.cc

   1 /* $Id: avl.cc,v 1.3 1994/06/24 10:59:08 ceriel Exp $ */
   2
   3 #include <alloc.h>
   4
   5 /* Implementation of AVL-trees: trees in which the difference in depth
   6    of the left branch and the right branch is at most one.
   7    The difference in depth is indicated by a "balance" flag in each node:
   8    this flag has one of three values:
   9    .    indicating that the left branch has the same depth as the right branch,
  10    +    indicating that the right branch is deeper,
  11    -    indicating that the left branch is deeper.
  12    So, a node has the following structure:
  13 */
  14
  15 struct avl_node {
  16   struct avl_node
  17                 *left,
  18                 *right;         /* the left and right branches */
  19   char          *info;          /* pointer to information in this node */
  20   char          balance;        /* balance information described above */
  21 };
  22
  23 /* create definitions for new_avl_node() and free_avl_node() */
  24 /* STATICALLOCDEF "avl_node" 10 */
  25
  26 /* There is also a tree header, which contains the root of the tree and
  27    the address of a user-supplied comparison routine:
  28 */
  29
  30 struct avl_tree {
  31   struct avl_node
  32                 *root;          /* root of the avl tree */
  33   int           (*cmp)();       /* address of comparison routine */
  34 };
  35 /* create definitions for new_avl_tree() and free_avl_tree() */
  36 /* STATICALLOCDEF "avl_tree" 2 */
  37
  38 /* The next routine adds a node to an avl tree. It returns 1 if the
  39    tree got deeper.
  40 */
  41 static int
  42 balance_add(ppsc, n, cmp)
  43   struct avl_node **ppsc;       /* address of root */
  44   register char *n;             /* user-supplied information */
  45   int (*cmp)();                 /* user-supplied comparison routine */
  46 {
  47   register struct avl_node *psc = *ppsc, *qsc, *ssc;
  48
  49   if (! psc) {
  50         *ppsc = new_avl_node();
  51         (*ppsc)->balance = '.';
  52         (*ppsc)->info = n;
  53         return 1;
  54   }
  55   if ((*cmp)(n, psc->info) < 0) {
  56         if (balance_add(&(psc->left), n, cmp)) {
  57                 /* left hand side got deeper */
  58                 if (psc->balance == '+') {
  59                         /* but the right hand side was deeper */
  60                         psc->balance = '.';
  61                         return 0;
  62                 }
  63                 if (psc->balance == '.') {
  64                         /* but the right hand side was as deep */
  65                         psc->balance = '-';
  66                         return 1;
  67                 }
  68                 /* left hand side already was one deeper; re-organize */
  69                 qsc = psc->left;
  70                 if (qsc->balance == '-') {
  71                         /* if left-hand side of left node was deeper,
  72                            this node becomes the new root
  73                         */
  74                         psc->balance = '.';
  75                         qsc->balance = '.';
  76                         psc->left = qsc->right;
  77                         qsc->right = psc;
  78                         *ppsc = qsc;
  79                         return 0;
  80                 }
  81                 /* else the right node of the left node becomes the new root */
  82                 ssc = qsc->right;
  83                 psc->left = ssc->right;
  84                 qsc->right = ssc->left;
  85                 ssc->left = qsc;
  86                 ssc->right = psc;
  87                 *ppsc = ssc;
  88                 if (ssc->balance == '.') {
  89                         psc->balance = '.';
  90                         qsc->balance = '.';
  91                         return 0;
  92                 }
  93                 if (ssc->balance == '-') {
  94                         psc->balance = '+';
  95                         qsc->balance = '.';
  96                         ssc->balance = '.';
  97                         return 0;
  98                 }
  99                 psc->balance = '.';
 100                 qsc->balance = '-';
 101         }
 102         return 0;
 103   }
 104   if (balance_add(&(psc->right), n, cmp)) {
 105         /* right hand side got deeper */
 106         if (psc->balance == '-') {
 107                 /* but the left hand side was deeper */
 108                 psc->balance = '.';
 109                 return 0;
 110         }
 111         if (psc->balance == '.') {
 112                 /* but the left hand side as deep */
 113                 psc->balance = '+';
 114                 return 1;
 115         }
 116         /* right hand side already was one deeper; re-organize */
 117         qsc = psc->right;
 118         if (qsc->balance == '+') {
 119                 /* if right-hand side of left node was deeper,
 120                    this node becomes the new root
 121                 */
 122                 psc->balance = '.';
 123                 qsc->balance = '.';
 124                 psc->right = qsc->left;
 125                 qsc->left = psc;
 126                 *ppsc = qsc;
 127                 return 0;
 128         }
 129         /* else the left node of the right node becomes the new root */
 130         ssc = qsc->left;
 131         psc->right = ssc->left;
 132         qsc->left = ssc->right;
 133         ssc->right = qsc;
 134         ssc->left = psc;
 135         *ppsc = ssc;
 136         if (ssc->balance == '.') {
 137                 psc->balance = '.';
 138                 qsc->balance = '.';
 139                 return 0;
 140         }
 141         if (ssc->balance == '+') {
 142                 psc->balance = '-';
 143                 qsc->balance = '.';
 144                 ssc->balance = '.';
 145                 return 0;
 146         }
 147         psc->balance = '.';
 148         qsc->balance = '+';
 149   }
 150   return 0;
 151 }
 152
 153 /* extern struct avl_tree *create_avl_tree(int (*cmp)());
 154    Returns a fresh avl_tree structure.
 155 */
 156 struct avl_tree *
 157 create_avl_tree(cmp)
 158   int   (*cmp)();               /* comparison routine */
 159 {
 160   register struct avl_tree *p = new_avl_tree();
 161
 162   p->cmp = cmp;
 163   return p;
 164 }
 165
 166 /* extern add_to_avl_tree(struct avl_tree *tree, char *n);
 167    Adds the information indicated by 'n' to the avl_tree indicated by 'tree'
 168 */
 169 add_to_avl_tree(tree, n)
 170   struct avl_tree       *tree;  /* tree to be added to */
 171   char                  *n;     /* information */
 172 {
 173   (void) balance_add(&(tree->root), n, tree->cmp);
 174 }
 175
 176 /* extern char *find_ngt(struct avl_tree *tree, char *n);
 177    Returns the information in the largest node that still compares <= to 'n',
 178    or 0 if not present.
 179 */
 180 char *
 181 find_ngt(tree, n)
 182   struct avl_tree       *tree;  /* tree to be searched in */
 183   char                  *n;     /* information to be compared with */
 184 {
 185   register struct avl_node *nd = tree->root, *lastnd = 0;
 186
 187   for (;;) {
 188         while (nd && (*tree->cmp)(nd->info, n) > 0) {
 189                 nd = nd->left;
 190         }
 191         while (nd && (*tree->cmp)(nd->info, n) <= 0) {
 192                 lastnd = nd;
 193                 nd = nd->right;
 194         }
 195         if (! nd) break;
 196   }
 197   return lastnd ? lastnd->info : (char *) 0;
 198 }
 199
 200 /* extern char *find_nlt(struct avl_tree *tree, char *n);
 201    Returns the information in the largest node that still compares >= to 'n',
 202    or 0 if not present.
 203 */
 204 char *
 205 find_nlt(tree, n)
 206   struct avl_tree       *tree;  /* tree to be searched in */
 207   char                  *n;     /* information to be compared with */
 208 {
 209   register struct avl_node *nd = tree->root, *lastnd = 0;
 210
 211   for (;;) {
 212         while (nd && (*tree->cmp)(nd->info, n) < 0) {
 213                 nd = nd->right;
 214         }
 215         while (nd && (*tree->cmp)(nd->info, n) >= 0) {
 216                 lastnd = nd;
 217                 nd = nd->left;
 218         }
 219         if (! nd) break;
 220   }
 221   return lastnd ? lastnd->info : (char *) 0;
 222 }
 223
 224 /* extern char *find_eq(struct avl_tree *tree, char *n);
 225    Returns the information in the node that compares equal to 'n',
 226    or 0 if not present.
 227 */
 228 char *
 229 find_eq(tree, n)
 230   struct avl_tree       *tree;  /* tree to be searched in */
 231   char                  *n;     /* information to be compared with */
 232 {
 233   register struct avl_node *nd = tree->root;
 234
 235   for (;;) {
 236         while (nd && (*tree->cmp)(nd->info, n) < 0) {
 237                 nd = nd->right;
 238         }
 239         while (nd && (*tree->cmp)(nd->info, n) > 0) {
 240                 nd = nd->left;
 241         }
 242         if (! nd) break;
 243   }
 244   return nd ? nd->info : (char *) 0;
 245 }