/* avl.c AVL routines Copyright 1988 Zinn Computer Company by Mark E. Mallett All rights reserved; 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 This is a general-purpose implementation of AVL trees in C. It is derived 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. The routines in this file deal with tree maintenance only. These routines 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). Please see the attached document for further information. Contained in this file: avlfind Find a node in an AVL tree avldelete Delete a node from an AVL tree avlinsert Insert a node into an AVL tree +-----------------------------------------------+ | rlp910619 -- I've modified this to include | | prototypes and register arguments. | +-----------------------------------------------+ */ #include #include "avltree.h" /*-------------------------------------------------------------- * rlp900624 -- Support for Lattice-style prototypes * If MSDOS, I assume Microsoft C compiler for DOS and OS/2 * If Lattice, I assume Lattice C compiler for Amiga *-------------------------------------------------------------- */ #ifndef __ARGS #if defined(MSDOS) || defined(LATTICE) #define __ARGS(a) a #else #define __ARGS(a) () #endif #endif /* Local definitions */ /* External routines */ /* External data */ /* Local routines */ /*-------------------------------------------------------- * rlp900624 -- Added Lattice-style prototypes. See AVL.H *-------------------------------------------------------- */ AVLNODE * __regargs avlfind (AVLTREE * treeP, void *keyP); int __regargs avlinsert (AVLTREE * treeP, void *keyP, void *dataP); int __regargs avldelete (AVLTREE * treeP, void *keyP); static int __regargs delete (AVLTREE * treeP, AVLNODE ** topPP, void *keyP); static int __regargs balance (AVLNODE ** branchPP); /* Local data */ /* *//* avlfind( treeP, keyP ) Lookup a value in an avl tree Accepts : treeP Address of the AVLTREE structure describing the tree. keyP Address of a key for the node. Interpretation of the key is left to the "compare key" routine. Returns : The address of the node if it is found, NULL if it is not. */ AVLNODE * __regargs avlfind( treeP, keyP ) AVLTREE *treeP; /* Address of the tree struct */ void *keyP; /* Address of the key info */ { AVLNODE *nodeP; /* To follow the tree with */ /* Traverse the tree until the node is found or the tree runs out. */ for( nodeP = treeP->t_rootP; nodeP != NULL; ) { switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) { case 0: /* Node found! */ return( nodeP ); /* Go ahead and return it */ case -1: /* Take left branch */ nodeP = nodeP->n_leftP; break; case 1: /* Take right branch */ nodeP = nodeP->n_rightP; break; } } /* Didn't find the node in the tree. */ return( NULL ); } /* *//* avlinsert( treeP, keyP, dataP ) Insert a node in an avl tree Accepts : treeP The address of the tree header structure. keyP The address of the key for the node. Interpretation of the key is by the compare and node-create routines specified in the avl tree header. dataP The address of the data info for the tree. The interpretation of this is left to the create-node routine specified in the avl tree header. Returns : -1 if failure of some kind 0 if successful insertion 1 if duplicate key Notes: The tree header structure specifies a node construction routine that is responsible for allocating a node and putting the new key and data information into it. It is called as follows: nodeP = construct( treeP, keyP, dataP, enodeP ) treeP, keyP, and dataP are as passed to this routine. "enodeP" is NULL if a new node is required; otherwise it is the address of an already existing node that matches the specified key - in this case it is up to the constructor to decide whether to overwrite the existing node or to call it an error. The routine is expected to return the address of the AVLNODE structure that is allocated (if enode==NULL ) or that exists, or to return NULL if the node is not made (or used). */ int __regargs avlinsert( treeP, keyP, dataP ) AVLTREE *treeP; /* Addr of the tree struct */ void *keyP; /* The key for insertion insert */ void *dataP; /* The data for the insertion */ { int direction; /* Direction we took from decision pt */ AVLNODE *nodeP; /* Node that we're looking at */ AVLNODE *clearP; /* For erasing tracks */ AVLNODE **nodePP; /* Pointer to the next link */ AVLNODE **topPP; /* Pointer to the top pointer */ /* Traverse the tree to find an insertion point (or existing key). Along the way, we'll adjust the balance counts on the nodes as we pass by them. And as we do this, we'll remember the potential tree rotation point (the lowest non-balanced treetop) as well as the direction we took from it (in case we have to fix it up when we discover a lower balance point). */ nodePP = topPP = &(treeP->t_rootP); /* Start at top of tree */ direction = 0; /* Haven't gone anywhwere yet */ while( (nodeP = *nodePP) != NULL ) { /* Till we reach the end */ /* See if we're at a potential balance point */ if ( nodeP->n_balance != 0 ) { /* New balance point. Erase any trail we've made to here */ if ( direction != 0 ) for( clearP = *topPP; clearP != nodeP; direction = clearP->n_balance ) { clearP->n_balance -= direction; if ( direction < 0 ) clearP = clearP->n_leftP; else clearP = clearP->n_rightP; } direction = 0; /* So we make new balance point */ topPP = nodePP; /* Remember new top */ } /* Now follow the tree... */ switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) { case 0: /* Match */ /* Here we have a duplicate node. First erase the trail that we left. */ if ( direction != 0 ) for( clearP = *topPP; clearP != NULL; direction = clearP->n_balance ) { clearP->n_balance -= direction; if ( direction < 0 ) clearP = clearP->n_leftP; else clearP = clearP->n_rightP; } /* Give the node to the node constructor and see what we get. */ if ( (*treeP->t_mknode)( treeP, keyP, dataP, nodeP ) == NULL ) return( 1 ); /* Duplicate key */ return( 0 ); /* Return success */ case -1: /* Go left */ nodePP = &(nodeP->n_leftP); --nodeP->n_balance; if ( direction == 0 ) /* Remember balance point branch? */ direction = -1; break; case 1: /* Go right */ nodePP = &(nodeP->n_rightP); ++nodeP->n_balance; if ( direction == 0 ) direction = 1; break; } } /* Here we've gotten to the bottom, so make a new node */ nodeP = (*treeP->t_mknode)( treeP, keyP, dataP, (AVLNODE *)NULL ); if ( nodeP != NULL ) { /* Successful node creation? */ nodeP->n_balance = 0; /* Fill in the nitty gritty */ nodeP->n_leftP = nodeP->n_rightP = NULL; *nodePP = nodeP; /* Link it in */ balance( topPP ); /* May need reshaping now */ return( 0 ); /* Return success */ } /* Error making node. Erase our trail */ if ( direction != 0 ) for( clearP = *topPP; clearP != NULL; direction = clearP->n_balance ) { clearP->n_balance -= direction; if ( direction < 0 ) clearP = clearP->n_leftP; else clearP = clearP->n_rightP; } return( -1 ); /* Return error */ } /* *//* avldelete( treeP, keyP ) Delete a node from an AVL tree Accepts: treeP Address of the tree definition structure. keyP Address of the key for the node. Interpretation of the key is left to the key-compare routine specified in the tree header. Returns : 0 if deleted OK -1 if not found */ int __regargs avldelete( treeP, keyP ) AVLTREE *treeP; /* Addr of tree block */ void *keyP; /* Addr of key */ { /* Simply call a local deletion routine */ if ( delete( treeP, &treeP->t_rootP, keyP ) < 0 ) return( -1 ); /* error in delete */ return( 0 ); /* Fine and dandy */ } /* *//* delete( treeP, topPP, keyP ) Local routine to delete from a subtree Accepts: treeP Address of the tree definition structure topPP Address of the pointer to this branch keyP Address of the key for the node. Interpretation of the key is left to the key-compare routine specified in the tree header. Returns : -1 if not found; 0 if deleted and tree did not shrink; 1 if deleted and tree shrunk by 1. */ static int __regargs delete( treeP, topPP, keyP ) AVLTREE *treeP; /* Addr of tree block */ AVLNODE **topPP; /* Addr of ptr to branch */ void *keyP; /* Addr of key */ { int i; /* Scratch */ int sts; int cmp; /* Comparison result */ AVLNODE *nodeP; /* Node pointer */ AVLNODE *node1P; /* Another one */ AVLNODE *tempP; /* For exchanging */ AVLNODE **linkPP; /* Addr of a node pointer */ nodeP = *topPP; /* Get addr of node */ if ( nodeP == NULL ) /* If we hit bottom */ return( -1 ); /* then we didn't find it */ cmp = (*treeP->t_cmprtc)( keyP, nodeP ); if ( cmp == 0 ) { /* We've found the node to delete. If it has no children we can just get rid of it. Otherwise we have to remove it from the tree somehow. If one or the other subtrees is empty, then it is easy. */ if ( nodeP->n_leftP == NULL ) { /* Just shorten the right branch (even if it doesn't exist) */ *topPP = nodeP->n_rightP; (*treeP->t_rmnode)( treeP, nodeP ); return( 1 ); /* Branch shrunk */ } if ( nodeP->n_rightP == NULL ) { /* Shorten the left branch */ *topPP = nodeP->n_leftP; (*treeP->t_rmnode)( treeP, nodeP ); return( 1 ); } /* Both subtrees exist. Exchange this node with the one logically adjacent (in value) to it. Then this node will be at the end of a branch and we can recurse to delete it. */ if( nodeP->n_balance < 0 ) { node1P = nodeP->n_leftP; linkPP = &(node1P->n_leftP); for( ; node1P->n_rightP != NULL; node1P = node1P->n_rightP ) linkPP = &(node1P->n_rightP); cmp = -1; /* We went left */ } else { node1P = nodeP->n_rightP; linkPP = &(node1P->n_rightP); for( ; node1P->n_leftP != NULL; node1P = node1P->n_leftP ) linkPP = &(node1P->n_leftP); cmp = 1; /* We're going right */ } /* Exchange the two nodes. We have to actually exchange by relinking rather than copying since the node may imply other stuff that we don't know about here. */ tempP = node1P->n_rightP; /* Exchange right pointers */ node1P->n_rightP = nodeP->n_rightP; nodeP->n_rightP = tempP; tempP = node1P->n_leftP; /* Exchange left pointers */ node1P->n_leftP = nodeP->n_leftP; nodeP->n_leftP = tempP; i = node1P->n_balance; /* Exchange balance values */ node1P->n_balance = nodeP->n_balance; nodeP->n_balance = i; *topPP = node1P; /* Exchange the nodes */ *linkPP = nodeP; nodeP = node1P; /* Pretend we're here */ } /* Remove the node from left or right subtree depending on "cmp" */ switch ( cmp ) { case -1: sts = delete( treeP, &nodeP->n_leftP, keyP ); if ( sts == 1 ) /* If it shrunk */ ++nodeP->n_balance; /* reflect that in the balance */ break; case 1: sts = delete( treeP, &nodeP->n_rightP, keyP ); if ( sts == 1 ) /* Right branch shrunk? */ --nodeP->n_balance; /* adjust the balance */ break; } if ( sts == 1 ) /* If we changed balance */ if ( nodeP->n_balance != 0 ) /* if it's 0 it shrunk but is ok */ sts = balance( topPP ); /* otherwise fix it up */ return( sts ); } /* *//* balance( branchPP ) Local routine to balance a branch Accepts : branchPP Addr of the variable pointing to the top n Returns : 0 if branch has stayed the same height; 1 if branch shrunk by one. Notes : This routine accepts a branch in conditions left by the internal routines only. No other cases are dealt with. */ static int __regargs balance( branchPP ) AVLNODE **branchPP; /* Ptr to top node */ { int shrunk; /* Whether we shrunk */ AVLNODE *nodeP; /* Current top node */ AVLNODE *leftP; /* Left child */ AVLNODE *rightP; /* Right child */ AVLNODE *migP; /* A ndoe that migrates */ /* Pick up relevant information */ nodeP = *branchPP; leftP = nodeP->n_leftP; rightP = nodeP->n_rightP; shrunk = 0; /* Assume tree doesn't shrink */ /* Process according to out-of-balance amount, if any */ switch( nodeP->n_balance ) { case -2: /* Too heavy on left */ if ( leftP->n_balance <= 0 ) { /* Single rotation */ *branchPP = leftP; nodeP->n_leftP = leftP->n_rightP; leftP->n_rightP = nodeP; ++leftP->n_balance; nodeP->n_balance = -(leftP->n_balance); if ( leftP->n_balance == 0 ) shrunk = 1; } else { /* Migration of inner node to top */ migP = leftP->n_rightP; leftP->n_rightP = migP->n_leftP; nodeP->n_leftP = migP->n_rightP; migP->n_leftP = leftP; migP->n_rightP = nodeP; *branchPP = migP; if ( migP->n_balance < 0 ) { leftP->n_balance = 0; nodeP->n_balance = 1; } else if ( migP->n_balance > 0 ) { leftP->n_balance = -1; nodeP->n_balance = 0; } else leftP->n_balance = nodeP->n_balance = 0; migP->n_balance = 0; shrunk = 1; } break; case 2: /* Too heavy on right */ if ( rightP->n_balance >= 0 ) { /* Single rotation */ *branchPP = rightP; nodeP->n_rightP = rightP->n_leftP; rightP->n_leftP = nodeP; --rightP->n_balance; nodeP->n_balance = -(rightP->n_balance); if ( rightP->n_balance == 0 ) shrunk = 1; } else { /* Migration of inner node */ migP = rightP->n_leftP; rightP->n_leftP = migP->n_rightP; nodeP->n_rightP = migP->n_leftP; migP->n_leftP = nodeP; migP->n_rightP = rightP; *branchPP = migP; if ( migP->n_balance < 0 ) { nodeP->n_balance = 0; rightP->n_balance = 1; } else if ( migP->n_balance > 0 ) { nodeP->n_balance = -1; rightP->n_balance = 0; } else nodeP->n_balance = rightP->n_balance = 0; migP->n_balance = 0; shrunk = 1; } } return( shrunk ); }