source/ubiqx/ubi_AVLtree.c

   1 /* ========================================================================== **
   2  *                              ubi_AVLtree.c
   3  *
   4  *  Copyright (C) 1991-1997 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 header file contains the basic AVL structure and pointer typedefs
  13  *  as well as the prototypes needed to access the functions in the AVL
  14  *  module ubi_AVLtree.  The .c file implements the low-level height balancing
  15  *  routines that manage the AVL tree, plus all of the basic primops for
  16  *  adding, searching for, and deleting nodes.
  17  *
  18  * -------------------------------------------------------------------------- **
  19  *
  20  *  This library is free software; you can redistribute it and/or
  21  *  modify it under the terms of the GNU Library General Public
  22  *  License as published by the Free Software Foundation; either
  23  *  version 2 of the License, or (at your option) any later version.
  24  *
  25  *  This library is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  28  *  Library General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU Library General Public
  31  *  License along with this library; if not, write to the Free
  32  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  33  *
  34  * -------------------------------------------------------------------------- **
  35  *
  36  * Log: ubi_AVLtree.c,v
  37  * Revision 3.1  1997/12/18 06:26:51  crh
  38  * Fixed some comment bugs.
  39  *
  40  * Revision 3.0  1997/12/08 05:38:55  crh
  41  * This is a new major revision level.  The handling of the pointers in the
  42  * ubi_trNode structure was redesigned.  The result is that there are fewer
  43  * macros floating about, and fewer cases in which values have to be
  44  * incremented or decremented.  See ubi_BinTree for more information.
  45  *
  46  * Revision 2; 1995/03/05 - 1997/12/07:
  47  * An overhaul to the node delete process.  I had gotten it wrong in a
  48  * couple of places, thought I'd fixed it, and then found that I'd missed
  49  * something more.  Thanks to Andrew Leppard for the bug report!
  50  *
  51  * Revision 1;  93/10/15 - 95/03/05:
  52  * Added the ubi_tr defines.  See ubi_BinTree.h for more info.
  53  *
  54  *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
  55  *
  56  *  ========================================================================= **
  57  */
  58
  59 #include "ubi_AVLtree.h"            /* Header for THIS module.             */
  60 #include <stdlib.h>                 /* Standard C definitions, etc.        */
  61
  62 /* ========================================================================== **
  63  * Static data.
  64  */
  65
  66 static char ModuleID[] = "ubi_AVLtree\n\
  67 \tRevision: 3.1\n\
  68 \tDate: 1997/12/18 06:26:51 GMT\n\
  69 \tAuthor: crh\n";
  70
  71 /* ========================================================================== **
  72  * The next set of functions are the AVL balancing routines.  There are left
  73  * and right, single and double rotations.  The rotation routines handle the
  74  * rotations and reconnect all tree pointers that might get confused by the
  75  * rotations.  A pointer to the new subtree root node is returned.
  76  *
  77  * Note that L1 and R1 are identical, except that all the RIGHTs and LEFTs
  78  * are reversed.  The same is true for L2 and R2.  I'm sure that there is
  79  * a clever way to reduce the amount of code by combining these functions,
  80  * but it might involve additional overhead, and it would probably be a pain
  81  * to read, debug, etc.
  82  * -------------------------------------------------------------------------- **
  83  */
  84
  85 static ubi_avlNodePtr L1( ubi_avlNodePtr p )
  86   /* ------------------------------------------------------------------------ **
  87    * Single rotate left.
  88    *
  89    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
  90    *  Output: A pointer to the new root of the same subtree (now that node
  91    *          p has been moved).
  92    * ------------------------------------------------------------------------ **
  93    */
  94   {
  95   ubi_avlNodePtr tmp;
  96
  97   tmp                      = p->Link[ubi_trRIGHT];
  98   p->Link[ubi_trRIGHT]     = tmp->Link[ubi_trLEFT];
  99   tmp->Link[ubi_trLEFT]    = p;
 100
 101   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
 102   tmp->gender              = p->gender;
 103   if(tmp->Link[ubi_trPARENT])
 104     (tmp->Link[ubi_trPARENT])->Link[(tmp->gender)] = tmp;
 105   p->Link[ubi_trPARENT]    = tmp;
 106   p->gender                = ubi_trLEFT;
 107   if( p->Link[ubi_trRIGHT] )
 108     {
 109     p->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = p;
 110     (p->Link[ubi_trRIGHT])->gender           = ubi_trRIGHT;
 111     }
 112   p->balance -= tmp->balance;
 113   (tmp->balance)--;
 114   return( tmp );
 115   } /* L1 */
 116
 117 static ubi_avlNodePtr R1( ubi_avlNodePtr p )
 118   /* ------------------------------------------------------------------------ **
 119    * Single rotate right.
 120    *
 121    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 122    *  Output: A pointer to the new root of the same subtree (now that node
 123    *          p has been moved).
 124    * ------------------------------------------------------------------------ **
 125    */
 126   {
 127   ubi_avlNodePtr tmp;
 128
 129   tmp                      = p->Link[ubi_trLEFT];
 130   p->Link[ubi_trLEFT]      = tmp->Link[ubi_trRIGHT];
 131   tmp->Link[ubi_trRIGHT]   = p;
 132
 133   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
 134   tmp->gender              = p->gender;
 135   if(tmp->Link[ubi_trPARENT])
 136     (tmp->Link[ubi_trPARENT])->Link[(tmp->gender)] = tmp;
 137   p->Link[ubi_trPARENT]    = tmp;
 138   p->gender                = ubi_trRIGHT;
 139   if(p->Link[ubi_trLEFT])
 140     {
 141     p->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = p;
 142     p->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
 143     }
 144   p->balance -= tmp->balance;
 145   (tmp->balance)++;
 146   return( tmp );
 147   } /* R1 */
 148
 149 static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
 150   /* ------------------------------------------------------------------------ **
 151    * Double rotate left.
 152    *
 153    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 154    *  Output: A pointer to the new root of the same subtree (now that node
 155    *          p has been moved).
 156    * ------------------------------------------------------------------------ **
 157    */
 158   {
 159   ubi_avlNodePtr tmp, newroot;
 160
 161   tmp                         = tree->Link[ubi_trRIGHT];
 162   newroot                     = tmp->Link[ubi_trLEFT];
 163   tmp->Link[ubi_trLEFT]       = newroot->Link[ubi_trRIGHT];
 164   newroot->Link[ubi_trRIGHT]  = tmp;
 165   tree->Link[ubi_trRIGHT]     = newroot->Link[ubi_trLEFT];
 166   newroot->Link[ubi_trLEFT]   = tree;
 167
 168   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
 169   newroot->gender             = tree->gender;
 170   tree->Link[ubi_trPARENT]    = newroot;
 171   tree->gender                = ubi_trLEFT;
 172   tmp->Link[ubi_trPARENT]     = newroot;
 173   tmp->gender                 = ubi_trRIGHT;
 174
 175   if( tree->Link[ubi_trRIGHT] )
 176     {
 177     tree->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = tree;
 178     tree->Link[ubi_trRIGHT]->gender             = ubi_trRIGHT;
 179     }
 180   if( tmp->Link[ubi_trLEFT] )
 181     {
 182     tmp->Link[ubi_trLEFT]->Link[ubi_trPARENT]   = tmp;
 183     tmp->Link[ubi_trLEFT]->gender               = ubi_trLEFT;
 184     }
 185   if(newroot->Link[ubi_trPARENT])
 186     newroot->Link[ubi_trPARENT]->Link[newroot->gender] = newroot;
 187
 188   switch( newroot->balance )
 189     {
 190     case ubi_trLEFT :
 191       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trRIGHT; break;
 192     case ubi_trEQUAL:
 193       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
 194     case ubi_trRIGHT:
 195       tree->balance = ubi_trLEFT;  tmp->balance = ubi_trEQUAL; break;
 196     }
 197   newroot->balance = ubi_trEQUAL;
 198   return( newroot );
 199   } /* L2 */
 200
 201 static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
 202   /* ------------------------------------------------------------------------ **
 203    * Double rotate right.
 204    *
 205    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
 206    *  Output: A pointer to the new root of the same subtree (now that node
 207    *          p has been moved).
 208    * ------------------------------------------------------------------------ **
 209    */
 210   {
 211   ubi_avlNodePtr tmp, newroot;
 212
 213   tmp                         = tree->Link[ubi_trLEFT];
 214   newroot                     = tmp->Link[ubi_trRIGHT];
 215   tmp->Link[ubi_trRIGHT]      = newroot->Link[ubi_trLEFT];
 216   newroot->Link[ubi_trLEFT]   = tmp;
 217   tree->Link[ubi_trLEFT]      = newroot->Link[ubi_trRIGHT];
 218   newroot->Link[ubi_trRIGHT]  = tree;
 219
 220   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
 221   newroot->gender             = tree->gender;
 222   tree->Link[ubi_trPARENT]    = newroot;
 223   tree->gender                = ubi_trRIGHT;
 224   tmp->Link[ubi_trPARENT]     = newroot;
 225   tmp->gender                 = ubi_trLEFT;
 226
 227   if( tree->Link[ubi_trLEFT] )
 228     {
 229     tree->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = tree;
 230     tree->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
 231     }
 232   if( tmp->Link[ubi_trRIGHT] )
 233     {
 234     tmp->Link[ubi_trRIGHT]->Link[ubi_trPARENT]  = tmp;
 235     tmp->Link[ubi_trRIGHT]->gender              = ubi_trRIGHT;
 236     }
 237   if(newroot->Link[ubi_trPARENT])
 238     newroot->Link[ubi_trPARENT]->Link[newroot->gender] = newroot;
 239
 240   switch( newroot->balance )
 241     {
 242     case ubi_trLEFT  :
 243       tree->balance = ubi_trRIGHT; tmp->balance = ubi_trEQUAL; break;
 244     case ubi_trEQUAL :
 245       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
 246     case ubi_trRIGHT :
 247       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trLEFT;  break;
 248     }
 249   newroot->balance = ubi_trEQUAL;
 250   return( newroot );
 251   } /* R2 */
 252
 253
 254 static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, signed char LorR )
 255   /* ------------------------------------------------------------------------ **
 256    * Adjust the balance value at node *p.  If necessary, rotate the subtree
 257    * rooted at p.
 258    *
 259    *  Input:  p    -  A pointer to the node to be adjusted.  One of the
 260    *                  subtrees of this node has changed height, so the
 261    *                  balance value at this node must be adjusted, possibly
 262    *                  by rotating the tree at this node.
 263    *          LorR -  Indicates the TALLER subtree.
 264    *
 265    *  Output: A pointer to the (possibly new) root node of the subtree.
 266    *
 267    *  Notes:  This function may be called after a node has been added *or*
 268    *          deleted, so LorR indicates the TALLER subtree.
 269    * ------------------------------------------------------------------------ **
 270    */
 271   {
 272   if( p->balance != LorR )
 273     p->balance += LorR;
 274   else
 275     {
 276     signed char tallerbal;  /* Balance of root of the taller subtree of p. */
 277
 278     tallerbal = p->Link[LorR]->balance;
 279     if( ( ubi_trEQUAL == tallerbal ) || ( p->balance == tallerbal ) )
 280       p = ( (ubi_trLEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
 281     else
 282       p = ( (ubi_trLEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
 283     }
 284   return( p );
 285   } /* Adjust */
 286
 287 static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
 288                                  ubi_avlNodePtr subtree,
 289                                  signed char    LorR )
 290   /* ------------------------------------------------------------------------ **
 291    * Rebalance the tree following an insertion.
 292    *
 293    *  Input:  Root    - A pointer to the root node of the whole tree.
 294    *          subtree - A pointer to the node that has just gained a new
 295    *                    child.
 296    *          LorR    - Gender of the child that has just been gained.
 297    *
 298    *  Output: A pointer to the (possibly new) root of the AVL tree.
 299    *          Rebalancing the tree moves nodes around a bit, so the node
 300    *          that *was* the root, may not be the root when we're finished.
 301    *
 302    *  Notes:  Rebalance() must walk up the tree from where we are (which is
 303    *          where the latest change occurred), rebalancing the subtrees
 304    *          along the way.  The rebalancing operation can stop if the
 305    *          change at the current subtree root won't affect the rest of
 306    *          the tree.  In the case of an addition, if a subtree root's
 307    *          balance becomes EQUAL, then we know that the height of that
 308    *          subtree has not changed, so we can exit.
 309    * ------------------------------------------------------------------------ **
 310    */
 311   {
 312   while( subtree )
 313     {
 314     subtree = Adjust( subtree, LorR );
 315     if( ubi_trPARENT == subtree->gender )
 316       return( subtree );
 317     if( ubi_trEQUAL == subtree->balance )
 318       return( Root );
 319     LorR = subtree->gender;
 320     subtree = subtree->Link[ubi_trPARENT];
 321     }
 322   return( Root );
 323   } /* Rebalance */
 324
 325 static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
 326                                  ubi_avlNodePtr subtree,
 327                                  signed char    LorR )
 328   /* ------------------------------------------------------------------------ **
 329    * Rebalance the tree following a deletion.
 330    *
 331    *  Input:  Root    - A pointer to the root node of the whole tree.
 332    *          subtree - A pointer to the node who's child has just "left the
 333    *                    nest".
 334    *          LorR    - Gender of the child that left.
 335    *
 336    *  Output: A pointer to the (possibly new) root of the AVL tree.
 337    *          Rebalancing the tree moves nodes around a bit, so the node
 338    *          that *was* the root, may not be the root when we're finished.
 339    *
 340    *  Notes:  Debalance() is subtly different from Rebalance() (above) in
 341    *          two respects.
 342    *            * When it calls Adjust(), it passes the *opposite* of LorR.
 343    *              This is because LorR, as passed into Debalance() indicates
 344    *              the shorter subtree.  As we move up the tree, LorR is
 345    *              assigned the gender of the node that we are leaving (i.e.,
 346    *              the subtree that we just rebalanced).
 347    *            * We know that a subtree has not changed height if the
 348    *              balance becomes LEFT or RIGHT.  This is the *opposite* of
 349    *              what happens in Rebalance().
 350    * ------------------------------------------------------------------------ **
 351    */
 352   {
 353   while( subtree )
 354     {
 355     subtree = Adjust( subtree, ubi_trRevWay(LorR) );
 356     if( ubi_trPARENT == subtree->gender )
 357       return( subtree );
 358     if( ubi_trEQUAL != subtree->balance )
 359       return( Root );
 360     LorR = subtree->gender;
 361     subtree = subtree->Link[ubi_trPARENT];
 362     }
 363   return( Root );
 364   } /* Debalance */
 365
 366
 367 /* -------------------------------------------------------------------------- **
 368  * The next two functions are used for general tree manipulation.  They are
 369  * each slightly different from their ubi_BinTree counterparts.
 370  * -------------------------------------------------------------------------- **
 371  */
 372
 373 static void ReplaceNode( ubi_avlNodePtr *parent,
 374                          ubi_avlNodePtr  oldnode,
 375                          ubi_avlNodePtr  newnode )
 376   /* ------------------------------------------------------------------------ **
 377    * Remove node oldnode from the tree, replacing it with node newnode.
 378    *
 379    * Input:
 380    *  parent   - A pointer to he parent pointer of the node to be
 381    *             replaced.  <parent> may point to the Link[] field of
 382    *             a parent node, or it may indicate the root pointer at
 383    *             the top of the tree.
 384    *  oldnode  - A pointer to the node that is to be replaced.
 385    *  newnode  - A pointer to the node that is to be installed in the
 386    *             place of <*oldnode>.
 387    *
 388    * Notes:    Don't forget to free oldnode.
 389    *           The only difference between this function and the ubi_bt
 390    *           version is that the node size is sizeof( ubi_avlNode ), not
 391    *           sizeof( ubi_btNode ).
 392    * ------------------------------------------------------------------------ **
 393    */
 394   {
 395   register int i;
 396   register int avlNodeSize = sizeof( ubi_avlNode );
 397
 398   for( i = 0; i < avlNodeSize; i++ )
 399     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
 400   (*parent) = newnode;
 401
 402   if(oldnode->Link[ubi_trLEFT ] )
 403     (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = newnode;
 404   if(oldnode->Link[ubi_trRIGHT] )
 405     (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode;
 406   } /* ReplaceNode */
 407
 408 static void SwapNodes( ubi_btRootPtr  RootPtr,
 409                        ubi_avlNodePtr Node1,
 410                        ubi_avlNodePtr Node2 )
 411   /* ------------------------------------------------------------------------ **
 412    * This function swaps two nodes in the tree.  Node1 will take the place of
 413    * Node2, and Node2 will fill in the space left vacant by Node 1.
 414    *
 415    * Input:
 416    *  RootPtr  - pointer to the tree header structure for this tree.
 417    *  Node1    - \
 418    *              > These are the two nodes which are to be swapped.
 419    *  Node2    - /
 420    *
 421    * Notes:
 422    *  This function does a three step swap, using a dummy node as a place
 423    *  holder.  This function is used by ubi_avlRemove().
 424    *  The only difference between this function and its ubi_bt counterpart
 425    *  is that the nodes are ubi_avlNodes, not ubi_btNodes.
 426    * ------------------------------------------------------------------------ **
 427    */
 428   {
 429   ubi_avlNodePtr *Parent;
 430   ubi_avlNode     dummy;
 431   ubi_avlNodePtr  dummy_p = &dummy;
 432
 433   if( Node1->Link[ubi_trPARENT] )
 434     Parent = &((Node1->Link[ubi_trPARENT])->Link[Node1->gender]);
 435   else
 436     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
 437   ReplaceNode( Parent, Node1, dummy_p );
 438
 439   if( Node2->Link[ubi_trPARENT] )
 440     Parent = &((Node2->Link[ubi_trPARENT])->Link[Node2->gender]);
 441   else
 442     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
 443   ReplaceNode( Parent, Node2, Node1 );
 444
 445   if( dummy_p->Link[ubi_trPARENT] )
 446     Parent = &((dummy_p->Link[ubi_trPARENT])->Link[dummy_p->gender]);
 447   else
 448     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
 449   ReplaceNode( Parent, dummy_p, Node2 );
 450   } /* SwapNodes */
 451
 452
 453 /* ========================================================================== **
 454  *         Public, exported (ie. not static-ly declared) functions...
 455  * -------------------------------------------------------------------------- **
 456  */
 457
 458 ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr )
 459   /* ------------------------------------------------------------------------ **
 460    * Initialize a tree node.
 461    *
 462    *  Input:   NodePtr  - pointer to a ubi_btNode structure to be
 463    *                      initialized.
 464    *  Output:  a pointer to the initialized ubi_avlNode structure (ie. the
 465    *           same as the input pointer).
 466    * ------------------------------------------------------------------------ **
 467    */
 468   {
 469   (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr );
 470   NodePtr->balance = ubi_trEQUAL;
 471   return( NodePtr );
 472   } /* ubi_avlInitNode */
 473
 474 ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
 475                           ubi_avlNodePtr  NewNode,
 476                           ubi_btItemPtr   ItemPtr,
 477                           ubi_avlNodePtr *OldNode )
 478   /* ------------------------------------------------------------------------ **
 479    * This function uses a non-recursive algorithm to add a new element to
 480    * the tree.
 481    *
 482    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
 483    *                       the root of the tree to which NewNode is to be added.
 484    *           NewNode  -  a pointer to an ubi_avlNode structure that is NOT
 485    *                       part of any tree.
 486    *           ItemPtr  -  A pointer to the sort key that is stored within
 487    *                       *NewNode.  ItemPtr MUST point to information stored
 488    *                       in *NewNode or an EXACT DUPLICATE.  The key data
 489    *                       indicated by ItemPtr is used to place the new node
 490    *                       into the tree.
 491    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
 492    *                       the tree, a duplicate node may be found.  If
 493    *                       duplicates are allowed, then the new node will
 494    *                       be simply placed into the tree.  If duplicates
 495    *                       are not allowed, however, then one of two things
 496    *                       may happen.
 497    *                       1) if overwritting *is not* allowed, this
 498    *                          function will return FALSE (indicating that
 499    *                          the new node could not be inserted), and
 500    *                          *OldNode will point to the duplicate that is
 501    *                          still in the tree.
 502    *                       2) if overwritting *is* allowed, then this
 503    *                          function will swap **OldNode for *NewNode.
 504    *                          In this case, *OldNode will point to the node
 505    *                          that was removed (thus allowing you to free
 506    *                          the node).
 507    *                          **  If you are using overwrite mode, ALWAYS  **
 508    *                          ** check the return value of this parameter! **
 509    *                 Note: You may pass NULL in this parameter, the
 510    *                       function knows how to cope.  If you do this,
 511    *                       however, there will be no way to return a
 512    *                       pointer to an old (ie. replaced) node (which is
 513    *                       a problem if you are using overwrite mode).
 514    *
 515    *  Output:  a boolean value indicating success or failure.  The function
 516    *           will return FALSE if the node could not be added to the tree.
 517    *           Such failure will only occur if duplicates are not allowed,
 518    *           nodes cannot be overwritten, AND a duplicate key was found
 519    *           within the tree.
 520    * ------------------------------------------------------------------------ **
 521    */
 522   {
 523   ubi_avlNodePtr OtherP;
 524
 525   if( !(OldNode) ) OldNode = &OtherP;
 526   if( ubi_btInsert( RootPtr,
 527                     (ubi_btNodePtr)NewNode,
 528                     ItemPtr,
 529                     (ubi_btNodePtr *)OldNode ) )
 530     {
 531     if( (*OldNode) )
 532       NewNode->balance = (*OldNode)->balance;
 533     else
 534       {
 535       NewNode->balance = ubi_trEQUAL;
 536       RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
 537                                                 NewNode->Link[ubi_trPARENT],
 538                                                 NewNode->gender );
 539       }
 540     return( ubi_trTRUE );
 541     }
 542   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
 543   } /* ubi_avlInsert */
 544
 545 ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
 546                               ubi_avlNodePtr DeadNode )
 547   /* ------------------------------------------------------------------------ **
 548    * This function removes the indicated node from the tree, after which the
 549    * tree is rebalanced.
 550    *
 551    *  Input:  RootPtr  -  A pointer to the header of the tree that contains
 552    *                      the node to be removed.
 553    *          DeadNode -  A pointer to the node that will be removed.
 554    *
 555    *  Output: This function returns a pointer to the node that was removed
 556    *          from the tree (ie. the same as DeadNode).
 557    *
 558    *  Note:   The node MUST be in the tree indicated by RootPtr.  If not,
 559    *          strange and evil things will happen to your trees.
 560    * ------------------------------------------------------------------------ **
 561    */
 562   {
 563   ubi_btNodePtr p,
 564                *parentp;
 565
 566   /* if the node has both left and right subtrees, then we have to swap
 567    * it with another node.
 568    */
 569   if( (DeadNode->Link[ubi_trLEFT]) && (DeadNode->Link[ubi_trRIGHT]) )
 570     SwapNodes( RootPtr, DeadNode, ubi_trPrev( DeadNode ) );
 571
 572   /* The parent of the node to be deleted may be another node, or it may be
 573    * the root of the tree.  Since we're not sure, it's best just to have
 574    * a pointer to the parent pointer, whatever it is.
 575    */
 576   if( DeadNode->Link[ubi_trPARENT] )
 577     parentp = (ubi_btNodePtr *)
 578               &((DeadNode->Link[ubi_trPARENT])->Link[(DeadNode->gender)]);
 579   else
 580     parentp = &( RootPtr->root );
 581
 582   /* Now link the parent to the only grand-child.  Patch up the gender and
 583    * such, and rebalance.
 584    */
 585   if( ubi_trEQUAL == DeadNode->balance )
 586     (*parentp) = NULL;
 587   else
 588     {
 589     p = (ubi_btNodePtr)(DeadNode->Link[(DeadNode->balance)]);
 590     p->Link[ubi_trPARENT]  = (ubi_btNodePtr)DeadNode->Link[ubi_trPARENT];
 591     p->gender              = DeadNode->gender;
 592     (*parentp) = p;
 593     }
 594   RootPtr->root = (ubi_btNodePtr)Debalance( (ubi_avlNodePtr)RootPtr->root,
 595                                             DeadNode->Link[ubi_trPARENT],
 596                                             DeadNode->gender );
 597
 598   (RootPtr->count)--;
 599   return( DeadNode );
 600   } /* ubi_avlRemove */
 601
 602 int ubi_avlModuleID( int size, char *list[] )
 603   /* ------------------------------------------------------------------------ **
 604    * Returns a set of strings that identify the module.
 605    *
 606    *  Input:  size  - The number of elements in the array <list>.
 607    *          list  - An array of pointers of type (char *).  This array
 608    *                  should, initially, be empty.  This function will fill
 609    *                  in the array with pointers to strings.
 610    *  Output: The number of elements of <list> that were used.  If this value
 611    *          is less than <size>, the values of the remaining elements are
 612    *          not guaranteed.
 613    *
 614    *  Notes:  Please keep in mind that the pointers returned indicate strings
 615    *          stored in static memory.  Don't free() them, don't write over
 616    *          them, etc.  Just read them.
 617    * ------------------------------------------------------------------------ **
 618    */
 619   {
 620   if( size > 0 )
 621     {
 622     list[0] = ModuleID;
 623     if( size > 1 )
 624       return( 1 + ubi_btModuleID( --size, &(list[1]) ) );
 625     return( 1 );
 626     }
 627   return( 0 );
 628   } /* ubi_avlModuleID */
 629
 630 /* ============================== The End ============================== */