home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / news / nn.tar / nn-6.5.1 / contrib / nnsub / avl.c next >
C/C++ Source or Header  |  1995-04-29  |  4KB  |  184 lines
  1. #include <stdio.h>
  2.  
  3. /*
  4.     Copyright
  5.     Rudi van Houten, Academic Computer Centre Utrecht
  6.              Budapestlaan 6  3584 CD  Utrecht  Netherlands
  7.     Author : Rudi van Houten
  8.  
  9.     Purpose:
  10.     C routines for handling AVL tree 
  11.     use the includefiel avl.h in the programs
  12.  
  13.     The field content is here defined as a character pointer
  14.     but all references to it are made outside these routines
  15.     e.g. the parameter function CNTCMP so the calling program
  16.     is free to use a different definition.
  17.     The routine CNTCMP is called with two parameters of the
  18.     type content, and yields an integer value:
  19.         < 0    if 1st par < 2nd par
  20.         = 0    if 1st par = 2nd par
  21.         > 0    if 1st par > 2nd par
  22.     e.g. the routine strcmp.
  23. --end_doc-
  24. */
  25.  
  26. typedef char * CONTENT;
  27. typedef struct avl_node
  28.             { CONTENT content;
  29.               short  balance;                 /* balance the tree */
  30.               struct avl_node *left, *right;  /* tree pointers */
  31.             } AVL_NODE;
  32.  
  33. typedef AVL_NODE * P_AVL_NODE;
  34.  
  35. P_AVL_NODE rotate1(p)
  36. P_AVL_NODE *p;
  37. {
  38.     P_AVL_NODE q;
  39.     if ((*p)->balance > 0)
  40.     {
  41.         q= (*p)->right;
  42.         (*p)->right= q->left;
  43.         q->left= *p;
  44.     }
  45.     else /* if ((*p)->balance > 0) */
  46.     {
  47.         q= (*p)->left;
  48.         (*p)->left= q->right;
  49.         q->right= *p;
  50.     } /* if ((*p)->balance > 0) */
  51.     (*p)->balance= 0; q->balance= 0;
  52.     *p= q;
  53.     return(*p);
  54. } /* rotate1 */
  55.  
  56. AVL_NODE * rotate2(p)
  57. P_AVL_NODE *p;
  58. {
  59.     P_AVL_NODE q, l, r;
  60.     if ( (*p)->balance > 0)
  61.     {
  62.         l= *p; r= (*p)->right; q= r->left;
  63.     }
  64.     else /* if ( (*p)->balance >  0) */
  65.     {
  66.         r= *p; l= (*p)->left; q= l->right;
  67.     } /* if ( (*p)->balance > 0 ) */
  68.     l->balance= r->balance= 0;
  69.     if (q->balance < 0)
  70.         r->balance= 1;
  71.     else
  72.     if (q->balance > 0)
  73.         l->balance= -1;
  74.  
  75.     q->balance= 0;
  76.     l->right= q->left;
  77.     r->left= q->right;
  78.     q->left= l; q->right= r; *p= q;
  79.     return(*p);
  80. } /* rotate2 */
  81.  
  82. AVL_NODE * rotate(p)
  83. P_AVL_NODE *p;
  84. {
  85.     if ( (*p)->balance > 0 )
  86.         if ( (*p)->right->balance > 0)
  87.             rotate1(p);
  88.         else
  89.             rotate2(p);
  90.     else
  91.         if ( (*p)->left->balance < 0 )
  92.             rotate1(p);
  93.         else
  94.             rotate2(p);
  95.     return(*p);
  96. } /* rotate */
  97.  
  98. int insert_avl(value,p,CNTCMP,rtnval)
  99. CONTENT value, *rtnval;
  100. P_AVL_NODE *p;
  101. int (*CNTCMP)();
  102. {
  103.     short k;
  104.  
  105.     if (*p == NULL)
  106.     {
  107.         *p= (P_AVL_NODE)malloc(sizeof(AVL_NODE));
  108.         (*p)->content= value;
  109.         (*p)->balance= 0;
  110.         (*p)->left= NULL; (*p)->right= NULL;
  111.         *rtnval= value;
  112.         return(1);
  113.     }
  114.     else /* if (*p == NULL) */
  115.     if (k= (*CNTCMP)(value,(*p)->content))
  116.     {
  117.         if (k < 0)
  118.             k= -insert_avl(value,&((*p)->left),CNTCMP,rtnval);
  119.         else
  120.             k= insert_avl(value,&((*p)->right),CNTCMP,rtnval);
  121.         if (k)
  122.         {
  123.             (*p)->balance += k;
  124.             if (abs((*p)->balance) > 1) rotate(p);
  125.             if ((*p)->balance) return(1);
  126.         }
  127.     }
  128.     else *rtnval= (*p)->content;
  129.     return(0);
  130. } /* insert_avl */
  131.  
  132. int insavlnode(node,p,CNTCMP)
  133. P_AVL_NODE node, *p;
  134. int (*CNTCMP)();
  135. {
  136.     short k;
  137.  
  138.     if (*p == NULL) *p= node;
  139.     else
  140.     if (k= (*CNTCMP)(node->content,(*p)->content))
  141.     {
  142.         if (k < 0)
  143.             k= -insavlnode(node,&((*p)->left),CNTCMP);
  144.         else
  145.             k= insavlnode(node,&((*p)->right),CNTCMP);
  146.         (*p)->balance += k;
  147.         if (abs((*p)->balance) > 1) rotate(p);
  148.  
  149.         if ((*p)->balance)
  150.             return(abs(k));
  151.         else
  152.             return(0);
  153.     }
  154.     else return(0);
  155. } /* insavlnode */
  156.  
  157. P_AVL_NODE find_avlnode(value,tree,CNTCMP)
  158. CONTENT value;
  159. P_AVL_NODE tree;
  160. int (*CNTCMP)(); /* must be the same routine as used by insavlnode */
  161. {
  162.     int k;
  163.     while (1)
  164.     {
  165.         if (tree == NULL) return(NULL);
  166.         if (k= (*CNTCMP)(value,tree->content))
  167.             if (k < 0) tree= tree->left; else tree= tree->right;
  168.         else return(tree);
  169.     }
  170. } /* find_avlnode */
  171.  
  172. int unravel_avl(tree,action,delflag)
  173. P_AVL_NODE *tree;
  174. int (*action)();
  175. int delflag;
  176. {
  177.     if (*tree == NULL) return(0);
  178.     unravel_avl(&(*tree)->left,action,delflag);
  179.     (*action)((*tree)->content);
  180.     unravel_avl(&(*tree)->right,action,delflag);
  181.     if (delflag) { free(*tree); *tree= NULL; }
  182.     return(1);
  183. } /* unravel_avl */
  184.