home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume27 / avl-subs / part01 / tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-09-06  |  10.5 KB  |  533 lines
  1. /* as_tree - tree library for as
  2.  * vix 14dec85 [written]
  3.  * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
  4.  * vix 06feb86 [added tree_mung()]
  5.  * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
  6.  * vix 23jun86 [added delete uar to add for replaced nodes]
  7.  * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
  8.  */
  9.  
  10.  
  11. /* This program text was created by Paul Vixie using examples from the book:
  12.  * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
  13.  * 0-13-022005-1.  This code and associated documentation is hereby placed
  14.  * in the public domain.
  15.  */
  16.  
  17.  
  18. #ifndef LINT
  19. static char RCSid[] = "$Id:";
  20. #endif
  21.  
  22.  
  23. /*#define        DEBUG    "tree"*/
  24.  
  25.  
  26. #include <stdio.h>
  27. #include <stdlib.h>
  28. #include "vixie.h"
  29. #include "tree.h"
  30.  
  31.  
  32. #ifdef DEBUG
  33. #define        MSG(msg)    printf("DEBUG: '%s'\n", msg);
  34. #else
  35. #define        MSG(msg)
  36. #endif
  37.  
  38.  
  39. static void    sprout    __P( (tree **, tree_t, int *, int (*)(), void (*)()) );
  40. static int    delete    __P( (tree **, int (*)(), tree_t, void (*)(),
  41.                   int *, int *) );
  42. static void    del    __P( (tree **, int *, tree **, void (*)(), int *) );
  43. static void    bal_L    __P( (tree **, int *) );
  44. static void    bal_R    __P( (tree **, int *) );
  45.  
  46.  
  47. void
  48. tree_init(ppr_tree)
  49.     tree    **ppr_tree;
  50. {
  51.     ENTER("tree_init")
  52.     *ppr_tree = NULL;
  53.     EXITV
  54. }
  55.     
  56.  
  57. tree_t
  58. tree_srch(ppr_tree, pfi_compare, p_user)
  59.     tree    **ppr_tree;
  60.     int    (*pfi_compare)();
  61.     tree_t    p_user;
  62. {
  63.     register int    i_comp;
  64.  
  65.     ENTER("tree_srch")
  66.  
  67.     if (*ppr_tree)
  68.     {
  69.         i_comp = (*pfi_compare)(p_user, (**ppr_tree).tree_p);
  70.         if (i_comp > 0)
  71.             EXIT(tree_srch(
  72.                 &(**ppr_tree).tree_r,
  73.                 pfi_compare,
  74.                 p_user
  75.             ))
  76.         if (i_comp < 0)
  77.             EXIT(tree_srch(
  78.                 &(**ppr_tree).tree_l,
  79.                 pfi_compare,
  80.                 p_user
  81.             ))
  82.  
  83.         /* not higher, not lower... this must be the one.
  84.          */
  85.         EXIT((**ppr_tree).tree_p)
  86.     }
  87.  
  88.     /* grounded. NOT found.
  89.      */
  90.     EXIT(NULL)
  91. }
  92.  
  93.  
  94. void
  95. tree_add(ppr_tree, pfi_compare, p_user, pfv_uar)
  96.     tree    **ppr_tree;
  97.     int    (*pfi_compare)();
  98.     tree_t    p_user;
  99.     void    (*pfv_uar)();
  100. {
  101.     int    i_balance = FALSE;
  102.  
  103.     ENTER("tree_add")
  104.     sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar);
  105.     EXITV
  106. }
  107.  
  108.  
  109. int
  110. tree_delete(ppr_p, pfi_compare, p_user, pfv_uar)
  111.     tree    **ppr_p;
  112.     int    (*pfi_compare)();
  113.     tree_t    p_user;
  114.     void    (*pfv_uar)();
  115. {
  116.     int    i_balance = FALSE,
  117.         i_uar_called = FALSE;
  118.  
  119.     ENTER("tree_delete");
  120.     EXIT(delete(ppr_p, pfi_compare, p_user, pfv_uar,
  121.             &i_balance, &i_uar_called))
  122. }
  123.  
  124.  
  125. int
  126. tree_trav(ppr_tree, pfi_uar)
  127.     tree    **ppr_tree;
  128.     int    (*pfi_uar)();
  129. {
  130.     ENTER("tree_trav")
  131.  
  132.     if (!*ppr_tree)
  133.         EXIT(TRUE)
  134.  
  135.     if (!tree_trav(&(**ppr_tree).tree_l, pfi_uar))
  136.         EXIT(FALSE)
  137.     if (!(*pfi_uar)((**ppr_tree).tree_p))
  138.         EXIT(FALSE)
  139.     if (!tree_trav(&(**ppr_tree).tree_r, pfi_uar))
  140.         EXIT(FALSE)
  141.     EXIT(TRUE)
  142. }
  143.  
  144.  
  145. void
  146. tree_mung(ppr_tree, pfv_uar)
  147.     tree    **ppr_tree;
  148.     void    (*pfv_uar)();
  149. {
  150.     ENTER("tree_mung")
  151.     if (*ppr_tree)
  152.     {
  153.         tree_mung(&(**ppr_tree).tree_l, pfv_uar);
  154.         tree_mung(&(**ppr_tree).tree_r, pfv_uar);
  155.         if (pfv_uar)
  156.             (*pfv_uar)((**ppr_tree).tree_p);
  157.         free(*ppr_tree);
  158.         *ppr_tree = NULL;
  159.     }
  160.     EXITV
  161. }
  162.  
  163.  
  164. static void
  165. sprout(ppr, p_data, pi_balance, pfi_compare, pfv_delete)
  166.     tree    **ppr;
  167.     tree_t    p_data;
  168.     int    *pi_balance;
  169.     int    (*pfi_compare)();
  170.     void    (*pfv_delete)();
  171. {
  172.     tree    *p1, *p2;
  173.     int    cmp;
  174.  
  175.     ENTER("sprout")
  176.  
  177.     /* are we grounded?  if so, add the node "here" and set the rebalance
  178.      * flag, then exit.
  179.      */
  180.     if (!*ppr) {
  181.         MSG("grounded. adding new node, setting h=true")
  182.         *ppr = (tree *) malloc(sizeof(tree));
  183.         (*ppr)->tree_l = NULL;
  184.         (*ppr)->tree_r = NULL;
  185.         (*ppr)->tree_b = 0;
  186.         (*ppr)->tree_p = p_data;
  187.         *pi_balance = TRUE;
  188.         EXITV
  189.     }
  190.  
  191.     /* compare the data using routine passed by caller.
  192.      */
  193.     cmp = (*pfi_compare)(p_data, (*ppr)->tree_p);
  194.  
  195.     /* if LESS, prepare to move to the left.
  196.      */
  197.     if (cmp < 0) {
  198.         MSG("LESS. sprouting left.")
  199.         sprout(&(*ppr)->tree_l, p_data, pi_balance,
  200.             pfi_compare, pfv_delete);
  201.         if (*pi_balance) {    /* left branch has grown longer */
  202.             MSG("LESS: left branch has grown")
  203.             switch ((*ppr)->tree_b)
  204.             {
  205.             case 1:    /* right branch WAS longer; balance is ok now */
  206.                 MSG("LESS: case 1.. balnce restored implicitly")
  207.                 (*ppr)->tree_b = 0;
  208.                 *pi_balance = FALSE;
  209.                 break;
  210.             case 0:    /* balance WAS okay; now left branch longer */
  211.                 MSG("LESS: case 0.. balnce bad but still ok")
  212.                 (*ppr)->tree_b = -1;
  213.                 break;
  214.             case -1:
  215.                 /* left branch was already too long. rebalnce */
  216.                 MSG("LESS: case -1: rebalancing")
  217.                 p1 = (*ppr)->tree_l;
  218.                 if (p1->tree_b == -1) {    /* LL */
  219.                     MSG("LESS: single LL")
  220.                     (*ppr)->tree_l = p1->tree_r;
  221.                     p1->tree_r = *ppr;
  222.                     (*ppr)->tree_b = 0;
  223.                     *ppr = p1;
  224.                 }
  225.                 else {            /* double LR */
  226.                     MSG("LESS: double LR")
  227.  
  228.                     p2 = p1->tree_r;
  229.                     p1->tree_r = p2->tree_l;
  230.                     p2->tree_l = p1;
  231.  
  232.                     (*ppr)->tree_l = p2->tree_r;
  233.                     p2->tree_r = *ppr;
  234.  
  235.                     if (p2->tree_b == -1)
  236.                         (*ppr)->tree_b = 1;
  237.                     else
  238.                         (*ppr)->tree_b = 0;
  239.  
  240.                     if (p2->tree_b == 1)
  241.                         p1->tree_b = -1;
  242.                     else
  243.                         p1->tree_b = 0;
  244.                     *ppr = p2;
  245.                 } /*else*/
  246.                 (*ppr)->tree_b = 0;
  247.                 *pi_balance = FALSE;
  248.             } /*switch*/
  249.         } /*if*/
  250.         EXITV
  251.     } /*if*/
  252.  
  253.     /* if MORE, prepare to move to the right.
  254.      */
  255.     if (cmp > 0) {
  256.         MSG("MORE: sprouting to the right")
  257.         sprout(&(*ppr)->tree_r, p_data, pi_balance,
  258.             pfi_compare, pfv_delete);
  259.         if (*pi_balance) {    /* right branch has grown longer */
  260.             MSG("MORE: right branch has grown")
  261.  
  262.             switch ((*ppr)->tree_b)
  263.             {
  264.             case -1:MSG("MORE: balance was off, fixed implicitly")
  265.                 (*ppr)->tree_b = 0;
  266.                 *pi_balance = FALSE;
  267.                 break;
  268.             case 0:    MSG("MORE: balance was okay, now off but ok")
  269.                 (*ppr)->tree_b = 1;
  270.                 break;
  271.             case 1:    MSG("MORE: balance was off, need to rebalance")
  272.                 p1 = (*ppr)->tree_r;
  273.                 if (p1->tree_b == 1) {    /* RR */
  274.                     MSG("MORE: single RR")
  275.                     (*ppr)->tree_r = p1->tree_l;
  276.                     p1->tree_l = *ppr;
  277.                     (*ppr)->tree_b = 0;
  278.                     *ppr = p1;
  279.                 }
  280.                 else {            /* double RL */
  281.                     MSG("MORE: double RL")
  282.  
  283.                     p2 = p1->tree_l;
  284.                     p1->tree_l = p2->tree_r;
  285.                     p2->tree_r = p1;
  286.  
  287.                     (*ppr)->tree_r = p2->tree_l;
  288.                     p2->tree_l = *ppr;
  289.  
  290.                     if (p2->tree_b == 1)
  291.                         (*ppr)->tree_b = -1;
  292.                     else
  293.                         (*ppr)->tree_b = 0;
  294.  
  295.                     if (p2->tree_b == -1)
  296.                         p1->tree_b = 1;
  297.                     else
  298.                         p1->tree_b = 0;
  299.  
  300.                     *ppr = p2;
  301.                 } /*else*/
  302.                 (*ppr)->tree_b = 0;
  303.                 *pi_balance = FALSE;
  304.             } /*switch*/
  305.         } /*if*/
  306.         EXITV
  307.     } /*if*/
  308.  
  309.     /* not less, not more: this is the same key!  replace...
  310.      */
  311.     MSG("I found it!  Replacing data value")
  312.     *pi_balance = FALSE;
  313.     if (pfv_delete)
  314.         (*pfv_delete)((*ppr)->tree_p);
  315.     (*ppr)->tree_p = p_data;
  316.     EXITV
  317. }
  318.  
  319.  
  320. static int
  321. delete(ppr_p, pfi_compare, p_user, pfv_uar, pi_balance, pi_uar_called)
  322.     tree    **ppr_p;
  323.     int    (*pfi_compare)();
  324.     tree_t    p_user;
  325.     void    (*pfv_uar)();
  326.     int    *pi_balance;
  327.     int    *pi_uar_called;
  328. {
  329.     tree    *pr_q;
  330.     int    i_comp, i_ret;
  331.  
  332.     ENTER("delete")
  333.  
  334.     if (*ppr_p == NULL) {
  335.         MSG("key not in tree")
  336.         EXIT(FALSE)
  337.     }
  338.  
  339.     i_comp = (*pfi_compare)((*ppr_p)->tree_p, p_user);
  340.     if (i_comp > 0) {
  341.         MSG("too high - scan left")
  342.         i_ret = delete(&(*ppr_p)->tree_l, pfi_compare, p_user, pfv_uar,
  343.                         pi_balance, pi_uar_called);
  344.         if (*pi_balance)
  345.             bal_L(ppr_p, pi_balance);
  346.     }
  347.     else if (i_comp < 0) {
  348.         MSG("too low - scan right")
  349.         i_ret = delete(&(*ppr_p)->tree_r, pfi_compare, p_user, pfv_uar,
  350.                         pi_balance, pi_uar_called);
  351.         if (*pi_balance)
  352.             bal_R(ppr_p, pi_balance);
  353.     }
  354.     else {
  355.         MSG("equal")
  356.         pr_q = *ppr_p;
  357.         if (pr_q->tree_r == NULL) {
  358.             MSG("right subtree null")
  359.             *ppr_p = pr_q->tree_l;
  360.             *pi_balance = TRUE;
  361.         }
  362.         else if (pr_q->tree_l == NULL) {
  363.             MSG("right subtree non-null, left subtree null")
  364.             *ppr_p = pr_q->tree_r;
  365.             *pi_balance = TRUE;
  366.         }
  367.         else {
  368.             MSG("neither subtree null")
  369.             del(&pr_q->tree_l, pi_balance, &pr_q, pfv_uar,
  370.                                 pi_uar_called);
  371.             if (*pi_balance)
  372.                 bal_L(ppr_p, pi_balance);
  373.         }
  374.         if (!*pi_uar_called && pfv_uar)
  375.             (*pfv_uar)(pr_q->tree_p);
  376.         free(pr_q);    /* thanks to wuth@castrov.cuc.ab.ca */
  377.         i_ret = TRUE;
  378.     }
  379.     EXIT(i_ret)
  380. }
  381.  
  382.  
  383. static void
  384. del(ppr_r, pi_balance, ppr_q, pfv_uar, pi_uar_called)
  385.     tree    **ppr_r;
  386.     int    *pi_balance;
  387.     tree    **ppr_q;
  388.     void    (*pfv_uar)();
  389.     int    *pi_uar_called;
  390. {
  391.     ENTER("del")
  392.  
  393.     if ((*ppr_r)->tree_r != NULL) {
  394.         del(&(*ppr_r)->tree_r, pi_balance, ppr_q,
  395.             pfv_uar, pi_uar_called);
  396.         if (*pi_balance)
  397.             bal_R(ppr_r, pi_balance);
  398.     } else {
  399.         if (pfv_uar)
  400.             (*pfv_uar)((*ppr_q)->tree_p);
  401.         *pi_uar_called = TRUE;
  402.         (*ppr_q)->tree_p = (*ppr_r)->tree_p;
  403.         *ppr_q = *ppr_r;
  404.         *ppr_r = (*ppr_r)->tree_l;
  405.         *pi_balance = TRUE;
  406.     }
  407.  
  408.     EXITV
  409. }
  410.  
  411.  
  412. static void
  413. bal_L(ppr_p, pi_balance)
  414.     tree    **ppr_p;
  415.     int    *pi_balance;
  416. {
  417.     tree    *p1, *p2;
  418.     int    b1, b2;
  419.  
  420.     ENTER("bal_L")
  421.     MSG("left branch has shrunk")
  422.  
  423.     switch ((*ppr_p)->tree_b)
  424.     {
  425.     case -1: MSG("was imbalanced, fixed implicitly")
  426.         (*ppr_p)->tree_b = 0;
  427.         break;
  428.     case 0:    MSG("was okay, is now one off")
  429.         (*ppr_p)->tree_b = 1;
  430.         *pi_balance = FALSE;
  431.         break;
  432.     case 1:    MSG("was already off, this is too much")
  433.         p1 = (*ppr_p)->tree_r;
  434.         b1 = p1->tree_b;
  435.         if (b1 >= 0) {
  436.             MSG("single RR")
  437.             (*ppr_p)->tree_r = p1->tree_l;
  438.             p1->tree_l = *ppr_p;
  439.             if (b1 == 0) {
  440.                 MSG("b1 == 0")
  441.                 (*ppr_p)->tree_b = 1;
  442.                 p1->tree_b = -1;
  443.                 *pi_balance = FALSE;
  444.             } else {
  445.                 MSG("b1 != 0")
  446.                 (*ppr_p)->tree_b = 0;
  447.                 p1->tree_b = 0;
  448.             }
  449.             *ppr_p = p1;
  450.         } else {
  451.             MSG("double RL")
  452.             p2 = p1->tree_l;
  453.             b2 = p2->tree_b;
  454.             p1->tree_l = p2->tree_r;
  455.             p2->tree_r = p1;
  456.             (*ppr_p)->tree_r = p2->tree_l;
  457.             p2->tree_l = *ppr_p;
  458.             if (b2 == 1)
  459.                 (*ppr_p)->tree_b = -1;
  460.             else
  461.                 (*ppr_p)->tree_b = 0;
  462.             if (b2 == -1)
  463.                 p1->tree_b = 1;
  464.             else
  465.                 p1->tree_b = 0;
  466.             *ppr_p = p2;
  467.             p2->tree_b = 0;
  468.         }
  469.     }
  470.     EXITV
  471. }
  472.  
  473.  
  474. static void
  475. bal_R(ppr_p, pi_balance)
  476.     tree    **ppr_p;
  477.     int    *pi_balance;
  478. {
  479.     tree    *p1, *p2;
  480.     int    b1, b2;
  481.  
  482.     ENTER("bal_R")
  483.     MSG("right branch has shrunk")
  484.     switch ((*ppr_p)->tree_b)
  485.     {
  486.     case 1:    MSG("was imbalanced, fixed implicitly")
  487.         (*ppr_p)->tree_b = 0;
  488.         break;
  489.     case 0:    MSG("was okay, is now one off")
  490.         (*ppr_p)->tree_b = -1;
  491.         *pi_balance = FALSE;
  492.         break;
  493.     case -1: MSG("was already off, this is too much")
  494.         p1 = (*ppr_p)->tree_l;
  495.         b1 = p1->tree_b;
  496.         if (b1 <= 0) {
  497.             MSG("single LL")
  498.             (*ppr_p)->tree_l = p1->tree_r;
  499.             p1->tree_r = *ppr_p;
  500.             if (b1 == 0) {
  501.                 MSG("b1 == 0")
  502.                 (*ppr_p)->tree_b = -1;
  503.                 p1->tree_b = 1;
  504.                 *pi_balance = FALSE;
  505.             } else {
  506.                 MSG("b1 != 0")
  507.                 (*ppr_p)->tree_b = 0;
  508.                 p1->tree_b = 0;
  509.             }
  510.             *ppr_p = p1;
  511.         } else {
  512.             MSG("double LR")
  513.             p2 = p1->tree_r;
  514.             b2 = p2->tree_b;
  515.             p1->tree_r = p2->tree_l;
  516.             p2->tree_l = p1;
  517.             (*ppr_p)->tree_l = p2->tree_r;
  518.             p2->tree_r = *ppr_p;
  519.             if (b2 == -1)
  520.                 (*ppr_p)->tree_b = 1;
  521.             else
  522.                 (*ppr_p)->tree_b = 0;
  523.             if (b2 == 1)
  524.                 p1->tree_b = -1;
  525.             else
  526.                 p1->tree_b = 0;
  527.             *ppr_p = p2;
  528.             p2->tree_b = 0;
  529.         }
  530.     }
  531.     EXITV
  532. }
  533.