Path: utzoo!utgpu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!caen!uflorida!travis!brad From: brad@SSD.CSD.HARRIS.COM (Brad Appleton) Newsgroups: alt.sources Subject: AVL tree library (part 2 of 2) Message-ID: <2822@travis.csd.harris.com> Date: 28 Mar 91 20:40:27 GMT References: <2821@travis.csd.harris.com> Sender: news@travis.csd.harris.com Organization: Harris Computers Systems Division, Fort Lauderdale,FL Lines: 2079 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 '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 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 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 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! ~~~~~~~~~~~~~~~~~~~