home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / avltree / avldel.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-08-09  |  6.2 KB  |  242 lines
  1. #include <stdio.h>
  2. #include "avl.h"
  3.  
  4. /* --------------------------------------------------------------------------
  5.  * Locally static subroutines:
  6.  * --------------------------------------------------------------------------
  7.  */
  8.  
  9.  extern  int   balance_l   ( HEADER** );
  10.  extern  int   balance_r   ( HEADER** );
  11.  extern  int   del         ( HEADER** );
  12.  extern  int   descend     ( HEADER**, HEADER** );
  13.  
  14. /* ----------------------------------------------------------------------- */
  15.  
  16. static   HEADER   *Key;
  17. static   int      (*Cmp)();
  18. static   int      Notfound;
  19.  
  20. /* ----------------------------------------------------------------------- */
  21.  
  22. static   int   balance_l( pp )
  23. HEADER   **pp;
  24. {
  25.    /* This routine is called when the left branch of the current
  26.     * subtree (pointed to by p) has shrunk.  It adjusts the balance
  27.     * factors and rebalances if necessary, modifying *pp to point
  28.     * at the new root ( after rebalance ).  Returns 1 if the
  29.     * tree got smaller as a result of the delete or the rebalance
  30.     * operation, else returns 0.
  31.    */
  32.  
  33.    register HEADER   *p, *p1, *p2;
  34.    int               b1, b2;
  35.    int               got_smaller = 1;
  36.  
  37.    p = *pp;
  38.  
  39.    switch(p->bal)
  40.       {
  41.       case  L:
  42.          p->bal = B;
  43.          break;
  44.       case  B:
  45.          p->bal = R;
  46.          got_smaller = 0;
  47.          break;
  48.       case  R:
  49.          p1 = p->right;
  50.          b1 = p1->bal;
  51.          if(b1 >= B)                /* Single RR */
  52.             {
  53.             p->right = p1->left;
  54.             p1->left = p;
  55.  
  56.             if(b1 != B)
  57.                p->bal = p1->bal = B;
  58.             else
  59.                {
  60.                p->bal = R;
  61.                p1->bal = L;
  62.                got_smaller = 0;
  63.                }
  64.             p = p1;
  65.             }
  66.          else                       /* Double RL */
  67.             {
  68.             p2       = p1->left;
  69.             b2       = p2->bal;
  70.             p1->left = p2->right;
  71.             p2->right = p1;
  72.             p->right = p2->left;
  73.             p2->left = p;
  74.             p->bal   = (b2 == R) ? L : B;
  75.             p1->bal  = (b2 == L) ? R : B;
  76.             p        = p2;
  77.             p2->bal  = B;
  78.             }
  79.       }
  80.    *pp = p;
  81.    return got_smaller;
  82. }
  83.  
  84. /* ----------------------------------------------------------------------- */
  85.  
  86. static   int   balance_r(pp)
  87. HEADER   **pp;
  88. {
  89.    /* Same as balance_l but is called when a right subtree
  90.     * has been made smaller.
  91.    */
  92.  
  93.    register HEADER   *p, *p1, *p2;
  94.    int               b1, b2;
  95.    int               got_smaller = 1;
  96.  
  97.    p = *pp;
  98.  
  99.    switch(p->bal)
  100.       {
  101.       case  R:
  102.          p->bal = B;
  103.          break;
  104.       case  B:
  105.          p->bal = L;
  106.          got_smaller = 0;
  107.          break;
  108.       case  L:
  109.          p1 = p->left;
  110.          b1 = p1->bal;
  111.          if(b1 <= B)                /* Single RR */
  112.             {
  113.             p->left     = p1->right;
  114.             p1->right   = p;
  115.  
  116.             if(b1 != B)
  117.                p->bal = p1->bal = B;
  118.             else
  119.                {
  120.                p->bal = L;
  121.                p1->bal = R;
  122.                got_smaller = 0;
  123.                }
  124.             p = p1;
  125.             }
  126.          else                       /* Double RL */
  127.             {
  128.             p2       = p1->right;
  129.             b2       = p2->bal;
  130.             p1->right = p2->left;
  131.             p2->left = p1;
  132.             p->left = p2->right;
  133.             p2->right = p;
  134.             p->bal   = (b2 == L) ? L : B;
  135.             p1->bal  = (b2 == R) ? R : B;
  136.             p        = p2;
  137.             p2->bal  = B;
  138.             }
  139.       }
  140.    *pp = p;
  141.    return got_smaller;
  142. }
  143.  
  144. /* ----------------------------------------------------------------------- */
  145.  
  146. static   int   descend(rootp, dpp)
  147. HEADER   **rootp;
  148. HEADER   **dpp;
  149. {
  150.    /* Does the actual delete when the root node has both left and
  151.     * right decendants. Decends to the rightmost node of the left
  152.     * subtree and then copies the contents of that node to the
  153.     * node-to-be-deleted (*dpp). Then the node-to-be-deleted is
  154.     * modified to point at the former rightmost node.
  155.    */
  156.  
  157.    if( (*rootp)->right )
  158.       return(descend( &(*rootp)->right, dpp) )
  159.          ? balance_r(rootp) : 0;
  160.    else
  161.       {
  162.       memcpy( *dpp + 1, *rootp + 1, (*rootp)->size );
  163.       *dpp     = (*rootp);
  164.       *rootp   = (*rootp)->left;
  165.       return 1;
  166.       }
  167. }
  168.  
  169. /* ----------------------------------------------------------------------- */
  170.  
  171. static   int   del(rootp)
  172. HEADER   **rootp;
  173. {
  174.    /* Delete Key from tree pointed to by *rootp.  Return 1 if the size
  175.     * of the tree has been reduced, 0 otherwise;
  176.    */
  177.  
  178.    HEADER         *dp;
  179.    int            got_smaller = 0;
  180.    static   int   relation;
  181.  
  182.    if( !*rootp )
  183.       Notfound = 1;
  184.    else
  185.       {
  186.       relation = (*Cmp)(Key, *rootp + 1);
  187.       if(relation < 0)
  188.          {
  189.          if( del( & (*rootp)->left ) )
  190.             got_smaller = balance_l(rootp);
  191.          }
  192.       else if(relation > 0)
  193.          {
  194.          if( del( & (*rootp)->right ) )
  195.             got_smaller = balance_r(rootp);
  196.          }
  197.       else
  198.          {
  199.          dp = *rootp;
  200.          if(dp->right == NULL)
  201.             {
  202.             *rootp      = dp->left;
  203.             got_smaller = 1;
  204.             }
  205.          else if(dp->left == NULL)
  206.             {
  207.             *rootp      = dp->right;
  208.             got_smaller = 1;
  209.             }
  210.          else if(descend( &(*rootp)->left, &dp) )
  211.             {
  212.             got_smaller = balance_l(rootp);
  213.             }
  214.          free(dp);
  215.          }
  216.       }
  217.    return got_smaller;
  218. }
  219.  
  220. /* ----------------------------------------------------------------------- */
  221.  
  222. int   delete(rootp, key, cmp )
  223. HEADER   **rootp;
  224. HEADER   *key;
  225. int      (*cmp)();
  226. {
  227.    /* Cmp is a comparison routine called with (*cmp) (key, node);
  228.     * where "key" is the second argument to delete and "node" is
  229.     * a pointer to one node in the tree.  It should return <0 if
  230.     * key < node, 0 if key == node or >0 if key > node. Returns
  231.     * 1 if the node was deleted, 0 if the node wasn't in the tree.
  232.    */
  233.  
  234.    Cmp      = cmp;
  235.    Key      = key;
  236.    Notfound = 0;
  237.  
  238.    del(rootp);
  239.  
  240.    return !Notfound;
  241. }
  242.