Path: utzoo!utgpu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!caen!uflorida!travis!brad From: brad@SSD.CSD.HARRIS.COM (Brad Appleton) Newsgroups: alt.sources Subject: AVL tree library (part 1 of 2) Message-ID: <2821@travis.csd.harris.com> Date: 28 Mar 91 20:38:53 GMT Sender: news@travis.csd.harris.com Organization: Harris Computers Systems Division, Fort Lauderdale,FL Lines: 1607 This is a Beta release of part 1 of an AVL tree library that I have been using on and off for a few years. Please report any bugs ASAP to me at brad@ssd.csd.harris.com #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh 'MANIFEST' <<'END_OF_FILE' X File Name Archive # Description X----------------------------------------------------------- X LICENSE 2 Permission to use/copy this package X MANIFEST 1 This file X Makefile 1 Makefile for the library X README 1 Discussion of algorithm(s) for AVL trees X avl.3 2 Documentation for the AVL tree library X avl.c 2 Source for the entire AVL library X avl.h 1 Include file for the AVL tree library X avl_test.c 1 The test program X avl_typs.h 1 Include file needed by the AVL tree library X key_gen.c 1 Generates random test values X rotate.old 1 Old code for AVL rotations (no longer used) X testvals.h 1 Test values for the test program X testvals.old 2 Old test values END_OF_FILE if test 892 -ne `wc -c <'MANIFEST'`; then echo shar: \"'MANIFEST'\" unpacked with wrong size! fi # end of 'MANIFEST' fi if test -f 'Makefile' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'Makefile'\" else echo shar: Extracting \"'Makefile'\" \(618 characters\) sed "s/^X//" >'Makefile' <<'END_OF_FILE' XDBG= -g XDEFS= XDEL= /bin/rm -f XHDRS= avl.h avl_typs.h testvals.h XLIBRARY= libavl.a XOBJS= avl.o avl_test.o X#OPT= -O XPRINT= pr XSRCS= avl.c \ X avl_test.c XTEST= avl_test X XCFLAGS= $(DBG) $(OPT) $(DEFS) X Xall: library test X Xlibrary: $(LIBRARY) X Xtest: $(TEST) X X$(LIBRARY): avl.o X ar cru $(LIBRARY) avl.o X ranlib $(LIBRARY) X X$(TEST): $(OBJS) X $(CC) $(CFLAGS) -o $(TEST) $(OBJS) X Xclean: X $(DEL) $(OBJS) X Xclobber: clean X $(DEL) $(LIBRARY) $(TEST) X Xindex: X ctags -wx $(HDRS) $(SRCS) X Xprint: X $(PRINT) $(HDRS) $(SRCS) X Xtags: $(HDRS) $(SRCS) X ctags $(HDRS) $(SRCS) X X### Xavl.o: avl.h avl_typs.h Xavl_test.o: avl.h testvals.h END_OF_FILE if test 618 -ne `wc -c <'Makefile'`; then echo shar: \"'Makefile'\" unpacked with wrong size! fi # end of 'Makefile' fi if test -f 'README' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'README'\" else echo shar: Extracting \"'README'\" \(37772 characters\) sed "s/^X//" >'README' <<'END_OF_FILE' XTo: oesterle@wpi.wpi.edu XSubject: Re: Binary Tree Re-balancing XNewsgroups: comp.lang.c XIn-Reply-To: <10403@wpi.wpi.edu> XOrganization: Harris Computer Systems, Fort Lauderdale, FL XCc: XBcc: X XIn article <10403@wpi.wpi.edu> you write: X> X>Greetings! X> X> I would like to make a request for some references or C code X>for balancing binary trees after insertion/deletion. I have been X>looking at two books (_Algorithms + Data Structures = Programs_, X>by Nicklaus Wirth; and _Algorithms: Their Complexity and X>Efficiency_ by Lydia Kronsj:o). Both the books' code is in X>PASCAL; I would more or less want to compare to see if I am X>interpreting the code correctly, since both books implement the X>balancing differently and I still want to implement it X>differently than both of the books. I plan to keep the balancing X>information in structures for speed. Simplicity is much X>desirable, recursive is great. X> XI have spent a couple of years doing exactly this. I have implemented Xwhat I feel is a very elegant and easy to understand solution and the Xresult is a C library for handling AVL trees as an abstract type. If Xyou want me to mail my code, then let me know! I will give a bit of a Xdiscussion though. X XFirst of all, I use a balance factor that ranges from -2 .. 2, XMany texts Ive seen use -1 .. 1 but I feel -2 .. 2 is easier to Xunderstand and provides for more simple balance updating. XIt is also UNNECESSARY to use separate routines to do left rotations, Xand right rotations, one routine that takes the direction as an Xextra parameter will do. X XCALCULATING NEW BALANCES AFTER A ROTATION: X========================================== XTo calculate the new balances after a single left rotation; assume we have Xthe following case: X X A B X / \ / \ X / \ / \ X a B ==> A c X / \ / \ X / \ / \ X b c a b X X XThe left is what the tree looked like BEFORE the rotation and the right Xis what the tree looks like after the rotation. Capital letters are used Xto denote single nodes and lowercase letters are used to denote subtrees. X XThe "balance" of a tree is the height of its right subtree less the Xheight of its left subtree. Therefore, we can calculate the new balances Xof "A" and "B" as follows (ht is the height function): X X NewBal(A) = ht(b) - ht(a) X X OldBal(A) = ht(B) - ht(a) X = ( 1 + max (ht(b), ht(c)) ) - ht(a) X X Xsubtracting the second equation from the first yields: X X X NewBal(A) - OldBal(A) = ht(b) - ( 1 + max (ht(b), ht(c)) ) X + ht(a) - ht(a) X X Xcanceling out the ht(a) terms and adding OldBal(A) to both sides yields: X X X NewBal(A) = OldBal(A) - 1 - (max (ht(b), ht(c)) - ht(b) ) X X XNoting that max(x, y) - z = max(x-z, y-z), we get: X X X NewBal(A) = OldBal(A) - 1 - (max (ht(b) - ht(b), ht(c) - ht(b)) ) X X XBut ht(c) - ht(b) is OldBal(B) so we get: X X X NewBal(A) = OldBal(A) - 1 - (max (0, OldBal(B)) ) X = OldBal(A) - 1 - max (0, OldBal(B)) X XThus, for A, we get the equation: X X NewBal(A) = OldBal(A) - 1 - max (0, OldBal(B)) X XTo calculate the Balance for B we perform a similar computation: X X NewBal(B) = ht(c) - ht(A) X = ht(c) - (1 + max(ht(a), ht(b)) ) X X OldBal(B) = ht(c) - ht(b) X X Xsubtracting the second equation from the first yields: X X X NewBal(B) - OldBal(B) = ht(c) - ht(c) X + ht(b) - (1 + max(ht(a), ht(b)) ) X X Xcanceling, and adding OldBal(B) to both sides gives: X X X NewBal(B) = OldBal(B) - 1 - (max(ht(a), ht(b)) - ht(b)) X = OldBal(B) - 1 - (max(ht(a) - ht(b), ht(b) - ht(b)) X X XBut ht(a) - ht(b) is - (ht(b) - ht(a)) = -NewBal(A), so ... X X X NewBal(B) = OldBal(B) - 1 - max( -NewBal(A), 0) X X XUsing the fact that min(x,y) = -max(-x, -y) we get: X X X NewBal(B) = OldBal(B) - 1 + min( NewBal(A), 0) X X XSo, for a single left rotation we have shown the the new balances Xfor the nodes A and B are given by the following equations: X X NewBal(A) = OldBal(A) - 1 - max(OldBal(B), 0) X NewBal(B) = OldBal(B) - 1 + min(NewBal(A), 0) X XNow let us look at the case of a single right rotation. The case Xwe will use is the same one we used for the single left rotation Xonly with all the left and right subtrees switched around so that Xwe have the mirror image of the case we used for our left rotation. X X X A B X / \ / \ X / \ / \ X B a ==> c A X / \ / \ X / \ / \ X c b b a X X XIf we perform the same calculations that we made for the left rotation, Xwe will see that the new balances for a single right rotation are given Xby the following equations: X X NewBal(A) = OldBal(A) + 1 - min(OldBal(B), 0) X NewBal(B) = OldBal(B) + 1 + max(NewBal(A), 0) X XHence, the C code for single left and right rotations would be: X X #define LEFT 0 X #define RIGHT 1 X X #define MAX(a,b) ( (a) > (b) ? (a) : (b) ) X #define MIN(a,b) ( (a) < (b) ? (a) : (b) ) X X typedef struct avl_node { X DATA_TYPE data; X short bal; X struct avl_node *subtree[2]; X } AVL_NODE, *AVL_TREE; /* avl_node */ X X void rotate_left (tree) X AVL_TREE tree; X { X AVL_TREE old_root = tree; X X /* perform rotation */ X tree = tree->subtree[RIGHT]; X old_root->subtree[RIGHT] = tree->subtree[LEFT]; X tree->subtree[LEFT] = old_root; X X /* update balances */ X old_root->bal -= ( 1 + MAX(tree->bal, 0) ); X tree->bal -= ( 1 - MIN(old_root->bal, 0) ); X }/* rotate_left */ X X X void rotate_right (tree) X AVL_TREE tree; X { X AVL_TREE old_root = tree; X X /* perform rotation */ X tree = tree->subtree[LEFT]; X old_root->subtree[LEFT] = tree->subtree[RIGHT]; X tree->subtree[RIGHT] = old_root; X X /* update balances */ X old_root->bal += ( 1 - MIN(tree->bal, 0) ); X tree->bal += ( 1 + MAX(old_root->bal, 0) ); X }/* rotate_right */ X XWe can make this code more compact however by using only ONE Xrotate routine which takes an additional parameter: the direction Xin which to rotate. Notice that I have defined LEFT, and RIGHT to Xbe mnemonic constants to index into an array of subtrees. I can Xpass the constant LEFT or RIGHT to the rotation routine and it can Xcalculate the direction opposite the given direction by subtracting Xthe given direction from the number one. X XIt does not matter whether LEFT is 0 or RIGHT is 0 as long as one Xof them is 0 and the other is 1. If this is the case, then: X X 1 - LEFT = RIGHT X and X 1 - RIGHT = LEFT X XUsing this and the same type definitions as before (and the same Xmacros), the C source for a single rotation becomes: X X #define OTHER_DIR(x) ( 1 - (x) ) X X typedef short DIRECTION X X void rotate (tree, dir) X AVL_TREE tree; X DIRECTION dir; X { X AVL_TREE old_root = tree; X DIRECTION other_dir = OTHER_DIR(dir); X X /* rotate */ X tree = tree->subtree[other_dir]; X old_root->subtree[other_dir] = tree->subtree[dir]; X tree->subtree[dir] = old_root; X X /* update balances */ X if ( dir == LEFT ) { X old_root->bal -= ( 1 + MAX(tree->bal, 0) ); X tree->bal -= ( 1 - MIN(old_root->bal, 0) ); X }/* if */ X X else /* dir == RIGHT */ { X old_root->bal += ( 1 - MIN(tree->bal, 0) ); X tree->bal += ( 1 + MAX(old_root->bal, 0) ); X }/* else */ X X }/* rotate */ X XWe can compact this code even further if we play around with the Xequations for updating the balances. Let us use the fact that Xmax(x,y) = -min(-x,-y): X X for a left rotation X ------------------------------------------------ X old_root->bal -= ( 1 + MAX(tree->bal, 0) ); X tree->bal -= ( 1 - MIN(old_root->bal, 0) ); X X X for a right rotation X ------------------------------------------------ X old_root->bal += ( 1 - MIN(tree->bal, 0) ); X tree->bal += ( 1 + MAX(old_root->bal, 0) ); X XUsing the above rule to change all occurrences of "MIN" to "MAX" Xthese equations become: X X for a left rotation X ------------------------------------------------ X old_root->bal -= ( 1 + MAX( +(tree->bal), 0) ); X tree->bal -= ( 1 + MAX( -(old_root->bal), 0) ); X X X for a right rotation X ------------------------------------------------ X old_root->bal += ( 1 + MAX( -(tree->bal), 0) ); X tree->bal += ( 1 + MAX( +(old_root->bal), 0) ); X X XNote that the difference between updating the balances for our right Xand left rotations is only the occurrence of a '+' where we would Xlike to see a '-' in the assignment operator, and the sign of the Xfirst argument to the MAX macro. If we had a function that would Xmap LEFT to +1 and RIGHT to -1 we could multiply by the result Xof that function to update our balances. Such a function is X X f(x) = 1 - 2x X X"f" maps 0 to 1 and maps 1 to -1. This function will NOT map LEFT Xand RIGHT to the same value regardless of which is 1 and which is X0 however. If we wish our function to have this property then we Xcan multiply (1 - 2x) by (RIGHT - LEFT) so that the result "switches" Xsigns accordingly depending upon whether LEFT is 0 or RIGHT is 0. XThis defines a new function "g": X X g(x) = (1 - 2x)(RIGHT - LEFT) X XIf LEFT = 0 and RIGHT = 1 then: X X g(LEFT) = (1 - 2*0)(1 - 0) = 1*1 = 1 X g(RIGHT) = (1 - 2*1)(1 - 0) = (-1)*1 = -1 X XIf LEFT = 1 and RIGHT = 0 then: X X g(LEFT) = (1 - 2*1)(0 - 1) = (-1)*(-1) = 1 X g(RIGHT) = (1 - 2*0)(0 - 1) = 1*(-1) = -1 X XSo, as desired, the function "g" maps LEFT to +1 and RIGHT to -1 Xregardless of which is 0 and which is 1. X XNow, if we introduce a new variable called "factor" and assign Xit the value "g(dir)", we may update the balances in our rotation Xroutine without using a conditional statement: X X for a rotation in the "dir" direction X ------------------------------------------------------------ X old_root->bal -= factor * ( 1 + MAX( factor * tree->bal, 0) ); X tree->bal += factor * ( 1 + MAX( factor * old_root->bal, 0) ); X XUsing this, the new code for our rotation routine becomes: X X #define OTHER_DIR(x) ( 1 - (x) ) X X typedef short DIRECTION X X void rotate (tree, dir) X AVL_TREE tree; X DIRECTION dir; X { X AVL_TREE old_root = tree; X DIRECTION other_dir = OTHER_DIR(dir); X short factor = (RIGHT - LEFT) * (1 - (2 * dir)); X X /* rotate */ X tree = tree->subtree[other_dir]; X old_root->subtree[other_dir] = tree->subtree[dir]; X tree->subtree[dir] = old_root; X X /* update balances */ X old_root->bal -= factor * ( 1 + MAX( factor * tree->bal, 0) ); X tree->bal += factor * ( 1 + MAX( factor * old_root->bal, 0) ); X X }/* rotate */ X XHowever, although this second version of "rotate" is more compact and Xdoesn't require the use of a conditional test on the variable "dir", XIt may actually run slower than our first version of "rotate" because Xthe time required to make the "test" may well be less than the time Xrequired to perform the additional multiplications and subtractions. X XNow a double rotation can be implemented as a series of single rotations: X X/* X* rotate_twice() -- rotate a given node in the given direction X* and then in the opposite direction X* to restore the balance of a tree X*/ Xvoid rotate_twice( rootp, dir ) XAVLtree *rootp; XDIRECTION dir; X{ X DIRECTION other_dir = OPPOSITE( dir ); X X rotate_once( &( (*rootp) -> subtree[ other_dir ] ), other_dir ); X rotate_once( rootp, dir ); X X}/* rotate_twice */ X X XANOTHER METHOD FOR CALCULATING BALANCES AFTER ROTATION: X======================================================= XOne may use a different method than the one described above which Xis perhaps simpler. Note however that the method for updating balances Xdescribed above works regardless of what numbers the balance factor Xmay contain (as long as they are correct -- it works, no matter how Ximbalanced). If we take into account some of conditions that cause Xa rotation, we have more information to work with (such that the Xnode to be rotated has a balance of +2 or -2 etc..) X XFor a single LL rotation we have one of two possibilities: X X X A B X / \ / \ X / \ / \ X a B ==> A c X / \ / \ X / \ / \ X b c a b X X============================================================== X BALANCE FACTORS X BEFORE ROTATION AFTER ROTATION X ------------------ ---------------- Xcase 1) A = +2 ; B = +1 A = 0 ; B = 0 Xcase 2) A = +2 ; B = 0 A = +1 ; B = -1 X============================================================== X X so in either case NewB = OldB -1 and newA = -newB so we get X A = - (--B) for a single left rotation. X XFor a single RR rotation the possibilities are (The picture is a Xmirror image (swap all right and left kids of each node) of the LL one) X============================================================== X BALANCE FACTORS X BEFORE ROTATION AFTER ROTATION X ------------------ ---------------- Xcase 1) A = -2 ; B = -1 A = 0 ; B = 0 Xcase 2) A = -2 ; B = 0 A = -1 ; B = +1 X============================================================== X X so in either case NewB = OldB +1 and newA = -newB so we get X A = - (++B) for a single left rotation. X XThis means that we can use the following to update balances: X X /* Directional Definitions */ Xtypedef short DIRECTION; X#define LEFT 0 X#define RIGHT 1 X#define OPPOSITE(x) ( 1 - (x) ) X X X /* return codes used by avl_insert(), avl_delete(), and balance() */ X#define HEIGHT_UNCHANGED 0 X#define HEIGHT_CHANGED 1 X X X/* X* rotate_once() -- rotate a given node in the given direction X* to restore the balance of a tree X*/ Xshort rotate_once( rootp, dir ) XAVLtree *rootp; XDIRECTION dir; X{ X DIRECTION other_dir = OPPOSITE( dir ); /* opposite direction to "dir" */ X AVLtree old_root = *rootp; /* copy of original root of tree */ X short ht_unchanged; /* true if height unchanged */ X X /* Here we need to take into account the special case that occurs when a X ** single rotation was made but the HEIGHT of the rotated tree did NOT X ** change as a result of the rotation (we will need this later) X */ X ht_unchanged = ( (*rootp) -> subtree[ other_dir ] -> bal ) ? FALSE : TRUE; X X /* assign new root */ X *rootp = old_root -> subtree[ other_dir ]; X X /* new-root exchanges it's "dir" subtree for it's parent */ X old_root -> subtree[ other_dir ] = (*rootp) -> subtree[ dir ]; X (*rootp) -> subtree[ dir ] = old_root; X X /* update balances */ X old_root -> bal = -( dir == LEFT ? --( (*rootp) -> bal ) X : ++( (*rootp) -> bal ) ); X X return ht_unchanged; X}/* rotate_once */ X XWe get an even nicer scenario when we look at LR and RL rotations. XFor a double LR rotation we have one of three possibilities: X X X A B X / \ / \ X / \ / \ X a C ==> A C X / \ / \ / \ X / \ / | | \ X B c a b1 b2 c X / \ X / \ X b1 b2 X X============================================================== X BALANCE FACTORS X BEFORE ROTATION AFTER ROTATION X------------------------ ----------------------- XA = +2 ; C = -1 ; B = +1 A = -1 ; B = 0 ; C = 0 XA = +2 ; C = -1 ; B = 0 A = 0 ; B = 0 ; C = 0 XA = +2 ; C = -1 ; B = -1 A = 0 ; B = 0 ; C =+1 X============================================================== X XSo we get, in all three cases: X X newA = -max( oldB, 0 ) X newC = -min( oldB, 0 ) X newB = 0 X XNow for a double RL rotation we have the following possibilities (again, the Xpicture is the mirror image of the LR case): X X============================================================== X BALANCE FACTORS X BEFORE ROTATION AFTER ROTATION X------------------------ ----------------------- XA = -2 ; C = +1 ; B = +1 A = -1 ; B = 0 ; C = 0 XA = -2 ; C = +1 ; B = 0 A = 0 ; B = 0 ; C = 0 XA = -2 ; C = +1 ; B = -1 A = 0 ; B = 0 ; C =+1 X============================================================== X XSo we get, in all three cases: X X newA = -max( oldB, 0 ) X newC = -min( oldB, 0 ) X newB = 0 X XThis is EXACTLY what we had for the LR case (isnt that nice!!!) so now we can Xcode up a double rotation as follows: X X/* X* rotate_twice() -- rotate a given node in the given direction X* and then in the opposite direction X* to restore the balance of a tree X*/ Xvoid rotate_twice( rootp, dir ) XAVLtree *rootp; XDIRECTION dir; X{ X DIRECTION other_dir = OPPOSITE( dir ); X AVLtree old_root = *rootp, X old_other_dir_subtree = (*rootp) -> subtree[ other_dir ]; X X /* assign new root */ X *rootp = old_root -> subtree[ other_dir ] -> subtree[ dir ]; X X /* new-root exchanges it's "dir" subtree for it's grandparent */ X old_root -> subtree[ other_dir ] = (*rootp) -> subtree[ dir ]; X (*rootp) -> subtree[ dir ] = old_root; X X /* new-root exchanges it's "other-dir" subtree for it's parent */ X old_other_dir_subtree -> subtree[ dir ] = (*rootp) -> subtree[ other_dir ]; X (*rootp) -> subtree[ other_dir ] = old_other_dir_subtree; X X /* update balances */ X (*rootp) -> subtree[ LEFT ] -> bal = -MAX( (*rootp) -> bal, 0 ); X (*rootp) -> subtree[ RIGHT ] -> bal = -MIN( (*rootp) -> bal, 0 ); X (*rootp) -> bal = 0; X X}/* rotate_twice */ X XNow isnt that special! Now that we have the rotation routines written, Xwe just need to worry about when to call them. One help is a routine called Xbalance which is called when a node gets too heavy on a particular side. XHere we need to take into account the special case that occurs when a Xsingle rotation was made but the HEIGHT of the rotated tree did NOT change Xas a result of the rotation (discussed in more detail in the next section): X X X /* return codes used by avl_insert(), avl_delete(), and balance() */ X#define HEIGHT_UNCHANGED 0 X#define HEIGHT_CHANGED 1 X X /* Balance Definitions */ X#define LEFT_HEAVY -1 X#define BALANCED 0 X#define RIGHT_HEAVY 1 X#define LEFT_IMBALANCE(nd) ( (nd)->bal < LEFT_HEAVY ) X#define RIGHT_IMBALANCE(nd) ( (nd)->bal > RIGHT_HEAVY ) X X/* X* balance() -- determines and performs the sequence of rotations needed X* (if any) to restore the balance of a given tree. X* X* Returns 1 if tree height changed due to rotation; 0 otherwise X*/ Xshort balance( rootp ) XAVLtree *rootp; X{ X short special_case = FALSE; X X if ( LEFT_IMBALANCE( *rootp ) ) { /* need a right rotation */ X if ( (*rootp) -> subtree[ LEFT ] -> bal == RIGHT_HEAVY ) X rotate_twice( rootp, RIGHT ); /* double RL rotation needed */ X X else /* single RR rotation needed */ X special_case = rotate_once( rootp, RIGHT ); X }/* if */ X X else if ( RIGHT_IMBALANCE( *rootp ) ) { /* need a left rotation */ X if ( (*rootp) -> subtree[ RIGHT ] -> bal == LEFT_HEAVY ) X rotate_twice( rootp, LEFT ); /* double LR rotation needed */ X X else /* single LL rotation needed */ X special_case = rotate_once( rootp, LEFT ); X }/* elif */ X X else return HEIGHT_UNCHANGED; /* no rotation occurred */ X X return ( special_case ) ? HEIGHT_UNCHANGED : HEIGHT_CHANGED; X}/* balance */ X XThis routine helps but now comes the hard part (IMHO at least), figuring Xout when the height of the current subtree has changed. X XCALCULATING WHEN THE HEIGHT OF THE CURRENT SUBTREE HAS CHANGED: X=============================================================== XAfter we have inserted or deleted a node from the current subtree, we Xneed to determine if the total height of the current tree has changed Xso that we may pass the information up the recursion stack to previous Xinstantiations of the insertion and deletion routines. X XLet us first consider the case of an insertion. The simplest case is Xat the point where the insertion occurred. Since we have created a node Xwhere one did not previously exist, we have increased the height of the Xinserted node from 0 to 1. Therefore we need to pass the value 1 (I will Xuse "1" for TRUE and "0" for FALSE) back to the previous level of Xrecursion to indicate the increase in the height of the current subtree. X X | after insertion | X NULL ================> | X A X X XThe remaining cases for an insertion are almost as simple. If a 0 (FALSE) Xwas the "height-change-indicator" passed back by inserting into a subtree Xof the current level, then there is no height change at the current level. XIt is true that the structure of one of the subtrees may have changed due Xto an insertion and/or rotation, but since the height of the subtree did Xnot change, neither did the height of the current level. X X | after insertion | X | ================> | X A A X / \ / \ X / \ / \ X b c b d X XIf the current level is balanced after inserting the node (but before Xattempting any rotations) then we just made one subtree equal in height Xto the other. Therefore the overall height of the current level remains Xunchanged and a 0 is returned. X X | after insertion | X | ================> | X A A X / / \ X / / \ X b b c X XBefore we go and write avl_insert, we will need some help from a few other Xsmall routines, most of which are needed for deletion more than for insertion. XThese routines will free/create a node, and tell the type of a node. X X/* ckalloc( size ) -- allocate space; check for success */ Xvoid *ckalloc( size ) Xint size; X{ X void *malloc(), *ptr; X X if ( (ptr = (char *) malloc( (unsigned) size)) == NULL ) { X fprintf( stderr, "Unable to allocate storage." ); X exit( 1 ); X }/* if */ X X return ptr; X}/* ckalloc */ X X X/* X* new_node() -- get space for a new node and its data; X* return the address of the new node X*/ XAVLtree new_node( data, size ) Xvoid *data; Xunsigned size; X{ X AVLtree root; X X root = (AVLtree) ckalloc( sizeof (AVLnode) ); X root -> data = (void *) ckalloc( size ); X memmove( root -> data, data, size ); X root -> bal = BALANCED; X root -> subtree[ LEFT ] = root -> subtree[ RIGHT ] = NULL_TREE; X X return root; X}/* new_node */ X X X/* X* free_node() -- free space for a node and its data! X* reset the node pointer to NULL X*/ Xvoid free_node( rootp ) XAVLtree *rootp; X{ X free( (void *) *rootp ); X *rootp = NULL_TREE; X}/* free_node */ X X X/* X* node_type() -- determine the number of null pointers for a given X* node in an AVL tree, Returns a value of type NODE X* which is an enumeration type with the following values: X* X* IS_TREE -- both subtrees are non-empty X* IS_LBRANCH -- left subtree is non-empty; right is empty X* IS_RBRANCH -- right subtree is non-empty; left is empty X* IS_LEAF -- both subtrees are empty X* IS_NULL -- given tree is empty X*/ XNODE node_type( tree ) XAVLtree tree; X{ X if ( tree == NULL_TREE ) X return IS_NULL; X X else if ( (tree -> subtree[ LEFT ] != NULL_TREE) X && (tree -> subtree[ RIGHT ] != NULL_TREE) ) X return IS_TREE; X X else if ( tree -> subtree[ LEFT ] != NULL_TREE ) X return IS_LBRANCH; X X else if ( tree -> subtree[ RIGHT ] != NULL_TREE ) X return IS_RBRANCH; X X else X return IS_LEAF; X}/* node_type */ X XNow the last helper routines we need will be a dirty trick. We need a function Xto compare items while we traverse the tree. Normally, we expect this compare Xfunction to return a strcmp() type result (<0, =0, or >0 for <,=,> respectively) XWe will be a little sneaky and write our own compare function which will take Xthe supplied compare function, and the node-type of the node being compared Xagainst. This will help in deletion when we want to delete the minimal/maximal Xelement of a given tree. We will go about it in such a way that we can delete Xor find a given item, or the min/max item in a tree. We do this as follows: X X/* X* avl_min() -- compare function used to find the minimal element in a tree X*/ Xint avl_min( elt1, elt2, nd_typ ) Xvoid *elt1, *elt2; XNODE nd_typ; X{ X if ( nd_typ == IS_RBRANCH || nd_typ == IS_LEAF ) X return 0; /* left subtree is empty -- this is the minimum */ X X else return -1; /* keep going left */ X}/* avl_min */ X X X/* X* avl_max() -- compare function used to find the maximal element in a tree X*/ Xint avl_max( elt1, elt2, nd_typ ) Xvoid *elt1, *elt2; XNODE nd_typ; X{ X if ( nd_typ == IS_RBRANCH || nd_typ == IS_LEAF ) X return 0; /* right subtree is empty -- this is the maximum */ X X else return 1; /* keep going right */ X}/* avl_max */ X XNow we can use avl_min/avl_max as compare functions. If the compare Xfunction is other than one of these two, usually it will only use the first Xtwo parameters (so it gets an extra one). This is not great for portability Xso we should really do something like: X X/* X* avl_compare() -- compare an item with a node-item in an avl tree X*/ Xint avl_compare( elt1, elt2, nd_typ, compar ) Xvoid *elt1, *elt2; XNODE nd_typ; Xint (*compar)(); X{ X if ( compare == avl_min || compar == avl_max ) X return (*compar)( elt1, elt2, nd_typ ); X else X return (*compare)( elt1, elt2 ); X}/* avl_compare */ X XIf you wish to do this you may, but my code works without it, it just ignores Xany extra parameters. If you have ANSI-C you may get some compiler complaints. XIn any case, I shall proceed without using avl_compare(). In addition, avl_min Xand avl_max should only be passed to avl_find (search without inserting), Xand avl_delete (NOT avl_insert). We are now ready to write avl_insert: X X/* X* avl_insert() -- insert an item into the given tree X* X* PARAMETERS: X* data -- a pointer to a pointer to the data to add; X* On exit, *data is NULL if insertion succeeded, X* otherwise address of the duplicate key X* rootp -- a pointer to an AVL tree X* compar -- name of the function to compare 2 data items X*/ Xshort avl_insert( data, rootp, compar ) Xvoid **data; XAVLtree *rootp; Xint (*compar)(); X{ X short increase; X int cmp; X X if ( *rootp == NULL_TREE ) { /* insert new node here */ X *rootp = new_node( *data, SIZE_OF_DATA )) ); X *data = NULL; /* set return value in data */ X return HEIGHT_CHANGED; X }/* if */ X X cmp = (*compar)( *data, (*rootp) -> data ); /* compare data items */ X X if ( cmp < 0 ) { /* insert into the left subtree */ X increase = -avl_insert( data, &( (*rootp) -> subtree[ LEFT ] ), compar ); X if ( *data != NULL ) return HEIGHT_UNCHANGED; X }/* elif */ X X else if ( cmp > 0 ) { /* insert into the right subtree */ X increase = avl_insert( data, &( (*rootp) -> subtree[ RIGHT ] ), compar ); X if ( *data != NULL ) return HEIGHT_UNCHANGED; X }/* elif */ X X else { /* data already exists */ X *data = (*rootp) -> data; /* set return value in data */ X return HEIGHT_UNCHANGED; X } /* else */ X X (*rootp) -> bal += increase; /* update balance factor */ X X /************************************************************************ X * re-balance if needed -- height of current tree increases only if its X * subtree height increases and the current tree needs no rotation. X ************************************************************************/ X if ( increase && (*rootp) -> bal ) X return ( 1 - balance( rootp ) ); X else X return HEIGHT_UNCHANGED; X}/* avl_insert */ X X XDeletion is more complicated than insertion. The height of the current level Xmay decrease for two reasons: either a rotation occurred to decrease the Xheight of a subtree (and hence the current level), or a subtree shortened Xin height resulting in a now balanced current level (subtree was "trimmed Xdown" to the same size as the other). Just because a rotation has occurred Xhowever, does not mean that the subtree height has decreased. There is a Xspecial case where rotating preserves the current subtree height. X XSuppose I have a tree as follows: X X X C X / \ X A E X / \ X D F X X XDeleting "A" results in the following (imbalanced) tree: X X X C X \ X E X / \ X D F X X XThis type of imbalance cannot occurr during insertion, only during Xdeletion. Notice that the root has a balance of 2 but its heavy subtree Xhas a balance of zero (the other case would be a -2 and a 0). Performing Xa single left rotation to restore the balance results in: X X X E X / \ X C F X \ X D X X XThis tree has the same height as it did before it was rotated. Hence, Xwe may determine if deletion caused the subtree height to change by Xseeing if one of the following occurred: X X 1) If the new balance (after deletion) is zero and NO rotation X took place. X X 2) If a rotation took place but was NOT one of the special rotations X mentioned above (a -2:0 or a 2:0 rotation). X XFor insertion, we only needed to check if a rotation occurred to see if the Xsubtree height had changed. But for deletion we need to ckeck all of the above. XSo for deletion of a node we have: X X/* X* avl_delete() -- delete an item from the given tree X* X* PARAMETERS: X* data -- a pointer to a pointer to the key to delete X* On exit, *data points to the deleted data item X* (or NULL if deletion failed). X* rootp -- a pointer to an AVL tree X* compar -- name of function to compare 2 data items X*/ XPRIVATE short avl_delete( data, rootp, compar ) Xvoid **data; XAVLtree *rootp; Xint (*compar)(); X{ X short decrease; X int cmp; X AVLtree old_root = *rootp; X NODE nd_typ = node_type( *rootp ); X DIRECTION dir = (nd_typ == IS_LBRANCH) ? LEFT : RIGHT; X X if ( *rootp == NULL_TREE ) { /* data not found */ X *data = NULL; /* set return value in data */ X return HEIGHT_UNCHANGED; X }/* if */ X X /* NOTE the extra parameter to compare this time */ X cmp = compar( *data, (*rootp) -> data, nd_typ ); /* compare data items */ X X if ( cmp < 0 ) { /* delete from left subtree */ X decrease = -avl_delete( data, &( (*rootp) -> subtree[ LEFT ] ), compar ); X if ( *data == NULL ) return HEIGHT_UNCHANGED; X }/* elif */ X X else if ( cmp > 0 ) { /* delete from right subtree */ X decrease = avl_delete( data, &( (*rootp) -> subtree[ RIGHT ] ), compar ); X if ( *data == NULL ) return HEIGHT_UNCHANGED; X }/* elif */ X X /************************************************************************ X * At this point we know that if "cmp" is zero then "*rootp" points to X * the node that we need to delete. There are three cases: X * X * 1) The node is a leaf. Remove it and return. X * X * 2) The node is a branch (has only 1 child). Make "*rootp" X * (the pointer to this node) point to the child. X * X * 3) The node has two children. We swap data with the successor of X * "*rootp" (the smallest item in its right subtree) and delete X * the successor from the right subtree of "*rootp". The X * identifier "decrease" should be reset if the subtree height X * decreased due to the deletion of the sucessor of "rootp". X ************************************************************************/ X X else { /* cmp == 0 */ X *data = (*rootp) -> data; /* set return value in data */ X X switch ( nd_typ ) { /* what kind of node are we removing? */ X case IS_LEAF : X free_node( rootp ); /* free the leaf, its height */ X return HEIGHT_CHANGED; /* changes from 1 to 0, return 1 */ X X case IS_RBRANCH : /* only child becomes new root */ X case IS_LBRANCH : X *rootp = (*rootp) -> subtree[ dir ]; X free_node( &old_root ); /* free the deleted node */ X return HEIGHT_CHANGED; /* we just shortened the "dir" subtree */ X X case IS_TREE : X decrease = avl_delete( &( (*rootp) -> data ), X &( (*rootp) -> subtree[ RIGHT ] ), X avl_min ); X } /* switch */ X } /* else */ X X (*rootp) -> bal -= decrease; /* update balance factor */ X X /********************************************************************** X * Rebalance if necessary -- the height of current tree changes if one X * of two things happens: (1) a rotation was performed which changed X * the height of the subtree (2) the subtree height decreased and now X * matches the height of its other subtree (so the current tree now X * has a zero balance when it previously did not). X **********************************************************************/ X if ( decrease && (*rootp) -> bal ) /* return 1 if height */ X return balance( rootp ); /* changed due to rotation */ X X else if ( decrease && !(*rootp) -> bal ) /* or if balance is 0 from */ X return HEIGHT_CHANGED; /* height decrease of subtree */ X X else X return HEIGHT_UNCHANGED; X X}/* avl_delete */ X XNOTICE how in the case of nd_typ == IS_TREE, I only need one statement. This Xis due to the way avl_delete sets its parameters. The data pointer passed on Xentrance points to the deleted node's data on exit. So I just delete the Xminimal element of the right subtree, and steal its data as my-own (returning Xmy former data item on exit). X X XAnd there we have it, the mantainenance of AVL tree manipulations, the brunt Xof which is covered in 5 routines, none of which (except for delete which Xis less than 1-1/2pages) is greater than 1 normal page in length, including Xcomments (and there are a lot). The main routines are: X Xrotate_once(), rotate_twice(), balance(), avl_insert(), avl_delete(). X XAll other routines are very small and auxillary in nature. END_OF_FILE if test 37772 -ne `wc -c <'README'`; then echo shar: \"'README'\" unpacked with wrong size! fi # end of 'README' fi if test -f 'avl.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'avl.h'\" else echo shar: Extracting \"'avl.h'\" \(2078 characters\) sed "s/^X//" >'avl.h' <<'END_OF_FILE' X/** X* avl.h -- public types and external declarations for avl trees X* X* Created 03/01/89 by Brad Appleton X* X* ^{Mods:* } X* X* Fri Jul 14 13:54:12 1989, Rev 1.0, brad(0165) X* X**/ X X#ifndef AVL_H X#define AVL_H X X#ifdef __STDC__ X# define _P(x) x X#else X# define _P(x) /*x*/ X#endif X X /* definition of traversal type */ Xtypedef enum { PREORDER, INORDER, POSTORDER } VISIT; X X X /* definition of sibling order type */ Xtypedef enum { LEFT_TO_RIGHT, RIGHT_TO_LEFT } SIBLING_ORDER; X X X /* definition of node type */ Xtypedef enum { IS_TREE, IS_LBRANCH, IS_RBRANCH, IS_LEAF, IS_NULL } NODE; X X X /* definition of opaque type for AVL trees */ Xtypedef void *AVL_TREE; X X X#ifndef NEXTERN X X /* Constructor and Destructor functions for AVL trees: X * avlfree is a macro for avldispose in the fashion X * of free(). It assumes certain default values X * (shown below) for the deallocation function and X * for the order in which children are traversed. X */ Xextern AVL_TREE avlinit _P( int(*) (), unsigned(*)() ); Xextern void avldispose _P( AVL_TREE *, void(*) (), SIBLING_ORDER ); X#define avlfree(x) avldispose _P( &(x), free, LEFT_TO_RIGHT ) X X X /* Routine for manipulating/accessing each data item in a tree */ Xextern void avlwalk _P( AVL_TREE, void(*) (), SIBLING_ORDER ); X X X /* Routine for obtaining the size of an AVL tree */ Xextern int avlcount _P( AVL_TREE ); X X X /* Routines to search for a given item */ Xextern void *avlins _P( void *, AVL_TREE ); Xextern void *avldel _P( void *, AVL_TREE ); Xextern void *avlfind _P( void *, AVL_TREE ); X X X /* Routines to search for the minimal item of a tree */ Xextern void *avldelmin _P( AVL_TREE ); Xextern void *avlfindmin _P( AVL_TREE ); X X X /* Routines to search for the maximal item of a tree */ Xextern void *avldelmax _P( AVL_TREE ); Xextern void *avlfindmax _P( AVL_TREE ); X X#endif /* NEXTERN */ X X#undef _P X#endif /* AVL_H */ END_OF_FILE if test 2078 -ne `wc -c <'avl.h'`; then echo shar: \"'avl.h'\" unpacked with wrong size! fi # end of 'avl.h' fi if test -f 'avl_test.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'avl_test.c'\" else echo shar: Extracting \"'avl_test.c'\" \(3000 characters\) sed "s/^X//" >'avl_test.c' <<'END_OF_FILE' X/** X* avl_test.c -- C source file to test the object-oriented AVL Tree X* Library (dont forget to link with "avl.o"). X* X* Created 03/01/89 by Brad Appleton X* X* ^{Mods:* } X* X* Fri Jul 14 13:54:34 1989, Rev 1.0, brad(0165) X* X**/ X X#ifndef DEBUG X# define DBG(x) /* x */ X#else X# define DBG(x) x X#endif X X#define LEFT_SUBTREE_EMPTY(nd) ( (nd == IS_RBRANCH) || (nd == IS_LEAF) ) X#define RIGHT_SUBTREE_EMPTY(nd) ( (nd == IS_LBRANCH) || (nd == IS_LEAF) ) X X#include X#include "avl.h" X#include "testvals.h" X Xstatic int intcmp( i1, i2 ) int *i1, *i2; { return ( *i1 - *i2 ); } Xstatic int intsize( i ) int i; { return sizeof(i); } X Xstatic void avlprint( dataptr, order, node, level, bal ) Xvoid *dataptr; XVISIT order; XNODE node; Xint level; Xshort bal; X{ X int len = ((level - 1) * 5), *key; X char fmt[9]; X X key = (int *) dataptr; X if ( len ) sprintf( fmt, "%%-%ds", len ); X else strcpy( fmt, "%-1s" ); X X if ( node == IS_NULL ) printf( "NULL_TREE\n" ); X X else { X if ( (order == PREORDER) && LEFT_SUBTREE_EMPTY( node ) ) X { printf( fmt, " " ); printf( " ==NULL==\n" ); } X X if ( order == INORDER ) X { printf( fmt, " " ); printf( "%d:%d\n", *key, bal ); } X X if ( (order == POSTORDER) && RIGHT_SUBTREE_EMPTY( node ) ) X { printf( fmt, " " ); printf( " ==NULL==\n" ); } X }/* else */ X}/* avlprint */ X X Xstatic void avlfreedata( dataptr, order, node, level ) Xvoid *dataptr; XVISIT order; XNODE node; Xint level; X{ X int key = (int) *( (int *) dataptr ); X X if ( order == PREORDER ) { X printf( "freeing left subtree of key: %d ...\n", key ); X } X else if ( order == INORDER ) { X printf( "freeing right subtree of key: %d ...\n", key ); X } X else if ( order == POSTORDER ) { X printf( "freeing avl-node for key: %d ...\n", key ); X } X}/* avlfreedata */ X X Xmain() X{ X AVL_TREE mytree; X int i; X X mytree = avlinit( intcmp, intsize ); X X for ( i = 0 ; i < NUM_VALS ; i++ ) { X printf( "+++ inserting key #%d: %d +++\n", i, TestVals[i] ); X avlins( (void *) &( TestVals[i] ), mytree ); X DBG( avlwalk( mytree, avlprint, RIGHT_TO_LEFT ); ) X }/* for */ X X printf( "------------------ contents of tree ----------------\n" ); X avlwalk( mytree, avlprint, RIGHT_TO_LEFT ); X printf( "----------------------------------------------------\n" ); X X for ( i = 0 ; i < NUM_DELS ; i++ ) { X printf( "+++ deleting key #%d: %d +++\n", i, DelVals[i] ); X DBG( avlwalk( mytree, avlprint, RIGHT_TO_LEFT ); ) X avldel( (void *) &( DelVals[i] ), mytree ); X }/* for */ X X printf( "------------------ contents of tree ----------------\n" ); X avlwalk( mytree, avlprint, RIGHT_TO_LEFT ); X printf( "----------------------------------------------------\n" ); X printf( "Deallocating tree ...\n" ); X avldispose( &mytree, avlfreedata, LEFT_TO_RIGHT ); X printf( "DONE!" ); X exit( 0 ); X}/* main */ END_OF_FILE if test 3000 -ne `wc -c <'avl_test.c'`; then echo shar: \"'avl_test.c'\" unpacked with wrong size! fi # end of 'avl_test.c' fi if test -f 'avl_typs.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'avl_typs.h'\" else echo shar: Extracting \"'avl_typs.h'\" \(1665 characters\) sed "s/^X//" >'avl_typs.h' <<'END_OF_FILE' X/** X* avl_typs.h -- declaration of private types used for avl trees X* X* Created 03/01/89 by Brad Appleton X* X* ^{Mods:* } X* X* Fri Jul 14 13:55:58 1989, Rev 1.0, brad(0165) X* X**/ X X X /* definition of a NULL action and a NULL tree */ X#define NULL_ACTION ( ( void(*)() ) NULL ) X#define NULL_TREE ( (AVLtree) NULL ) X X X /* MIN and MAX macros (used for rebalancing) */ X#define MIN(a,b) ( (a) < (b) ? (a) : (b) ) X#define MAX(a,b) ( (a) > (b) ? (a) : (b) ) X X X /* Directional Definitions */ Xtypedef short DIRECTION; X#define LEFT 0 X#define RIGHT 1 X#define OPPOSITE(x) ( 1 - (x) ) X X X /* return codes used by avl_insert(), avl_delete(), and balance() */ X#define HEIGHT_UNCHANGED 0 X#define HEIGHT_CHANGED 1 X X X /* Balance Definitions */ X#define LEFT_HEAVY -1 X#define BALANCED 0 X#define RIGHT_HEAVY 1 X#define LEFT_IMBALANCE(nd) ( (nd)->bal < LEFT_HEAVY ) X#define RIGHT_IMBALANCE(nd) ( (nd)->bal > RIGHT_HEAVY ) X X X /* structure for a node in an AVL tree */ Xtypedef struct avl_node { X void *data; /* pointer to data */ X short bal; /* balance factor */ X struct avl_node *subtree[2]; /* LEFT and RIGHT subtrees */ X} AVLnode, *AVLtree; X X X /* structure which holds information about an AVL tree */ Xtypedef struct avl_descriptor { X AVLtree root; /* pointer to the root node of the tree */ X int (*compar)(); /* function used to compare keys */ X unsigned (*isize)(); /* function to return the size of an item */ X long count; /* number of nodes in the tree */ X} AVLdescriptor; END_OF_FILE if test 1665 -ne `wc -c <'avl_typs.h'`; then echo shar: \"'avl_typs.h'\" unpacked with wrong size! fi # end of 'avl_typs.h' fi if test -f 'key_gen.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'key_gen.c'\" else echo shar: Extracting \"'key_gen.c'\" \(383 characters\) sed "s/^X//" >'key_gen.c' <<'END_OF_FILE' X/** X* key_gen.c -- C source file to generate test keys (at random) X* to insert into an AVL tree X* X* Created 03/01/89 by Brad Appleton X* X* ^{Mods:* } X* X* Fri Jul 14 13:57:44 1989, Rev 1.0, brad(0165) X* X**/ X X#include X Xmain() { X int num, i; X X for ( i = 0 ; i < 500 ; i++ ) { X num = rand(); X printf( "%d\n", num ); X }/* for */ X X exit (0); X}/* main */ END_OF_FILE if test 383 -ne `wc -c <'key_gen.c'`; then echo shar: \"'key_gen.c'\" unpacked with wrong size! fi # end of 'key_gen.c' fi if test -f 'rotate.old' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'rotate.old'\" else echo shar: Extracting \"'rotate.old'\" \(3031 characters\) sed "s/^X//" >'rotate.old' <<'END_OF_FILE' X/** X* X* rotate.old -- first set of rotations used for avl trees. There are two ways X* to code up the avl tree rotations. X* X* The first way to implement the rotations is to write a X* single rotation procedure which adjusts balances with no X* prior knowledge of what they previously were. Then a double X* double roatation is merely two single rotation. This is the X* method used in this file. X* X* The second method is to write two procedures and to adjust X* balances by taking advantage of the knowledge of what the X* balances must be in order for the rotation procedure to have X* been called. This second method is implemented in the file X* "avl_tree.c" which contains all the other avl tree functions. X* X* The advantage of the first approach is less code. X* X* The advantage of the second approach is less function calls X* and less statements executed for a given rotation. X* X* ^{Mods:* } X* X* Fri Jul 14 13:56:20 1989, Rev 1.0, brad(0165) X* X* 16 Jun 89 -- Created. X**/ X X/* X* rotate_once() -- rotate a given node in the given direction X* to restore the balance of a tree X*/ XPRIVATE short rotate_once( rootp, dir ) XAVLtree *rootp; XDIRECTION dir; X{ X DIRECTION other_dir = OPPOSITE( dir ); /* opposite direction to "dir" */ X AVLtree old_root = *rootp; /* copy of original root of tree */ X short ht_unchanged; /* true if height unchanged */ X X ht_unchanged = ( (*rootp) -> subtree[ other_dir ] -> bal ) ? FALSE : TRUE; X X /* assign new root */ X *rootp = old_root -> subtree[ other_dir ]; X X /* new-root exchanges it's "dir" subtree for it's parent */ X old_root -> subtree[ other_dir ] = (*rootp) -> subtree[ dir ]; X (*rootp) -> subtree[ dir ] = old_root; X X /* update balances */ X if ( dir == LEFT ) { X old_root -> bal -= ( 1 + MAX( (*rootp) -> bal, 0) ); X (*rootp) -> bal -= ( 1 - MIN( old_root -> bal, 0) ); X }/* if */ X X else /* dir == RIGHT */ { X old_root -> bal += ( 1 - MIN( (*rootp)-> bal, 0) ); X (*rootp) -> bal += ( 1 + MAX( old_root -> bal, 0) ); X }/* else */ X X return ht_unchanged; X}/* rotate_once */ X X X/**************************************************************************** X* Normally I wouldnt bother with this next routine; I'd just call * X* the above function twice. However, by using the routine below, * X* I was able to use the same function calls in the "balance()" * X* routine in "avl_tree.fns". * X****************************************************************************/ X X X/* X* rotate_twice() -- rotate a given node in the given direction X* and then in the opposite direction X* to restore the balance of a tree X*/ XPRIVATE void rotate_twice( rootp, dir ) XAVLtree *rootp; XDIRECTION dir; X{ X DIRECTION other_dir = OPPOSITE( dir ); X X rotate_once( &( (*rootp) -> subtree[ other_dir ] ), other_dir ); X rotate_once( rootp, dir ); X X}/* rotate_twice */ END_OF_FILE if test 3031 -ne `wc -c <'rotate.old'`; then echo shar: \"'rotate.old'\" unpacked with wrong size! fi # end of 'rotate.old' fi if test -f 'testvals.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'testvals.h'\" else echo shar: Extracting \"'testvals.h'\" \(526 characters\) sed "s/^X//" >'testvals.h' <<'END_OF_FILE' X/** X* X* testvals.h -- test values for avl trees X* X* Created 03/01/89 by Brad Appleton X* X* ^{Mods:* } X* X* Fri Jul 14 13:53:18 1989, Rev 1.0, brad(0165) X* X**/ X Xint TestVals[] = { X 1, X 3, X 2, X 5, X 4, X 7, X 6, X 9, X 8, X 11, X 10, X 13, X 12, X 15, X 14 X}; /* TestVals */ X X#define NUM_VALS ( sizeof( TestVals ) / sizeof( int ) ) X X Xint DelVals[] = { X 1, X 2, X 3, X 4, X 5, X 6, X 7, X 8, X 9 X#ifdef NEVER X, X X 10, X 11, X 12, X 13, X 14, X 15 X#endif X}/* DelVals */; X X#define NUM_DELS ( sizeof( DelVals ) / sizeof( int ) ) END_OF_FILE if test 526 -ne `wc -c <'testvals.h'`; then echo shar: \"'testvals.h'\" unpacked with wrong size! fi # end of 'testvals.h' fi echo shar: End of archive 1 \(of 2\). cp /dev/null ark1isdone MISSING="" for I in 1 2 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked both archives. rm -f ark[1-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0 ______________________ "And miles to go before I sleep." ______________________ Brad Appleton brad@ssd.csd.harris.com Harris Computer Systems uunet!hcx1!brad Fort Lauderdale, FL USA ~~~~~~~~~~~~~~~~~~~~ Disclaimer: I said it, not my company! ~~~~~~~~~~~~~~~~~~~