home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 446.lha / avlsort / avl.c < prev    next >
C/C++ Source or Header  |  1990-12-02  |  14KB  |  521 lines
  1. /*    avl.c        AVL routines
  2.  
  3.     Copyright 1988 Zinn Computer Company
  4.             by Mark E. Mallett
  5.  
  6.     All rights reserved;
  7.     This software may be used at will, provided that all credits
  8. and style be left in place, and that its distribution is not restricted.
  9. Bug fixes and improvements are welcomed, please send these back to
  10. me at mem@zinn.MV.COM
  11.  
  12.     This is a general-purpose implementation of AVL trees in C.
  13. It is derived from the description of AVL (Adelson-Velskii and Landis)
  14. trees found in Knuth's "The Art of Computer Programming Volume 3:
  15. Searching and Sorting" (Addison-Wesley, 1973) pgs 451-471.
  16.  
  17.     The routines in this file deal with tree maintenance only.
  18. These routines are only concerned with the arrangement of the nodes
  19. in the tree.  Composition of those nodes is left to outside knowledge.
  20. The caller must construct an AVL tree header structure which specifies
  21. routines that deal with nodes (comparison, construction, and deletion).
  22. Please see the attached document for further information.
  23.  
  24. Contained in this file:
  25.  
  26.     avlfind        Find a node in an AVL tree
  27.     avldelete    Delete a node from an AVL tree
  28.     avlinsert    Insert a node into an AVL tree
  29.  
  30. */
  31.  
  32. #include <stdio.h>
  33.  
  34. #include "avl.h"
  35.  
  36.     /*--------------------------------------------------------------
  37.      * rlp900624 -- Support for Lattice-style prototypes
  38.      *    If MSDOS, I assume Microsoft C compiler for DOS and OS/2
  39.      *    If Lattice, I assume Lattice C compiler for Amiga
  40.      *--------------------------------------------------------------
  41.      */
  42.  
  43. #ifndef __ARGS
  44.  #if    defined(MSDOS) || defined(LATTICE)
  45.   #define __ARGS(a) a
  46.  #else
  47.   #define __ARGS(a) ()
  48.  #endif
  49. #endif
  50.  
  51.  
  52. /* Local definitions */
  53.  
  54.  
  55. /* External routines */
  56.  
  57.  
  58. /* External data */
  59.  
  60.  
  61. /* Local routines */
  62.  
  63.     /*--------------------------------------------------------
  64.      * rlp900624 -- Added Lattice-style prototypes.  See AVL.H
  65.      *--------------------------------------------------------
  66.      */
  67.  
  68. static    int    delete  __ARGS(( AVLTREE *treeP, AVLNODE **topPP, void *keyP ));
  69. static    int    balance __ARGS(( AVLNODE **branchPP ));
  70.  
  71. /* Local data */
  72.  
  73. /*
  74.  
  75. *//* avlfind( treeP, keyP )
  76.  
  77.     Lookup a value in an avl tree
  78.  
  79. Accepts :
  80.  
  81.     treeP        Address of the AVLTREE structure describing the tree.
  82.     keyP        Address of a key for the node.  Interpretation of
  83.               the key is left to the "compare key" routine.
  84.  
  85. Returns :
  86.  
  87.     <value>        The address of the node if it is found,
  88.             NULL if it is not.
  89.  
  90.  
  91. */
  92.  
  93. AVLNODE *
  94. avlfind( treeP, keyP )
  95.     AVLTREE        *treeP;        /* Address of the tree struct */
  96.     void        *keyP;        /* Address of the key info */
  97.  
  98. {
  99.     AVLNODE        *nodeP;        /* To follow the tree with */
  100.  
  101.     /* Traverse the tree until the node is found or the tree runs out. */
  102.     for( nodeP = treeP->t_rootP; nodeP != NULL; ) {
  103.     switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) {
  104.         case 0:            /* Node found! */
  105.         return( nodeP );    /* Go ahead and return it */
  106.         
  107.         case -1:            /* Take left branch */
  108.         nodeP = nodeP->n_leftP;
  109.         break;
  110.  
  111.         case 1:            /* Take right branch */
  112.             nodeP = nodeP->n_rightP;
  113.         break;
  114.     }
  115.     }
  116.  
  117.     /* Didn't find the node in the tree. */
  118.     return( NULL );
  119. }
  120. /*
  121.  
  122. *//* avlinsert( treeP, keyP, dataP )
  123.  
  124.     Insert a node in an avl tree
  125.  
  126. Accepts :
  127.  
  128.     treeP        The address of the tree header structure.
  129.     keyP        The address of the key for the node.  Interpretation
  130.               of the key is by the compare and node-create
  131.               routines specified in the avl tree header.
  132.     dataP        The address of the data info for the tree.  The
  133.              interpretation of this is left to the create-node
  134.              routine specified in the avl tree header.
  135.  
  136. Returns :
  137.  
  138.     <value>        -1 if failure of some kind
  139.              0 if successful insertion
  140.              1 if duplicate key
  141.  
  142. Notes:
  143.  
  144.     The tree header structure specifies a node construction routine
  145.     that is responsible for allocating a node and putting the new
  146.     key and data information into it.  It is called as follows:
  147.  
  148.        nodeP = construct( treeP, keyP, dataP, enodeP )
  149.  
  150.     treeP, keyP, and dataP are as passed to this routine.  "enodeP"
  151.     is NULL if a new node is required; otherwise it is the address
  152.     of an already existing node that matches the specified key -
  153.     in this case it is up to the constructor to decide whether to
  154.     overwrite the existing node or to call it an error.  The routine
  155.     is expected to return the address of the AVLNODE structure
  156.     that is allocated (if enode==NULL ) or that exists, or to
  157.     return NULL if the node is not made (or used).
  158.  
  159. */
  160.  
  161. int
  162. avlinsert( treeP, keyP, dataP )
  163.     AVLTREE        *treeP;        /* Addr of the tree struct */
  164.     void        *keyP;        /* The key for insertion insert */
  165.     void        *dataP;        /* The data for the insertion */
  166. {
  167.     int        direction;    /* Direction we took from decision pt */
  168.     AVLNODE        *nodeP;        /* Node that we're looking at */
  169.     AVLNODE        *clearP;    /* For erasing tracks */
  170.     AVLNODE        **nodePP;    /* Pointer to the next link */
  171.     AVLNODE        **topPP;    /* Pointer to the top pointer */
  172.  
  173.     /* Traverse the tree to find an insertion point (or existing key).
  174.        Along the way, we'll adjust the balance counts on the nodes as
  175.        we pass by them.  And as we do this, we'll remember the potential
  176.        tree rotation point (the lowest non-balanced treetop) as well as
  177.        the direction we took from it (in case we have to fix it up when
  178.        we discover a lower balance point). */
  179.  
  180.     nodePP = topPP = &(treeP->t_rootP);    /* Start at top of tree */
  181.     direction = 0;            /* Haven't gone anywhwere yet */
  182.     while( (nodeP = *nodePP) != NULL ) { /* Till we reach the end */
  183.  
  184.     /* See if we're at a potential balance point */
  185.     if ( nodeP->n_balance != 0 ) {
  186.  
  187.         /* New balance point.  Erase any trail we've made to here */
  188.         if ( direction != 0 )
  189.         for( clearP = *topPP; clearP != nodeP;
  190.                  direction = clearP->n_balance ) {
  191.             clearP->n_balance -= direction;
  192.             if ( direction < 0 )
  193.             clearP = clearP->n_leftP;
  194.             else
  195.             clearP = clearP->n_rightP;
  196.         }
  197.          direction = 0;        /* So we make new balance point */
  198.          topPP = nodePP;        /* Remember new top */
  199.     }
  200.  
  201.     /* Now follow the tree... */
  202.     switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) {
  203.         case 0:            /* Match */
  204.         /* Here we have a duplicate node.  First erase the
  205.            trail that we left. */
  206.         if ( direction != 0 )
  207.             for( clearP = *topPP; clearP != NULL;
  208.                 direction = clearP->n_balance ) {
  209.             clearP->n_balance -= direction;
  210.             if ( direction < 0 )
  211.                 clearP = clearP->n_leftP;
  212.             else
  213.                 clearP = clearP->n_rightP;
  214.             }
  215.  
  216.         /* Give the node to the node constructor and
  217.            see what we get. */
  218.         if ( (*treeP->t_mknode)( treeP, keyP, dataP, nodeP ) == NULL )
  219.             return( 1 );    /* Duplicate key */
  220.         return( 0 );        /* Return success */
  221.  
  222.         case -1:            /* Go left */
  223.         nodePP = &(nodeP->n_leftP);
  224.         --nodeP->n_balance;
  225.         if ( direction == 0 )    /* Remember balance point branch? */
  226.             direction = -1;
  227.         break;
  228.  
  229.         case 1:            /* Go right */
  230.         nodePP = &(nodeP->n_rightP);
  231.         ++nodeP->n_balance;
  232.         if ( direction == 0 )
  233.             direction = 1;
  234.         break;
  235.     }
  236.     }
  237.  
  238.     /* Here we've gotten to the bottom, so make a new node */
  239.     nodeP = (*treeP->t_mknode)( treeP, keyP, dataP, (AVLNODE *)NULL );
  240.     if ( nodeP != NULL ) {        /* Successful node creation? */
  241.     nodeP->n_balance = 0;        /* Fill in the nitty gritty */
  242.     nodeP->n_leftP = nodeP->n_rightP = NULL;
  243.     *nodePP = nodeP;        /* Link it in */
  244.     balance( topPP );        /* May need reshaping now */
  245.     return( 0 );            /* Return success */
  246.     }
  247.  
  248.     /* Error making node.  Erase our trail */
  249.     if ( direction != 0 )
  250.     for( clearP = *topPP; clearP != NULL;
  251.             direction = clearP->n_balance ) {
  252.         clearP->n_balance -= direction;
  253.         if ( direction < 0 )
  254.         clearP = clearP->n_leftP;
  255.         else
  256.         clearP = clearP->n_rightP;
  257.     }
  258.     return( -1 );            /* Return error */
  259. }
  260. /*
  261.  
  262. *//* avldelete( treeP, keyP )
  263.  
  264.     Delete a node from an AVL tree
  265.  
  266. Accepts:
  267.  
  268.     treeP        Address of the tree definition structure.
  269.     keyP        Address of the key for the node.  Interpretation
  270.              of the key is left to the key-compare routine
  271.              specified in the tree header.
  272.  
  273. Returns :
  274.  
  275.      <value>        0 if deleted OK
  276.             -1 if not found
  277.  
  278. */
  279.  
  280. int
  281. avldelete( treeP, keyP )
  282.     AVLTREE        *treeP;        /* Addr of tree block */
  283.     void        *keyP;        /* Addr of key */
  284. {
  285.     /* Simply call a local deletion routine */
  286.     if ( delete( treeP, &treeP->t_rootP, keyP ) < 0 )
  287.     return( -1 );            /* error in delete */
  288.     return( 0 );            /* Fine and dandy */
  289. }
  290. /*
  291.  
  292. *//* delete( treeP, topPP, keyP )
  293.  
  294.     Local routine to delete from a subtree
  295.  
  296. Accepts:
  297.  
  298.     treeP        Address of the tree definition structure
  299.     topPP        Address of the pointer to this branch
  300.     keyP        Address of the key for the node.  Interpretation
  301.              of the key is left to the key-compare routine
  302.              specified in the tree header.
  303.  
  304. Returns :
  305.  
  306.      <value>        -1 if not found;
  307.              0 if deleted and tree did not shrink;
  308.              1 if deleted and tree shrunk by 1.
  309.  
  310. */
  311.  
  312. static int
  313. delete( treeP, topPP, keyP )
  314.     AVLTREE        *treeP;        /* Addr of tree block */
  315.     AVLNODE        **topPP;    /* Addr of ptr to branch */
  316.     void        *keyP;        /* Addr of key */
  317. {
  318.     int        i;        /* Scratch */
  319.     int        sts;
  320.     int        cmp;        /* Comparison result */
  321.     AVLNODE        *nodeP;        /* Node pointer */
  322.     AVLNODE        *node1P;    /* Another one */
  323.     AVLNODE        *tempP;        /* For exchanging */
  324.     AVLNODE        **linkPP;    /* Addr of a node pointer */
  325.  
  326.     nodeP = *topPP;            /* Get addr of node */
  327.     if ( nodeP == NULL )        /* If we hit bottom */
  328.     return( -1 );            /*  then we didn't find it */
  329.  
  330.     cmp = (*treeP->t_cmprtc)( keyP, nodeP );
  331.     if ( cmp == 0 ) {
  332.     /* We've found the node to delete.  If it has no children we
  333.        can just get rid of it.  Otherwise we have to remove it
  334.        from the tree somehow.  If one or the other subtrees
  335.         is empty, then it is easy. */
  336.  
  337.     if ( nodeP->n_leftP == NULL ) {
  338.         /* Just shorten the right branch (even if it doesn't exist) */
  339.         *topPP = nodeP->n_rightP;
  340.         (*treeP->t_rmnode)( treeP, nodeP );
  341.         return( 1 );        /* Branch shrunk */
  342.     }
  343.  
  344.     if ( nodeP->n_rightP == NULL ) {
  345.         /* Shorten the left branch */
  346.         *topPP = nodeP->n_leftP;
  347.         (*treeP->t_rmnode)( treeP, nodeP );
  348.         return( 1 );
  349.     }
  350.  
  351.     /* Both subtrees exist.  Exchange this node with the one
  352.        logically adjacent (in value) to it.  Then this node
  353.        will be at the end of a branch and we can recurse to
  354.        delete it. */
  355.  
  356.     if( nodeP->n_balance < 0 ) {
  357.         node1P = nodeP->n_leftP;
  358.         linkPP = &(node1P->n_leftP);
  359.         for( ; node1P->n_rightP != NULL; node1P = node1P->n_rightP )
  360.         linkPP = &(node1P->n_rightP);
  361.         cmp = -1;            /* We went left */
  362.     } else {
  363.         node1P = nodeP->n_rightP;
  364.         linkPP = &(node1P->n_rightP);
  365.         for( ; node1P->n_leftP != NULL; node1P = node1P->n_leftP )
  366.         linkPP = &(node1P->n_leftP);
  367.         cmp = 1;            /* We're going right */
  368.     }
  369.  
  370.     /* Exchange the two nodes.  We have to actually exchange by
  371.        relinking rather than copying since the node may imply
  372.        other stuff that we don't know about here. */
  373.  
  374.     tempP = node1P->n_rightP;    /* Exchange right pointers */
  375.     node1P->n_rightP = nodeP->n_rightP;
  376.     nodeP->n_rightP = tempP;
  377.  
  378.     tempP = node1P->n_leftP;    /* Exchange left pointers */
  379.     node1P->n_leftP = nodeP->n_leftP;
  380.     nodeP->n_leftP = tempP;
  381.  
  382.     i = node1P->n_balance;        /* Exchange balance values */
  383.     node1P->n_balance = nodeP->n_balance;
  384.     nodeP->n_balance = i;
  385.  
  386.     *topPP = node1P;        /* Exchange the nodes */
  387.     *linkPP = nodeP;
  388.     nodeP = node1P;            /* Pretend we're here */
  389.     }
  390.  
  391.     /* Remove the node from left or right subtree depending on "cmp" */
  392.     switch ( cmp ) {
  393.     case -1:
  394.         sts = delete( treeP, &nodeP->n_leftP, keyP );
  395.         if ( sts == 1 )        /* If it shrunk */
  396.         ++nodeP->n_balance;    /*  reflect that in the balance */
  397.         break;
  398.  
  399.     case 1:
  400.         sts = delete( treeP, &nodeP->n_rightP, keyP );
  401.         if ( sts == 1 )        /* Right branch shrunk? */
  402.         --nodeP->n_balance;    /*  adjust the balance */
  403.         break;
  404.     }
  405.  
  406.     if ( sts == 1 )            /* If we changed balance */
  407.     if ( nodeP->n_balance != 0 )    /*  if it's 0 it shrunk but is ok */
  408.         sts = balance( topPP );    /*    otherwise fix it up */
  409.     return( sts );
  410. }
  411. /*
  412.  
  413. *//* balance( branchPP )
  414.  
  415.     Local routine to balance a branch
  416.  
  417. Accepts :
  418.  
  419.     branchPP    Addr of the variable pointing to the top n
  420.  
  421. Returns :
  422.  
  423.     <value>        0 if branch has stayed the same height;
  424.             1 if branch shrunk by one.
  425.  
  426.  
  427. Notes :
  428.  
  429.     This routine accepts a branch in conditions left by the
  430. internal routines only.  No other cases are dealt with.
  431.  
  432. */
  433.  
  434. static int
  435. balance( branchPP )
  436.     AVLNODE        **branchPP;    /* Ptr to top node */
  437. {
  438.     int        shrunk;        /* Whether we shrunk */
  439.     AVLNODE        *nodeP;        /* Current top node */
  440.     AVLNODE        *leftP;        /* Left child */
  441.     AVLNODE        *rightP;    /* Right child */
  442.     AVLNODE        *migP;        /* A ndoe that migrates */
  443.  
  444.     /* Pick up relevant information */
  445.     nodeP = *branchPP;
  446.     leftP = nodeP->n_leftP;
  447.     rightP = nodeP->n_rightP;
  448.     shrunk = 0;                /* Assume tree doesn't shrink */
  449.  
  450.     /* Process according to out-of-balance amount, if any */
  451.     switch( nodeP->n_balance ) {
  452.     case -2:            /* Too heavy on left */
  453.         if ( leftP->n_balance <= 0 ) {
  454.  
  455.         /* Single rotation */
  456.         *branchPP = leftP;
  457.         nodeP->n_leftP = leftP->n_rightP;
  458.         leftP->n_rightP = nodeP;
  459.         ++leftP->n_balance;
  460.         nodeP->n_balance = -(leftP->n_balance);
  461.         if ( leftP->n_balance == 0 )
  462.             shrunk = 1;
  463.         }
  464.         else {            /* Migration of inner node to top */
  465.         migP = leftP->n_rightP;
  466.         leftP->n_rightP = migP->n_leftP;
  467.         nodeP->n_leftP = migP->n_rightP;
  468.         migP->n_leftP = leftP;
  469.         migP->n_rightP = nodeP;
  470.         *branchPP = migP;
  471.         if ( migP->n_balance < 0 ) {
  472.             leftP->n_balance = 0;
  473.             nodeP->n_balance = 1;
  474.         }
  475.         else if ( migP->n_balance > 0 ) {
  476.             leftP->n_balance = -1;
  477.             nodeP->n_balance = 0;
  478.         }
  479.         else
  480.             leftP->n_balance = nodeP->n_balance = 0;
  481.         migP->n_balance = 0;
  482.         shrunk = 1;
  483.         }
  484.         break;
  485.             
  486.     case  2:            /* Too heavy on right */
  487.         if ( rightP->n_balance >= 0 ) {
  488.  
  489.         /* Single rotation */
  490.         *branchPP = rightP;
  491.         nodeP->n_rightP = rightP->n_leftP;
  492.         rightP->n_leftP = nodeP;
  493.         --rightP->n_balance;
  494.         nodeP->n_balance = -(rightP->n_balance);
  495.         if ( rightP->n_balance == 0 )
  496.             shrunk = 1;
  497.         }
  498.         else {            /* Migration of inner node */
  499.         migP = rightP->n_leftP;
  500.         rightP->n_leftP = migP->n_rightP;
  501.         nodeP->n_rightP = migP->n_leftP;
  502.         migP->n_leftP = nodeP;
  503.         migP->n_rightP = rightP;
  504.         *branchPP = migP;
  505.         if ( migP->n_balance < 0 ) {
  506.             nodeP->n_balance = 0;
  507.             rightP->n_balance = 1;
  508.         }
  509.         else if ( migP->n_balance > 0 ) {
  510.             nodeP->n_balance = -1;
  511.             rightP->n_balance = 0;
  512.         }
  513.         else
  514.             nodeP->n_balance = rightP->n_balance = 0;
  515.         migP->n_balance = 0;
  516.         shrunk = 1;
  517.         }
  518.     }
  519.     return( shrunk );
  520. }
  521.