home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / games / volume2 / advsys / part03 / advavl.c next >
C/C++ Source or Header  |  1987-10-23  |  4KB  |  194 lines
  1.  
  2. /* advavl.c - avl tree manipulation routines */
  3. /*
  4.     Copyright (c) 1986, by David Michael Betz
  5.     All rights reserved
  6. */
  7.  
  8. #include "advavl.h"
  9. #include "advdbs.h"
  10.  
  11. #define TRUE    1
  12. #define FALSE    0
  13. #define NULL    0
  14.  
  15. /* external routines */
  16. extern char *save();
  17. extern char *malloc();
  18.  
  19. /* external variables */
  20. extern char *data;
  21. extern int curwrd;
  22. extern int dptr;
  23.  
  24. /* local variables */
  25. static TREE *curtree;
  26. static char thiskey[WRDSIZE+1];
  27.  
  28. /* tnew - allocate a new avl tree */
  29. TREE *tnew()
  30. {
  31.     TREE *tree;
  32.  
  33.     /* allocate the tree structure */
  34.     if ((tree = (TREE *)malloc(sizeof(TREE))) == NULL)
  35.     return (NULL);
  36.  
  37.     /* initialize the new tree */
  38.     tree->tr_root = NULL;
  39.     tree->tr_cnt = 0;
  40.  
  41.     /* return the new tree */
  42.     return (tree);
  43. }
  44.  
  45. /* tenter - add an entry to an avl tree */
  46. int tenter(tree,key)
  47.   TREE *tree; char *key;
  48. {
  49.     int h;
  50.     curtree = tree;
  51.     strncpy(thiskey,key,WRDSIZE); thiskey[WRDSIZE] = 0;
  52.     return (tenter1(&tree->tr_root,&h));
  53. }
  54.  
  55. /* tenter1 - internal insertion routine */
  56. int tenter1(pnode,ph)
  57.   TNODE **pnode; int *ph;
  58. {
  59.     TNODE *p,*q,*r;
  60.     int val,c;
  61.  
  62.     /* check for the subtree being empty */
  63.     if ((p = *pnode) == NULL) {
  64.     if (p = (TNODE *)malloc(sizeof(TNODE))) {
  65.         curtree->tr_cnt++;
  66.         KEY(p) = save(thiskey);
  67.         WORD(p) = curwrd;
  68.         LLINK(p) = RLINK(p) = NULL;
  69.         B(p) = 0;
  70.         *pnode = p;
  71.         *ph = TRUE;
  72.         return (WORD(p));
  73.     }
  74.     else {
  75.         *ph = FALSE;
  76.         return (NIL);
  77.     }
  78.     }
  79.  
  80.     /* otherwise, check for a match at this node */
  81.     else if ((c = strcmp(thiskey,KEY(p))) == 0) {
  82.     *ph = FALSE;
  83.     return (WORD(p));
  84.     }
  85.  
  86.     /* otherwise, check the left subtree */
  87.     else if (c < 0) {
  88.     val = tenter1(&LLINK(p),ph);
  89.     if (*ph)
  90.         switch (B(p)) {
  91.         case 1:
  92.         B(p) = 0;
  93.         *ph = FALSE;
  94.         break;
  95.         case 0:
  96.         B(p) = -1;
  97.         break;
  98.         case -1:
  99.         q = LLINK(p);
  100.         if (B(q) == -1) {
  101.             LLINK(p) = RLINK(q);
  102.             RLINK(q) = p;
  103.             B(p) = 0;
  104.             p = q;
  105.         }
  106.         else {
  107.             r = RLINK(q);
  108.             RLINK(q) = LLINK(r);
  109.             LLINK(r) = q;
  110.             LLINK(p) = RLINK(r);
  111.             RLINK(r) = p;
  112.             B(p) = (B(r) == -1 ?  1 : 0);
  113.             B(q) = (B(r) ==  1 ? -1 : 0);
  114.             p = r;
  115.         }
  116.         B(p) = 0;
  117.         *pnode = p;
  118.         *ph = FALSE;
  119.         break;
  120.         }
  121.     }
  122.  
  123.     /* otherwise, check the right subtree */
  124.     else {
  125.     val = tenter1(&RLINK(p),ph);
  126.     if (*ph)
  127.         switch (B(p)) {
  128.         case -1:
  129.         B(p) = 0;
  130.         *ph = FALSE;
  131.         break;
  132.         case 0:
  133.         B(p) = 1;
  134.         break;
  135.         case 1:
  136.         q = RLINK(p);
  137.         if (B(q) == 1) {
  138.             RLINK(p) = LLINK(q);
  139.             LLINK(q) = p;
  140.             B(p) = 0;
  141.             p = q;
  142.         }
  143.         else {
  144.             r = LLINK(q);
  145.             LLINK(q) = RLINK(r);
  146.             RLINK(r) = q;
  147.             RLINK(p) = LLINK(r);
  148.             LLINK(r) = p;
  149.             B(p) = (B(r) ==  1 ? -1 : 0);
  150.             B(q) = (B(r) == -1 ?  1 : 0);
  151.             p = r;
  152.         }
  153.         B(p) = 0;
  154.         *pnode = p;
  155.         *ph = FALSE;
  156.         break;
  157.         }
  158.     }
  159.  
  160.     /* return the node found or inserted */
  161.     return (val);
  162. }
  163.  
  164. /* tfind - find an entry in an avl tree */
  165. int tfind(tree,key)
  166.   TREE *tree; char *key;
  167. {
  168.     strncpy(thiskey,key,WRDSIZE); thiskey[WRDSIZE] = 0;
  169.     return (tfind1(tree->tr_root));
  170. }
  171.  
  172. /* tfind1 - internal lookup routine */
  173. int tfind1(node)
  174.   TNODE *node;
  175. {
  176.     int c;
  177.  
  178.     /* check for the subtree being empty */
  179.     if (node == NULL)
  180.     return (NIL);
  181.  
  182.     /* otherwise, check for a match at this node */
  183.     else if ((c = strcmp(thiskey,KEY(node))) == 0)
  184.     return (WORD(node));
  185.  
  186.     /* otherwise, check the left subtree */
  187.     else if (c < 0)
  188.     return (tfind1(LLINK(node)));
  189.  
  190.     /* otherwise, check the right subtree */
  191.     else
  192.     return (tfind1(RLINK(node)));
  193. }
  194.