home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / avltree / avlins.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-08-09  |  4.6 KB  |  176 lines
  1. #include <stdio.h>
  2. #include "avl.h"
  3.  
  4. /* --------------------------------------------------------------------------
  5.  * Externally accessible routines:
  6.  *
  7.  * HEADER   *insert(rootp, newnode, cmp)   Insert newnode in tree
  8.  * HEADER   *talloc(size)                  Allocate a new tree node
  9.  * void     tfree(p)                       Free a tree node
  10.  *
  11.  * --------------------------------------------------------------------------
  12.  */
  13.  
  14. static   int      (*Cmp)();
  15. static   HEADER   *Newnode;
  16. static   HEADER   *Conflicting;
  17.  
  18. /* ----------------------------------------------------------------------- */
  19.  
  20. HEADER   *talloc(size)
  21. int      size;
  22. {
  23.    HEADER   *malloc();
  24.    HEADER   *p;
  25.  
  26.    if(p = malloc(size + sizeof(HEADER) ) )
  27.       {
  28.       p->left  =  NULL;
  29.       p->right =  NULL;
  30.       p->size  =  size;
  31.       p->bal   =  B;
  32.       p++;
  33.       }
  34.    return p;
  35. }
  36.  
  37. /* ----------------------------------------------------------------------- */
  38.  
  39. void     tfree(p)
  40. HEADER   *p;
  41. {
  42.    free(--p);
  43. }
  44.  
  45. /* ----------------------------------------------------------------------- */
  46.  
  47. static   int   ins(pp)
  48. HEADER   **pp;
  49. {
  50.    HEADER   *p;
  51.    HEADER   *p1,*p2;
  52.    int      relation;   /* relation >  0 <==> p >  Newnode
  53.                          * relation <  0 <==> p <  Newnode
  54.                          * relation == 0 <==> p == Newnode
  55.                         */
  56.  
  57.    static int h = 0;    /* Set by recursive calls to search to
  58.                          * indicate that the tree has grown.
  59.                          * It will magically change its value
  60.                          * everytime ins() is called recursively.
  61.                         */
  62.  
  63.    if( !(p = *pp) )
  64.       {
  65.       p = Newnode;      /* insert node in tree  */
  66.       h = 1;
  67.       }
  68.    else if( (relation=(* Cmp) (p+1, Newnode+1)) == 0)
  69.       {
  70.       Conflicting = p + 1;
  71.       }
  72.    else if( relation > 0)
  73.       {
  74.       ins(&p->left);
  75.  
  76.       if(h)             /* left branch has grown */
  77.          {
  78.          switch(p->bal)
  79.             {
  80.             case  R:
  81.                p->bal = B;
  82.                h = 0;
  83.                break;
  84.             case  B:
  85.                p->bal = L;
  86.                break;
  87.             case  L:                /* Rebalance */
  88.                p1 = p->left;
  89.                if(p1->bal == L)     /* Single LL */
  90.                   {
  91.                   p->left     = p1->right;
  92.                   p1->right   = p;
  93.                   p->bal      = B;
  94.                   p           = p1;
  95.                   }
  96.                else                 /* Double LR */
  97.                   {
  98.                   p2          = p1->right;
  99.                   p1->right   = p2->left;
  100.                   p2->left    = p1;
  101.                   p->left     = p2->right;
  102.                   p2->right   = p;
  103.                   p->bal      = (p2->bal == L) ? R : B;
  104.                   p1->bal     = (p2->bal == R) ? L : B;
  105.                   p           = p2;
  106.                   }
  107.                p->bal = B;
  108.                h = 0;
  109.             }
  110.          }
  111.       }
  112.    else
  113.       {
  114.       ins(&p->right);
  115.  
  116.       if(h)             /* right branch has grown */
  117.          {
  118.          switch(p->bal)
  119.             {
  120.             case  L:
  121.                p->bal = B;
  122.                h = 0;
  123.                break;
  124.             case  B:
  125.                p->bal = R;
  126.                break;
  127.             case  R:
  128.                p1 = p->right;
  129.                if(p1->bal == R)
  130.                   {
  131.                   p->right = p1->left;
  132.                   p1->left = p;
  133.                   p->bal   = B;
  134.                   p        = p1;
  135.                   }
  136.                else
  137.                   {
  138.                   p2       = p1->left;
  139.                   p1->left = p2->right;
  140.                   p2->right = p1;
  141.                   p->right = p2->left;
  142.                   p2->left = p;
  143.                   p->bal   = (p2->bal == R) ? L : B;
  144.                   p1->bal  = (p2->bal == L) ? R : B;
  145.                   p        = p2;
  146.                   }
  147.                p->bal   = B;
  148.                h        = 0;
  149.             }
  150.          }
  151.       }
  152.    *pp = p;
  153. }
  154.  
  155. /* ----------------------------------------------------------------------- */
  156.  
  157. HEADER   *insert(rootp, newnode, cmp)
  158. HEADER   **rootp;
  159. HEADER   *newnode;
  160. int      (*cmp)();
  161. {
  162.    /* Insert newnode into tree pointed to by *rootp. Cmp is passed
  163.     * two pointers to HEADER and should work like strcmp().
  164.     * Return NULL on success or a pointer to the conflicting node
  165.     * on error.
  166.    */
  167.  
  168.    Cmp         = cmp;
  169.    Newnode     = newnode - 1;
  170.    Conflicting = NULL;
  171.  
  172.    ins(rootp);
  173.  
  174.    return Conflicting;
  175. }
  176.