home *** CD-ROM | disk | FTP | other *** search
/ System Booster / System Booster.iso / Texteditors / XDME / Src / AVL.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-27  |  19.1 KB  |  950 lines
  1. #define XDME
  2. /******************************************************************************
  3.  
  4.     MODULE
  5.     AVL.c
  6.  
  7.     DESCRIPTION
  8.     simple implementation for (recursive) AVL-trees
  9.     this code can be used for an Amiga(c) shared library
  10.  
  11.     NOTES
  12.     the nodes do need valid C-strings;
  13.     currently, there is no possibility
  14.     to change search/comparison and keys
  15.     anything is done via strcmp.
  16.  
  17.     if You wanna use that code as a non-shared library
  18.     You might have to modify some "#define"s below; also
  19.     it might be useful to re"#define" A0,A1,D0 and PRE.
  20.     (see below (search for LIB_TYPE))
  21.  
  22.     compile w/ #define ANY_DEBUG to get basic error-checking
  23.            #define AVL_DEBUG to get almost full-featured error-checking
  24.         in either case You must initialize an function-var called
  25.         extern void (*error)(char*, char*, char*);
  26.         which displays our errors;
  27.  
  28.     BUGS
  29.     that implementation on AVL - as is - does not
  30.     create any errormessages; user must make sure,
  31.     not to mess up w/ the trees, nor using two nodes
  32.     of the same name;
  33.  
  34.     TODO
  35.     maybe certain Header structures,
  36.     to support other comparison functions
  37.     and error functions
  38.  
  39.     EXAMPLES
  40.     for AVL-trees there are soooo many examples in other pgms
  41.  
  42.     SEE ALSO
  43.  
  44.     INDEX
  45.  
  46.     HISTORY
  47.     05-07-93 b_noll created
  48.     12-07-93 b_noll added ScanTree, FreeTree
  49.     21-07-93 b_noll changed switch()'s to if()'s
  50.     22-07-93 b_noll disabled all error-calls
  51.     07-10-93 b_noll [re]activated LSON/RSON/NAME/BAL-Macros
  52.     07-11-93 b_noll fixed bug in rem_rek (there were no reports)
  53.     12-05-94 b_noll joined xdme-verion and lib-version
  54.     $Date: $ last update
  55.  
  56. ******************************************************************************/
  57.  
  58. /**************************************
  59.         Includes
  60. **************************************/
  61.  
  62. /* we do not import AVL.h since we did hide tn_Balance from the user there */
  63. #ifndef   AVL_H
  64. /* #include <AVL.h> */
  65. #define   AVL_H
  66. #endif /* AVL_H */
  67.  
  68. #ifndef   EXEC_TYPES_H
  69. #include <exec/types.h>
  70. #endif /* EXEC_TYPES_H */
  71.  
  72. #ifndef   STRINGS_H
  73. #include <strings.h>
  74. #endif /* STRINGS_H */
  75.  
  76. /**************************************
  77.         Global Variables
  78. **************************************/
  79.  
  80. #ifdef XDME
  81. #define   ERROR(x,y,z) error(x,y,z)
  82. extern void error(const char*, ...);
  83. #define   ANY_DEBUG 1
  84. #else
  85. #define   ERROR(x,y,z) if (error) (*error)(x,y,z)
  86. void (*error)(char const *, char const *, char const *) = NULL;
  87. #endif
  88.  
  89.  
  90. /**************************************
  91.         Internal Defines & Structures
  92. **************************************/
  93.  
  94. /* redefine it here as we did comment out tn_Balance in AVL.h */
  95. struct TreeNode {
  96.     struct TreeNode * tn_Left;
  97.     struct TreeNode * tn_Right;
  98.     UBYTE          tn_Type;
  99.     BYTE          tn_Balance; /* !PRIVATE! for AVL - do not use it! */
  100.     char        * tn_Name;
  101. }; /* struct TreeNode */
  102.  
  103. /**************************************
  104.         Internal Variables
  105. **************************************/
  106.  
  107. /* none */
  108.  
  109. /**************************************
  110.         Internal Prototypes
  111. **************************************/
  112.  
  113. /* static int AVL_rem_rek (struct TreeNode**, struct TreeNode*); */
  114. /* static int AVL_add_rek (struct TreeNode**, struct TreeNode*); */
  115. /* static int AVL_balance (struct TreeNode**); */
  116.  
  117. /**************************************
  118.         Macros
  119. **************************************/
  120.  
  121. /**************************************************
  122. **
  123. **  !!    LIB_TYPE  !!
  124. **
  125. **  Change the following lines to switch
  126. **  between a shared-library and a link-library
  127. **  #if 1 -> SHARED
  128. **  #if 0 ->LINK
  129. **
  130. **************************************************/
  131. #if 0
  132. /* SHARED LIB: */
  133. #define AVL_Find     LIBAVL_Find
  134. #define AVL_Append   LIBAVL_Append
  135. #define AVL_Remove   LIBAVL_Remove
  136. #define AVL_FreeTree LIBAVL_FreeTree
  137. #define AVL_ScanTree LIBAVL_ScanTree
  138. #define PRE __asm __saveds
  139. #define A0(x) register __a0 x
  140. #define A1(x) register __a1 x
  141. #define D0(x) register __d0 x
  142. #else
  143. /* LINK LIB: */
  144. #define PRE
  145. #define A0(x) x
  146. #define A1(x) x
  147. #define D0(x) x
  148. #endif
  149. /*************************************************/
  150.  
  151. #define INC(x) ++(x)
  152. #define DEC(x) --(x)
  153.  
  154. #define RSON(x) (x)->tn_Right
  155. #define LSON(x) (x)->tn_Left
  156. #define BLNC(x) (x)->tn_Balance
  157. #define NAME(x) (x)->tn_Name
  158.  
  159. #define BAL(x) BLNC(x)
  160.  
  161. #define AVL_SCAN_PRAEFIX  0
  162. #define AVL_SCAN_INFIX      1
  163. #define AVL_SCAN_POSTFIX -1
  164.  
  165. /**************************************
  166.         Implementation
  167. **************************************/
  168.  
  169. #ifdef      ANY_DEBUG
  170. const char* AVL_errdisp1 = "AVL:\n%s!\n";
  171. const char* AVL_errdisp2 = "AVL:\n%s %s!\n";
  172.  
  173. const char* AVL_err_notree = "without a tree";
  174. const char* AVL_err_cotree = "with a corrupt tree";
  175. const char* AVL_err_multi  = "Can not manage multiple nodes\nof same name in one tree";
  176.  
  177. const char* AVL_err_balan  = "called Balance";
  178. const char* AVL_err_rem    = "called Remove";
  179. const char* AVL_err_add    = "called Append";
  180. const char* AVL_err_find   = "called Find";
  181. const char* AVL_err_free   = "called FreeTree";
  182. const char* AVL_err_scan   = "called ScanTree";
  183. #endif /* ANY_DEBUG */
  184.  
  185.  
  186. /*****************************************************************************
  187.  
  188.     NAME
  189.     AVL_balance
  190.  
  191.     PARAMETER
  192.     struct TreeNode** t;
  193.  
  194.     RESULT
  195.     the balance of the new root (? really)
  196.  
  197.     RETURN
  198.     int;
  199.  
  200.     DESCRIPTION
  201.     do a local rebalance if the current node's
  202.     balance is worse than +/- 1
  203.  
  204.     the function is used by AVL_add_rek and
  205.     by AVL_rem_rek on the way back from a
  206.     addition/deletion;
  207.  
  208.     NOTES
  209.     that rebalance affect only up to three nodes;
  210.  
  211.     the function might have been done in a more
  212.     effective way - but I wanna be able to read it
  213.     also in 2 weeks.
  214.  
  215.     BUGS
  216.     none known
  217.  
  218.     EXAMPLES
  219.     why - its hidden
  220.  
  221.     SEE ALSO
  222.     AVL_add_rek, AVL_rem_rek
  223.  
  224.     INTERNALS
  225.     verschachtelte case-construkte,
  226.     um alle normalen Faelle abzudecken,
  227.     die bei AVL_Append und AVL_Remove
  228.     auftreten koennen;
  229.     den Rest habe in mir mit Bildchen
  230.     klargemacht.
  231.  
  232.     Hier mehr zu schreiben hat m.E. keinen
  233.     Sinn, das geht besser mit Papier und Bleistift;
  234.  
  235.     HISTORY
  236.     05-07-93    b_noll  created
  237.  
  238. ******************************************************************************/
  239. static
  240. int AVL_balance (struct TreeNode** t)
  241. {
  242.     struct TreeNode* ot = *t;
  243.     struct TreeNode* lt = LSON(ot);
  244.     struct TreeNode* rt = RSON(ot);
  245.     char         b    = BAL(ot);
  246.  
  247. /* D(bug("AVL:balancing...")); */
  248.  
  249.     switch (b) {
  250.  
  251. #ifdef AVL_DEBUG
  252.     case -1:
  253.     case  0:
  254.     case +1:
  255.     ERROR (AVL_errdisp2, AVL_err_balan, "without need");
  256.     return (b);
  257. #endif /* AVL_DEBUG */
  258.  
  259.     case +2:
  260.     b = BAL(lt);
  261.     switch (b) {
  262.     case -1:
  263. /* D(bug("LR")); */
  264.         rt = RSON(lt);
  265.         *t = rt;
  266.         LSON(ot) = RSON(rt);
  267.         RSON(lt) = LSON(rt);
  268.         LSON(rt) = lt;
  269.         RSON(rt) = ot;
  270.  
  271.  
  272.         b        = BAL(rt);
  273.         BAL(rt) = 0;
  274.         BAL(lt) =  (1-b)/2; /* -:1 0:0 +:0 */
  275.         BAL(ot) = -(1+b)/2; /*   0   0  -1 */
  276.  
  277.         return 0;
  278.  
  279.     case  0:
  280.     case +1: /* LL */
  281. /* D(bug("LL")); */
  282.         *t = lt;
  283.         LSON(ot) = RSON(lt);
  284.         RSON(lt) = ot;
  285.  
  286.         BAL(ot) = -(b-1); /* 0:+1; +1:0 */
  287.         BAL(lt) = +(b-1); /*   -1;    0 */
  288.  
  289.         return b-1;
  290.  
  291. #ifdef AVL_DEBUG
  292.     default:
  293.         ERROR ( AVL_errdisp2, AVL_err_balan, AVL_err_cotree);
  294. #endif /* AVL_DEBUG */
  295.     } /* switch */
  296.  
  297.     break;
  298.  
  299.     case -2:
  300.     b = BAL(rt);
  301.     switch (b) {
  302.     case +1:
  303. /* D(bug("RL")); */
  304.         lt = LSON(rt);
  305.         *t = lt;
  306.         RSON(ot) = LSON(lt);
  307.         LSON(rt) = RSON(lt);
  308.         LSON(lt) = ot;
  309.         RSON(lt) = rt;
  310.  
  311.         b        = BAL(lt);
  312.         BAL(lt) = 0;
  313.         BAL(rt) =  (1+b)/2; /* -:0 0:0 +: */
  314.         BAL(ot) =  (1-b)/2; /*   1   0    */
  315. /* D(bug("b== %d\n",b)); */
  316.  
  317.         return 0;
  318.  
  319.     case  0:
  320.     case -1: /* RR */
  321.  
  322. /* D(bug("RR")); */
  323.         *t = rt;
  324.         RSON(ot) = LSON(rt);
  325.         LSON(rt) = ot;
  326.  
  327.         /* Vorzeichen ??? */
  328.         BAL(ot) = -(b+1); /* 0:-1; -1:0 */
  329.         BAL(rt) = +(b+1); /*   +1;    0 */
  330. /* D(bug("ot%d rt%d\n", -(b+1), (b+1))); */
  331.         return -(b-1);
  332.  
  333. #ifdef AVL_DEBUG
  334.     default:
  335.         ERROR ( AVL_errdisp2, AVL_err_balan, AVL_err_cotree);
  336. #endif /* AVL_DEBUG */
  337.     } /* switch */
  338.     break;
  339.  
  340. #ifdef AVL_DEBUG
  341.     default:
  342.     ERROR ( AVL_errdisp2, AVL_err_balan, AVL_err_cotree);
  343. #endif /* AVL_DEBUG */
  344.     } /* switch */
  345.  
  346.     return 0;
  347. } /* AVL_balance */
  348.  
  349.  
  350.  
  351. /*****************************************************************************
  352.  
  353.     NAME
  354.     AVL_swap_best_right
  355.  
  356.     PARAMETER
  357.     struct TreeNode** swapme;
  358.  
  359.     RESULT
  360.     swapping was necessary and done
  361.  
  362.     RETURN
  363.     BOOL;
  364.  
  365.     DESCRIPTION
  366.     swap the current node (swapme) with the
  367.     leftmost follower/son of its right son
  368.  
  369.     NOTES
  370.     swapping with the rightmost follower of its left son
  371.     would have a similar effect;
  372.  
  373.     perhaps we should first check for a better balance to
  374.     decide which one to use (we have to rename the function then)
  375.  
  376.     BUGS
  377.     none known
  378.  
  379.     EXAMPLES
  380.     why - its hidden
  381.  
  382.     SEE ALSO
  383.     AVL_rem_rek
  384.  
  385.     INTERNALS
  386.     die function ist in 2 Teile zerlegbar:
  387.     die Suche nach dem "optimalen" Nachfolger
  388.     danach das Vertauschen dieses Nachfolgers
  389.     mit dem Root.
  390.  
  391.     HISTORY
  392.     05-07-93    b_noll  created
  393.  
  394. ******************************************************************************/
  395. static
  396. BOOL AVL_swap_best_right (struct TreeNode** swapme)
  397. {
  398.     struct TreeNode* root = *swapme;
  399.     struct TreeNode* curr = root;
  400.     struct TreeNode* prev = NULL;
  401.     struct TreeNode* z;
  402.  
  403. /* D(bug("AVL:swappin' ...")); */
  404.  
  405.     { /* search the mostleft node of the right son */
  406.     if ((curr = RSON(root)) == NULL) {
  407.         return FALSE;
  408.     } /* if */
  409.  
  410.  
  411.     while ((z = LSON(curr))) {
  412.         prev = curr;
  413.         curr = z;
  414.     } /* while */
  415.     }
  416.  
  417.     { /* swap our node and the leftmost right son */
  418.     z = RSON(curr);
  419.     if (prev) {
  420.         LSON(prev) = root;
  421.         RSON(curr) = RSON(root);
  422.     } else {
  423.         RSON(curr) = root;
  424.     } /* if */
  425.  
  426.     RSON(root) = z;
  427.  
  428.     *swapme    = curr;
  429.     LSON(curr) = LSON(root);
  430.     LSON(root) = NULL;
  431.     }
  432.  
  433.  
  434.     { /* swap the balances, too! */
  435.     char bal  = BAL(root);
  436.     BAL(root) = BAL(curr);
  437.     BAL(curr) = bal;
  438.     }
  439.  
  440.     return TRUE;
  441. } /* AVL_swap_best_right */
  442.  
  443.  
  444.  
  445. /*****************************************************************************
  446.  
  447.     NAME
  448.     AVL_rem_rek
  449.  
  450.     PARAMETER
  451.     struct TreeNode** tree;
  452.     struct TreeNode*  obj;
  453.  
  454.     RESULT
  455.     The Tree's change of height
  456.  
  457.     RETURN
  458.     int;
  459.  
  460.     DESCRIPTION
  461.     hidden part of AVL_Remove
  462.  
  463.     NOTES
  464.     no security checks involved;
  465.  
  466.     BUGS
  467.     use of 2 nodes w/ the same Id will
  468.     lead into trouble
  469.  
  470.     EXAMPLES
  471.     why - its hidden
  472.  
  473.     SEE ALSO
  474.     AVL_Remove
  475.  
  476.     INTERNALS
  477.     the deletion is done recursively
  478.  
  479.     zunaechst suchen wir nach dem Knoten,
  480.     den wir herausloesen wollen (nur ueber
  481.     strcmp!) bringen den dann an eine
  482.     Position, wo wir loeschen koennen
  483.     und knipsen ihn dort heraus;
  484.     auf dem Rueckweg wird der Baum bei Bedarf
  485.     rebalaniert
  486.  
  487.     HISTORY
  488.     05-07-93    b_noll  created
  489.     21-07-93    b_noll  switch(strcmp) -> if(diff) to handle w/ SAS
  490.  
  491. ******************************************************************************/
  492. static
  493. int AVL_rem_rek (struct TreeNode** tree, struct TreeNode* obj)
  494. {
  495.  
  496.     struct TreeNode* n     = *tree;
  497.     int          diff;
  498.  
  499.     if (!n) {
  500. #ifdef      ANY_DEBUG
  501.     ERROR ( AVL_errdisp1, "Can't remove non-added node", NULL);
  502. #endif /* ANY_DEBUG */
  503.     return 0;
  504.     } /* if */
  505.  
  506.     if ((diff = strcmp (NAME(obj), NAME(n))) == 0) {
  507.     if (n != obj) {
  508. #ifdef      ANY_DEBUG
  509.         ERROR ( AVL_errdisp1, AVL_err_multi, NULL);
  510. #endif /* ANY_DEBUG */
  511.         return 0;
  512.     } /* if */
  513.  
  514.     if (AVL_swap_best_right(tree)) { /* noch nich' am boden */
  515.         n = *tree;
  516.         goto remright;        /* ab hier koennte es beschleunigt werden */
  517.     } else {            /* schon am rand - abschneiden */
  518.         *tree = LSON(n);        /* PATCH_NULL BUGFIX [07 Nov 1993] : Right <-> Left */
  519.         return 1;
  520.     } /* if am rand */
  521.  
  522.     } else if (diff > 0) {
  523. remright:
  524.     if ( AVL_rem_rek(&RSON(n), obj) ) {
  525.         INC(BAL(n));
  526.         if (BAL(n) == 2) {
  527.         AVL_balance(tree);
  528.         } /* if */
  529.         return !BAL(*tree);
  530.     } /* if */
  531.     return 0;
  532.  
  533.     } else {
  534.     if ( AVL_rem_rek(&LSON(n), obj) ) {
  535.         DEC(BAL(n));
  536.         if (BAL(n) == -2) {
  537.         AVL_balance(tree);
  538.         } /* if */
  539.         return !BAL(*tree);
  540.     } /* if */
  541.     return 0;
  542.  
  543.     } /* if */
  544. } /* AVL_rem_rek */
  545.  
  546.  
  547. /*****************************************************************************
  548.  
  549.     NAME
  550.     AVL_add_rek
  551.  
  552.     PARAMETER
  553.     struct TreeNode** tree;
  554.     struct TreeNode*  obj;
  555.  
  556.     RESULT
  557.     The Tree's change of height
  558.  
  559.     RETURN
  560.     int;
  561.  
  562.     DESCRIPTION
  563.     hidden part of AVL_Append
  564.  
  565.     NOTES
  566.     no security checks involved;
  567.  
  568.     BUGS
  569.     none known
  570.  
  571.     EXAMPLES
  572.     why - its hidden
  573.  
  574.     SEE ALSO
  575.     AVL_Append
  576.  
  577.     INTERNALS
  578.     the addition is done recursively
  579.  
  580.     wir gehen solange nach unten, bis
  581.     wir auf ein NIL-kind stossen und
  582.     haengen unseren Node dorthin;
  583.     auf dem Rueckweg wird der Baum bei Bedarf
  584.     rebalaniert
  585.  
  586.     HISTORY
  587.     05-07-93    b_noll  created
  588.     21-07-93    b_noll  switch(strcmp) -> if(diff) to handle w/ SAS
  589.  
  590. ******************************************************************************/
  591. static
  592. int AVL_add_rek (struct TreeNode** tree, struct TreeNode* obj)
  593. {
  594.     struct TreeNode* n     = *tree;
  595.     int          diff;
  596.  
  597.     if (!n) {
  598.     *tree = obj;
  599.     RSON(obj) = NULL;
  600.     LSON(obj) = NULL;
  601.     BAL(obj)  = 0;
  602.     return 1;
  603.     } /* if */
  604.  
  605.     if ((diff = strcmp (NAME(obj), NAME(n))) == 0) {
  606. #ifdef     ANY_DEBUG
  607.     ERROR ( AVL_errdisp1, AVL_err_multi, NULL);
  608. #endif /* ANY_DEBUG */
  609.     return 0;
  610.  
  611.     } else if (diff > 0) {
  612.     if (AVL_add_rek(&RSON(n), obj)) {
  613.         DEC(BAL(n));
  614.         if (BAL(n) == -2) {
  615.         AVL_balance(tree);
  616.         } else {
  617.         return BAL(n);
  618.         } /* if */
  619.     } /* if */
  620.     return 0;
  621.  
  622.     } else {
  623.     if (AVL_add_rek(&LSON(n), obj)) {
  624.         INC(BAL(n));
  625.         if (BAL(n) == 2) {
  626.         AVL_balance(tree);
  627.         } else {
  628.         return BAL(n);
  629.         } /* if */
  630.     } /* if */
  631.     return 0;
  632.  
  633.     } /* if */
  634. } /* AVL_add_rek */
  635.  
  636.  
  637.  
  638. /*****************************************************************************
  639.  
  640.     NAME
  641.     AVL_Find
  642.  
  643.     PARAMETER
  644.     A0( struct TreeNode** tree );
  645.     A1( const char*       name );
  646.  
  647.     RESULT
  648.     the treenode, that matches name - if exists
  649.  
  650.     RETURN
  651.     PRE struct TreeNode*;
  652.  
  653.     DESCRIPTION
  654.     search for name in the tree
  655.  
  656.     NOTES
  657.     search is done with strcmp()
  658.  
  659.     ** Be Aware - You must give the Tree's ADDRESS **
  660.     (that would not have been necessary, here, but
  661.     so I can show a little bit more consistency,
  662.     since AVL_Append and AVL_Remove do need it)
  663.  
  664.     BUGS
  665.     none known
  666.  
  667.     EXAMPLES
  668.  
  669.     SEE ALSO
  670.     AVL_Append, AVL_Remove
  671.  
  672.     INTERNALS
  673.     search is done iteratively
  674.  
  675.     HISTORY
  676.     05-07-93    b_noll  created
  677.  
  678. ******************************************************************************/
  679.  
  680. PRE struct TreeNode* AVL_Find (A0( struct TreeNode** tree ), A1( const char* name ))
  681. {
  682.     int          diff;
  683.     struct TreeNode* n;
  684.  
  685.     if (!tree) {
  686. #ifdef     AVL_DEBUG
  687.     ERROR ( AVL_errdisp2, AVL_err_find, AVL_err_notree);
  688. #endif /* AVL_DEBUG */
  689.     return NULL;
  690.     } /* if */
  691.  
  692.     n = *tree;
  693.  
  694.     while ((n != NULL) && (diff = strcmp (name, NAME(n)))) {
  695.     if (diff > 0) {
  696.         n = RSON(n);
  697.     } else {
  698.         n = LSON(n);
  699.     } /* if */
  700.     } /* while */
  701.  
  702.     return n;
  703. } /* AVL_Find */
  704.  
  705.  
  706.  
  707. /*****************************************************************************
  708.  
  709.     NAME
  710.     AVL_Remove
  711.  
  712.     PARAMETER
  713.     A0( struct TreeNode** tree   );
  714.     A1( struct TreeNode*  remove );
  715.  
  716.     RESULT
  717.     *tree == the tree after Deleting the obsolete node
  718.  
  719.     RETURN
  720.     PRE struct TreeNode*;
  721.  
  722.     DESCRIPTION
  723.     Remove a node from an avl-tree; the right
  724.     position is searched with strcmp()
  725.  
  726.     NOTES
  727.     U first have to search for the node which
  728.     is to be deleted e.g.:
  729.     AVL_Rem(&tree, FindTreeNode(&tree, name ));
  730.  
  731.     ** Be Aware - You must give the Tree's ADDRESS **
  732.  
  733.     BUGS
  734.     none known
  735.  
  736.     EXAMPLES
  737.  
  738.     SEE ALSO
  739.     AVL_Find, AVL_Append, AVL_rem_rek
  740.  
  741.     INTERNALS
  742.     the deletion is actually done by AVL_rem_rek
  743.     AVL_Remove is only something like a security-
  744.     interface
  745.  
  746.     HISTORY
  747.     05-07-93    b_noll  created
  748.  
  749. ******************************************************************************/
  750.  
  751. PRE struct TreeNode* AVL_Remove (A0( struct TreeNode** tree ), A1( struct TreeNode* remove ))
  752. {
  753.     if (!tree) {
  754. #ifdef     AVL_DEBUG
  755.     ERROR ( AVL_errdisp2, AVL_err_rem, AVL_err_notree);
  756. #endif /* AVL_DEBUG */
  757.     return NULL;
  758.     } /* if */
  759.  
  760.     if (!(*tree))
  761.     return NULL;
  762.  
  763.     if (remove)
  764.     AVL_rem_rek (tree, remove);
  765.  
  766.     return *tree;
  767. } /* AVL_Remove */
  768.  
  769.  
  770.  
  771.  
  772. /*****************************************************************************
  773.  
  774.     NAME
  775.     AVL_Append
  776.  
  777.     PARAMETER
  778.     A0( struct TreeNode** tree );
  779.     A1( struct TreeNode*  new  );
  780.  
  781.     RESULT
  782.     *tree == the tree after Appending the new node
  783.  
  784.     RETURN
  785.     PRE struct TreeNode*;
  786.  
  787.     DESCRIPTION
  788.     Append a new node to an avl-tree; the right
  789.     position is calculated with strcmp()
  790.  
  791.     NOTES
  792.     U cannot define two nodes with the same
  793.     name in one tree
  794.  
  795.     ** Be Aware - You must give the Tree's ADDRESS **
  796.  
  797.     BUGS
  798.     none known
  799.  
  800.     EXAMPLES
  801.  
  802.     SEE ALSO
  803.     AVL_Remove, AVL_add_rek
  804.  
  805.     INTERNALS
  806.     the Addition is actually done by AVL_add_rek
  807.     AVL_Append is only something like a security-
  808.     interface
  809.  
  810.     HISTORY
  811.     05-07-93    b_noll  created
  812.  
  813. ******************************************************************************/
  814.  
  815. PRE struct TreeNode* AVL_Append (A0( struct TreeNode** tree ), A1( struct TreeNode* new ))
  816. {
  817.     if (!tree) {
  818. #ifdef     AVL_DEBUG
  819.     ERROR ( AVL_errdisp2, AVL_err_add, AVL_err_notree);
  820. #endif /* AVL_DEBUG */
  821.     return NULL;
  822.     } /* if */
  823.  
  824.     if (new)
  825.     AVL_add_rek (tree, new);
  826.  
  827.     return *tree;
  828. } /* AVL_Append */
  829.  
  830.  
  831.  
  832. /*****************************************************************************
  833.  
  834.     NAME
  835.     AVL_FreeTree
  836.  
  837.     PARAMETER
  838.     A0( struct TreeNode** tree );
  839.     A1( void (*freefunc)(A0( APTR )) );
  840.  
  841.     RESULT
  842.     -/-
  843.  
  844.     RETURN
  845.     PRE void
  846.  
  847.     DESCRIPTION
  848.     free all entries of a certain tree;
  849.  
  850.     NOTES
  851.     ** Be Aware - You must give the Tree's ADDRESS **
  852.  
  853.     ** Be Aware - You must not delete a partial tree,
  854.                     but only whole trees **
  855.  
  856.     BUGS
  857.     none known
  858.  
  859.     EXAMPLES
  860.  
  861.     SEE ALSO
  862.  
  863.     INTERNALS
  864.     the tree is completely deleted, without respect to
  865.     any balance; we expect to call that function only on
  866.     root-nodes;
  867.  
  868.     HISTORY
  869.     12-07-93    b_noll  created
  870.  
  871. ******************************************************************************/
  872.  
  873. PRE void AVL_FreeTree (A0( struct TreeNode** tree ), A1( void (*freefunc)(A0( APTR )) ))
  874. {
  875.     if (tree) {
  876.     if (*tree) {
  877.         AVL_FreeTree(&(LSON(*tree)),  freefunc);
  878.         AVL_FreeTree(&(RSON(*tree)), freefunc);
  879.         (*freefunc) (*tree);
  880.         *tree = NULL;
  881.     } /* if */
  882. #ifdef     AVL_DEBUG
  883.     } else {
  884.     ERROR ( AVL_errdisp2, AVL_err_free, AVL_err_notree);
  885. #endif /* AVL_DEBUG */
  886.     } /* if */
  887. } /* AVL_FreeTree */
  888.  
  889.  
  890.  
  891. /*****************************************************************************
  892.  
  893.     NAME
  894.     AVL_ScanTree
  895.  
  896.     PARAMETER
  897.     A0( struct TreeNode** tree );
  898.     A1( void (*scanfunc)(A0( APTR )) );
  899.     D0( char mode );
  900.  
  901.     RESULT
  902.     -/-
  903.  
  904.     RETURN
  905.     PRE void
  906.  
  907.     DESCRIPTION
  908.     call a certain function on all nodes of a certain tree
  909.  
  910.     NOTES
  911.     ** Be Aware - You must give the Tree's ADDRESS **
  912.  
  913.     BUGS
  914.  
  915.     EXAMPLES
  916.  
  917.     SEE ALSO
  918.  
  919.     INTERNALS
  920.  
  921.     HISTORY
  922.     12-07-93    b_noll  created
  923.  
  924. ******************************************************************************/
  925.  
  926. PRE void AVL_ScanTree (A0( struct TreeNode** tree ), A1( void (*scanfunc)(A0( APTR )) ), D0( char mode ))
  927. {
  928.     if (tree) {
  929.     if (*tree) {
  930.         if (mode == AVL_SCAN_PRAEFIX) (*scanfunc) (*tree);
  931.         AVL_ScanTree(&(LSON(*tree)),  scanfunc, mode);
  932.         if (mode == AVL_SCAN_INFIX  ) (*scanfunc) (*tree);
  933.         AVL_ScanTree(&(RSON(*tree)), scanfunc, mode);
  934.         if (mode == AVL_SCAN_POSTFIX) (*scanfunc) (*tree);
  935.     } /* if */
  936. #ifdef     AVL_DEBUG
  937.     } else {
  938.     ERROR ( AVL_errdisp2, AVL_err_scan, AVL_err_notree);
  939. #endif /* AVL_DEBUG */
  940.     } /* if */
  941. } /* AVL_ScanTree */
  942.  
  943.  
  944.  
  945.  
  946. /******************************************************************************
  947. *****  END AVL.c
  948. ******************************************************************************/
  949.  
  950.