brad@SSD.CSD.HARRIS.COM (Brad Appleton) (03/29/91)
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 <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@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@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 <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@ssd.csd.harris.com Harris Computer Systems
uunet!hcx1!brad Fort Lauderdale, FL USA
~~~~~~~~~~~~~~~~~~~~ Disclaimer: I said it, not my company! ~~~~~~~~~~~~~~~~~~~brad@SSD.CSD.HARRIS.COM (Brad Appleton) (03/29/91)
In article <2821@travis.csd.harris.com> brad@SSD.CSD.HARRIS.COM (Brad Appleton) writes:
This is a Beta release of part 2 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 <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 2 (of 2)."
# Contents: LICENSE avl.3 avl.c testvals.old
# Wrapped by brad@hcx2 on Thu Mar 28 15:32:56 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'LICENSE' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'LICENSE'\"
else
echo shar: Extracting \"'LICENSE'\" \(3563 characters\)
sed "s/^X//" >'LICENSE' <<'END_OF_FILE'
X_______________________________________________________________________________
X
X LICENSE
X =======
X
XThis software is not subject to any license of the American Telephone and
XTelegraph Company or of the Regents of the University of California.
X
XPermission is granted to anyone to use this software for any purpose on any
Xcomputer system, and to alter it and redistribute it freely, subject to the
Xfollowing restrictions:
X
X 1. Neither the authors of the software nor their employers
X (including any of the employers' subsidiaries and subdivisions)
X are responsible for maintaining & supporting this software or
X for any consequences resulting from the use of this software, no
X matter how awful, even if they arise from flaws in the software
X (see LIABILITY).
X
X 2. The origin of this software must not be misrepresented, either
X by explicit claim or by omission. Since few users ever read
X sources, credits must appear in the documentation.
X
X 3. Altered versions must be plainly marked as such, and must not be
X misrepresented as being the original software. Since few users
X ever read sources, credits must appear in the documentation.
X
X 4. This notice may not be removed or altered.
X_______________________________________________________________________________
X
X NO WARRANTY
X ===========
X
XBecause this software is licensed free of charge, we (the authors and/or
Xdistributors of this software) provide absolutely no warranty, to the extent
Xpermitted by applicable state law. Except when otherwise stated in writing,
Xthe authors and distributors of this software and/or other parties provide
Xthis program "as is" without warranty of any kind, either expressed or
Ximplied, including, but not limited to, the implied warranties of
Xmerchantability and fitness for a particular purpose. The entire risk as to
Xthe quality and performance of this software lies with the recipients and/or
Xusers of this software and not with any of the authors and/or distributors of
Xthis software, nor with any of their employers, including any of the
Xemployers' subsidiaries and subdivisions. Should the program prove defective,
Xthe recipients/users of this software assume the cost of all necessary
Xservicing, repair, or correction.
X_______________________________________________________________________________
X
X LIABILITY
X =========
X
XIn no event unless required by applicable law will the authors and/or
Xdistributors of this software, their employers, and any subsidiaries and/or
Xsubdivisions of their employers, and/or any other party who may redistribute
Xthis software as permitted in the LICENSE section of this notice, be liable to
Xthe recipients/users of this software for damages including any lost profits,
Xlost monies, or other special, incidental, or consequential damages arising
Xout of the use or inabilty to use (including but not limited to loss of data
Xor data being rendered inaccurate or lossed sustained by third parties or a
Xfailure of the software to operate with any other software or hardware) this
Xsoftware, even if you have been advised of the possibility of such damages, or
Xfor any claim by any other party.
X_______________________________________________________________________________
X
END_OF_FILE
if test 3563 -ne `wc -c <'LICENSE'`; then
echo shar: \"'LICENSE'\" unpacked with wrong size!
fi
# end of 'LICENSE'
fi
if test -f 'avl.3' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'avl.3'\"
else
echo shar: Extracting \"'avl.3'\" \(4005 characters\)
sed "s/^X//" >'avl.3' <<'END_OF_FILE'
X.TH AVL 3 "28 March 1991"
X.SH NAME
Xavl \- library for creating and manipulating AVL trees.
X.SH SYNOPSIS
X.nf
X#include <avl.h>
X
XAVL_TREE avlinit( int(*icmp)(), unsigned(*isize)() );
Xvoid avldispose( AVL_TREE *tree, void(*ifree)(), SIBLING_ORDER sib_ord );
Xvoid avlfree( AVL_TREE tree )
Xvoid avlwalk( AVL_TREE tree, void(*action)(), SIBLING_ORDER sib_ord );
Xint avlcount( AVL_TREE tree );
Xvoid *avlins( void *item, AVL_TREE tree );
Xvoid *avldel( void *item, AVL_TREE tree );
Xvoid *avlfind( void *item, AVL_TREE tree );
Xvoid *avldelmin( AVL_TREE tree );
Xvoid *avlfindmin( AVL_TREE tree );
Xvoid *avldelmax( AVL_TREE tree );
Xvoid *avlfindmax( AVL_TREE tree );
X.fi
X
X.SH DESCRIPTION
XThe functions above provide a library package for creating and manipulating
Xgeneric avl-trees.
X.PP
X.I Avlinit
Xtakes an item compare function (which returns a \fIstrcmp\fP-type result),
Xand a size function (which returns the size of an item), and returns the
Xroot of an empty AVL tree for the corresponding item-type.
X.PP
X.I Avldispose
Xwill walk through a tree, applying the function \fIifree\fP (which should be
Xsome type of item-deallocation function) to the item in each node, and then
Xdeallocates space for the given node. The parameter \fIorder\fP should be
Xone of \fILEFT_TO_RIGHT\fP or \fIRIGHT_TO_LEFT\fP.
Xof each node
X.PP
X.I Avlfree
Xis a macro which expands to
X"\f4avldispose( &tree, free, LEFT_TO_RIGHT )\fP".
X.PP
X.I Avlwalk
Xwill traverse each item in the tree in the specified sibling order and apply
Xthe function \fIaction\fP each time it encounters a node. Each non-empty
Xnode will be encountered three times (corresponding to the three different
Xtypes of tree traversal: preorder, inorder, and postorder). The declaration
Xfor \fIaction\fP should be the following:
X
X.RS
X.nf
X.ft 4
Xvoid action( void *dataptr, VISIT order, NODE node, int level, short bal );
X.ft R
X.fi
X
X.I Dataptr
Xis the pointer to the data item contained in the current node.
X.sp 8p
X.I Order
Xwill be one of
X.I PREORDER,
X.I INORDER,
Xor
X.I POSTORDER
Xdepending upon whether this is the first, second, or third time
X(respectively) that the current node has been visited by \fIavlwalk\fP.
X.sp 8p
X.I Node
Xwill be one of
X.I IS_TREE,
X.I IS_LBRANCH,
X.I IS_RBRANCH,
X.I IS_LEAF,
Xor
X.I IS_NULL
Xdepending upon whether the current node has two non-null children,
Xone non-null child in the left-subtree, one non-null child in the
Xright-subtree, two null children, or a null node (respectively).
X.sp 8p
X.I Level
Xwill be the current depth of the tree (with the root being level zero)
Xthat the current node corresponds to.
X.sp 8p
X.I Bal
Xwill be the balance factor for the current node (which should range
Xfrom -1 .. 1).
X.RE
X
X.PP
X.I Avlcount
Xwill return the number of items currently contained in the given AVL tree.
X.PP
X.I Avldel
Xwill remove the node containing the given item from the given AVL tree and
Xwill return a pointer to the data-item of the deleted node (or NULL if the
Xitem was not found in the tree).
X.PP
X.I Avlins
Xwill insert a node containing the given data item into the given AVL tree
Xand will return NULL (unless the item is already in the tree, in which case
Xthe address of the located data item is returned).
X.PP
X.I Avlfind
Xwill search for the node containing in the given tree which conatins the given
Xdata item. If found the address of the data item is returned, otherwise NULL
Xis returned.
X.PP
X.I Avldelmin
Xwill remove the "smallest" item (according the the compare function passed
Xto \fIavlinit\fP) from the given tree and return the address of the item
Xthat was removed.
X.PP
X.I Avlfindmin
Xwill return the address of the "smallest" data item in the tree.
X.PP
X.I Avldelmax
Xwill remove the "largest" item (according the the compare function passed
Xto \fIavlinit\fP) from the given tree and return the address of the item
Xthat was removed.
X.PP
X.I Avlfindmax
Xwill return the address of the "largest" data item in the tree.
X
X.SH AUTHOR
X.nf
XBrad Appleton <brad@ssd.csd.Harris.COM>
XHarris Computer Systems, Fort Lauderdale, FL USA
X.fi
END_OF_FILE
if test 4005 -ne `wc -c <'avl.3'`; then
echo shar: \"'avl.3'\" unpacked with wrong size!
fi
# end of 'avl.3'
fi
if test -f 'avl.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'avl.c'\"
else
echo shar: Extracting \"'avl.c'\" \(24464 characters\)
sed "s/^X//" >'avl.c' <<'END_OF_FILE'
X/**
X*
X* avl.c -- C source file for avl trees. Contains the auxillary routines
X* and defines for the avl tree functions and user interface and
X* includes all the necessary public and private routines
X*
X* Created 03/01/89 by Brad Appleton
X*
X* ^{Mods:* }
X*
X* Fri Jul 14 13:53:42 1989, Rev 1.0, brad(0165)
X*
X**/
X
X /* some common #defines used throughout most of my files */
X#define PUBLIC /* default */
X#define PRIVATE static
X#define FALSE 0
X#define TRUE !FALSE
X
X /* some defines for debugging purposes */
X#ifdef NDEBUG
X#define DBG(x) /* x */
X#else
X#define DBG(x) x
X#endif
X
X#define NEXTERN /* dont include "extern" declarations from header files */
X
X#include <stdio.h>
X#include "avl.h" /* public types for avl trees */
X#include "avl_typs.h" /* private types for avl trees */
X
X
X
X/************************************************************************
X* Auxillary functions
X*
X* routines to allocate/de-allocate an AVL node,
X* and determine the type of an AVL node.
X************************************************************************/
X
X/* ckalloc( size ) -- allocate space; check for success */
XPRIVATE char *ckalloc( size )
Xint size;
X{
X char *malloc(), *ptr;
X
X if ( (ptr = 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*/
XPRIVATE AVLtree 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 memcpy( 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*/
XPRIVATE void 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*/
XPRIVATE NODE node_type( tree )
XAVLtree tree;
X{
X if ( tree == NULL_TREE )
X return IS_NULL;
X
X else if ( (tree -> subtree[ LEFT ] != NULL_TREE) && (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
X
X
X/************************************************************************
X* PRIVATE functions for manipulating AVL trees
X*
X* This following defines a set of routines for creating, maintaining, and
X* manipulating AVL Trees as an Abtract Data Type. The routines in this
X* file that are accessible (through the avl tree user-interface) to other
X* files to allow other programmers to:
X*
X* Insert, Delete, and Find a given data item from a Tree.
X*
X* Delete and Find the minimal and Maximal items in a Tree.
X*
X* Walk through every node in a tree performing a giving operation.
X*
X* Walk through and free up space for every node in a tree while performing
X* a given operation on the data items as they are encountered.
X************************************************************************/
X
X
X
X/************************************************************************
X* routines used to find the minimal and maximal elements
X* (nodes) of an AVL tree.
X************************************************************************/
X
X/*
X* avl_min() -- compare function used to find the minimal element in a tree
X*/
XPRIVATE int 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*/
XPRIVATE int 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
X
X
X/************************************************************************
X* Routines to perform rotations on AVL trees
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 old_root -> bal = -( dir == LEFT ? --( (*rootp) -> bal ) : ++( (*rootp) -> bal ) );
X
X return ht_unchanged;
X}/* rotate_once */
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 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
X
X/************************************************************************
X* Rebalance an AVL tree
X************************************************************************/
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*/
XPRIVATE short 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
X
X/************************************************************************
X* Routines to: Find an item in an AVL tree
X* Insert an item into an AVL tree
X* Delete an item from an AVL tree
X************************************************************************/
X
X/*
X* avl_find() -- find an item in the given tree
X*
X* PARAMETERS:
X* data -- a pointer to the key to find
X* rootp -- a pointer to an AVL tree
X* compar -- name of a function to compare 2 data items
X*/
XPRIVATE void *avl_find( data, tree, compar )
Xvoid *data;
XAVLtree tree;
Xint (*compar)();
X{
X NODE nd_typ = node_type( tree );
X int cmp;
X
X while ( (cmp = (*compar)( data, tree -> data, nd_typ )) &&
X (tree != NULL_TREE) )
X tree = tree -> subtree[ (cmp < 0) ? LEFT : RIGHT ];
X
X return ( tree == NULL_TREE ) ? NULL : tree -> data;
X}/* avl_find */
X
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*/
XPRIVATE short avl_insert( data, size, rootp, compar )
Xvoid **data;
Xunsigned size;
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 );
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, size, &( (*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, size, &( (*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
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 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
X
X
X/**
X* Routines which Recursively Traverse an AVL TREE
X*
X* These routines may perform a particular action function upon each node
X* encountered. In these cases, "action" has the following definition:
X*
X* void action( data, order, node, level, bal )
X* void *data
X* VISIT order;
X* NODE node;
X* short bal;
X* int level;
X*
X* "data" is a pointer to the data field of an AVL node
X* "order" corresponds to whether this is the 1st, 2nd or 3rd time
X* that this node has been visited.
X* "node" indicates which children (if any) of the current node
X* are null.
X* "level" is the current level (or depth) in the tree of the
X* curent node.
X* "bal" is the balance factor of the current node.
X**/
X
X
X/************************************************************************
X* Walk an AVL tree, performing a given function at each node
X************************************************************************/
X
X
X/*
X* avl_walk -- traverse the given tree performing "action"
X* upon each data item encountered.
X*
X*/
XPRIVATE void avl_walk( tree, action, sibling_order, level )
XAVLtree tree;
Xvoid (*action)();
XSIBLING_ORDER sibling_order;
Xint level;
X{
X DIRECTION dir1 = (sibling_order == LEFT_TO_RIGHT) ? LEFT : RIGHT,
X dir2 = OPPOSITE( dir1 );
X NODE node = node_type( tree );
X
X if ( (tree != NULL_TREE) && (action != NULL_ACTION) ) {
X (*action)( tree -> data, PREORDER, node, level, tree -> bal );
X
X if ( tree -> subtree[ dir1 ] != NULL_TREE )
X avl_walk( tree -> subtree[ dir1 ], action, sibling_order, level+1 );
X
X (*action)( tree -> data, INORDER, node, level, tree -> bal );
X
X if ( tree -> subtree[ dir2 ] != NULL_TREE )
X avl_walk( tree -> subtree[ dir2 ], action, sibling_order, level+1 );
X
X (*action)( tree -> data, POSTORDER, node, level, tree -> bal );
X }/* if non-empty tree */
X
X}/* avl_walk */
X
X
X
X/************************************************************************
X* Walk an AVL tree, de-allocating space for each node
X* and performing a given function at each node
X* (such as de-allocating the user-defined data item).
X************************************************************************/
X
X
X/*
X* avl_free() -- free up space for all nodes in a given tree
X* performing "action" upon each data item encountered.
X*
X* (only perform "action" if it is a non-null function)
X*/
X
XPRIVATE void avl_free( rootp, action, sibling_order, level )
XAVLtree *rootp;
Xvoid (*action)();
XSIBLING_ORDER sibling_order;
Xint level;
X{
X DIRECTION dir1 = (sibling_order == LEFT_TO_RIGHT) ? LEFT : RIGHT,
X dir2 = OPPOSITE( dir1 );
X NODE node = node_type( *rootp );
X
X if ( *rootp != NULL_TREE ) {
X
X if ( action != NULL_ACTION )
X (*action)( (*rootp) -> data, PREORDER, node, level );
X
X if ( (*rootp) -> subtree[ dir1 ] != NULL_TREE )
X avl_free( &( (*rootp) -> subtree[ dir1 ] ),
X action, sibling_order, level+1 );
X
X if ( action != NULL_ACTION )
X (*action)( (*rootp) -> data, INORDER, node, level );
X
X if ( (*rootp) -> subtree[ dir2 ] != NULL_TREE )
X avl_free( &( (*rootp) -> subtree[ dir2 ] ),
X action, sibling_order, level+1 );
X
X if ( action != NULL_ACTION )
X (*action)( (*rootp) -> data, POSTORDER, node, level );
X
X free( *rootp );
X }/* if non-empty tree */
X
X}/* avl_free */
X
X
X
X
X/**********************************************************************
X*
X* C-interface (public functions) for avl trees
X*
X* These are the functions that are visible to the user of the
X* AVL Tree Library. Mostly they just return or modify a
X* particular attribute, or Call a private functions with the
X* given parameters.
X*
X* Note that public routine names begin with "avl" whereas
X* private routine names that are called by public routines
X* begin with "avl_" (the underscore character is added).
X*
X* Each public routine must convert (cast) any argument of the
X* public type "AVL_TREE" to a pointer to on object of the
X* private type "AVLdescriptor" before passing the actual
X* AVL tree to any of the private routines. In this way, the
X* type "AVL_TREE" is implemented as an opaque type.
X*
X* An "AVLdescriptor" is merely a container for AVL-tree
X* objects which contains the pointer to the root of the
X* tree and the various attributes of the tree.
X*
X* The function types prototypes for the routines which follow
X* are declared in the include file "avl.h"
X*
X***********************************************************************/
X
X
X
X/*
X* avlinit() -- get space for an AVL descriptor for the given tree
X* structure and initialize its fields.
X*/
XPUBLIC AVL_TREE avlinit( compar, isize )
Xint (*compar) ();
Xunsigned (*isize) ();
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) ckalloc( sizeof (AVLdescriptor) );
X avl_desc -> root = NULL_TREE;
X avl_desc -> compar = compar;
X avl_desc -> isize = isize;
X avl_desc -> count = 0;
X
X return (AVL_TREE) avl_desc;
X}/* avlinit */
X
X
X
X/*
X* avldispose() -- free up all space associated with the given tree structure.
X*/
XPUBLIC void avldispose( treeptr, action, sibling_order )
XAVL_TREE *treeptr;
Xvoid (*action) ();
XSIBLING_ORDER sibling_order;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) *treeptr;
X avl_free( &(avl_desc -> root), action, sibling_order, 1 );
X *treeptr = (AVL_TREE) NULL;
X}/* avldispose */
X
X
X
X/*
X* avlwalk() -- traverse the given tree structure and perform the
X* given action on each data item in the tree.
X*/
XPUBLIC void avlwalk( tree, action, sibling_order )
XAVL_TREE tree;
Xvoid (*action)();
XSIBLING_ORDER sibling_order;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_walk( avl_desc -> root, action, sibling_order, 1 );
X}/* avlwalk */
X
X
X
X/*
X* avlcount () -- return the number of nodes in the given tree
X*/
XPUBLIC int avlcount( tree )
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X return avl_desc -> count;
X}/* avlcount */
X
X
X
X/*
X* avlins() -- insert the given item into the tree structure
X*/
XPUBLIC void *avlins( data, tree )
Xvoid *data;
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_insert( &data, (*(avl_desc -> isize))( data ), &(avl_desc -> root), avl_desc -> compar );
X if ( data == NULL ) ++(avl_desc -> count);
X
X return data;
X}/* avlins */
X
X
X
X/*
X* avldel() -- delete the given item from the given tree structure
X*/
XPUBLIC void *avldel( data, tree )
Xvoid *data;
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_delete( &data, &(avl_desc -> root), avl_desc -> compar );
X if ( data != NULL ) --(avl_desc -> count);
X
X return data;
X}/* avldel */
X
X
X
X/*
X* avlfind() -- find the given item in the given tree structure
X* and return its address (NULL if not found).
X*/
XPUBLIC void *avlfind( data, tree )
Xvoid *data;
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X return avl_find( data, &(avl_desc -> root), avl_desc -> compar );
X}/* avlfind */
X
X
X
X/*
X* avldelmin() -- delete the minimal item from the given tree structure
X*/
XPUBLIC void *avldelmin( tree )
XAVL_TREE tree;
X{
X void *data;
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_delete( &data, &(avl_desc -> root), avl_min );
X if ( data != NULL ) --(avl_desc -> count);
X
X return data;
X}/* avldelmin */
X
X
X
X/*
X* avlfindmin() -- find the minimal item in the given tree structure
X* and return its address (NULL if not found).
X*/
XPUBLIC void *avlfindmin( tree )
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X return avl_find( NULL, &(avl_desc -> root), avl_min );
X}/* avlfindmin */
X
X
X
X/*
X* avldelmax() -- delete the maximal item from the given tree structure
X*/
XPUBLIC void *avldelmax( tree )
XAVL_TREE tree;
X{
X void *data;
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X avl_delete( &data, &(avl_desc -> root), avl_max );
X if ( data != NULL ) --(avl_desc -> count);
X
X return data;
X}/* avldelmax */
X
X
X
X/*
X* avlfindmax() -- find the maximal item in the given tree structure
X* and return its address (NULL if not found).
X*/
XPUBLIC void *avlfindmax (tree)
XAVL_TREE tree;
X{
X AVLdescriptor *avl_desc;
X
X avl_desc = (AVLdescriptor *) tree;
X return avl_find( NULL, &(avl_desc -> root), avl_max );
X}/* avlfindmax */
END_OF_FILE
if test 24464 -ne `wc -c <'avl.c'`; then
echo shar: \"'avl.c'\" unpacked with wrong size!
fi
# end of 'avl.c'
fi
if test -f 'testvals.old' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'testvals.old'\"
else
echo shar: Extracting \"'testvals.old'\" \(9970 characters\)
sed "s/^X//" >'testvals.old' <<'END_OF_FILE'
X/**
X*
X* testvals.old -- old test values for avl trees.
X*
X* Created 03/01/89 by Brad Appleton
X*
X* ^{Mods:* }
X*
X**/
X
Xint TestVals[] = {
X 16838,
X 5758,
X 10113,
X 17515,
X 31051,
X 5627,
X 23010,
X 7419,
X 16212,
X 4086,
X 2749,
X 12767,
X 9084,
X 12060,
X 32225,
X 17543,
X 25089,
X 21183,
X 25137,
X 25566,
X 26966,
X 4978,
X 20495,
X 10311,
X 11367,
X 30054,
X 17031,
X 13145,
X 19882,
X 25736,
X 30524,
X 28505,
X 28394,
X 22102,
X 24851,
X 19067,
X 12754,
X 11653,
X 6561,
X 27096,
X 13628,
X 15188,
X 32085,
X 4143,
X 6967,
X 31406,
X 24165,
X 13403,
X 25562,
X 24834,
X 31353,
X 920,
X 10444,
X 24803,
X 7962,
X 19318,
X 1422,
X 31327,
X 10457,
X 1945,
X 14479,
X 29983,
X 18751,
X 3894,
X 18670,
X 8259,
X 16248,
X 7757,
X 15629,
X 13306,
X 28606,
X 13990,
X 11738,
X 12516,
X 1414,
X 5262,
X 17116,
X 22825,
X 3181,
X 13134,
X 25343,
X 8022,
X 11233,
X 7536,
X 9760,
X 9979,
X 29071,
X 1201,
X 21336,
X 13061,
X 22160,
X 24005,
X 30729,
X 7644,
X 27475,
X 31693,
X 25514,
X 14139,
X 22088,
X 26521,
X 5202,
X 9171,
X 4434,
X 28317,
X 24582,
X 6815,
X 4586,
X 9653,
X 26306,
X 7174,
X 18451,
X 23448,
X 6473,
X 32434,
X 8193,
X 14110,
X 24748,
X 28210,
X 29320,
X 32049,
X 12956,
X 14162,
X 4166,
X 14997,
X 7793,
X 32310,
X 21391,
X 19799,
X 7926,
X 14905,
X 25885,
X 2582,
X 15610,
X 5000,
X 8052,
X 30965,
X 20120,
X 32380,
X 15639,
X 26204,
X 24385,
X 12475,
X 15725,
X 17265,
X 3214,
X 19471,
X 11376,
X 4697,
X 25543,
X 23297,
X 14619,
X 23087,
X 3123,
X 31549,
X 18065,
X 24256,
X 18973,
X 20901,
X 25613,
X 6157,
X 9899,
X 9267,
X 22413,
X 9598,
X 18526,
X 13711,
X 10046,
X 14566,
X 18536,
X 15988,
X 19878,
X 13626,
X 4273,
X 8387,
X 1171,
X 32017,
X 3752,
X 12388,
X 21191,
X 11483,
X 18122,
X 11744,
X 18528,
X 15585,
X 5363,
X 20159,
X 5641,
X 18176,
X 9575,
X 28578,
X 27363,
X 27685,
X 29344,
X 19489,
X 17713,
X 5511,
X 21461,
X 22626,
X 8645,
X 3496,
X 26703,
X 6270,
X 13870,
X 11529,
X 27499,
X 4500,
X 8607,
X 5808,
X 15725,
X 12457,
X 16542,
X 16474,
X 11531,
X 17222,
X 3952,
X 17024,
X 19894,
X 24015,
X 18247,
X 11276,
X 26278,
X 19365,
X 8746,
X 21976,
X 18092,
X 25851,
X 29088,
X 29163,
X 2231,
X 26233,
X 29732,
X 21106,
X 5411,
X 9874,
X 5448,
X 9344,
X 27589,
X 17574,
X 1191,
X 6789,
X 695,
X 11735,
X 20364,
X 17040,
X 17892,
X 5035,
X 26979,
X 1092,
X 850,
X 12390,
X 20195,
X 668,
X 20531,
X 29989,
X 12281,
X 23902,
X 12970,
X 32186,
X 19571,
X 3680,
X 7261,
X 26187,
X 28529,
X 24190,
X 446,
X 24233,
X 13708,
X 11863,
X 6681,
X 6001,
X 2499,
X 3786,
X 5214,
X 25829,
X 1322,
X 25907,
X 19628,
X 13192,
X 7505,
X 5990,
X 20129,
X 10875,
X 19829,
X 31591,
X 12388,
X 6042,
X 9833,
X 1775,
X 4719,
X 342,
X 28994,
X 31392,
X 20509,
X 31313,
X 20677,
X 1282,
X 11511,
X 4795,
X 3474,
X 6469,
X 2750,
X 879,
X 30989,
X 30134,
X 29752,
X 28364,
X 4880,
X 5629,
X 2235,
X 21332,
X 24145,
X 3356,
X 5243,
X 3079,
X 3988,
X 807,
X 24979,
X 31357,
X 914,
X 21187,
X 3540,
X 14022,
X 10149,
X 609,
X 29009,
X 24833,
X 16696,
X 5432,
X 24999,
X 28863,
X 16369,
X 28676,
X 24077,
X 7701,
X 1691,
X 19840,
X 28703,
X 16515,
X 22229,
X 32420,
X 19817,
X 16264,
X 19324,
X 29343,
X 1462,
X 28929,
X 3546,
X 17043,
X 18967,
X 325,
X 12683,
X 15634,
X 6322,
X 16642,
X 25395,
X 11612,
X 22864,
X 29910,
X 21985,
X 23126,
X 13988,
X 685,
X 6978,
X 31050,
X 16476,
X 6365,
X 21126,
X 4193,
X 8681,
X 11011,
X 23058,
X 1249,
X 31247,
X 24731,
X 28650,
X 20774,
X 7980,
X 20833,
X 27868,
X 7778,
X 23624,
X 11115,
X 1645,
X 15892,
X 29408,
X 7939,
X 17285,
X 16202,
X 28018,
X 11334,
X 4058,
X 7062,
X 3784,
X 11901,
X 6684,
X 14289,
X 27141,
X 16702,
X 26853,
X 13458,
X 28528,
X 23363,
X 21087,
X 19052,
X 31235,
X 15109,
X 17075,
X 11755,
X 10675,
X 288,
X 32053,
X 14157,
X 5758,
X 5222,
X 17488,
X 18945,
X 10294,
X 11200,
X 5171,
X 14305,
X 7951,
X 6601,
X 23608,
X 7214,
X 6377,
X 13865,
X 25369,
X 27215,
X 8030,
X 177,
X 16849,
X 11337,
X 2699,
X 23099,
X 8531,
X 11517,
X 17567,
X 28479,
X 9966,
X 2597,
X 14885,
X 12341,
X 15227,
X 27149,
X 785,
X 29615,
X 6476,
X 20753,
X 4236,
X 7730,
X 19668,
X 21210,
X 27519,
X 27608,
X 5142,
X 6999,
X 20449,
X 14246,
X 18638,
X 2941,
X 12481,
X 23726,
X 16738,
X 26047,
X 28947,
X 3300,
X 21639,
X 17996,
X 23866,
X 14785,
X 27571,
X 25356,
X 12633,
X 27289,
X 20551,
X 20312,
X 14426,
X 7357,
X 8056,
X 16252,
X 20410,
X 2384,
X 4353,
X 2029,
X 23579,
X 27882,
X 31882,
X 21577,
X 31368,
X 11502,
X 18902,
X 21012,
X 31365,
X 30379,
X 14256,
X 19244,
X 27870,
X 13365,
X 9619,
X 27665
X }; /* TestVals */
X
X#define NUM_VALS ( sizeof( TestVals ) / sizeof( int ) )
X
X
Xint DelVals[] = {
X 16838,
X 5758,
X 10113,
X 17515,
X 31051,
X 5627,
X 23010,
X 7419,
X 16212,
X 4086,
X 2749,
X 12767,
X 9084,
X 12060,
X 32225,
X 17543,
X 25089,
X 21183,
X 25137,
X 25566,
X 26966,
X 4978,
X 20495,
X 10311,
X 11367,
X 30054,
X 17031,
X 13145,
X 19882,
X 25736,
X 30524,
X 28505,
X 28394,
X 22102,
X 24851,
X 19067,
X 12754,
X 11653,
X 6561,
X 27096,
X 13628,
X 15188,
X 32085,
X 4143,
X 6967,
X 31406,
X 24165,
X 13403,
X 25562,
X 24834,
X 31353,
X 920,
X 10444,
X 24803,
X 7962,
X 19318,
X 1422,
X 31327,
X 10457,
X 1945,
X 14479,
X 29983,
X 18751,
X 3894,
X 18670,
X 8259,
X 16248,
X 7757,
X 15629,
X 13306,
X 28606,
X 13990,
X 11738,
X 12516,
X 1414,
X 5262,
X 17116,
X 22825,
X 3181,
X 13134,
X 25343,
X 8022,
X 11233,
X 7536,
X 9760,
X 9979,
X 29071,
X 1201,
X 21336,
X 13061,
X 22160,
X 24005,
X 30729,
X 7644,
X 27475,
X 31693,
X 25514,
X 14139,
X 22088,
X 26521,
X 5202,
X 9171,
X 4434,
X 28317,
X 24582,
X 6815,
X 4586,
X 9653,
X 26306,
X 7174,
X 18451,
X 23448,
X 6473,
X 32434,
X 8193,
X 14110,
X 24748,
X 28210,
X 29320,
X 32049,
X 12956,
X 14162,
X 4166,
X 14997,
X 7793,
X 32310,
X 21391,
X 19799,
X 7926,
X 14905,
X 25885,
X 2582,
X 15610,
X 5000,
X 8052,
X 30965,
X 20120,
X 32380,
X 15639,
X 26204,
X 24385,
X 12475,
X 15725,
X 17265,
X 3214,
X 19471,
X 11376,
X 4697,
X 25543,
X 23297,
X 14619,
X 23087,
X 3123,
X 31549,
X 18065,
X 24256,
X 18973,
X 20901,
X 25613,
X 6157,
X 9899,
X 9267,
X 22413,
X 9598,
X 18526,
X 13711,
X 10046,
X 14566,
X 18536,
X 15988,
X 19878,
X 13626,
X 4273,
X 8387,
X 1171,
X 32017,
X 3752,
X 12388,
X 21191,
X 11483,
X 18122,
X 11744,
X 18528,
X 15585,
X 5363,
X 20159,
X 5641,
X 18176,
X 9575,
X 28578,
X 27363,
X 27685,
X 29344,
X 19489,
X 17713,
X 5511,
X 21461,
X 22626,
X 8645,
X 3496,
X 26703,
X 6270,
X 13870,
X 11529,
X 27499,
X 4500,
X 8607,
X 5808,
X 15725,
X 12457,
X 16542,
X 16474,
X 11531,
X 17222,
X 3952,
X 17024,
X 19894,
X 24015,
X 18247,
X 11276,
X 26278,
X 19365,
X 8746,
X 21976,
X 18092,
X 25851,
X 29088,
X 29163,
X 2231,
X 26233,
X 29732,
X 21106,
X 5411,
X 9874,
X 5448,
X 9344,
X 27589,
X 17574,
X 1191,
X 6789,
X 695,
X 11735,
X 20364,
X 17040,
X 17892,
X 5035,
X 26979,
X 1092,
X 850,
X 12390,
X 20195,
X 668,
X 20531,
X 29989,
X 12281,
X 23902,
X 12970,
X 32186,
X 19571,
X 3680,
X 7261,
X 26187,
X 28529,
X 24190,
X 446,
X 24233,
X 13708,
X 11863,
X 6681,
X 6001,
X 2499,
X 3786,
X 5214,
X 25829,
X 1322,
X 25907,
X 19628,
X 13192,
X 7505,
X 5990,
X 20129,
X 10875,
X 19829,
X 31591,
X 12388,
X 6042,
X 9833,
X 1775,
X 4719,
X 342,
X 28994,
X 31392,
X 20509,
X 31313,
X 20677,
X 1282,
X 11511,
X 4795,
X 3474,
X 6469,
X 2750,
X 879,
X 30989,
X 30134,
X 29752,
X 28364,
X 4880,
X 5629,
X 2235,
X 21332,
X 24145,
X 3356,
X 5243,
X 3079,
X 3988,
X 807,
X 24979,
X 31357,
X 914,
X 21187,
X 3540,
X 14022,
X 10149,
X 609,
X 29009,
X 24833,
X 16696,
X 5432,
X 24999,
X 28863,
X 16369,
X 28676,
X 24077,
X 7701,
X 1691,
X 19840,
X 28703,
X 16515,
X 22229,
X 32420,
X 19817,
X 16264,
X 19324,
X 29343,
X 1462,
X 28929,
X 3546,
X 17043,
X 18967,
X 325,
X 12683,
X 15634,
X 6322,
X 16642,
X 25395,
X 11612,
X 22864,
X 29910,
X 21985,
X 23126,
X 13988,
X 685,
X 6978,
X 31050,
X 16476,
X 6365,
X 21126,
X 4193,
X 8681,
X 11011,
X 23058,
X 1249,
X 31247,
X 24731,
X 28650,
X 20774,
X 7980,
X 20833,
X 27868,
X 7778,
X 23624,
X 11115,
X 1645,
X 15892,
X 29408,
X 7939,
X 17285,
X 16202,
X 28018,
X 11334,
X 4058,
X 7062,
X 3784,
X 11901,
X 6684,
X 14289,
X 27141,
X 16702,
X 26853,
X 13458,
X 28528,
X 23363,
X 21087,
X 19052,
X 31235,
X 15109,
X 17075,
X 11755,
X 10675,
X 288,
X 32053,
X 14157,
X 5758,
X 5222,
X 17488,
X 18945,
X 10294,
X 11200,
X 5171,
X 14305,
X 7951,
X 6601,
X 23608,
X 7214,
X 6377,
X 13865,
X 25369,
X 27215,
X 8030,
X 177,
X 16849,
X 11337,
X 2699,
X 23099,
X 8531,
X 11517,
X 17567,
X 28479,
X 9966,
X 2597,
X 14885,
X 12341,
X 15227,
X 27149,
X 785,
X 29615,
X 6476,
X 20753,
X 4236,
X 7730,
X 19668,
X 21210,
X 27519,
X 27608,
X 5142,
X 6999,
X 20449,
X 14246,
X 18638,
X 2941,
X 12481,
X 23726,
X 16738,
X 26047,
X 28947,
X 3300
X/*,
X 21639,
X 17996,
X 23866,
X 14785,
X 27571,
X 25356,
X 12633,
X 27289,
X 20551,
X 20312,
X 14426,
X 7357,
X 8056,
X 16252,
X 20410,
X 2384,
X 4353,
X 2029,
X 23579,
X 27882,
X 31882,
X 21577,
X 31368,
X 11502,
X 18902,
X 21012,
X 31365,
X 30379,
X 14256,
X 19244,
X 27870,
X 13365,
X 9619,
X 27665
X*/
X }; /*DelVals */
X
X#define NUM_DELS ( sizeof( DelVals ) / sizeof( int ) )
END_OF_FILE
if test 9970 -ne `wc -c <'testvals.old'`; then
echo shar: \"'testvals.old'\" unpacked with wrong size!
fi
# end of 'testvals.old'
fi
echo shar: End of archive 2 \(of 2\).
cp /dev/null ark2isdone
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! ~~~~~~~~~~~~~~~~~~~brad@SSD.CSD.HARRIS.COM (Brad Appleton) (03/29/91)
I tried to hack up avl.h for ANSI-C at the last minute in my previous
posting. I did not do it correctly. Here is the corrected version of
avl.h (sorry about that). This should replace the previous version of
avl.h.
#! /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 shell archive."
# Contents: avl.h
# Wrapped by brad@hcx2 on Thu Mar 28 16:20:18 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'avl.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'avl.h'\"
else
echo shar: Extracting \"'avl.h'\" \(2097 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#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 2097 -ne `wc -c <'avl.h'`; then
echo shar: \"'avl.h'\" unpacked with wrong size!
fi
# end of 'avl.h'
fi
echo shar: 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! ~~~~~~~~~~~~~~~~~~~