home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 3 / 3147 / README < prev    next >
Text File  |  1991-03-28  |  38KB  |  1,004 lines
  1. To: oesterle@wpi.wpi.edu
  2. Subject: Re: Binary Tree Re-balancing
  3. Newsgroups: comp.lang.c
  4. In-Reply-To: <10403@wpi.wpi.edu>
  5. Organization: Harris Computer Systems, Fort Lauderdale, FL
  6. Cc: 
  7. Bcc: 
  8.  
  9. In article <10403@wpi.wpi.edu> you write:
  10. >
  11. >Greetings!
  12. >
  13. >     I would like to make a request for some references or C code
  14. >for balancing binary trees after insertion/deletion.  I have been
  15. >looking at two books (_Algorithms + Data Structures = Programs_,
  16. >by Nicklaus Wirth; and _Algorithms:  Their Complexity and
  17. >Efficiency_ by Lydia Kronsj:o).  Both the books' code is in
  18. >PASCAL; I would more or less want to compare to see if I am
  19. >interpreting the code correctly, since both books implement the
  20. >balancing differently and I still want to implement it
  21. >differently than both of the books.  I plan to keep the balancing
  22. >information in structures for speed.  Simplicity is much
  23. >desirable, recursive is great.
  24. >
  25. I have spent a couple of years doing exactly this. I have implemented 
  26. what I feel is a very elegant and easy to understand solution and the 
  27. result is a C library for handling AVL trees as an abstract type. If 
  28. you want me to mail my code, then let me know! I will give a bit of a
  29. discussion though.
  30.  
  31. First of all, I use a balance factor that ranges from -2 .. 2, 
  32. Many texts Ive seen use -1 .. 1 but I feel -2 .. 2 is easier to
  33. understand and provides for more simple balance updating.
  34. It is also UNNECESSARY to use separate routines to do left rotations,
  35. and right rotations, one routine that takes the direction as an 
  36. extra parameter will do.
  37.  
  38. CALCULATING NEW BALANCES AFTER A ROTATION:
  39. ==========================================
  40. To calculate the new balances after a single left rotation; assume we have
  41. the following case:
  42.  
  43.                   A                                     B
  44.                  / \                                   / \
  45.                 /   \                                 /   \
  46.                a     B           ==>                 A     c
  47.                     / \                             / \
  48.                    /   \                           /   \
  49.                   b     c                         a     b
  50.  
  51.  
  52. The left is what the tree looked like BEFORE the rotation and the right
  53. is what the tree looks like after the rotation. Capital letters are used
  54. to denote single nodes and lowercase letters are used to denote subtrees.
  55.  
  56. The "balance" of a tree is the height of its right subtree less the
  57. height of its left subtree. Therefore, we can calculate the new balances
  58. of "A" and "B" as follows (ht is the height function):
  59.  
  60.         NewBal(A) = ht(b) - ht(a)
  61.  
  62.         OldBal(A) = ht(B) - ht(a)
  63.                   = ( 1 + max (ht(b), ht(c)) ) - ht(a)
  64.  
  65.  
  66. subtracting the second equation from the first yields:
  67.  
  68.  
  69.         NewBal(A) - OldBal(A) = ht(b) - ( 1 + max (ht(b), ht(c)) )
  70.                                 + ht(a) - ht(a)
  71.  
  72.  
  73. canceling out the ht(a) terms and adding OldBal(A) to both sides yields:
  74.  
  75.  
  76.         NewBal(A) = OldBal(A) - 1 - (max (ht(b), ht(c)) - ht(b) )
  77.  
  78.  
  79. Noting that   max(x, y) - z  =  max(x-z, y-z), we get:
  80.  
  81.  
  82.         NewBal(A) = OldBal(A) - 1 - (max (ht(b) - ht(b), ht(c) - ht(b)) )
  83.  
  84.  
  85. But   ht(c) - ht(b)  is  OldBal(B)  so we get:
  86.  
  87.  
  88.         NewBal(A) = OldBal(A) - 1 - (max (0, OldBal(B)) )
  89.                   = OldBal(A) - 1 -  max (0, OldBal(B))
  90.  
  91. Thus, for A, we get the equation:
  92.  
  93.         NewBal(A) = OldBal(A) - 1 - max (0, OldBal(B))
  94.  
  95. To calculate the Balance for B we perform a similar computation:
  96.  
  97.         NewBal(B) = ht(c) - ht(A)
  98.                   = ht(c) - (1 + max(ht(a), ht(b)) )
  99.  
  100.         OldBal(B) = ht(c) - ht(b)
  101.  
  102.  
  103. subtracting the second equation from the first yields:
  104.  
  105.  
  106.         NewBal(B) - OldBal(B) = ht(c) - ht(c)
  107.                                 + ht(b) - (1 + max(ht(a), ht(b)) )
  108.  
  109.  
  110. canceling, and adding OldBal(B) to both sides gives:
  111.  
  112.  
  113.         NewBal(B) = OldBal(B) - 1 - (max(ht(a), ht(b)) - ht(b))
  114.                   = OldBal(B) - 1 - (max(ht(a) - ht(b), ht(b) - ht(b))
  115.  
  116.  
  117. But  ht(a) - ht(b)  is  - (ht(b) - ht(a))  =  -NewBal(A), so ...
  118.  
  119.  
  120.         NewBal(B) = OldBal(B) - 1 - max( -NewBal(A), 0)
  121.  
  122.  
  123. Using the fact that  min(x,y) = -max(-x, -y) we get:
  124.  
  125.  
  126.         NewBal(B) = OldBal(B) - 1 + min( NewBal(A), 0)
  127.  
  128.  
  129. So, for a single left rotation we have shown the the new balances
  130. for the nodes A and B are given by the following equations:
  131.  
  132.         NewBal(A) = OldBal(A) - 1 - max(OldBal(B), 0)
  133.         NewBal(B) = OldBal(B) - 1 + min(NewBal(A), 0)
  134.  
  135. Now let us look at the case of a single right rotation. The case
  136. we will use is the same one we used for the single left rotation
  137. only with all the left and right subtrees switched around so that
  138. we have the mirror image of the case we used for our left rotation.
  139.  
  140.  
  141.                   A                                     B
  142.                  / \                                   / \
  143.                 /   \                                 /   \
  144.                B     a           ==>                 c     A
  145.               / \                                         / \
  146.              /   \                                       /   \
  147.             c     b                                     b     a
  148.  
  149.  
  150. If we perform the same calculations that we made for the left rotation,
  151. we will see that the new balances for a single right rotation are given 
  152. by the following equations:
  153.  
  154.         NewBal(A) = OldBal(A) + 1 - min(OldBal(B), 0)
  155.         NewBal(B) = OldBal(B) + 1 + max(NewBal(A), 0)
  156.  
  157. Hence, the C code for single left and right rotations would be:
  158.  
  159.         #define LEFT  0
  160.         #define RIGHT 1
  161.  
  162.         #define MAX(a,b)  ( (a) > (b) ? (a) : (b) )
  163.         #define MIN(a,b)  ( (a) < (b) ? (a) : (b) )
  164.  
  165.         typedef struct avl_node  {
  166.           DATA_TYPE         data;
  167.           short             bal;
  168.           struct avl_node  *subtree[2];
  169.          } AVL_NODE, *AVL_TREE; /* avl_node */
  170.  
  171.         void rotate_left (tree)
  172.           AVL_TREE  tree;
  173.         {
  174.           AVL_TREE  old_root = tree;
  175.  
  176.                 /* perform rotation */
  177.           tree = tree->subtree[RIGHT];
  178.           old_root->subtree[RIGHT] = tree->subtree[LEFT]; 
  179.           tree->subtree[LEFT] = old_root;
  180.  
  181.                 /* update balances */
  182.           old_root->bal -=  ( 1 + MAX(tree->bal, 0) );
  183.           tree->bal     -=  ( 1 - MIN(old_root->bal, 0) );
  184.         }/* rotate_left */
  185.  
  186.  
  187.         void rotate_right (tree)
  188.           AVL_TREE  tree;
  189.         {
  190.           AVL_TREE  old_root = tree;
  191.  
  192.                 /* perform rotation */
  193.           tree = tree->subtree[LEFT];
  194.           old_root->subtree[LEFT] = tree->subtree[RIGHT]; 
  195.           tree->subtree[RIGHT] = old_root;
  196.  
  197.                 /* update balances */
  198.           old_root->bal +=  ( 1 - MIN(tree->bal, 0) );
  199.           tree->bal     +=  ( 1 + MAX(old_root->bal, 0) );
  200.         }/* rotate_right */
  201.  
  202. We can make this code more compact however by using only ONE
  203. rotate routine which takes an additional parameter: the direction
  204. in which to rotate. Notice that I have defined LEFT, and RIGHT to
  205. be mnemonic constants to index into an array of subtrees. I can
  206. pass the constant LEFT or RIGHT to the rotation routine and it can
  207. calculate the direction opposite the given direction by subtracting
  208. the given direction from the number one.
  209.  
  210. It does not matter whether LEFT is 0 or RIGHT is 0 as long as one
  211. of them is 0 and the other is 1.  If this is the case, then:
  212.  
  213.      1 - LEFT  = RIGHT
  214.                                    and
  215.      1 - RIGHT = LEFT
  216.  
  217. Using this and the same type definitions as before (and the same
  218. macros), the C source for a single rotation becomes:
  219.  
  220.         #define  OTHER_DIR(x)   ( 1 - (x) )
  221.  
  222.         typedef  short  DIRECTION
  223.  
  224.         void  rotate (tree, dir)
  225.           AVL_TREE    tree;
  226.           DIRECTION   dir;
  227.         {
  228.           AVL_TREE    old_root  = tree;
  229.           DIRECTION   other_dir = OTHER_DIR(dir);
  230.  
  231.                 /* rotate */
  232.           tree = tree->subtree[other_dir];
  233.           old_root->subtree[other_dir] = tree->subtree[dir];
  234.           tree->subtree[dir] = old_root;
  235.  
  236.                 /* update balances */
  237.           if ( dir == LEFT )  {
  238.              old_root->bal -=  ( 1 + MAX(tree->bal, 0) );
  239.              tree->bal     -=  ( 1 - MIN(old_root->bal, 0) );
  240.            }/* if */
  241.  
  242.           else  /* dir == RIGHT */  {
  243.              old_root->bal +=  ( 1 - MIN(tree->bal, 0) );
  244.              tree->bal     +=  ( 1 + MAX(old_root->bal, 0) );
  245.            }/* else */
  246.  
  247.         }/* rotate */
  248.  
  249. We can compact this code even further if we play around with the
  250. equations for updating the balances. Let us use the fact that
  251. max(x,y) = -min(-x,-y):
  252.  
  253.                       for a left rotation
  254.              ------------------------------------------------
  255.              old_root->bal -=  ( 1 + MAX(tree->bal, 0) );
  256.              tree->bal     -=  ( 1 - MIN(old_root->bal, 0) );
  257.  
  258.  
  259.                       for a right rotation
  260.              ------------------------------------------------
  261.              old_root->bal +=  ( 1 - MIN(tree->bal, 0) );
  262.              tree->bal     +=  ( 1 + MAX(old_root->bal, 0) );
  263.  
  264. Using the above rule to change all occurrences of "MIN" to "MAX"
  265. these equations become:
  266.  
  267.                       for a left rotation
  268.              ------------------------------------------------
  269.              old_root->bal -=  ( 1 + MAX( +(tree->bal), 0) );
  270.              tree->bal     -=  ( 1 + MAX( -(old_root->bal), 0) );
  271.  
  272.  
  273.                       for a right rotation
  274.              ------------------------------------------------
  275.              old_root->bal +=  ( 1 + MAX( -(tree->bal), 0) );
  276.              tree->bal     +=  ( 1 + MAX( +(old_root->bal), 0) );
  277.  
  278.  
  279. Note that the difference between updating the balances for our right
  280. and left rotations is only the occurrence of a '+' where we would 
  281. like to see a '-' in the assignment operator, and the sign of the 
  282. first argument to the MAX macro. If we had a function that would
  283. map LEFT to +1 and RIGHT to -1 we could multiply by the result
  284. of that function to update our balances. Such a function is
  285.  
  286.         f(x) = 1 - 2x
  287.  
  288. "f" maps 0 to 1 and maps  1 to -1. This function will NOT map LEFT
  289. and RIGHT to the same value regardless of which is 1 and which is
  290. 0 however. If we wish our function to have this property then we
  291. can multiply (1 - 2x) by (RIGHT - LEFT) so that the result "switches"
  292. signs accordingly depending upon whether LEFT is 0 or RIGHT is 0.
  293. This defines a new function "g":
  294.  
  295.         g(x) = (1 - 2x)(RIGHT - LEFT)
  296.  
  297. If LEFT = 0 and RIGHT = 1 then:
  298.  
  299.         g(LEFT)  = (1 - 2*0)(1 - 0) =  1*1    = 1
  300.         g(RIGHT) = (1 - 2*1)(1 - 0) = (-1)*1  = -1
  301.  
  302. If LEFT = 1 and RIGHT = 0 then:
  303.  
  304.         g(LEFT)  = (1 - 2*1)(0 - 1) = (-1)*(-1)  = 1
  305.         g(RIGHT) = (1 - 2*0)(0 - 1) =  1*(-1)    = -1
  306.  
  307. So, as desired, the function "g" maps LEFT to +1 and RIGHT to -1
  308. regardless of which is 0 and which is 1.
  309.  
  310. Now, if we introduce a new variable called "factor" and assign
  311. it the value "g(dir)", we may update the balances in our rotation
  312. routine without using a conditional statement:
  313.  
  314.                  for a rotation in the "dir" direction
  315.         ------------------------------------------------------------
  316.         old_root->bal -=  factor * ( 1 + MAX( factor * tree->bal, 0) );
  317.         tree->bal     +=  factor * ( 1 + MAX( factor * old_root->bal, 0) );
  318.  
  319. Using this, the new code for our rotation routine becomes:
  320.  
  321.         #define  OTHER_DIR(x)   ( 1 - (x) )
  322.  
  323.         typedef  short  DIRECTION
  324.  
  325.         void  rotate (tree, dir)
  326.           AVL_TREE    tree;
  327.           DIRECTION   dir;
  328.         {
  329.           AVL_TREE    old_root  = tree;
  330.           DIRECTION   other_dir = OTHER_DIR(dir);
  331.           short       factor = (RIGHT - LEFT) * (1 - (2 * dir));
  332.  
  333.                 /* rotate */
  334.           tree = tree->subtree[other_dir];
  335.           old_root->subtree[other_dir] = tree->subtree[dir];
  336.           tree->subtree[dir] = old_root;
  337.  
  338.                 /* update balances */
  339.           old_root->bal -=  factor * ( 1 + MAX( factor * tree->bal, 0) );
  340.           tree->bal     +=  factor * ( 1 + MAX( factor * old_root->bal, 0) );
  341.  
  342.         }/* rotate */
  343.  
  344. However, although this second version of "rotate" is more compact and 
  345. doesn't require the use of a conditional test on the variable "dir",
  346. It may actually run slower than our first version of "rotate" because
  347. the time required to make the "test" may well be less than the time
  348. required to perform the additional multiplications and subtractions.
  349.  
  350. Now a double rotation can be implemented as a series of single rotations:
  351.  
  352. /*
  353. * rotate_twice()  --  rotate a given node in the given direction
  354. *                     and then in the opposite direction
  355. *                     to restore the balance of a tree
  356. */
  357. void rotate_twice( rootp, dir )
  358. AVLtree    *rootp;
  359. DIRECTION  dir;
  360. {
  361.     DIRECTION   other_dir = OPPOSITE( dir );
  362.   
  363.     rotate_once( &( (*rootp) -> subtree[ other_dir ] ), other_dir );  
  364.     rotate_once( rootp, dir );
  365.  
  366. }/* rotate_twice */
  367.  
  368.  
  369. ANOTHER METHOD FOR CALCULATING BALANCES AFTER ROTATION:
  370. =======================================================
  371. One may use a different method than the one described above which
  372. is perhaps simpler. Note however that the method for updating balances
  373. described above works regardless of what numbers the balance factor
  374. may contain (as long as they are correct -- it works, no matter how
  375. imbalanced). If we take into account some of conditions that cause
  376. a rotation, we have more information to work with (such that the 
  377. node to be rotated has a balance of +2 or -2 etc..)
  378.  
  379. For a single LL rotation we have one of two possibilities:
  380.  
  381.  
  382.                   A                                     B
  383.                  / \                                   / \
  384.                 /   \                                 /   \
  385.                a     B           ==>                 A     c
  386.                     / \                             / \
  387.                    /   \                           /   \
  388.                   b     c                         a     b
  389.  
  390. ==============================================================
  391.                              BALANCE FACTORS
  392.           BEFORE ROTATION                      AFTER ROTATION
  393.          ------------------                   ----------------
  394. case 1)   A = +2 ; B = +1                      A = 0  ; B = 0 
  395. case 2)   A = +2 ; B = 0                       A = +1 ; B = -1
  396. ==============================================================
  397.  
  398.  so in either case  NewB = OldB -1 and newA = -newB so we get
  399.  A = - (--B) for a single left rotation.
  400.  
  401. For a single RR rotation the possibilities are (The picture is a
  402. mirror image (swap all right and left kids of each node) of the LL one)
  403. ==============================================================
  404.                              BALANCE FACTORS
  405.           BEFORE ROTATION                      AFTER ROTATION
  406.          ------------------                   ----------------
  407. case 1)   A = -2 ; B = -1                      A = 0  ; B = 0 
  408. case 2)   A = -2 ; B = 0                       A = -1 ; B = +1
  409. ==============================================================
  410.  
  411.  so in either case  NewB = OldB +1 and newA = -newB so we get
  412.  A = - (++B) for a single left rotation.
  413.  
  414. This means that we can use the following to update balances:
  415.  
  416.        /* Directional Definitions */
  417. typedef  short  DIRECTION;
  418. #define  LEFT             0
  419. #define  RIGHT            1
  420. #define  OPPOSITE(x)     ( 1 - (x) )
  421.   
  422.  
  423.        /* return codes used by avl_insert(), avl_delete(), and balance() */
  424. #define  HEIGHT_UNCHANGED    0
  425. #define  HEIGHT_CHANGED        1
  426.  
  427.  
  428. /*
  429. * rotate_once()  --  rotate a given node in the given direction
  430. *                    to restore the balance of a tree
  431. */
  432. short rotate_once( rootp, dir )
  433. AVLtree    *rootp;
  434. DIRECTION  dir;
  435. {
  436.    DIRECTION   other_dir = OPPOSITE( dir );    /* opposite direction to "dir" */
  437.    AVLtree     old_root  = *rootp;        /* copy of original root of tree */
  438.    short    ht_unchanged;            /* true if height unchanged */
  439.  
  440.    /* Here we need to take into account the special case that occurs when a 
  441.    ** single rotation was made but the HEIGHT of the rotated tree did NOT
  442.    ** change as a result of the rotation (we will need this later)
  443.    */
  444.    ht_unchanged = ( (*rootp) -> subtree[ other_dir ] -> bal ) ? FALSE : TRUE;
  445.   
  446.         /* assign new root */
  447.     *rootp = old_root -> subtree[ other_dir ];
  448.   
  449.         /* new-root exchanges it's "dir" subtree for it's parent */
  450.     old_root -> subtree[ other_dir ]   =   (*rootp) -> subtree[ dir ];
  451.     (*rootp) -> subtree[ dir ]         =   old_root;
  452.   
  453.         /* update balances */
  454.     old_root -> bal = -( dir == LEFT ? --( (*rootp) -> bal )
  455.                                      : ++( (*rootp) -> bal )  );
  456.   
  457.     return  ht_unchanged;
  458. }/* rotate_once */
  459.  
  460. We get an even nicer scenario when we look at LR and RL rotations.
  461. For a double LR rotation we have one of three possibilities:
  462.  
  463.  
  464.                   A                                     B
  465.                  / \                                   / \
  466.                 /   \                                /     \
  467.                a     C           ==>                A       C
  468.                     / \                            / \     / \
  469.                    /   \                          /   |   |   \
  470.                   B     c                        a   b1   b2   c
  471.                  / \ 
  472.                 /   \
  473.               b1    b2
  474.  
  475. ==============================================================
  476.                          BALANCE FACTORS
  477.     BEFORE ROTATION                              AFTER ROTATION
  478. ------------------------                    -----------------------
  479. A = +2 ; C = -1 ; B = +1                    A = -1 ; B = 0 ; C = 0
  480. A = +2 ; C = -1 ; B =  0                    A =  0 ; B = 0 ; C = 0
  481. A = +2 ; C = -1 ; B = -1                    A =  0 ; B = 0 ; C =+1
  482. ==============================================================
  483.  
  484. So we get, in all three cases:
  485.  
  486.           newA = -max( oldB, 0 )
  487.           newC = -min( oldB, 0 )
  488.           newB = 0
  489.  
  490. Now for a double RL rotation we have the following possibilities (again, the
  491. picture is the mirror image of the LR case):
  492.  
  493. ==============================================================
  494.                          BALANCE FACTORS
  495.     BEFORE ROTATION                              AFTER ROTATION
  496. ------------------------                    -----------------------
  497. A = -2 ; C = +1 ; B = +1                    A = -1 ; B = 0 ; C = 0
  498. A = -2 ; C = +1 ; B =  0                    A =  0 ; B = 0 ; C = 0
  499. A = -2 ; C = +1 ; B = -1                    A =  0 ; B = 0 ; C =+1
  500. ==============================================================
  501.  
  502. So we get, in all three cases:
  503.  
  504.           newA = -max( oldB, 0 )
  505.           newC = -min( oldB, 0 )
  506.           newB = 0
  507.  
  508. This is EXACTLY what we had for the LR case (isnt that nice!!!) so now we can 
  509. code up a double rotation as follows:
  510.  
  511. /*
  512. * rotate_twice()  --  rotate a given node in the given direction
  513. *                     and then in the opposite direction
  514. *                     to restore the balance of a tree
  515. */
  516. void rotate_twice( rootp, dir )
  517. AVLtree    *rootp;
  518. DIRECTION  dir;
  519. {
  520.  DIRECTION   other_dir        = OPPOSITE( dir );
  521.  AVLtree     old_root        = *rootp,
  522.              old_other_dir_subtree    = (*rootp) -> subtree[ other_dir ];
  523.     
  524.         /* assign new root */
  525.  *rootp = old_root -> subtree[ other_dir ] -> subtree[ dir ];
  526.   
  527.         /* new-root exchanges it's "dir" subtree for it's grandparent */
  528.  old_root -> subtree[ other_dir ]  =   (*rootp) -> subtree[ dir ];
  529.  (*rootp) -> subtree[ dir ]        =   old_root;
  530.   
  531.        /* new-root exchanges it's "other-dir" subtree for it's parent */
  532.  old_other_dir_subtree -> subtree[ dir ] =   (*rootp) -> subtree[ other_dir ];
  533.  (*rootp) -> subtree[ other_dir ]         =   old_other_dir_subtree;
  534.   
  535.         /* update balances */
  536.  (*rootp) -> subtree[ LEFT ] -> bal   =  -MAX( (*rootp) -> bal, 0 );
  537.  (*rootp) -> subtree[ RIGHT ] -> bal  =  -MIN( (*rootp) -> bal, 0 );
  538.  (*rootp) -> bal                      =  0;
  539.  
  540. }/* rotate_twice */
  541.  
  542. Now isnt that special! Now that we have the rotation routines written,
  543. we just need to worry about when to call them. One help is a routine called
  544. balance which is called when a node gets too heavy on a particular side. 
  545. Here we need to take into account the special case that occurs when a 
  546. single rotation was made but the HEIGHT of the rotated tree did NOT change
  547. as a result of the rotation (discussed in more detail in the next section):
  548.  
  549.  
  550.        /* return codes used by avl_insert(), avl_delete(), and balance() */
  551. #define  HEIGHT_UNCHANGED    0
  552. #define  HEIGHT_CHANGED        1
  553.  
  554.        /* Balance Definitions */
  555. #define  LEFT_HEAVY            -1
  556. #define  BALANCED               0
  557. #define  RIGHT_HEAVY            1
  558. #define  LEFT_IMBALANCE(nd)    ( (nd)->bal < LEFT_HEAVY  )
  559. #define  RIGHT_IMBALANCE(nd)   ( (nd)->bal > RIGHT_HEAVY )
  560.  
  561. /*
  562. * balance()  --  determines and performs the  sequence of rotations needed
  563. *                   (if any) to restore the balance of a given tree.
  564. *
  565. *     Returns 1 if tree height changed due to rotation; 0 otherwise
  566. */
  567. short  balance( rootp )
  568. AVLtree    *rootp;
  569. {
  570.     short  special_case = FALSE;
  571.  
  572.     if ( LEFT_IMBALANCE( *rootp )  )  {   /* need a right rotation */
  573.         if ( (*rootp) -> subtree[ LEFT ] -> bal  ==  RIGHT_HEAVY )
  574.             rotate_twice( rootp, RIGHT );    /* double RL rotation needed */
  575.  
  576.         else    /* single RR rotation needed */
  577.             special_case = rotate_once( rootp, RIGHT );
  578.     }/* if */
  579.   
  580.     else if ( RIGHT_IMBALANCE( *rootp )  )  {   /* need a left rotation */
  581.         if ( (*rootp) -> subtree[ RIGHT ] -> bal  ==  LEFT_HEAVY )
  582.             rotate_twice( rootp, LEFT );     /* double LR rotation needed */
  583.  
  584.         else    /* single LL rotation needed */
  585.             special_case = rotate_once( rootp, LEFT );
  586.     }/* elif */
  587.   
  588.     else  return  HEIGHT_UNCHANGED;    /* no rotation occurred */
  589.   
  590.     return  ( special_case ) ? HEIGHT_UNCHANGED : HEIGHT_CHANGED;
  591. }/* balance */
  592.  
  593. This routine helps but now comes the hard part (IMHO at least), figuring
  594. out when the height of the current subtree has changed.
  595.  
  596. CALCULATING WHEN THE HEIGHT OF THE CURRENT SUBTREE HAS CHANGED:
  597. ===============================================================
  598. After we have inserted or deleted a node from the current subtree, we
  599. need to determine if the total height of the current tree has changed 
  600. so that we may pass the information up the recursion stack to previous
  601. instantiations of the insertion and deletion routines.
  602.  
  603. Let us first consider the case of an insertion. The simplest case is 
  604. at the point where the insertion occurred. Since we have created a node
  605. where one did not previously exist, we have increased the height of the
  606. inserted node from 0 to 1. Therefore we need to pass the value 1 (I will
  607. use "1" for TRUE and "0" for FALSE) back to the previous level of
  608. recursion to indicate the increase in the height of the current subtree.
  609.  
  610.              |            after insertion               |
  611.             NULL         ================>              |
  612.                                                         A
  613.  
  614.  
  615. The remaining cases for an insertion are almost as simple. If a 0 (FALSE)
  616. was the "height-change-indicator" passed back by inserting into a subtree
  617. of the current level, then there is no height change at the current level.
  618. It is true that the structure of one of the subtrees may have changed due
  619. to an insertion and/or rotation, but since the height of the subtree did
  620. not change, neither did the height of the current level.
  621.  
  622.              |            after insertion               |
  623.              |           ================>              |
  624.              A                                          A
  625.             / \                                        / \
  626.            /   \                                      /   \
  627.           b     c                                    b     d
  628.  
  629. If the current level is balanced after inserting the node (but before
  630. attempting any rotations) then we just made one subtree equal in height
  631. to the other. Therefore the overall height of the current level remains
  632. unchanged and a 0 is returned.
  633.  
  634.              |            after insertion               |
  635.              |           ================>              |
  636.              A                                          A
  637.             /                                          / \
  638.            /                                          /   \
  639.           b                                          b     c
  640.  
  641. Before we go and write avl_insert, we will need some help from a few other
  642. small routines, most of which are needed for deletion more than for insertion.
  643. These routines will free/create a node, and tell the type of a node.
  644.  
  645. /* ckalloc( size ) -- allocate space; check for success */
  646. void *ckalloc( size )
  647. int size;
  648. {
  649.     void *malloc(), *ptr;
  650.   
  651.     if ( (ptr = (char *) malloc(  (unsigned) size)) == NULL )  {
  652.         fprintf( stderr, "Unable to allocate storage." );
  653.         exit( 1 );
  654.     }/* if */
  655.   
  656.     return  ptr;
  657. }/* ckalloc */
  658.  
  659.  
  660. /*
  661. * new_node() -- get space for a new node and its data;
  662. *               return the address of the new node
  663. */
  664. AVLtree  new_node( data, size )
  665. void     *data;
  666. unsigned  size;
  667. {
  668.     AVLtree  root;
  669.   
  670.     root = (AVLtree) ckalloc( sizeof (AVLnode) );
  671.     root -> data = (void *) ckalloc( size );
  672.     memmove( root -> data, data, size );
  673.     root -> bal  = BALANCED;
  674.     root -> subtree[ LEFT ]  = root -> subtree[ RIGHT ] = NULL_TREE;
  675.   
  676.     return  root;
  677. }/* new_node */
  678.  
  679.  
  680. /*
  681. * free_node()  --  free space for a node and its data!
  682. *                  reset the node pointer to NULL
  683. */
  684. void free_node( rootp )
  685. AVLtree     *rootp;
  686. {
  687.     free( (void *) *rootp );
  688.     *rootp = NULL_TREE;
  689. }/* free_node */
  690.   
  691.   
  692. /*
  693. * node_type() -- determine the number of null pointers for a given
  694. *                node in an AVL tree, Returns a value of type NODE
  695. *                which is an enumeration type with the following values:
  696. *
  697. *                  IS_TREE     --  both subtrees are non-empty
  698. *                  IS_LBRANCH  --  left subtree is non-empty; right is empty
  699. *                  IS_RBRANCH  --  right subtree is non-empty; left is empty
  700. *                  IS_LEAF     --  both subtrees are empty
  701. *                  IS_NULL     --  given tree is empty
  702. */
  703. NODE node_type( tree )
  704. AVLtree    tree;
  705. {
  706.     if ( tree == NULL_TREE )
  707.         return  IS_NULL;
  708.   
  709.     else if (     (tree -> subtree[ LEFT ] != NULL_TREE) 
  710.               &&  (tree -> subtree[ RIGHT ] != NULL_TREE) )
  711.         return  IS_TREE;
  712.   
  713.     else if ( tree -> subtree[ LEFT ] != NULL_TREE )
  714.         return  IS_LBRANCH;
  715.   
  716.     else if ( tree -> subtree[ RIGHT ] != NULL_TREE )
  717.         return  IS_RBRANCH;
  718.   
  719.     else
  720.     return  IS_LEAF;
  721. }/* node_type */
  722.  
  723. Now the last helper routines we need will be a dirty trick. We need a function
  724. to compare items while we traverse the tree. Normally, we expect this compare
  725. function to return a strcmp() type result (<0, =0, or >0 for <,=,> respectively)
  726. We will be a little sneaky and write our own compare function which will take 
  727. the supplied compare function, and the node-type of the node being compared 
  728. against. This will help in deletion when we want to delete the minimal/maximal
  729. element of a given tree. We will go about it in such a way that we can delete
  730. or find a given item, or the min/max item in a tree. We do this as follows:
  731.  
  732. /*
  733. * avl_min() -- compare function used to find the minimal element in a tree
  734. */
  735. int avl_min( elt1, elt2, nd_typ )
  736. void  *elt1, *elt2;
  737. NODE  nd_typ;
  738. {
  739.     if ( nd_typ == IS_RBRANCH  ||  nd_typ == IS_LEAF )
  740.         return   0;   /* left subtree is empty -- this is the minimum */
  741.     
  742.     else  return  -1;   /* keep going left */
  743. }/* avl_min */
  744.  
  745.  
  746. /*
  747. * avl_max() -- compare function used to find the maximal element in a tree
  748. */
  749. int avl_max( elt1, elt2, nd_typ )
  750. void  *elt1, *elt2;
  751. NODE  nd_typ;
  752. {
  753.     if ( nd_typ == IS_RBRANCH  ||  nd_typ == IS_LEAF )
  754.         return  0;   /* right subtree is empty -- this is the maximum */
  755.     
  756.     else  return  1;   /* keep going right */
  757. }/* avl_max */
  758.  
  759. Now we can use avl_min/avl_max as compare functions. If the compare 
  760. function is other than one of these two, usually it will only use the first 
  761. two parameters (so it gets an extra one). This is not great for portability
  762. so we should really do something like:
  763.  
  764. /*
  765. * avl_compare() -- compare an item with a node-item in an avl tree
  766. */
  767. int avl_compare( elt1, elt2, nd_typ, compar )
  768. void  *elt1, *elt2;
  769. NODE  nd_typ;
  770. int (*compar)();
  771. {
  772.    if ( compare == avl_min || compar == avl_max )
  773.      return  (*compar)( elt1, elt2, nd_typ );
  774.    else
  775.      return  (*compare)( elt1, elt2 );
  776. }/* avl_compare */
  777.  
  778. If you wish to do this you may, but my code works without it, it just ignores
  779. any extra parameters. If you have ANSI-C you may get some compiler complaints.
  780. In any case, I shall proceed without using avl_compare(). In addition, avl_min
  781. and avl_max should only be passed to avl_find (search without inserting),
  782. and avl_delete (NOT avl_insert).  We are now ready to write avl_insert:
  783.  
  784. /*
  785. * avl_insert() -- insert an item into the given tree
  786. *
  787. *   PARAMETERS:
  788. *                data       --  a pointer to a pointer to the data to add;
  789. *                               On exit, *data is NULL if insertion succeeded,
  790. *                               otherwise address of the duplicate key
  791. *                rootp      --  a pointer to an AVL tree
  792. *                compar     --  name of the function to compare 2 data items
  793. */
  794. short avl_insert( data, rootp, compar )
  795. void     **data;
  796. AVLtree  *rootp;
  797. int      (*compar)();
  798. {
  799.     short increase;
  800.     int   cmp;
  801.   
  802.     if ( *rootp == NULL_TREE )  {  /* insert new node here */
  803.         *rootp = new_node( *data, SIZE_OF_DATA )) );
  804.         *data  = NULL;     /* set return value in data */
  805.         return  HEIGHT_CHANGED;
  806.     }/* if */
  807.   
  808.     cmp = (*compar)( *data, (*rootp) -> data );   /* compare data items */
  809.   
  810.     if ( cmp < 0 )  {  /* insert into the left subtree */
  811.         increase =  -avl_insert( data, &( (*rootp) -> subtree[ LEFT ] ), compar );
  812.         if ( *data != NULL )     return  HEIGHT_UNCHANGED;
  813.     }/* elif */
  814.   
  815.     else if ( cmp > 0 )  {  /* insert into the right subtree */
  816.         increase =  avl_insert( data, &( (*rootp) -> subtree[ RIGHT ] ), compar );
  817.         if ( *data != NULL )     return  HEIGHT_UNCHANGED;
  818.     }/* elif */
  819.   
  820.     else  {   /* data already exists */
  821.         *data = (*rootp) -> data;   /* set return value in data */
  822.         return  HEIGHT_UNCHANGED;
  823.     } /* else */
  824.   
  825.     (*rootp) -> bal += increase;    /* update balance factor */
  826.  
  827.   /************************************************************************
  828.   * re-balance if needed -- height of current tree increases only if its
  829.   * subtree height increases and the current tree needs no rotation.
  830.   ************************************************************************/
  831.     if ( increase  &&  (*rootp) -> bal )
  832.         return  (  1 - balance( rootp )  );
  833.     else
  834.         return  HEIGHT_UNCHANGED;
  835. }/* avl_insert */
  836.  
  837.  
  838. Deletion is more complicated than insertion. The height of the current level
  839. may decrease for two reasons: either a rotation occurred to decrease the
  840. height of a subtree (and hence the current level), or a subtree shortened
  841. in height resulting in a now balanced current level (subtree was "trimmed
  842. down" to the same size as the other). Just because a rotation has occurred
  843. however, does not mean that the subtree height has decreased. There is a
  844. special case where rotating preserves the current subtree height.
  845.  
  846. Suppose I have a tree as follows:
  847.  
  848.  
  849.                                  C
  850.                                /   \
  851.                               A      E
  852.                                    /   \
  853.                                   D     F
  854.  
  855.  
  856. Deleting "A" results in the following (imbalanced) tree:
  857.  
  858.  
  859.                                  C
  860.                                    \
  861.                                      E
  862.                                    /   \
  863.                                   D     F
  864.  
  865.  
  866. This type of imbalance cannot occurr during insertion, only during 
  867. deletion. Notice that the root has a balance of 2 but its heavy subtree
  868. has a balance of zero (the other case would be a -2 and a 0). Performing
  869. a single left rotation to restore the balance results in:
  870.  
  871.  
  872.                                  E
  873.                                /   \
  874.                               C      F
  875.                                \
  876.                                  D
  877.  
  878.  
  879. This tree has the same height as it did before it was rotated. Hence,
  880. we may determine if deletion caused the subtree height to change by
  881. seeing if one of the following occurred:
  882.  
  883.     1) If the new balance (after deletion) is zero and NO rotation
  884.        took place.
  885.  
  886.     2) If a rotation took place but was NOT one of the special rotations
  887.        mentioned above (a -2:0 or a 2:0 rotation).
  888.  
  889. For insertion, we only needed to check if a rotation occurred to see if the
  890. subtree height had changed. But for deletion we need to ckeck all of the above.
  891. So for deletion of a node we have:
  892.  
  893. /*
  894. * avl_delete() -- delete an item from the given tree
  895. *
  896. *   PARAMETERS:
  897. *                data       --  a pointer to a pointer to the key to delete
  898. *                               On exit, *data points to the deleted data item
  899. *                               (or NULL if deletion failed).
  900. *                rootp      --  a pointer to an AVL tree
  901. *                compar     --  name of function to compare 2 data items
  902. */
  903. PRIVATE     short avl_delete( data, rootp, compar )
  904. void      **data;
  905. AVLtree   *rootp;
  906. int       (*compar)();
  907. {
  908.     short      decrease;
  909.     int        cmp;
  910.     AVLtree    old_root  = *rootp;
  911.     NODE       nd_typ    = node_type( *rootp );
  912.     DIRECTION  dir       = (nd_typ == IS_LBRANCH) ? LEFT : RIGHT;
  913.   
  914.     if ( *rootp == NULL_TREE )  {  /* data not found */
  915.         *data = NULL;    /* set return value in data */
  916.         return  HEIGHT_UNCHANGED;
  917.     }/* if */
  918.   
  919.         /* NOTE the extra parameter to compare this time */
  920.     cmp = compar( *data, (*rootp) -> data, nd_typ );   /* compare data items */
  921.   
  922.     if ( cmp < 0 )  {  /* delete from left subtree */
  923.         decrease =  -avl_delete( data, &( (*rootp) -> subtree[ LEFT ] ), compar );
  924.         if ( *data == NULL )     return  HEIGHT_UNCHANGED;
  925.     }/* elif */
  926.   
  927.     else if ( cmp > 0 )  {  /* delete from right subtree */
  928.         decrease =  avl_delete( data, &( (*rootp) -> subtree[ RIGHT ] ), compar );
  929.         if ( *data == NULL )     return  HEIGHT_UNCHANGED;
  930.     }/* elif */
  931.     
  932.   /************************************************************************
  933.   *  At this point we know that if "cmp" is zero then "*rootp" points to
  934.   *  the node that we need to delete.  There are three cases:
  935.   *
  936.   *     1) The node is a leaf.  Remove it and return.
  937.   *
  938.   *     2) The node is a branch (has only 1 child). Make "*rootp"
  939.   *        (the pointer to this node) point to the child.
  940.   *
  941.   *     3) The node has two children. We swap data with the successor of
  942.   *        "*rootp" (the smallest item in its right subtree) and delete
  943.   *        the successor from the right subtree of "*rootp".  The
  944.   *        identifier "decrease" should be reset if the subtree height
  945.   *        decreased due to the deletion of the sucessor of "rootp".
  946.   ************************************************************************/
  947.   
  948.     else  {  /* cmp == 0 */
  949.         *data = (*rootp) -> data;  /* set return value in data */
  950.   
  951.         switch ( nd_typ )  {  /* what kind of node are we removing? */
  952.             case  IS_LEAF :
  953.             free_node( rootp );          /* free the leaf, its height     */
  954.                 return  HEIGHT_CHANGED;      /* changes from 1 to 0, return 1 */
  955.   
  956.             case  IS_RBRANCH :       /* only child becomes new root */
  957.             case  IS_LBRANCH :
  958.             *rootp = (*rootp) -> subtree[ dir ];
  959.                 free_node( &old_root );      /* free the deleted node */
  960.                 return  HEIGHT_CHANGED;      /* we just shortened the "dir" subtree */
  961.   
  962.             case  IS_TREE  :
  963.                 decrease = avl_delete(  &( (*rootp) -> data ),
  964.                                         &( (*rootp) -> subtree[ RIGHT ] ),
  965.                                         avl_min                );
  966.         } /* switch */
  967.     } /* else */
  968.  
  969.     (*rootp) -> bal -= decrease;       /* update balance factor */
  970.   
  971.   /**********************************************************************
  972.   * Rebalance if necessary -- the height of current tree changes if one
  973.   * of two things happens: (1) a rotation was performed which changed
  974.   * the height of the subtree (2) the subtree height decreased and now
  975.   * matches the height of its other subtree (so the current tree now
  976.   * has a zero balance when it previously did not).
  977.   **********************************************************************/
  978.     if ( decrease  &&  (*rootp) -> bal )    /* return 1 if height      */
  979.         return  balance( rootp );        /* changed due to rotation */
  980.   
  981.     else if ( decrease  && !(*rootp) -> bal )    /* or if balance is 0 from    */
  982.         return  HEIGHT_CHANGED;            /* height decrease of subtree */
  983.   
  984.     else
  985.         return  HEIGHT_UNCHANGED;
  986.   
  987. }/* avl_delete */
  988.  
  989. NOTICE how in the case of nd_typ == IS_TREE, I only need one statement. This
  990. is due to the way avl_delete sets its parameters. The data pointer passed on
  991. entrance points to the deleted node's data on exit. So I just delete the 
  992. minimal element of the right subtree, and steal its data as my-own (returning
  993. my former data item on exit).
  994.  
  995.  
  996. And there we have it, the mantainenance of AVL tree manipulations, the brunt
  997. of which is covered in 5 routines, none of which (except for delete which
  998. is less than 1-1/2pages) is greater than 1 normal page in length, including
  999. comments (and there are a lot). The main routines are:
  1000.  
  1001. rotate_once(), rotate_twice(), balance(), avl_insert(), avl_delete().
  1002.  
  1003. All other routines are very small and auxillary in nature.
  1004.