home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / database / avl / avl.c next >
Encoding:
C/C++ Source or Header  |  1991-12-31  |  29.2 KB  |  1,051 lines
  1. /****************************************************************************
  2. *
  3. *                    Copyright (C) 1991 Kendall Bennett.
  4. *                            All rights reserved.
  5. *
  6. * Filename:        $RCSfile: avl.c $
  7. * Version:        $Revision: 1.3 $
  8. *
  9. * Language:        ANSI C
  10. * Environment:    any
  11. *
  12. * Description:    Module to implement balanced AVL trees.
  13. *
  14. * $Id: avl.c 1.3 91/12/31 19:40:43 kjb Exp $
  15. *
  16. * Revision History:
  17. * -----------------
  18. *
  19. * $Log:    avl.c $
  20. * Revision 1.3  91/12/31  19:40:43  kjb
  21. * Modified include file directories
  22. * 
  23. * Revision 1.2  91/09/27  03:10:00  kjb
  24. * Added stuff keep track of the number of nodes in the tree.
  25. * 
  26. * Revision 1.1  91/09/27  02:50:49  kjb
  27. * Initial revision
  28. * 
  29. ****************************************************************************/
  30.  
  31. #include <stdio.h>
  32. #include <malloc.h>
  33. #include <signal.h>
  34. #include "debug.h"
  35. #include "avl.h"
  36.  
  37. /*--------------------------- Globals Variables ---------------------------*/
  38.  
  39. PRIVATE AVL_TREE    *Tree;        /* Pointer to tree we are working with    */
  40. PRIVATE    AVL_BUCKET    *Node;        /* Pointer to node we are working with    */
  41. PRIVATE void        *Conflicting;    /* Conflicting node                 */
  42. PRIVATE bool        Notfound;    /* Flags if a node cannot be found        */
  43. PRIVATE void         (*Visit)(void*,void*);
  44. PRIVATE void        (*Prnt)(FILE*,void*);
  45. PRIVATE    void        *Params,*Lower,*Upper;
  46. PRIVATE    FILE*        Out;
  47. PRIVATE char        Map[MAXLEVEL / 8];
  48. PRIVATE    char        *Graph_chars[] = { "│","┌──","└──","──┤","──┘","──┐"};
  49. PRIVATE    char        *Norm_chars[] = { "|","+--","+--","--+","--+","--+"};
  50. PRIVATE    char        **Cset;
  51.  
  52. /*----------------------------- Implementation ----------------------------*/
  53.  
  54. PUBLIC void *avl_newnode(int size)
  55. /****************************************************************************
  56. *
  57. * Function:        avl_newnode
  58. * Parameters:    size    - Amount of memory to allocate for node
  59. * Returns:        Pointer to the allocated nodes user space.
  60. *
  61. * Description:    Allocates the memory required for a node, adding a small
  62. *                header at the start of the node. We return a reference to
  63. *                the user space of the node, as if it had be allocated via
  64. *                malloc.
  65. *
  66. ****************************************************************************/
  67. {
  68.     AVL_BUCKET    *n;
  69.  
  70.     if ( !(n = (AVL_BUCKET*)malloc(size+sizeof(AVL_BUCKET))) ) {
  71.         fprintf(stderr,"Can't get memory for BUCKET\n");
  72.         raise(SIGABRT);
  73.         return NULL;
  74.         }
  75.  
  76.     return AVL_USERSPACE(n);        /* Return pointer to user space        */
  77. }
  78.  
  79. /*-------------------------------------------------------------------------*/
  80.  
  81. PUBLIC void avl_freenode(void *node)
  82. /****************************************************************************
  83. *
  84. * Function:        avl_freesym
  85. * Parameters:    node    - Node to free
  86. *
  87. * Description:    Frees a node previously allocated with avl_newsym().
  88. *
  89. ****************************************************************************/
  90. {
  91.     free(AVL_HEADER(node));
  92. }
  93.  
  94. /*-------------------------------------------------------------------------*/
  95.  
  96. PUBLIC AVL_TREE *avl_init(int (*cmp_function)(void*,void*))
  97. /****************************************************************************
  98. *
  99. * Function:        avl_init
  100. * Parameters:    cmp_function    - Function to compare the value of two nodes
  101. *                prnt_function    - Function to print the value of a node
  102. * Returns:        Pointer to the newly created AVL tree.
  103. *
  104. * Description:    Makes a new AVL tree with no elements and returns a pointer
  105. *                to it.
  106. *
  107. ****************************************************************************/
  108. {
  109.     AVL_TREE    *tree;
  110.  
  111.     if( (tree = (AVL_TREE*)malloc(sizeof(AVL_TREE))) != NULL) {
  112.         tree->count = 0;
  113.         tree->cmp = cmp_function;
  114.         tree->root = NULL;
  115.         }
  116.     else {
  117.         fprintf(stderr,"Insufficient memory for AVL tree\n");
  118.         raise(SIGABRT);
  119.         return NULL;
  120.         }
  121.     return tree;
  122. }
  123.  
  124. /*-------------------------------------------------------------------------*/
  125.  
  126. PRIVATE void (*_freeNode)(void*);
  127.  
  128. PRIVATE void free_subtree(AVL_BUCKET *t)
  129. /****************************************************************************
  130. *
  131. * Function:        free_subtree
  132. * Parameters:    t    - Subtree to free
  133. *
  134. * Description:    Recursive routine to free the elements of a particular
  135. *                subtree.
  136. *
  137. ****************************************************************************/
  138. {
  139.     if (t) {
  140.         free_subtree(t->left);
  141.         free_subtree(t->right);
  142.         _freeNode(AVL_USERSPACE(t));
  143.         }
  144. }
  145.  
  146. PUBLIC void avl_empty(AVL_TREE *t,void (*freeNode)(void*))
  147. /****************************************************************************
  148. *
  149. * Function:        avl_empty
  150. * Parameters:    t            - Tree to kill
  151. *                freeNode    - Routine to free each node of the tree
  152. *
  153. * Description:    Deletes the entire AVL tree from memory including all the
  154. *                nodes of the tree. We call the user supplied routine
  155. *                freeNode() to free each node in the tree. This allows the
  156. *                user program to perform any extra processing that is
  157. *                required to kill each node (for example if they contain
  158. *                pointers to other items on the heap). If no extra
  159. *                processing is required, just pass the address of
  160. *                avl_freenode(), ie:
  161. *
  162. *                    avl_kill(myTree,avl_freenode);
  163. *
  164. ****************************************************************************/
  165. {
  166.     _freeNode = freeNode;
  167.     free_subtree(t->root);
  168.     t->root = NULL;
  169. }
  170.  
  171. /*-------------------------------------------------------------------------*/
  172.  
  173. PRIVATE void insert(AVL_BUCKET **pp)
  174. /****************************************************************************
  175. *
  176. * Function:        insert
  177. * Parameters:    pp    - Pointer to pointer to root of subtree to insert into
  178. *
  179. * Description:    Internal recursive routine to insert a node into an
  180. *                AVL tree. Expects the global variables Tree, and Node
  181. *                to be set up. If we encounter a duplicate key, we return
  182. *                the address of this key in the global Conflicting;
  183. *
  184. ****************************************************************************/
  185. {
  186.     AVL_BUCKET    *p = *pp;
  187.     AVL_BUCKET    *p1,*p2;
  188.     int            relation;    /* Relationship between root and Node        */
  189.     static bool    h = 0;            /* Set to indicate that subtree has grown    */
  190.  
  191.     if (p == NULL) {
  192.  
  193.         /* We have found a valid spot for the node, so insert it and
  194.          * let the higher level recursions know that the tree has
  195.          * subsequently grown.
  196.          */
  197.  
  198.         p = Node;
  199.         p->left = p->right = NULL;
  200.         p->bal = BAL;
  201.         h = true;
  202.         }
  203.     else if ((relation = Tree->cmp(AVL_USERSPACE(p),
  204.             AVL_USERSPACE(Node))) == 0) {
  205.  
  206.         /* We have a node with a duplicate key that we cannot insert
  207.          * into the tree. We return the address of the user space for
  208.          * the node in the global Conflicting
  209.          */
  210.  
  211.         Conflicting = AVL_USERSPACE(p);
  212.         h = false;
  213.         }
  214.     else if (relation > 0) {
  215.  
  216.         /* If relation is > 0, then the current node p is greater than
  217.          * Node, so we insert the node into the left subtree.
  218.          */
  219.  
  220.         insert(&p->left);
  221.  
  222.         if (h) {                /* The left subtree has grown in height    */
  223.             switch (p->bal) {
  224.                 case LH:
  225.  
  226.                     /* The left subtree has grown taller than it is allowed,
  227.                      * so we must perform a rebalance of the tree.
  228.                      */
  229.  
  230.                     p1 = p->left;
  231.                     if (p1->bal == LH) {
  232.  
  233.                         /* Left subtree is LEFTHIGH, so we need to do a
  234.                          * single right rotation to rebalance the subtree p.
  235.                          */
  236.  
  237.                         p->left = p1->right;
  238.                         p1->right = p;
  239.                         p->bal = BAL;
  240.                         p = p1;
  241.                         }
  242.                     else {
  243.  
  244.                         /* Left subtree is RIGHTHIGH, so we need to do a
  245.                          * double right rotation to rebalance the subtree p.
  246.                          */
  247.  
  248.                         p2 = p1->right;
  249.                         p1->right = p2->left;
  250.                         p2->left = p1;
  251.                         p->left = p2->right;
  252.                         p2->right = p;
  253.                         p->bal = (p2->bal == LH) ? RH : BAL;
  254.                         p1->bal = (p2->bal == RH) ? LH : BAL;
  255.                         p = p2;
  256.                         }
  257.                     p->bal = BAL;            /* Tree is now balanced        */
  258.                     h = 0;
  259.                     break;
  260.                 case BAL:
  261.  
  262.                     /* The subtree was previously balanced, so now it
  263.                      * simply becomes LEFTHIGH.
  264.                      */
  265.  
  266.                     p->bal = LH;
  267.                     break;
  268.                 case RH:
  269.  
  270.                     /* The subtree was previously RIGHTHIGH, so now it
  271.                      * has become balanced. In this case the height of this
  272.                      * particular subtree has not grown, so h is reset to
  273.                      * false.
  274.                      */
  275.  
  276.                     p->bal = BAL;
  277.                     h = false;
  278.                 }
  279.             }
  280.         }
  281.     else {
  282.  
  283.         /* Relation was < 0, indicating that the current node p is smaller
  284.          * than Node, so we insert the new node into the right subtree.
  285.          */
  286.  
  287.         insert(&p->right);
  288.  
  289.         if (h) {            /* The right subtree has grown in height    */
  290.             switch (p->bal) {
  291.                 case LH:
  292.  
  293.                     /* The subtree was previously LEFTHIGH, so now it
  294.                      * has become balanced. In this case the height of this
  295.                      * particular subtree has not grown, so h is reset to
  296.                      * false.
  297.                      */
  298.  
  299.                     p->bal = BAL;
  300.                     h = false;
  301.                     break;
  302.                 case BAL:
  303.  
  304.                     /* The subtree was previously balanced, so now it
  305.                      * simply becomes RIGHTHIGH.
  306.                      */
  307.  
  308.                     p->bal = RH;
  309.                     break;
  310.                 case RH:
  311.  
  312.                     /* The right subtree has grown taller than it is allowed,
  313.                      * so we must perform a rebalance of the tree.
  314.                      */
  315.  
  316.                     p1 = p->right;
  317.                     if (p1->bal == RH) {
  318.  
  319.                         /* Right subtree is RIGHTHIGH, so we need to do a
  320.                          * single left rotation to rebalance the subtree p.
  321.                          */
  322.  
  323.                         p->right = p1->left;
  324.                         p1->left = p;
  325.                         p->bal = BAL;
  326.                         p = p1;
  327.                         }
  328.                     else {
  329.  
  330.                         /* Right subtree is LEFTHIGH, so we need to do a
  331.                          * double left rotation to rebalance the subtree p.
  332.                          */
  333.  
  334.                         p2 = p1->left;
  335.                         p1->left = p2->right;
  336.                         p2->right = p1;
  337.                         p->right = p2->left;
  338.                         p2->left = p;
  339.                         p->bal = (p2->bal == RH) ? LH : BAL;
  340.                         p1->bal = (p2->bal == LH) ? RH : BAL;
  341.                         p = p2;
  342.                         }
  343.                     p->bal = BAL;            /* Tree is now balanced        */
  344.                     h = 0;
  345.                 }
  346.             }
  347.         }
  348.  
  349.     /* Reset the root of this subtree to the new root p, since it may have
  350.      * changed during a rotate of the tree.
  351.      */
  352.  
  353.     *pp = p;
  354. }
  355.  
  356. PUBLIC void *avl_insert(AVL_TREE *tree,void *node)
  357. /****************************************************************************
  358. *
  359. * Function:        avl_insert
  360. * Parameters:    tree    - Tree to insert the node into
  361. *                node    - New node to insert into the tree
  362. * Returns:        NULL on success, or a pointer to the conflicting node.
  363. *
  364. * Description:    Inserts a new node into an AVL tree. Duplicate keys are
  365. *                currently not supported.
  366. *
  367. ****************************************************************************/
  368. {
  369.     Tree = tree;
  370.     Node = AVL_HEADER(node);
  371.     Conflicting = NULL;
  372.  
  373.     insert(&tree->root);
  374.     if (!Conflicting)    tree->count++;
  375.  
  376.     return Conflicting;
  377. }
  378.  
  379. /*-------------------------------------------------------------------------*/
  380.  
  381. PRIVATE bool balance_left(AVL_BUCKET **pp)
  382. /****************************************************************************
  383. *
  384. * Function:        balance_left
  385. * Parameters:    pp    - Point to root of subtree to balance
  386. * Returns:        True if the entire subtree shrank, false if not
  387. *
  388. * Description:    Routine to rebalance the subtree pointed to by pp when its
  389. *                left subtree has just shrunk. We adjust the balance factors
  390. *                and rebalance the subtree adjusting pp to point to the
  391. *                new root of the subtree.
  392. *
  393. ****************************************************************************/
  394. {
  395.     AVL_BUCKET    *p,*p1,*p2;
  396.     short        b1,b2;
  397.     bool        subtree_shrank = true;
  398.  
  399.     p = *pp;
  400.     switch (p->bal) {
  401.         case LH:
  402.  
  403.             /* The subtree was previously left high. Since the left subtree
  404.              * just shrank, this tree is now balanced while the overall
  405.              * height has been reduced.
  406.              */
  407.  
  408.             p->bal = BAL;
  409.             break;
  410.         case BAL:
  411.  
  412.             /* The subtree was previously balanced, so we simply make
  413.              * it right high, and signal that it did not shrink.
  414.              */
  415.  
  416.             p->bal = RH;
  417.             subtree_shrank = false;
  418.             break;
  419.         case RH:
  420.  
  421.             /* The subtree was previously right high. In this case we must do
  422.              * either a single or double left rotation. If the right
  423.              * subtree was balanced or right high, we only need a single
  424.              * left rotation. We do a double left rotate if the right subtree
  425.              * was left high.
  426.              */
  427.  
  428.             p1 = p->right;
  429.             b1 = p1->bal;
  430.             if (b1 >= BAL) {
  431.                 p->right = p1->left;        /* Single left rotatation    */
  432.                 p1->left = p;
  433.                 if (b1 == RH)
  434.                     p->bal = p1->bal = BAL;
  435.                 else {
  436.                     p->bal = RH;
  437.                     p1->bal = LH;
  438.                     subtree_shrank = false;
  439.                     }
  440.                 p = p1;                    /* Right subtree is new root    */
  441.                 }
  442.             else {
  443.                 p2 = p1->left;                /* Double left rotation        */
  444.                 b2 = p2->bal;
  445.                 p1->left = p2->right;
  446.                 p2->right = p1;
  447.                 p->right = p2->left;
  448.                 p2->left = p;
  449.                 p->bal = (b2 == RH) ? LH : BAL;
  450.                 p1->bal = (b2 == LH) ? RH : BAL;
  451.                 p2->bal = BAL;
  452.                 p = p2;
  453.                 }
  454.         }
  455.     *pp = p;
  456.     return subtree_shrank;
  457. }
  458.  
  459. PRIVATE bool balance_right(AVL_BUCKET **pp)
  460. /****************************************************************************
  461. *
  462. * Function:        balance_right
  463. * Parameters:    pp    - Point to root of subtree to balance
  464. * Returns:        True if the entire subtree shrank, false if not
  465. *
  466. * Description:    Routine to rebalance the subtree pointed to by pp when its
  467. *                right subtree has just shrunk. We adjust the balance factors
  468. *                and rebalance the subtree adjusting pp to point to the
  469. *                new root of the subtree.
  470. *
  471. ****************************************************************************/
  472. {
  473.     AVL_BUCKET    *p,*p1,*p2;
  474.     short        b1, b2;
  475.     bool        subtree_shrank = true;
  476.  
  477.     p = *pp;
  478.     switch (p->bal) {
  479.         case RH:
  480.  
  481.             /* The subtree was previously right high. Since the right subtree
  482.              * just shrank, this tree is now balanced while the overall
  483.              * height has been reduced.
  484.              */
  485.  
  486.             p->bal = BAL;
  487.             break;
  488.         case BAL:
  489.  
  490.             /* The subtree was previously balanced, so we simply make
  491.              * it right high, and signal that it did not shrink.
  492.              */
  493.  
  494.             p->bal = LH;
  495.             subtree_shrank = false;
  496.             break;
  497.         case LH:
  498.  
  499.             /* The subtree was previously left high. In this case we must do
  500.              * either a single or double right rotation. If the left
  501.              * subtree was balanced or left high, we only need a single
  502.              * right rotation. We do a double right rotate if the left
  503.              * subtree was right high.
  504.              */
  505.  
  506.             p1 = p->left;
  507.             b1 = p1->bal;
  508.             if (b1 <= BAL) {
  509.                 p->left = p1->right;        /* Single right rotation    */
  510.                 p1->right = p;
  511.                 if (b1 == LH)
  512.                     p->bal = p1->bal = BAL;
  513.                 else {
  514.                     p->bal = LH;
  515.                     p1->bal = RH;
  516.                     subtree_shrank = true;
  517.                     }
  518.                 p = p1;
  519.                 }
  520.             else {
  521.                 p2 = p1->right;                /* Double right rotation    */
  522.                 b2 = p2->bal;
  523.                 p1->right = p2->left;
  524.                 p2->left = p1;
  525.                 p->left = p2->right;
  526.                 p2->right = p;
  527.                 p->bal = (b2 == LH) ? LH : BAL;
  528.                 p1->bal = (b2 == RH) ? RH : BAL;
  529.                 p2->bal = BAL;
  530.                 p = p2;
  531.                 }
  532.         }
  533.     *pp = p;
  534.     return subtree_shrank;
  535. }
  536.  
  537. PRIVATE bool descend(AVL_BUCKET **rootp,AVL_BUCKET **pp)
  538. /****************************************************************************
  539. *
  540. * Function:        descend
  541. * Parameters:    rootp    - Pointer to pointer to tree to descend
  542. *                pp        - Pointer to pointer to node to replace
  543. * Returns:        True if the subtree just shrank, false if not.
  544. *
  545. * Description:    Routine to descend to the rightmost node of the left
  546. *                subtree. When we get there, we move it up into the position
  547. *                occupied by pp (retaining pp's balance factor) and delete
  548. *                this node. On the way back we rebalance the tree if
  549. *                necessary.
  550. *
  551. ****************************************************************************/
  552. {
  553.     AVL_BUCKET    *p = *rootp;
  554.     bool        has_shrunk,was_left = 0;
  555.  
  556.     if (p->right) {
  557.  
  558.         /* Continue to descend the right subtree, until we can go no
  559.          * further. On the way back up the recursion, if the tree has
  560.          * shrunk, we rebalance it.
  561.          */
  562.  
  563.         if (rootp == &(*pp)->left)
  564.             was_left = true;
  565.         has_shrunk = descend(&p->right,pp);
  566.         if (was_left)
  567.             rootp = &(*pp)->left;
  568.         return has_shrunk ? balance_right(rootp) : 0;
  569.         }
  570.     else {
  571.         *rootp = p->left;            /* Kill the old link to p            */
  572.  
  573.         p->bal = (*pp)->bal;        /* Retain the old balance factor    */
  574.         p->left = (*pp)->left;        /* and links                        */
  575.         p->right = (*pp)->right;
  576.         Node = *pp;                    /* Free the node                    */
  577.         *pp = p;                    /* Replace with p                    */
  578.         return true;                /* Subtree has shrunk - rebalance    */
  579.         }
  580. }
  581.  
  582. PRIVATE bool delete(AVL_BUCKET **pp)
  583. /****************************************************************************
  584. *
  585. * Function:        delete
  586. * Parameters:    pp    - Pointer to pointer to root of subtree to delete from
  587. * Returns:        True if the subtree shrunk in size, false if not.
  588. *
  589. * Description:    Internal recursive routine to delete a node from an
  590. *                AVL tree. Expects the global variables Tree, and Node
  591. *                to be set up. If the node is not found, we set the global
  592. *                Notfound to true.
  593. *
  594. ****************************************************************************/
  595. {
  596.     AVL_BUCKET    *p = *pp;
  597.     int            relation;
  598.  
  599.     if (p == NULL) {
  600.  
  601.         /* We could not locate the node in the tree, so set Notfound to
  602.          * true.
  603.          */
  604.  
  605.         Notfound = true;
  606.         return false;
  607.         }
  608.     else if ((relation = Tree->cmp(AVL_USERSPACE(p),
  609.             AVL_USERSPACE(Node))) == 0) {
  610.  
  611.         /* We have found the node, so delete it from the tree.
  612.          */
  613.  
  614.         if (p->right == NULL) {
  615.  
  616.             /* There is only a single left node in the tree, so move this
  617.              * node up to where p used to be, and then delete p.
  618.              */
  619.  
  620.             *pp = p->left;
  621.             Node = p;
  622.             return true;
  623.             }
  624.         else if (p->left == NULL) {
  625.  
  626.             /* There is only a single right node in the tree, so move this
  627.              * node up to where p used to be, and then delete p.
  628.              */
  629.  
  630.             *pp = p->right;
  631.             Node = p;
  632.             return true;
  633.             }
  634.         else if (descend(&p->left,pp))
  635.             return balance_left(pp);
  636.         }
  637.     else if (relation > 0) {
  638.  
  639.         /* If relation is > 0, then the current node p is greater than
  640.          * Node, so we delete node from the left subtree. If the left
  641.          * subtree has shrunk in size, we rebalance the tree and return
  642.          * the result of this rebalance (tree shrunk, or stayed the same
  643.          * size).
  644.          */
  645.  
  646.         if (delete(&p->left))
  647.             return balance_left(pp);
  648.         }
  649.     else {
  650.  
  651.         /* If relation is < 0, then the current node p is less than
  652.          * Node, so we delete node from the right subtree. If the right
  653.          * subtree has shrunk in size, we rebalance the tree and return
  654.          * the result of this rebalance (tree shrunk, or stayed the same
  655.          * size).
  656.          */
  657.  
  658.         if (delete(&p->right))
  659.             return balance_right(pp);
  660.         }
  661.     return false;
  662. }
  663.  
  664. PUBLIC void *avl_delete(AVL_TREE *tree,void *node)
  665. /****************************************************************************
  666. *
  667. * Function:        avl_delete
  668. * Parameters:    tree    - Tree to delete node from
  669. *                node    - Node to delete from tree
  670. * Returns:        Pointer to the node if successful, NULL of failure
  671. *
  672. * Description:    Deletes a node from an AVL tree. The node is removed from
  673. *                the tree, but it's memory is not released. You must call
  674. *                avl_freenode() to free the nodes memory.
  675. *
  676. ****************************************************************************/
  677. {
  678.     Tree = tree;
  679.     Node = AVL_HEADER(node);
  680.     Notfound = false;
  681.  
  682.     delete(&tree->root);
  683.     if (!Notfound)    tree->count--;
  684.  
  685.     return Notfound ? NULL : AVL_USERSPACE(Node);
  686. }
  687.  
  688. /*-------------------------------------------------------------------------*/
  689.  
  690. PRIVATE void pre_order(AVL_BUCKET *p)
  691. {
  692.     if (p) {
  693.         Visit(Params,AVL_USERSPACE(p));
  694.         pre_order(p->left);
  695.         pre_order(p->right);
  696.         }
  697. }
  698.  
  699. PRIVATE void in_order(AVL_BUCKET *p)
  700. {
  701.     if (p) {
  702.         in_order(p->left);
  703.         Visit(Params,AVL_USERSPACE(p));
  704.         in_order(p->right);
  705.         }
  706. }
  707.  
  708. PRIVATE void post_order(AVL_BUCKET *p)
  709. {
  710.     if (p) {
  711.         post_order(p->left);
  712.         post_order(p->right);
  713.         Visit(Params,AVL_USERSPACE(p));
  714.         }
  715. }
  716.  
  717. PUBLIC void avl_traverse(AVL_TREE *tree,int order,void (*visit)(void*,void*),
  718.     void *params)
  719. /****************************************************************************
  720. *
  721. * Function:        avl_preorder
  722. * Parameters:    tree    - Tree to traverse
  723. *
  724. * Description:    Traverses the AVL tree in a pre-order fashion, visiting
  725. *                the node first, then the left and then the right subtree.
  726. *
  727. *                The function visit() must accept two parameters. The second
  728. *                is a pointer to the node to visit, while the first is the
  729. *                params argument passed to avl_traverse.
  730. *
  731. ****************************************************************************/
  732. {
  733.     Visit = visit;
  734.     Params = params;
  735.     switch (order) {
  736.         case PREORDER:
  737.             pre_order(tree->root);
  738.             break;
  739.         case INORDER:
  740.             in_order(tree->root);
  741.             break;
  742.         case POSTORDER:
  743.             post_order(tree->root);
  744.         }
  745. }
  746.  
  747. /*-------------------------------------------------------------------------*/
  748.  
  749. /* Macro to test if the depth bit for level c is set    */
  750.  
  751. #define testbit(level)    (Map[level >> 3] & (1 << (level & 0x07)))
  752.  
  753. #ifdef DEBUG
  754. #define  PAD()    fprintf(Out,"   ");
  755. #define  PBAL(r)  fprintf(Out,"(%c)", r->bal == BAL ? 'B' : r->bal==LH ? 'L' : 'R');
  756. #else
  757. #define  PAD()
  758. #define  PBAL(r)
  759. #endif
  760.  
  761. PRIVATE void setbit(int level,bool set_it)
  762. /****************************************************************************
  763. *
  764. * Function:        setbit
  765. * Parameters:    depth    - Depth of bit to set
  766. *                set_it    - True to set bit, false to reset it
  767. *
  768. * Description:    Sets or resets the depth bit for a level. If this bit is
  769. *                set, we we draw a vertical line at that depth level.
  770. *
  771. ****************************************************************************/
  772. {
  773.     if (set_it)
  774.         Map[level >> 3] |= 1 << (level & 0x07);
  775.     else
  776.         Map[level >> 3] &= ~(1 << (level & 0x07));
  777. }
  778.  
  779. PRIVATE void print_tree(AVL_BUCKET *root,int left_subtree)
  780. /****************************************************************************
  781. *
  782. * Function:        print_tree
  783. * Parameters:    root            - Root of subtree to display
  784. *                left_subtree    - True if this is a left subtree
  785. *
  786. * Description:    Dumps the contents of subtree 'root' to the file Out.
  787. *
  788. ****************************************************************************/
  789. {
  790.     static int    depth = -1;            /* Current depth within subtree        */
  791.     int            i;
  792.  
  793.     if (root) {
  794.         depth++;
  795.  
  796.         if(root->right)
  797.             print_tree(root->right,false);
  798.         else
  799.             setbit(depth+1,true);
  800.  
  801.         for(i = 1; i <= depth; i++) {
  802.             Prnt(Out,NULL);
  803.             PAD();
  804.  
  805.             if (i == depth)
  806.                 fprintf(Out,"  %s", left_subtree ? Cset[2] : Cset[1]);
  807.             else if(testbit(i))
  808.                 fprintf(Out,"  %s  ", Cset[0]);
  809.             else
  810.                 fprintf(Out,"     ");
  811.             }
  812.  
  813.         Prnt(Out,AVL_USERSPACE(root));
  814.         PBAL(root);
  815.         fprintf(Out,"%s\n",root->left ? (root->right ? Cset[3] : Cset[5]) :
  816.             (root->right ? Cset[4] : ""));
  817.  
  818.         setbit(depth,left_subtree ? false : true);
  819.  
  820.         if(root->left)
  821.             print_tree(root->left,true);
  822.         else
  823.             setbit(depth+1,false);
  824.         depth--;
  825.         }
  826. }
  827.  
  828. PUBLIC void avl_print(FILE *out,AVL_TREE *tree,void (*prnt)(FILE*,void*),
  829.     bool graph_chars)
  830. /****************************************************************************
  831. *
  832. * Function:        avl_print
  833. * Parameters:    out                - Stream to print to
  834. *                tree            - Tree to print out
  835. *                prnt            - Routine to print each node
  836. *                graph_chars        - True if we print with graphics characters
  837. *
  838. * Description:    Dumps the contents of the AVL tree to the specified file.
  839. *                If graph_chars is true, the structure of the tree is
  840. *                printed using IBM graphics characters, otherwise it is
  841. *                printed using standard ASCII characters. If show_balance
  842. *                is true, the balance factors are displayed.
  843. *
  844. *                The routine prnt() takes a pointer to a file to print the
  845. *                node to, and a pointer to the node to print. It must print
  846. *                every node in a field of the same width, and when passed
  847. *                a null pointer for the node it should print a blank field
  848. *                the same width as the nodes. This provides correct
  849. *                formatting for the printed tree.
  850. *
  851. *                The tree can have a maximum height of 64 levels. If the
  852. *                tree is taller than this, the result is undefined. A
  853. *                balanced AVL tree with 64 levels would have in the order
  854. *                of 1e19 nodes!
  855. *
  856. ****************************************************************************/
  857. {
  858.     Tree = tree;
  859.     Out = out;
  860.     Prnt = prnt;
  861.     Cset = graph_chars ? Graph_chars : Norm_chars;
  862.     print_tree(tree->root,false);
  863. }
  864.  
  865. /*-------------------------------------------------------------------------*/
  866.  
  867. PUBLIC void *avl_findsym(AVL_TREE *tree,void *node)
  868. /****************************************************************************
  869. *
  870. * Function:        avl_findsym
  871. * Parameters:    tree    - Tree to search for the symbol
  872. *                node    - Node containing key to search for
  873. * Returns:        Pointer to the node if found, NULL if not.
  874. *
  875. * Description:    Searches the AVL tree for the specified node and returns
  876. *                it if it is found.
  877. *
  878. ****************************************************************************/
  879. {
  880.     AVL_BUCKET    *p;
  881.     int            relation;
  882.  
  883.     p = tree->root;
  884.  
  885.     while (p) {
  886.         if ((relation = tree->cmp(node,AVL_USERSPACE(p))) == 0)
  887.             return AVL_USERSPACE(p);
  888.         else if (relation > 0)
  889.             p = p->right;
  890.         else
  891.             p = p->left;
  892.         }
  893.     return NULL;
  894. }
  895.  
  896. /*-------------------------------------------------------------------------*/
  897.  
  898. PRIVATE void range_search(AVL_BUCKET *root)
  899. /****************************************************************************
  900. *
  901. * Function:        range_search
  902. * Parameters:    root    - Root of subtree to range search
  903. *
  904. * Description:    Recursive routine to range search a subtree.
  905. *
  906. ****************************************************************************/
  907. {
  908.     if (root) {
  909.         if (Tree->cmp(AVL_USERSPACE(root),Lower) < 0) {
  910.             /* If the root node is smaller than the lower bound, then recurse
  911.              * down the right subtree.
  912.              */
  913.  
  914.             range_search(root->right);
  915.             }
  916.         else if (Tree->cmp(AVL_USERSPACE(root),Upper) > 0) {
  917.             /* If the root node is larger than the lower bound, then recurse
  918.              * down the left subtree.
  919.              */
  920.  
  921.             range_search(root->left);
  922.             }
  923.         else {
  924.             /* We are within the range so recurse down the left subtree,
  925.              * visit the node and then recurse down the right subtree.
  926.              */
  927.  
  928.             range_search(root->left);
  929.             Visit(Params,AVL_USERSPACE(root));
  930.             range_search(root->right);
  931.             }
  932.         }
  933. }
  934.  
  935. PUBLIC void avl_range(AVL_TREE *tree,void *lower,void *upper,
  936.     void (*visit)(void*,void*),void *params)
  937. /****************************************************************************
  938. *
  939. * Function:        avl_range
  940. * Parameters:    tree    - Tree to range search
  941. *                lower    - Lower bound of range search (inclusive)
  942. *                upper    - Upper bound of range search (inclusive)
  943. *                visit    - Function to visit each node in range
  944. *                params    - Parameters for the visit routine.
  945. *
  946. * Description:    Calls visit for every node in the range [lower,upper]
  947. *                for the AVL tree 'tree'. Visit must accept two parameters.
  948. *                The first is the params argument passed to this function,
  949. *                while the second is a pointer to the node to visit.
  950. *
  951. ****************************************************************************/
  952. {
  953.     Tree = tree;
  954.     Visit = visit;
  955.     Params = params;
  956.     Lower = lower;
  957.     Upper = upper;
  958.     range_search(tree->root);
  959. }
  960.  
  961. /*-------------------------------------------------------------------------*/
  962.  
  963. int delmin(AVL_BUCKET **pp)
  964. /****************************************************************************
  965. *
  966. * Function:        delmin
  967. * Parameters:    root    - Root of subtree to delete from
  968. * Returns:        True if the subtree shrank.
  969. *
  970. * Description:    Recursive routine to delete the smallest node from an
  971. *                AVL tree.
  972. *
  973. ****************************************************************************/
  974. {
  975.     AVL_BUCKET    *p = *pp;
  976.  
  977.     if (p->left)
  978.         return delmin(&p->left) ? balance_left(pp) : 0;
  979.     else {
  980.         *pp = p->right;        /* Delete the node        */
  981.         Node = p;
  982.         return true;        /* Subtree just shrank    */
  983.         }
  984. }
  985.  
  986. PUBLIC void *avl_delmin(AVL_TREE *tree)
  987. /****************************************************************************
  988. *
  989. * Function:        avl_delmin
  990. * Parameters:    tree    - Tree to delete node from
  991. * Returns:        Pointer to the node found, or NULL on error.
  992. *
  993. * Description:    Deletes (removes) the smallest node from an AVL tree. The
  994. *                tree is rebalanced if need be. Note that the node is not
  995. *                freed. You will need to call avl_freenode() to do this.
  996. *
  997. ****************************************************************************/
  998. {
  999.     Node = NULL;
  1000.     delmin(&tree->root);
  1001.     if (Node)    tree->count--;
  1002.     return Node ? AVL_USERSPACE(Node) : NULL;
  1003. }
  1004.  
  1005. /*-------------------------------------------------------------------------*/
  1006.  
  1007. int delmax(AVL_BUCKET **pp)
  1008. /****************************************************************************
  1009. *
  1010. * Function:        delmax
  1011. * Parameters:    root    - Root of subtree to delete from
  1012. * Returns:        True if the subtree shrank.
  1013. *
  1014. * Description:    Recursive routine to delete the largest node from an
  1015. *                AVL tree.
  1016. *
  1017. ****************************************************************************/
  1018. {
  1019.     AVL_BUCKET    *p = *pp;
  1020.  
  1021.     if (p->right)
  1022.         return delmax(&p->right) ? balance_right(pp) : 0;
  1023.     else {
  1024.         *pp = p->left;        /* Delete the node        */
  1025.         Node = p;
  1026.         return true;        /* Subtree just shrank    */
  1027.         }
  1028. }
  1029.  
  1030. PUBLIC void *avl_delmax(AVL_TREE *tree)
  1031. /****************************************************************************
  1032. *
  1033. * Function:        avl_delmax
  1034. * Parameters:    tree    - Tree to delete node from
  1035. * Returns:        Pointer to the node found, or NULL on error.
  1036. *
  1037. * Description:    Deletes (removes) the largest node from an AVL tree. The
  1038. *                tree is rebalanced if need be. Note that the node is not
  1039. *                freed. You will need to call avl_freenode() to do this.
  1040. *
  1041. ****************************************************************************/
  1042. {
  1043.     Node = NULL;
  1044.     delmax(&tree->root);
  1045.     if (Node)    tree->count--;
  1046.     return Node ? AVL_USERSPACE(Node) : NULL;
  1047. }
  1048.  
  1049. /*-------------------------------------------------------------------------*/
  1050.  
  1051.