AVL(n) UNIX 5.0 AVL(n) NAME avl - General Purpose AVL tree subroutines SYNOPSIS #include "avl.h" AVLNODE *avlfind( treeP, keyP ) AVLTREE *treeP; void *keyP; int avlinsert( treeP, keyP, dataP ) AVLTREE *treeP; void *keyP; void *dataP; int avldelete( treeP, keyP ) AVLTREE *treeP; void *keyP; SYNOPSIS avlfind searches an AVL tree for a node that matches a given key, according to the key comparison routine specified in the tree description structure. treeP is the address of the tree description block; keyP is the address of a key; this is given to the key comparison routine specified in the tree description structure. Its interpretation, if any, is left to the comparison routine. avlfind returns the address of the node found, or NULL if none found. avlinsert inserts a new node into an AVL tree. treeP is the address of the tree description structure; keyP is the address of a key; this address is given to the key comparison routine and the node construction routines specified in the tree description structure, and is not otherwise handled by avlinsert. avlinsert returns -1 if there was a failure of some sort; 0 if the node was inserted; 1 if the key was already in the tree (and the node construction routine rejected the duplication). avldelete deletes a node from an AVL tree. treeP is the address of the tree description structure; keyP is the address of the key that identifies the node to be deleted - it is given to the key comparison routine specified in the tree description structure in the process of locating the node to delete. avldelete returns 0 if the node was deleted, -1 if it was not found in the tree. Note well: all node addresses refer to the address of AVLNODE structures; typically an AVLNODE structure will be imbedded in an enveloping structure that contains key and/or data information. Nevertheless, the AVL routines require, pass, and return the AVLNODE node structure address, not the Page 1 (printed 6/3/88) AVL(n) UNIX 5.0 AVL(n) address of the containing structure (if any). In most cases, arranging to have the AVLNODE structure address be the same as the general structure address (i.e., be the first element within that structure) is the best thing to do, so that address translation is not necessary. In the case of multiple membership, this is obviously not possible. DESCRIPTION These routines are a general-purpose implementation of AVL trees in C. They are derived, with small changes, from the description of AVL (Adelson-Velskii and Landis) trees found in Knuth's "The Art of Computer Programming Volume 3: Searching and Sorting" (Addison-Wesley, 1973) pgs 451-471. These routines deal with tree maintenance only. They are only concerned with the arrangement of the nodes in the tree. Composition of those nodes is left to outside knowledge. The caller must construct an AVL tree header structure which specifies routines that deal with nodes (comparison, construction, and deletion). AVL nodes therefore do not need to contain any specific kind of key, or data, or even both key and data. For instance, the address of an AVL node may imply this information without the information being present. Also, multiple AVL nodes may be attached to a particular piece of data so that that data may be keyed and accessed in multiple ways. RELATED INFORMATION The AVL tree header (AVLTREE) has the following structure: typedef struct { /* Tree parameters */ AVLNODE *t_rootP; /* Ptr to root node */ /* Handler functions for the tree */ int (*t_cmprtc)(); /* Compare two keys */ AVLNODE *(*t_mknode)(); /* Node maker */ int (*t_rmnode)(); /* Node destroyer */ } AVLTREE; Before any use of AVL routines, the handler functions must be specified. We'll refer to them as simply cmprtc, mknode, and rmnode. int cmprtc( keyP, nodeP ) void *keyP; AVLNODE *nodeP; AVLNODE *mknode( treeP, keyP, dataP, enodeP ) AVLTREE *treeP; void *keyP; Page 2 (printed 6/3/88) AVL(n) UNIX 5.0 AVL(n) void *dataP; AVLNODE *enodeP; void rmnode( treeP, nodeP ) AVLTREE *treeP; AVLNODE *nodeP; cmprtc compares a given key against a key associated with a node. keyP is the address of a key (interpreted in whatever way is applicable); nodeP is the address of an AVLNODE structure to which the key should be compared. It shall return -1 if keyP is less than the key associated with nodeP key; 0 if they match; +1 if keyP is greater than the key associated with nodeP. mknode creates a node on behalf of tree insertion. treeP is the address of the tree description structure; keyP is the address of any key associated with the node; dataP is the address of any data associated with the node; enodeP is the address of any node that already exists in the tree for keyP. If enodeP is not NULL, then this routine is being called to replace the data in an existing node. It can signal its unwillingness to do this by returning NULL as its return value, otherwise it must return the address of the existing node. Otherwise (if enodeP is not NULL), this routine should allocate (or otherwise create) a new node and fill it in. mknode shall return the address of the node constructed, or NULL if no node was made. rmnode is called to delete a node and its information. treeP is the address of the tree description structure; nodeP is the address of the node to delete. It is called when a node is removed from a tree; it may do what it likes and does not return any information. FILES avl.h avl.c avl.n avltest.c RESTRICTIONS This software may be used at will, provided that all credits and style be left in place, and that its distribution is not restricted. Bug fixes and improvements are welcomed, please send these back to me at mem@zinn.MV.COM CREDITS TO Mark E. Mallett (mem@zinn.MV.COM) BUGS You tell me.. Page 3 (printed 6/3/88)