source/ubiqx/ubi_AVLtree.c

   1 /* ========================================================================== **
   2  *                              ubi_AVLtree.c
   3  *
   4  *  Copyright (C) 1991-1998 by Christopher R. Hertel
   5  *
   6  *  Email: crh@ubiqx.mn.org
   7  * -------------------------------------------------------------------------- **
   8  *
   9  *  This module provides an implementation of AVL height balanced binary
  10  *  trees.  (Adelson-Velskii, Landis 1962)
  11  *
  12  *  This file implements the core of the height-balanced (AVL) tree management
  13  *  routines.  The header file, ubi_AVLtree.h, contains function prototypes
  14  *  for all "exported" functions.
  15  *
  16  * -------------------------------------------------------------------------- **
  17  *
  18  *  This library is free software; you can redistribute it and/or
  19  *  modify it under the terms of the GNU Library General Public
  20  *  License as published by the Free Software Foundation; either
  21  *  version 2 of the License, or (at your option) any later version.
  22  *
  23  *  This library is distributed in the hope that it will be useful,
  24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26  *  Library General Public License for more details.
  27  *
  28  *  You should have received a copy of the GNU Library General Public
  29  *  License along with this library; if not, write to the Free
  30  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  31  *
  32  * -------------------------------------------------------------------------- **
  33  *
  34  * Log: ubi_AVLtree.c,v
  35  * Revision 4.1  1998/05/20 04:35:50  crh
  36  * The C file now includes ubi_null.h.  See ubi_null.h for more info.
  37  *
  38  * Revision 4.0  1998/03/10 03:37:09  crh
  39  * Major changes.
  40  * By adding the AVL balance field to the base ubi_btNode structure, I no
  41  * longer need AVL-specific ReplaceNode(), SwapNodes(), and InitNode()
  42  * functions.  The Remove() function is also simplified.  It's all much
  43  * cleaner.
  44  * This is rev. 4.0.  The 3.x series was dropped.
  45  *
  46  * Revision 2.5  1997/12/23 04:00:42  crh
  47  * In this version, all constants & macros defined in the header file have
  48  * the ubi_tr prefix.  Also cleaned up anything that gcc complained about
  49  * when run with '-pedantic -fsyntax-only -Wall'.
  50  *
  51  * Revision 2.4  1997/07/26 04:36:20  crh
  52  * Andrew Leppard, aka "Grazgur", discovered that I still had my brains tied
  53  * on backwards with respect to node deletion.  I did some more digging and
  54  * discovered that I was not changing the balance values correctly in the
  55  * single rotation functions.  Double rotation was working correctly because
  56  * the formula for changing the balance values is the same for insertion or
  57  * deletion.  Not so for single rotation.
  58  *
  59  * I have tested the fix by loading the tree with over 44 thousand names,
  60  * deleting 2,629 of them (all those in which the second character is 'u')
  61  * and then walking the tree recursively to verify that the balance factor of
  62  * each node is correct.  Passed.
  63  *
  64  * Thanks Andrew!
  65  *
  66  * Also:
  67  * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
  68  * + Rewrote the ubi_tr<func> macros because they weren't doing what I'd
  69  *   hoped they would do (see the bottom of the header file).  They work now.
  70  *
  71  * Revision 2.3  1997/06/03 04:41:35  crh
  72  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
  73  * problems.
  74  *
  75  * Revision 2.2  1995/10/03 22:16:01  CRH
  76  * Ubisized!
  77  *
  78  * Revision 2.1  95/03/09  23:45:59  CRH
  79  * Added the ModuleID static string and function.  These modules are now
  80  * self-identifying.
  81  *
  82  * Revision 2.0  95/03/05  14:10:51  CRH
  83  * This revision of ubi_AVLtree coincides with revision 2.0 of ubi_BinTree,
  84  * and so includes all of the changes to that module.  In addition, a bug in
  85  * the node deletion process has been fixed.
  86  *
  87  * After rewriting the Locate() function in ubi_BinTree, I decided that it was
  88  * time to overhaul this module.  In the process, I discovered a bug related
  89  * to node deletion.  To fix the bug, I wrote function Debalance().  A quick
  90  * glance will show that it is very similar to the Rebalance() function.  In
  91  * previous versions of this module, I tried to include the functionality of
  92  * Debalance() within Rebalance(), with poor results.
  93  *
  94  * Revision 1.0  93/10/15  22:58:56  CRH
  95  * With this revision, I have added a set of #define's that provide a single,
  96  * standard API to all existing tree modules.  Until now, each of the three
  97  * existing modules had a different function and typedef prefix, as follows:
  98  *
  99  *       Module        Prefix
 100  *     ubi_BinTree     ubi_bt
 101  *     ubi_AVLtree     ubi_avl
 102  *     ubi_SplayTree   ubi_spt
 103  *
 104  * To further complicate matters, only those portions of the base module
 105  * (ubi_BinTree) that were superceeded in the new module had the new names.
 106  * For example, if you were using ubi_SplayTree, the locate function was
 107  * called "ubi_sptLocate", but the next and previous functions remained
 108  * "ubi_btNext" and "ubi_btPrev".
 109  *
 110  * This was not too terrible if you were familiar with the modules and knew
 111  * exactly which tree model you wanted to use.  If you wanted to be able to
 112  * change modules (for speed comparisons, etc), things could get messy very
 113  * quickly.
 114  *
 115  * So, I have added a set of defined names that get redefined in any of the
 116  * descendant modules.  To use this standardized interface in your code,
 117  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
 118  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
 119  * datatype names for the module that you are using.  Just remember to
 120  * include the header for that module in your program file.  Because these
 121  * names are handled by the preprocessor, there is no added run-time
 122  * overhead.
 123  *
 124  * Note that the original names do still exist, and can be used if you wish
 125  * to write code directly to a specific module.  This should probably only be
 126  * done if you are planning to implement a new descendant type, such as
 127  * red/black trees.  CRH
 128  *
 129  *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
 130  *
 131  *  ========================================================================= **
 132  */
 133
 134 #include "ubi_null.h"     /* ubiqx NULL source.       */
 135 #include "ubi_AVLtree.h"  /* Header for THIS module.  */
 136
 137 /* ========================================================================== **
 138  * Static data.
 139  */
 140
 141 static char ModuleID[] = "ubi_AVLtree\n\
 142 \tRevision: 4.1 \n\
 143 \tDate: 1998/05/20 04:35:50 \n\
 144 \tAuthor: crh \n";
 145
 146 /* ========================================================================== **
 147  * The next set of functions are the AVL balancing routines.  There are left
 148  * and right, single and double rotations.  The rotation routines handle the
 149  * rotations and reconnect all tree pointers that might get confused by the
 150  * rotations.  A pointer to the new subtree root node is returned.
 151  *
 152  * Note that L1 and R1 are identical, except that all the RIGHTs and LEFTs
 153  * are reversed.  The same is true for L2 and R2.  I'm sure that there is
 154  * a clever way to reduce the amount of code by combining these functions,
 155  * but it might involve additional overhead, and it would probably be a pain
 156  * to read, debug, etc.
 157  * -------------------------------------------------------------------------- **
 158  */
 159
 160 static ubi_btNodePtr L1( ubi_btNodePtr p )
 161   /* ------------------------------------------------------------------------ **
 162    * Single rotate left.
 163    *
 164    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 165    *  Output: A pointer to the new root of the same subtree (now that node
 166    *          p has been moved).
 167    * ------------------------------------------------------------------------ **
 168    */
 169   {
 170   ubi_btNodePtr tmp;
 171
 172   tmp                      = p->Link[ubi_trRIGHT];
 173   p->Link[ubi_trRIGHT]     = tmp->Link[ubi_trLEFT];
 174   tmp->Link[ubi_trLEFT]    = p;
 175
 176   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
 177   tmp->gender              = p->gender;
 178   if(tmp->Link[ubi_trPARENT])
 179     (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
 180   p->Link[ubi_trPARENT]    = tmp;
 181   p->gender                = ubi_trLEFT;
 182   if( p->Link[ubi_trRIGHT] )
 183     {
 184     p->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = p;
 185     (p->Link[ubi_trRIGHT])->gender           = ubi_trRIGHT;
 186     }
 187   p->balance -= ubi_trNormalize( tmp->balance );
 188   (tmp->balance)--;
 189   return( tmp );
 190   } /* L1 */
 191
 192 static ubi_btNodePtr R1( ubi_btNodePtr p )
 193   /* ------------------------------------------------------------------------ **
 194    * Single rotate right.
 195    *
 196    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 197    *  Output: A pointer to the new root of the same subtree (now that node
 198    *          p has been moved).
 199    * ------------------------------------------------------------------------ **
 200    */
 201   {
 202   ubi_btNodePtr tmp;
 203
 204   tmp                      = p->Link[ubi_trLEFT];
 205   p->Link[ubi_trLEFT]      = tmp->Link[ubi_trRIGHT];
 206   tmp->Link[ubi_trRIGHT]   = p;
 207
 208   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
 209   tmp->gender              = p->gender;
 210   if(tmp->Link[ubi_trPARENT])
 211     (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
 212   p->Link[ubi_trPARENT]    = tmp;
 213   p->gender                = ubi_trRIGHT;
 214   if(p->Link[ubi_trLEFT])
 215     {
 216     p->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = p;
 217     p->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
 218     }
 219   p->balance -= ubi_trNormalize( tmp->balance );
 220   (tmp->balance)++;
 221   return( tmp );
 222   } /* R1 */
 223
 224 static ubi_btNodePtr L2( ubi_btNodePtr tree )
 225   /* ------------------------------------------------------------------------ **
 226    * Double rotate left.
 227    *
 228    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 229    *  Output: A pointer to the new root of the same subtree (now that node
 230    *          p has been moved).
 231    * ------------------------------------------------------------------------ **
 232    */
 233   {
 234   ubi_btNodePtr tmp, newroot;
 235
 236   tmp                         = tree->Link[ubi_trRIGHT];
 237   newroot                     = tmp->Link[ubi_trLEFT];
 238   tmp->Link[ubi_trLEFT]       = newroot->Link[ubi_trRIGHT];
 239   newroot->Link[ubi_trRIGHT]  = tmp;
 240   tree->Link[ubi_trRIGHT]     = newroot->Link[ubi_trLEFT];
 241   newroot->Link[ubi_trLEFT]   = tree;
 242
 243   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
 244   newroot->gender             = tree->gender;
 245   tree->Link[ubi_trPARENT]    = newroot;
 246   tree->gender                = ubi_trLEFT;
 247   tmp->Link[ubi_trPARENT]     = newroot;
 248   tmp->gender                 = ubi_trRIGHT;
 249
 250   if( tree->Link[ubi_trRIGHT] )
 251     {
 252     tree->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = tree;
 253     tree->Link[ubi_trRIGHT]->gender             = ubi_trRIGHT;
 254     }
 255   if( tmp->Link[ubi_trLEFT] )
 256     {
 257     tmp->Link[ubi_trLEFT]->Link[ubi_trPARENT]   = tmp;
 258     tmp->Link[ubi_trLEFT]->gender               = ubi_trLEFT;
 259     }
 260   if(newroot->Link[ubi_trPARENT])
 261     newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
 262
 263   switch( newroot->balance )
 264     {
 265     case ubi_trLEFT :
 266       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trRIGHT; break;
 267     case ubi_trEQUAL:
 268       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
 269     case ubi_trRIGHT:
 270       tree->balance = ubi_trLEFT;  tmp->balance = ubi_trEQUAL; break;
 271     }
 272   newroot->balance = ubi_trEQUAL;
 273   return( newroot );
 274   } /* L2 */
 275
 276 static ubi_btNodePtr R2( ubi_btNodePtr tree )
 277   /* ------------------------------------------------------------------------ **
 278    * Double rotate right.
 279    *
 280    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 281    *  Output: A pointer to the new root of the same subtree (now that node
 282    *          p has been moved).
 283    * ------------------------------------------------------------------------ **
 284    */
 285   {
 286   ubi_btNodePtr tmp, newroot;
 287
 288   tmp                         = tree->Link[ubi_trLEFT];
 289   newroot                     = tmp->Link[ubi_trRIGHT];
 290   tmp->Link[ubi_trRIGHT]      = newroot->Link[ubi_trLEFT];
 291   newroot->Link[ubi_trLEFT]   = tmp;
 292   tree->Link[ubi_trLEFT]      = newroot->Link[ubi_trRIGHT];
 293   newroot->Link[ubi_trRIGHT]  = tree;
 294
 295   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
 296   newroot->gender             = tree->gender;
 297   tree->Link[ubi_trPARENT]    = newroot;
 298   tree->gender                = ubi_trRIGHT;
 299   tmp->Link[ubi_trPARENT]     = newroot;
 300   tmp->gender                 = ubi_trLEFT;
 301
 302   if( tree->Link[ubi_trLEFT] )
 303     {
 304     tree->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = tree;
 305     tree->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
 306     }
 307   if( tmp->Link[ubi_trRIGHT] )
 308     {
 309     tmp->Link[ubi_trRIGHT]->Link[ubi_trPARENT]  = tmp;
 310     tmp->Link[ubi_trRIGHT]->gender              = ubi_trRIGHT;
 311     }
 312   if(newroot->Link[ubi_trPARENT])
 313     newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
 314
 315   switch( newroot->balance )
 316     {
 317     case ubi_trLEFT  :
 318       tree->balance = ubi_trRIGHT; tmp->balance = ubi_trEQUAL; break;
 319     case ubi_trEQUAL :
 320       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
 321     case ubi_trRIGHT :
 322       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trLEFT;  break;
 323     }
 324   newroot->balance = ubi_trEQUAL;
 325   return( newroot );
 326   } /* R2 */
 327
 328
 329 static ubi_btNodePtr Adjust( ubi_btNodePtr p, char LorR )
 330   /* ------------------------------------------------------------------------ **
 331    * Adjust the balance value at node *p.  If necessary, rotate the subtree
 332    * rooted at p.
 333    *
 334    *  Input:  p    -  A pointer to the node to be adjusted.  One of the
 335    *                  subtrees of this node has changed height, so the
 336    *                  balance value at this node must be adjusted, possibly
 337    *                  by rotating the tree at this node.
 338    *          LorR -  Indicates the TALLER subtree.
 339    *
 340    *  Output: A pointer to the (possibly new) root node of the subtree.
 341    *
 342    *  Notes:  This function may be called after a node has been added *or*
 343    *          deleted, so LorR indicates the TALLER subtree.
 344    * ------------------------------------------------------------------------ **
 345    */
 346   {
 347   if( p->balance != LorR )
 348     p->balance += ubi_trNormalize(LorR);
 349   else
 350     {
 351     char tallerbal;  /* Balance value of the root of the taller subtree of p. */
 352
 353     tallerbal = p->Link[(int)LorR]->balance;
 354     if( ( ubi_trEQUAL == tallerbal ) || ( p->balance == tallerbal ) )
 355       p = ( (ubi_trLEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
 356     else
 357       p = ( (ubi_trLEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
 358     }
 359   return( p );
 360   } /* Adjust */
 361
 362 static ubi_btNodePtr Rebalance( ubi_btNodePtr Root,
 363                                 ubi_btNodePtr subtree,
 364                                 char          LorR )
 365   /* ------------------------------------------------------------------------ **
 366    * Rebalance the tree following an insertion.
 367    *
 368    *  Input:  Root    - A pointer to the root node of the whole tree.
 369    *          subtree - A pointer to the node that has just gained a new
 370    *                    child.
 371    *          LorR    - Gender of the child that has just been gained.
 372    *
 373    *  Output: A pointer to the (possibly new) root of the AVL tree.
 374    *          Rebalancing the tree moves nodes around a bit, so the node
 375    *          that *was* the root, may not be the root when we're finished.
 376    *
 377    *  Notes:  Rebalance() must walk up the tree from where we are (which is
 378    *          where the latest change occurred), rebalancing the subtrees
 379    *          along the way.  The rebalancing operation can stop if the
 380    *          change at the current subtree root won't affect the rest of
 381    *          the tree.  In the case of an addition, if a subtree root's
 382    *          balance becomes EQUAL, then we know that the height of that
 383    *          subtree has not changed, so we can exit.
 384    * ------------------------------------------------------------------------ **
 385    */
 386   {
 387   while( subtree )
 388     {
 389     subtree = Adjust( subtree, LorR );
 390     if( ubi_trPARENT == subtree->gender )
 391       return( subtree );
 392     if( ubi_trEQUAL == subtree->balance )
 393       return( Root );
 394     LorR = subtree->gender;
 395     subtree = subtree->Link[ubi_trPARENT];
 396     }
 397   return( Root );
 398   } /* Rebalance */
 399
 400 static ubi_btNodePtr Debalance( ubi_btNodePtr Root,
 401                                 ubi_btNodePtr subtree,
 402                                 char          LorR )
 403   /* ------------------------------------------------------------------------ **
 404    * Rebalance the tree following a deletion.
 405    *
 406    *  Input:  Root    - A pointer to the root node of the whole tree.
 407    *          subtree - A pointer to the node who's child has just "left the
 408    *                    nest".
 409    *          LorR    - Gender of the child that left.
 410    *
 411    *  Output: A pointer to the (possibly new) root of the AVL tree.
 412    *          Rebalancing the tree moves nodes around a bit, so the node
 413    *          that *was* the root, may not be the root when we're finished.
 414    *
 415    *  Notes:  Debalance() is subtly different from Rebalance() (above) in
 416    *          two respects.
 417    *            * When it calls Adjust(), it passes the *opposite* of LorR.
 418    *              This is because LorR, as passed into Debalance() indicates
 419    *              the shorter subtree.  As we move up the tree, LorR is
 420    *              assigned the gender of the node that we are leaving (i.e.,
 421    *              the subtree that we just rebalanced).
 422    *            * We know that a subtree has not changed height if the
 423    *              balance becomes LEFT or RIGHT.  This is the *opposite* of
 424    *              what happens in Rebalance().
 425    * ------------------------------------------------------------------------ **
 426    */
 427   {
 428   while( subtree )
 429     {
 430     subtree = Adjust( subtree, ubi_trRevWay(LorR) );
 431     if( ubi_trPARENT == subtree->gender )
 432       return( subtree );
 433     if( ubi_trEQUAL != subtree->balance )
 434       return( Root );
 435     LorR = subtree->gender;
 436     subtree = subtree->Link[ubi_trPARENT];
 437     }
 438   return( Root );
 439   } /* Debalance */
 440
 441 /* ========================================================================== **
 442  *         Public, exported (ie. not static-ly declared) functions...
 443  * -------------------------------------------------------------------------- **
 444  */
 445
 446 ubi_trBool ubi_avlInsert( ubi_btRootPtr  RootPtr,
 447                           ubi_btNodePtr  NewNode,
 448                           ubi_btItemPtr  ItemPtr,
 449                           ubi_btNodePtr *OldNode )
 450   /* ------------------------------------------------------------------------ **
 451    * This function uses a non-recursive algorithm to add a new element to
 452    * the tree.
 453    *
 454    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
 455    *                       the root of the tree to which NewNode is to be added.
 456    *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
 457    *                       part of any tree.
 458    *           ItemPtr  -  A pointer to the sort key that is stored within
 459    *                       *NewNode.  ItemPtr MUST point to information stored
 460    *                       in *NewNode or an EXACT DUPLICATE.  The key data
 461    *                       indicated by ItemPtr is used to place the new node
 462    *                       into the tree.
 463    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
 464    *                       the tree, a duplicate node may be found.  If
 465    *                       duplicates are allowed, then the new node will
 466    *                       be simply placed into the tree.  If duplicates
 467    *                       are not allowed, however, then one of two things
 468    *                       may happen.
 469    *                       1) if overwritting *is not* allowed, this
 470    *                          function will return FALSE (indicating that
 471    *                          the new node could not be inserted), and
 472    *                          *OldNode will point to the duplicate that is
 473    *                          still in the tree.
 474    *                       2) if overwritting *is* allowed, then this
 475    *                          function will swap **OldNode for *NewNode.
 476    *                          In this case, *OldNode will point to the node
 477    *                          that was removed (thus allowing you to free
 478    *                          the node).
 479    *                          **  If you are using overwrite mode, ALWAYS  **
 480    *                          ** check the return value of this parameter! **
 481    *                 Note: You may pass NULL in this parameter, the
 482    *                       function knows how to cope.  If you do this,
 483    *                       however, there will be no way to return a
 484    *                       pointer to an old (ie. replaced) node (which is
 485    *                       a problem if you are using overwrite mode).
 486    *
 487    *  Output:  a boolean value indicating success or failure.  The function
 488    *           will return FALSE if the node could not be added to the tree.
 489    *           Such failure will only occur if duplicates are not allowed,
 490    *           nodes cannot be overwritten, AND a duplicate key was found
 491    *           within the tree.
 492    * ------------------------------------------------------------------------ **
 493    */
 494   {
 495   ubi_btNodePtr OtherP;
 496
 497   if( !(OldNode) )
 498     OldNode = &OtherP;
 499   if( ubi_btInsert( RootPtr,
 500                     (ubi_btNodePtr)NewNode,
 501                     ItemPtr,
 502                     (ubi_btNodePtr *)OldNode ) )
 503     {
 504     if( (*OldNode) )
 505       NewNode->balance = (*OldNode)->balance;
 506     else
 507       {
 508       NewNode->balance = ubi_trEQUAL;
 509       RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_btNodePtr)RootPtr->root,
 510                                                 NewNode->Link[ubi_trPARENT],
 511                                                 NewNode->gender );
 512       }
 513     return( ubi_trTRUE );
 514     }
 515   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
 516   } /* ubi_avlInsert */
 517
 518 ubi_btNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
 519                              ubi_btNodePtr  DeadNode )
 520   /* ------------------------------------------------------------------------ **
 521    * This function removes the indicated node from the tree, after which the
 522    * tree is rebalanced.
 523    *
 524    *  Input:  RootPtr  -  A pointer to the header of the tree that contains
 525    *                      the node to be removed.
 526    *          DeadNode -  A pointer to the node that will be removed.
 527    *
 528    *  Output: This function returns a pointer to the node that was removed
 529    *          from the tree (ie. the same as DeadNode).
 530    *
 531    *  Note:   The node MUST be in the tree indicated by RootPtr.  If not,
 532    *          strange and evil things will happen to your trees.
 533    *
 534    * ------------------------------------------------------------------------ **
 535    */
 536   {
 537   /* Let the base binary tree module do the removal, then rebalance. */
 538   if( ubi_btRemove( RootPtr, DeadNode ) )
 539     RootPtr->root = Debalance( RootPtr->root,
 540                                DeadNode->Link[ubi_trPARENT],
 541                                DeadNode->gender );
 542   return( DeadNode );
 543   } /* ubi_avlRemove */
 544
 545 int ubi_avlModuleID( int size, char *list[] )
 546   /* ------------------------------------------------------------------------ **
 547    * Returns a set of strings that identify the module.
 548    *
 549    *  Input:  size  - The number of elements in the array <list>.
 550    *          list  - An array of pointers of type (char *).  This array
 551    *                  should, initially, be empty.  This function will fill
 552    *                  in the array with pointers to strings.
 553    *  Output: The number of elements of <list> that were used.  If this value
 554    *          is less than <size>, the values of the remaining elements are
 555    *          not guaranteed.
 556    *
 557    *  Notes:  Please keep in mind that the pointers returned indicate strings
 558    *          stored in static memory.  Don't free() them, don't write over
 559    *          them, etc.  Just read them.
 560    * ------------------------------------------------------------------------ **
 561    */
 562   {
 563   if( size > 0 )
 564     {
 565     list[0] = ModuleID;
 566     if( size > 1 )
 567       return( 1 + ubi_btModuleID( --size, &(list[1]) ) );
 568     return( 1 );
 569     }
 570   return( 0 );
 571   } /* ubi_avlModuleID */
 572
 573 /* ============================== The End ============================== */