home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 3 / 3148 / avl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-29  |  23.9 KB  |  786 lines
  1. /**
  2. *
  3. * avl.c -- C source file for avl trees. Contains the auxillary routines
  4. *          and defines for the avl tree functions and user interface and
  5. *          includes all the necessary public and private routines
  6. *
  7. * Created 03/01/89 by Brad Appleton
  8. *
  9. * ^{Mods:* }
  10. * 
  11. * Fri Jul 14 13:53:42 1989, Rev 1.0, brad(0165)
  12. *
  13. **/
  14.  
  15.     /* some common #defines used throughout most of my files */
  16. #define  PUBLIC   /* default */
  17. #define  PRIVATE  static
  18. #define  FALSE    0
  19. #define  TRUE     !FALSE
  20.   
  21.     /* some defines for debugging purposes */
  22. #ifdef NDEBUG
  23. #define DBG(x)        /* x */
  24. #else
  25. #define DBG(x)        x
  26. #endif
  27.  
  28. #define  NEXTERN   /* dont include "extern" declarations from header files */
  29.  
  30. #include  <stdio.h>
  31. #include  "avl.h"         /* public types for avl trees */
  32. #include  "avl_typs.h"    /* private types for avl trees */
  33.  
  34.  
  35.  
  36. /************************************************************************
  37. *    Auxillary functions
  38. *
  39. *    routines to allocate/de-allocate an AVL node,
  40. *       and determine the type of an AVL node.
  41. ************************************************************************/
  42.  
  43. /* ckalloc( size ) -- allocate space; check for success */
  44. PRIVATE     char *ckalloc( size )
  45. int size;
  46. {
  47.     char *malloc(), *ptr;
  48.   
  49.     if ( (ptr = malloc(  (unsigned) size)) == NULL )  {
  50.         fprintf( stderr, "Unable to allocate storage." );
  51.         exit( 1 );
  52.     }/* if */
  53.   
  54.     return  ptr;
  55. }/* ckalloc */
  56.  
  57.  
  58. /*
  59. * new_node() -- get space for a new node and its data;
  60. *               return the address of the new node
  61. */
  62. PRIVATE   AVLtree  new_node( data, size )
  63. void     *data;
  64. unsigned  size;
  65. {
  66.     AVLtree  root;
  67.   
  68.     root = (AVLtree) ckalloc( sizeof (AVLnode) );
  69.     root -> data = (void *) ckalloc( size );
  70.     memcpy( root -> data, data, size );
  71.     root -> bal  = BALANCED;
  72.     root -> subtree[ LEFT ]  = root -> subtree[ RIGHT ] = NULL_TREE;
  73.   
  74.     return  root;
  75. }/* new_node */
  76.  
  77.  
  78. /*
  79. * free_node()  --  free space for a node and its data!
  80. *                  reset the node pointer to NULL
  81. */
  82. PRIVATE    void free_node( rootp )
  83. AVLtree     *rootp;
  84. {
  85.     free( (void *) *rootp );
  86.     *rootp = NULL_TREE;
  87. }/* free_node */
  88.   
  89.   
  90. /*
  91. * node_type() -- determine the number of null pointers for a given
  92. *                node in an AVL tree, Returns a value of type NODE
  93. *                which is an enumeration type with the following values:
  94. *
  95. *                  IS_TREE     --  both subtrees are non-empty
  96. *                  IS_LBRANCH  --  left subtree is non-empty; right is empty
  97. *                  IS_RBRANCH  --  right subtree is non-empty; left is empty
  98. *                  IS_LEAF     --  both subtrees are empty
  99. *                  IS_NULL     --  given tree is empty
  100. */
  101. PRIVATE     NODE node_type( tree )
  102. AVLtree    tree;
  103. {
  104.     if ( tree == NULL_TREE )
  105.         return  IS_NULL;
  106.   
  107.     else if ( (tree -> subtree[ LEFT ] != NULL_TREE)  &&  (tree -> subtree[ RIGHT ] != NULL_TREE) )
  108.         return  IS_TREE;
  109.   
  110.     else if ( tree -> subtree[ LEFT ] != NULL_TREE )
  111.         return  IS_LBRANCH;
  112.   
  113.     else if ( tree -> subtree[ RIGHT ] != NULL_TREE )
  114.         return  IS_RBRANCH;
  115.   
  116.     else
  117.     return  IS_LEAF;
  118. }/* node_type */
  119.  
  120.  
  121.  
  122. /************************************************************************
  123. *    PRIVATE functions for manipulating AVL trees
  124. *
  125. *  This following defines a set of routines for creating, maintaining, and
  126. *  manipulating AVL Trees as an Abtract Data Type. The routines in this
  127. *  file that are accessible (through the avl tree user-interface) to other
  128. *  files to allow other programmers to:
  129. *
  130. *       Insert, Delete, and Find a given data item from a Tree.
  131. *
  132. *       Delete and Find the minimal and Maximal items in a Tree.
  133. *
  134. *       Walk through every node in a tree performing a giving operation.
  135. *
  136. *       Walk through and free up space for every node in a tree while performing
  137. *       a given operation on the data items as they are encountered.
  138. ************************************************************************/
  139.  
  140.  
  141.  
  142. /************************************************************************
  143. *    routines used to find the minimal and maximal elements
  144. *       (nodes) of an AVL tree.
  145. ************************************************************************/
  146.   
  147. /*
  148. * avl_min() -- compare function used to find the minimal element in a tree
  149. */
  150. PRIVATE int avl_min( elt1, elt2, nd_typ )
  151. void  *elt1, *elt2;
  152. NODE  nd_typ;
  153. {
  154.     if ( nd_typ == IS_RBRANCH  ||  nd_typ == IS_LEAF )
  155.         return   0;   /* left subtree is empty -- this is the minimum */
  156.     
  157.     else  return  -1;   /* keep going left */
  158. }/* avl_min */
  159.  
  160.  
  161. /*
  162. * avl_max() -- compare function used to find the maximal element in a tree
  163. */
  164. PRIVATE int avl_max( elt1, elt2, nd_typ )
  165. void  *elt1, *elt2;
  166. NODE  nd_typ;
  167. {
  168.     if ( nd_typ == IS_RBRANCH  ||  nd_typ == IS_LEAF )
  169.         return  0;   /* right subtree is empty -- this is the maximum */
  170.     
  171.     else  return  1;   /* keep going right */
  172. }/* avl_max */
  173.  
  174.  
  175.  
  176. /************************************************************************
  177. *    Routines to perform rotations on AVL trees
  178. ************************************************************************/
  179.  
  180. /*
  181. * rotate_once()  --  rotate a given node in the given direction
  182. *                    to restore the balance of a tree
  183. */
  184. PRIVATE     short rotate_once( rootp, dir )
  185. AVLtree    *rootp;
  186. DIRECTION  dir;
  187. {
  188.     DIRECTION   other_dir = OPPOSITE( dir );    /* opposite direction to "dir" */
  189.     AVLtree     old_root  = *rootp;        /* copy of original root of tree */
  190.     short    ht_unchanged;            /* true if height unchanged */
  191.  
  192.     ht_unchanged = ( (*rootp) -> subtree[ other_dir ] -> bal ) ? FALSE : TRUE;
  193.   
  194.         /* assign new root */
  195.     *rootp = old_root -> subtree[ other_dir ];
  196.   
  197.         /* new-root exchanges it's "dir" subtree for it's parent */
  198.     old_root -> subtree[ other_dir ]   =   (*rootp) -> subtree[ dir ];
  199.     (*rootp) -> subtree[ dir ]         =   old_root;
  200.   
  201.         /* update balances */
  202.     old_root -> bal = -( dir == LEFT ? --( (*rootp) -> bal ) : ++( (*rootp) -> bal )  );
  203.   
  204.     return  ht_unchanged;
  205. }/* rotate_once */
  206.   
  207.   
  208. /*
  209. * rotate_twice()  --  rotate a given node in the given direction
  210. *                     and then in the opposite direction
  211. *                     to restore the balance of a tree
  212. */
  213. PRIVATE     void rotate_twice( rootp, dir )
  214. AVLtree    *rootp;
  215. DIRECTION  dir;
  216. {
  217.     DIRECTION   other_dir        = OPPOSITE( dir );
  218.     AVLtree     old_root        = *rootp,
  219.                 old_other_dir_subtree    = (*rootp) -> subtree[ other_dir ];
  220.     
  221.         /* assign new root */
  222.     *rootp = old_root -> subtree[ other_dir ] -> subtree[ dir ];
  223.   
  224.         /* new-root exchanges it's "dir" subtree for it's grandparent */
  225.     old_root -> subtree[ other_dir ]  =   (*rootp) -> subtree[ dir ];
  226.     (*rootp) -> subtree[ dir ]        =   old_root;
  227.   
  228.         /* new-root exchanges it's "other-dir" subtree for it's parent */
  229.     old_other_dir_subtree -> subtree[ dir ]    =   (*rootp) -> subtree[ other_dir ];
  230.     (*rootp) -> subtree[ other_dir ]        =   old_other_dir_subtree;
  231.   
  232.         /* update balances */
  233.     (*rootp) -> subtree[ LEFT ] -> bal   =  -MAX( (*rootp) -> bal, 0 );
  234.     (*rootp) -> subtree[ RIGHT ] -> bal  =  -MIN( (*rootp) -> bal, 0 );
  235.     (*rootp) -> bal                      =  0;
  236.  
  237. }/* rotate_twice */
  238.  
  239.  
  240. /************************************************************************
  241. *                    Rebalance an AVL tree
  242. ************************************************************************/
  243.  
  244. /*
  245. * balance()  --  determines and performs the  sequence of rotations needed
  246. *                   (if any) to restore the balance of a given tree.
  247. *
  248. *     Returns 1 if tree height changed due to rotation; 0 otherwise
  249. */
  250. PRIVATE    short  balance( rootp )
  251. AVLtree    *rootp;
  252. {
  253.     short  special_case = FALSE;
  254.  
  255.     if ( LEFT_IMBALANCE( *rootp )  )  {   /* need a right rotation */
  256.         if ( (*rootp) -> subtree[ LEFT ] -> bal  ==  RIGHT_HEAVY )
  257.             rotate_twice( rootp, RIGHT );    /* double RL rotation needed */
  258.  
  259.         else    /* single RR rotation needed */
  260.             special_case = rotate_once( rootp, RIGHT );
  261.     }/* if */
  262.   
  263.     else if ( RIGHT_IMBALANCE( *rootp )  )  {   /* need a left rotation */
  264.         if ( (*rootp) -> subtree[ RIGHT ] -> bal  ==  LEFT_HEAVY )
  265.             rotate_twice( rootp, LEFT );     /* double LR rotation needed */
  266.  
  267.         else    /* single LL rotation needed */
  268.             special_case = rotate_once( rootp, LEFT );
  269.     }/* elif */
  270.   
  271.     else  return  HEIGHT_UNCHANGED;    /* no rotation occurred */
  272.   
  273.     return  ( special_case ) ? HEIGHT_UNCHANGED : HEIGHT_CHANGED;
  274. }/* balance */
  275.  
  276.  
  277. /************************************************************************
  278. *    Routines to:    Find an item in an AVL tree
  279. *            Insert an item into an AVL tree
  280. *            Delete an item from an AVL tree
  281. ************************************************************************/
  282.  
  283. /*
  284. * avl_find() -- find an item in the given tree
  285. *
  286. *   PARAMETERS:
  287. *                data       --  a pointer to the key to find
  288. *                rootp      --  a pointer to an AVL tree
  289. *                compar     --  name of a function to compare 2 data items
  290. */
  291. PRIVATE      void *avl_find( data, tree, compar )
  292. void      *data;
  293. AVLtree   tree;
  294. int       (*compar)();
  295. {
  296.     NODE       nd_typ = node_type( tree );
  297.     int        cmp;
  298.   
  299.     while ( (cmp = (*compar)( data, tree -> data, nd_typ ))  &&
  300.         (tree != NULL_TREE) )
  301.         tree = tree -> subtree[ (cmp < 0) ? LEFT : RIGHT ];
  302.   
  303.     return  ( tree == NULL_TREE ) ? NULL : tree -> data;
  304. }/* avl_find */
  305.   
  306.  
  307. /*
  308. * avl_insert() -- insert an item into the given tree
  309. *
  310. *   PARAMETERS:
  311. *                data       --  a pointer to a pointer to the data to add;
  312. *                               On exit, *data is NULL if insertion succeeded,
  313. *                               otherwise address of the duplicate key
  314. *                rootp      --  a pointer to an AVL tree
  315. *                compar     --  name of the function to compare 2 data items
  316. */
  317. PRIVATE     short avl_insert( data, size, rootp, compar )
  318. void     **data;
  319. unsigned size;
  320. AVLtree  *rootp;
  321. int      (*compar)();
  322. {
  323.     short increase;
  324.     int   cmp;
  325.   
  326.     if ( *rootp == NULL_TREE )  {  /* insert new node here */
  327.         *rootp = new_node( *data, size );
  328.         *data  = NULL;     /* set return value in data */
  329.         return  HEIGHT_CHANGED;
  330.     }/* if */
  331.   
  332.     cmp = (*compar)( *data, (*rootp) -> data );   /* compare data items */
  333.   
  334.     if ( cmp < 0 )  {  /* insert into the left subtree */
  335.         increase =  -avl_insert( data, size, &( (*rootp) -> subtree[ LEFT ] ), compar );
  336.         if ( *data != NULL )     return  HEIGHT_UNCHANGED;
  337.     }/* elif */
  338.   
  339.     else if ( cmp > 0 )  {  /* insert into the right subtree */
  340.         increase =  avl_insert( data, size, &( (*rootp) -> subtree[ RIGHT ] ), compar );
  341.         if ( *data != NULL )     return  HEIGHT_UNCHANGED;
  342.     }/* elif */
  343.   
  344.     else  {   /* data already exists */
  345.         *data = (*rootp) -> data;   /* set return value in data */
  346.         return  HEIGHT_UNCHANGED;
  347.     } /* else */
  348.   
  349.     (*rootp) -> bal += increase;    /* update balance factor */
  350.  
  351.   /************************************************************************
  352.   * re-balance if needed -- height of current tree increases only if its
  353.   * subtree height increases and the current tree needs no rotation.
  354.   ************************************************************************/
  355.     if ( increase  &&  (*rootp) -> bal )
  356.         return  (  1 - balance( rootp )  );
  357.     else
  358.         return  HEIGHT_UNCHANGED;
  359. }/* avl_insert */
  360.  
  361.  
  362. /*
  363. * avl_delete() -- delete an item from the given tree
  364. *
  365. *   PARAMETERS:
  366. *                data       --  a pointer to a pointer to the key to delete
  367. *                               On exit, *data points to the deleted data item
  368. *                               (or NULL if deletion failed).
  369. *                rootp      --  a pointer to an AVL tree
  370. *                compar     --  name of function to compare 2 data items
  371. */
  372. PRIVATE     short avl_delete( data, rootp, compar )
  373. void      **data;
  374. AVLtree   *rootp;
  375. int       (*compar)();
  376. {
  377.     short      decrease;
  378.     int        cmp;
  379.     AVLtree    old_root  = *rootp;
  380.     NODE       nd_typ    = node_type( *rootp );
  381.     DIRECTION  dir       = (nd_typ == IS_LBRANCH) ? LEFT : RIGHT;
  382.   
  383.     if ( *rootp == NULL_TREE )  {  /* data not found */
  384.         *data = NULL;    /* set return value in data */
  385.         return  HEIGHT_UNCHANGED;
  386.     }/* if */
  387.   
  388.     cmp = compar( *data, (*rootp) -> data, nd_typ );   /* compare data items */
  389.   
  390.     if ( cmp < 0 )  {  /* delete from left subtree */
  391.         decrease =  -avl_delete( data, &( (*rootp) -> subtree[ LEFT ] ), compar );
  392.         if ( *data == NULL )     return  HEIGHT_UNCHANGED;
  393.     }/* elif */
  394.   
  395.     else if ( cmp > 0 )  {  /* delete from right subtree */
  396.         decrease =  avl_delete( data, &( (*rootp) -> subtree[ RIGHT ] ), compar );
  397.         if ( *data == NULL )     return  HEIGHT_UNCHANGED;
  398.     }/* elif */
  399.     
  400.   /************************************************************************
  401.   *  At this point we know that if "cmp" is zero then "*rootp" points to
  402.   *  the node that we need to delete.  There are three cases:
  403.   *
  404.   *     1) The node is a leaf.  Remove it and return.
  405.   *
  406.   *     2) The node is a branch (has only 1 child). Make "*rootp"
  407.   *        (the pointer to this node) point to the child.
  408.   *
  409.   *     3) The node has two children. We swap data with the successor of
  410.   *        "*rootp" (the smallest item in its right subtree) and delete
  411.   *        the successor from the right subtree of "*rootp".  The
  412.   *        identifier "decrease" should be reset if the subtree height
  413.   *        decreased due to the deletion of the sucessor of "rootp".
  414.   ************************************************************************/
  415.   
  416.     else  {  /* cmp == 0 */
  417.         *data = (*rootp) -> data;  /* set return value in data */
  418.   
  419.         switch ( nd_typ )  {  /* what kind of node are we removing? */
  420.             case  IS_LEAF :
  421.             free_node( rootp );          /* free the leaf, its height     */
  422.                 return  HEIGHT_CHANGED;      /* changes from 1 to 0, return 1 */
  423.   
  424.             case  IS_RBRANCH :       /* only child becomes new root */
  425.             case  IS_LBRANCH :
  426.             *rootp = (*rootp) -> subtree[ dir ];
  427.                 free_node( &old_root );      /* free the deleted node */
  428.                 return  HEIGHT_CHANGED;      /* we just shortened the "dir" subtree */
  429.   
  430.             case  IS_TREE  :
  431.                 decrease = avl_delete(  &( (*rootp) -> data ),
  432.                                         &( (*rootp) -> subtree[ RIGHT ] ),
  433.                                         avl_min                );
  434.         } /* switch */
  435.     } /* else */
  436.  
  437.     (*rootp) -> bal -= decrease;       /* update balance factor */
  438.   
  439.   /**********************************************************************
  440.   * Rebalance if necessary -- the height of current tree changes if one
  441.   * of two things happens: (1) a rotation was performed which changed
  442.   * the height of the subtree (2) the subtree height decreased and now
  443.   * matches the height of its other subtree (so the current tree now
  444.   * has a zero balance when it previously did not).
  445.   **********************************************************************/
  446.     if ( decrease  &&  (*rootp) -> bal )    /* return 1 if height      */
  447.         return  balance( rootp );        /* changed due to rotation */
  448.   
  449.     else if ( decrease  && !(*rootp) -> bal )    /* or if balance is 0 from    */
  450.         return  HEIGHT_CHANGED;            /* height decrease of subtree */
  451.   
  452.     else
  453.         return  HEIGHT_UNCHANGED;
  454.   
  455. }/* avl_delete */
  456.  
  457.  
  458.  
  459. /**
  460. *    Routines which Recursively Traverse an AVL TREE
  461. *
  462. * These routines may perform a particular action function upon each node
  463. * encountered. In these cases, "action" has the following definition:
  464. *
  465. *   void action( data, order, node, level, bal )
  466. *       void   *data
  467. *       VISIT   order;
  468. *       NODE    node;
  469. *    short    bal;
  470. *       int     level;
  471. *
  472. *         "data"    is a pointer to the data field of an AVL node
  473. *         "order"   corresponds to whether this is the 1st, 2nd or 3rd time
  474. *                   that this node has been visited.
  475. *         "node"    indicates which children (if any) of the current node
  476. *                   are null.
  477. *         "level"   is the current level (or depth) in the tree of the
  478. *                   curent node.
  479. *         "bal"     is the balance factor of the current node.
  480. **/
  481.  
  482.  
  483. /************************************************************************
  484. *    Walk an AVL tree, performing a given function at each node
  485. ************************************************************************/
  486.  
  487.  
  488. /*
  489. * avl_walk -- traverse the given tree performing "action"
  490. *            upon each data item encountered.
  491. *
  492. */
  493. PRIVATE     void  avl_walk( tree, action, sibling_order, level )
  494. AVLtree        tree;
  495. void           (*action)();
  496. SIBLING_ORDER  sibling_order;
  497. int            level;
  498. {
  499.     DIRECTION  dir1 = (sibling_order == LEFT_TO_RIGHT) ? LEFT : RIGHT,
  500.                dir2 = OPPOSITE( dir1 );
  501.     NODE       node = node_type( tree );
  502.   
  503.     if ( (tree != NULL_TREE)  &&  (action != NULL_ACTION) )  {
  504.         (*action)( tree -> data, PREORDER, node, level, tree -> bal );
  505.   
  506.         if ( tree -> subtree[ dir1 ]  !=  NULL_TREE )
  507.             avl_walk( tree -> subtree[ dir1 ], action, sibling_order, level+1 );
  508.   
  509.         (*action)( tree -> data, INORDER, node, level, tree -> bal );
  510.   
  511.         if ( tree -> subtree[ dir2 ]  !=  NULL_TREE )
  512.             avl_walk( tree -> subtree[ dir2 ], action, sibling_order, level+1 );
  513.   
  514.         (*action)( tree -> data, POSTORDER, node, level, tree -> bal );
  515.     }/* if non-empty tree */
  516.   
  517. }/* avl_walk */
  518.  
  519.  
  520.  
  521. /************************************************************************
  522. *    Walk an AVL tree, de-allocating space for each node
  523. *       and performing a given function at each node
  524. *       (such as de-allocating the user-defined data item).
  525. ************************************************************************/
  526.  
  527.  
  528. /*
  529. * avl_free() -- free up space for all nodes in a given tree
  530. *              performing "action" upon each data item encountered.
  531. *
  532. *    (only perform "action" if it is a non-null function) 
  533. */
  534.  
  535. PRIVATE     void  avl_free( rootp, action, sibling_order, level )
  536. AVLtree        *rootp;
  537. void           (*action)();
  538. SIBLING_ORDER  sibling_order;
  539. int            level;
  540. {
  541.     DIRECTION  dir1 = (sibling_order == LEFT_TO_RIGHT) ? LEFT : RIGHT,
  542.                dir2 = OPPOSITE( dir1 );
  543.     NODE       node = node_type( *rootp );
  544.   
  545.     if ( *rootp != NULL_TREE )  {
  546.   
  547.         if ( action != NULL_ACTION )
  548.        (*action)( (*rootp) -> data, PREORDER, node, level );
  549.   
  550.         if ( (*rootp) -> subtree[ dir1 ]  !=  NULL_TREE )
  551.             avl_free( &( (*rootp) -> subtree[ dir1 ] ),
  552.             action, sibling_order, level+1 );
  553.   
  554.         if ( action != NULL_ACTION )
  555.        (*action)( (*rootp) -> data, INORDER, node, level );
  556.   
  557.         if ( (*rootp) -> subtree[ dir2 ]  !=  NULL_TREE )
  558.             avl_free( &( (*rootp) -> subtree[ dir2 ] ),
  559.             action, sibling_order, level+1 );
  560.   
  561.         if ( action != NULL_ACTION )
  562.        (*action)( (*rootp) -> data, POSTORDER, node, level );
  563.   
  564.         free( *rootp );
  565.     }/* if non-empty tree */
  566.   
  567. }/* avl_free */
  568.  
  569.  
  570.  
  571.  
  572. /**********************************************************************
  573. * 
  574. *        C-interface (public functions) for avl trees 
  575. *
  576. *    These are the functions that are visible to the user of the
  577. *    AVL Tree Library. Mostly they just return or modify a
  578. *    particular attribute, or Call a private functions with the
  579. *    given parameters.
  580. *
  581. *    Note that public routine names begin with "avl" whereas
  582. *    private routine names that are called by public routines
  583. *    begin with "avl_" (the underscore character is added).
  584. *
  585. *    Each public routine must convert (cast) any argument of the 
  586. *    public type "AVL_TREE" to a pointer to on object of the 
  587. *    private type "AVLdescriptor" before passing the actual 
  588. *    AVL tree to any of the private routines. In this way, the
  589. *    type "AVL_TREE" is implemented as an opaque type.
  590. * 
  591. *    An "AVLdescriptor" is merely a container for AVL-tree
  592. *    objects which contains the pointer to the root of the 
  593. *    tree and the various attributes of the tree.
  594. *
  595. *    The function types prototypes for the routines which follow
  596. *    are declared in the include file "avl.h"
  597. *
  598. ***********************************************************************/
  599.  
  600.  
  601.  
  602. /*
  603. * avlinit() -- get space for an AVL descriptor for the given tree
  604. *              structure and initialize its fields.
  605. */
  606. PUBLIC AVL_TREE   avlinit( compar, isize )
  607. int       (*compar) ();
  608. unsigned  (*isize) ();
  609. {
  610.     AVLdescriptor  *avl_desc;
  611.   
  612.     avl_desc = (AVLdescriptor *) ckalloc( sizeof (AVLdescriptor) );
  613.     avl_desc -> root    = NULL_TREE;
  614.     avl_desc -> compar    = compar;
  615.     avl_desc -> isize    = isize;
  616.     avl_desc -> count    = 0;
  617.   
  618.     return  (AVL_TREE) avl_desc;
  619. }/* avlinit */
  620.  
  621.  
  622.  
  623. /*
  624. * avldispose() -- free up all space associated with the given tree structure.
  625. */
  626. PUBLIC void   avldispose( treeptr, action, sibling_order )
  627. AVL_TREE       *treeptr;
  628. void           (*action) ();
  629. SIBLING_ORDER  sibling_order;
  630. {
  631.     AVLdescriptor  *avl_desc;
  632.   
  633.     avl_desc = (AVLdescriptor *) *treeptr;
  634.     avl_free( &(avl_desc -> root), action, sibling_order, 1 );
  635.     *treeptr = (AVL_TREE) NULL;
  636. }/* avldispose */
  637.  
  638.  
  639.  
  640. /*
  641. * avlwalk() -- traverse the given tree structure and perform the
  642. *              given action on each data item in the tree.
  643. */
  644. PUBLIC void   avlwalk( tree, action, sibling_order )
  645. AVL_TREE       tree;
  646. void           (*action)();
  647. SIBLING_ORDER  sibling_order;
  648. {
  649.     AVLdescriptor  *avl_desc;
  650.   
  651.     avl_desc = (AVLdescriptor *) tree;
  652.     avl_walk( avl_desc -> root, action, sibling_order, 1 );
  653. }/* avlwalk */
  654.   
  655.    
  656.  
  657. /*
  658. * avlcount () --  return the number of nodes in the given tree
  659. */
  660. PUBLIC int  avlcount( tree )
  661. AVL_TREE  tree;
  662. {
  663.     AVLdescriptor  *avl_desc;
  664.   
  665.     avl_desc = (AVLdescriptor *) tree;
  666.     return  avl_desc -> count;
  667. }/* avlcount */
  668.  
  669.  
  670.  
  671. /*
  672. * avlins() -- insert the given item into the tree structure
  673. */
  674. PUBLIC void  *avlins( data, tree )
  675. void      *data;
  676. AVL_TREE  tree;
  677. {
  678.     AVLdescriptor  *avl_desc;
  679.   
  680.     avl_desc = (AVLdescriptor *) tree;
  681.     avl_insert( &data, (*(avl_desc -> isize))( data ), &(avl_desc -> root), avl_desc -> compar );
  682.     if ( data == NULL )    ++(avl_desc -> count);
  683.  
  684.     return  data;
  685. }/* avlins */
  686.  
  687.  
  688.  
  689. /*
  690. * avldel() -- delete the given item from the given tree structure
  691. */
  692. PUBLIC void  *avldel( data, tree )
  693. void      *data;
  694. AVL_TREE  tree;
  695. {
  696.     AVLdescriptor  *avl_desc;
  697.   
  698.     avl_desc = (AVLdescriptor *) tree;
  699.     avl_delete( &data, &(avl_desc -> root), avl_desc -> compar );
  700.     if ( data != NULL )     --(avl_desc -> count);
  701.   
  702.     return  data;
  703. }/* avldel */
  704.  
  705.  
  706.  
  707. /*
  708. * avlfind() -- find the given item in the given tree structure
  709. *              and return its address (NULL if not found).
  710. */
  711. PUBLIC void  *avlfind( data, tree )
  712. void      *data;
  713. AVL_TREE  tree;
  714. {
  715.     AVLdescriptor  *avl_desc;
  716.   
  717.     avl_desc = (AVLdescriptor *) tree;
  718.     return  avl_find( data, &(avl_desc -> root), avl_desc -> compar );
  719. }/* avlfind */
  720.  
  721.   
  722.  
  723. /*
  724. * avldelmin() -- delete the minimal item from the given tree structure
  725. */
  726. PUBLIC void  *avldelmin( tree )
  727. AVL_TREE  tree;
  728. {
  729.     void  *data;
  730.     AVLdescriptor  *avl_desc;
  731.   
  732.     avl_desc = (AVLdescriptor *) tree;
  733.     avl_delete( &data, &(avl_desc -> root), avl_min );
  734.     if ( data != NULL )     --(avl_desc -> count);
  735.   
  736.     return  data;
  737. }/* avldelmin */
  738.  
  739.  
  740.  
  741. /*
  742. * avlfindmin() -- find the minimal item in the given tree structure
  743. *              and return its address (NULL if not found).
  744. */
  745. PUBLIC void  *avlfindmin( tree )
  746. AVL_TREE  tree;
  747. {
  748.     AVLdescriptor  *avl_desc;
  749.   
  750.     avl_desc = (AVLdescriptor *) tree;
  751.     return  avl_find( NULL, &(avl_desc -> root), avl_min );
  752. }/* avlfindmin */
  753.  
  754.   
  755.  
  756. /*
  757. * avldelmax() -- delete the maximal item from the given tree structure
  758. */
  759. PUBLIC void  *avldelmax( tree )
  760. AVL_TREE  tree;
  761. {
  762.     void  *data;
  763.     AVLdescriptor  *avl_desc;
  764.   
  765.     avl_desc = (AVLdescriptor *) tree;
  766.     avl_delete( &data, &(avl_desc -> root), avl_max );
  767.     if ( data != NULL )     --(avl_desc -> count);
  768.   
  769.     return  data;
  770. }/* avldelmax */
  771.  
  772.   
  773.  
  774. /*
  775. * avlfindmax() -- find the maximal item in the given tree structure
  776. *              and return its address (NULL if not found).
  777. */
  778. PUBLIC void  *avlfindmax (tree)
  779. AVL_TREE  tree;
  780. {
  781.     AVLdescriptor  *avl_desc;
  782.   
  783.     avl_desc = (AVLdescriptor *) tree;
  784.     return  avl_find( NULL, &(avl_desc -> root), avl_max );
  785. }/* avlfindmax */
  786.