AVL tree library (part 1 of 2)
Brad Appleton
brad at SSD.CSD.HARRIS.COM
Fri Mar 29 06:38:53 AEST 1991
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 at 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 <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 1 (of 2)."
# Contents: MANIFEST Makefile README avl.h avl_test.c avl_typs.h
# key_gen.c rotate.old testvals.h
# Wrapped by brad at hcx2 on Thu Mar 28 15:32:54 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'MANIFEST' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'MANIFEST'\"
else
echo shar: Extracting \"'MANIFEST'\" \(892 characters\)
sed "s/^X//" >'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 at wpi.wpi.edu
XSubject: Re: Binary Tree Re-balancing
XNewsgroups: comp.lang.c
XIn-Reply-To: <10403 at wpi.wpi.edu>
XOrganization: Harris Computer Systems, Fort Lauderdale, FL
XCc:
XBcc:
X
XIn article <10403 at 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 <stdio.h>
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 <stdio.h>
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 at ssd.csd.harris.com Harris Computer Systems
uunet!hcx1!brad Fort Lauderdale, FL USA
~~~~~~~~~~~~~~~~~~~~ Disclaimer: I said it, not my company! ~~~~~~~~~~~~~~~~~~~
More information about the Alt.sources
mailing list