home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_09_01 / 9n01070a < prev    next >
Text File  |  1990-11-19  |  18KB  |  750 lines
  1. // TREE.CPP - implementation of balanced binary trees.
  2.  
  3. #include <stream.hpp>
  4. #include <stddef.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include "tree.hpp"
  8.  
  9. // constants which tell which way the subtree is out of balance
  10.  
  11. #define BALANCED     0
  12. #define LEFT        -1
  13. #define RIGHT        1
  14.  
  15. #define DOUBLE_LEFT  (LEFT*2)
  16. #define DOUBLE_RIGHT (RIGHT*2)
  17.  
  18. #define RETURN_CURRENT  0     // messages used by getprev() and getnext()
  19. #define RETURN_PARENT   1
  20.  
  21. // maximum allowable imbalance in a subtree
  22.  
  23. #define ALLOWABLE_IMBALANCE   1
  24.  
  25. // messages passed from a child to a parent node
  26.  
  27. #define DELETE_THIS_NODE   2
  28. #define TREE_SHRANK        1
  29. #define NO_CHANGE          0
  30. #define NODE_NOT_FOUND    -2
  31.  
  32. TREE::TREE(void)     // construct a tree
  33.    {
  34.    head = NULL;
  35.    current = NULL;
  36.    errval = OK;
  37.    }
  38.  
  39. void TREE::delete_subtree(NODE *nodeptr)
  40.    {
  41.    if(nodeptr->right != NULL)
  42.       {
  43.       delete_subtree(nodeptr->right);
  44.       delete nodeptr->right;
  45.       }
  46.  
  47.    if(nodeptr->left != NULL)
  48.       {
  49.       delete_subtree(nodeptr->left);
  50.       delete nodeptr->left;
  51.       }
  52.  
  53.    delete_data(nodeptr);
  54.    }
  55.  
  56. TREE::~TREE(void)    // destroy a tree
  57.    {
  58.    if(head != NULL)
  59.       {
  60.       delete_subtree(head);
  61.       delete head;
  62.       head = NULL;
  63.       }
  64.    }
  65.  
  66. void TREE::rebalance(NODE *parent)
  67.    {
  68.    NODE *p1, *p2;
  69.    NODE swapnode;
  70.  
  71.    if(parent->balance == DOUBLE_LEFT)
  72.       {
  73.       if(parent->left->balance != RIGHT)      // LL imbalance
  74.          {
  75.          p1           = parent->left;
  76.          parent->left = p1->right;
  77.          p1->right    = p1;   // will resolve properly after node swapping
  78.  
  79.          if(p1->balance == LEFT)
  80.             parent->balance = p1->balance = BALANCED;
  81.          else
  82.             {
  83.             parent->balance = LEFT;
  84.             p1->balance = RIGHT;
  85.             }
  86.  
  87.          swapnode = *parent;
  88.          *parent  = *p1;
  89.          *p1      = swapnode;
  90.          }
  91.       else                                   // LR imbalance
  92.          {
  93.          p1           = parent->left;
  94.          p2           = p1->right;
  95.          p1->right    = p2->left;
  96.          p2->left     = p1;
  97.          parent->left = p2->right;
  98.          p2->right    = p2;   // will resolve properly after node swapping
  99.  
  100.          if(p2->balance == RIGHT)
  101.             {
  102.             parent->balance = BALANCED;
  103.             p1->balance     = LEFT;
  104.             p2->balance     = RIGHT;
  105.             }
  106.          else if(p2->balance == LEFT)
  107.             {
  108.             parent->balance = RIGHT;
  109.             p1->balance     = BALANCED;
  110.             p2->balance     = BALANCED;
  111.             }
  112.          else
  113.             parent->balance = p1->balance = p2->balance = BALANCED;
  114.  
  115.          swapnode = *parent;
  116.          *parent  = *p2;
  117.          *p2      = swapnode;
  118.          }
  119.       }
  120.    else     // parent->balance == DOUBLE_RIGHT
  121.       {
  122.       if(parent->right->balance != LEFT)    // RR imbalance
  123.          {
  124.          p1            = parent->right;
  125.          parent->right = p1->left;
  126.          p1->left      = p1;  // will resolve properly after node swapping
  127.  
  128.          if(p1->balance == RIGHT)
  129.             parent->balance = p1->balance = BALANCED;
  130.          else
  131.             {
  132.             parent->balance = RIGHT;
  133.             p1->balance = LEFT;
  134.             }
  135.  
  136.          swapnode = *parent;
  137.          *parent  = *p1;
  138.          *p1      = swapnode;
  139.          }
  140.       else                                   // RL imbalance
  141.          {
  142.          p1 = parent->right;
  143.          p2 = p1->left;
  144.          p1->left = p2->right;
  145.          p2->right = p1;
  146.          parent->right = p2->left;
  147.          p2->left = p2;       // will resolve properly after node swapping
  148.  
  149.          if(p2->balance == RIGHT)
  150.             {
  151.             parent->balance = LEFT;
  152.             p1->balance     = BALANCED;
  153.             p2->balance     = BALANCED;
  154.             }
  155.          else if(p2->balance == LEFT)
  156.             {
  157.             parent->balance = BALANCED;
  158.             p1->balance     = RIGHT;
  159.             p2->balance     = BALANCED;
  160.             }
  161.          else
  162.             parent->balance = p1->balance = p2->balance = BALANCED;
  163.  
  164.          swapnode = *parent;
  165.          *parent  = *p2;
  166.          *p2      = swapnode;
  167.          }
  168.       }
  169.    }
  170.  
  171. int TREE::addnode(NODE *parent, NODE *newnode)
  172.    {
  173.    int retval;
  174.    int addside;
  175.  
  176.    if((retval = compare(parent->data,newnode->data,parent->dsize)) != 0)
  177.       {
  178.       if(retval < 0)         // parent < newnode - add on RIGHT side of parent
  179.          {
  180.          if(parent->right != NULL)
  181.             retval = addnode(parent->right,newnode);
  182.          else
  183.             {
  184.             parent->right = newnode;
  185.             retval = (parent->balance == LEFT) ? 0 : 1;
  186.             }
  187.          addside = RIGHT;
  188.          }
  189.       else                    // parent > newnode - add on LEFT side of parent
  190.          {
  191.          if(parent->left != NULL)
  192.             retval = addnode(parent->left,newnode);
  193.          else
  194.             {
  195.             parent->left = newnode;
  196.             retval = (parent->balance == RIGHT) ? 0 : 1;
  197.             }
  198.          addside = LEFT;
  199.          }
  200.       }
  201.    else     // duplicate items not allowed
  202.       {
  203.       errval = NO_DUPES;
  204.       return 0;
  205.       }
  206.  
  207.    // Part B - adjust the parent balance if necessary
  208.  
  209.    if(retval != 0)      // tree changed depth
  210.       {
  211.       parent->balance += addside;
  212.       if(abs(parent->balance) > ALLOWABLE_IMBALANCE)
  213.          rebalance(parent);
  214.       }
  215.  
  216.    return (parent->balance == BALANCED) ? 0 : retval;
  217.    }
  218.  
  219. int TREE::add(void *data, size_t size)
  220.    {
  221.    // build the node to be added
  222.  
  223.    errval = OK;
  224.  
  225.    NODE *nptr = new NODE;
  226.    if(nptr == NULL)     // unable to allocate new node
  227.       {
  228.       errval = MEM_ALLOC_FAIL;
  229.       return 0;
  230.       }
  231.  
  232.    nptr->left    = NULL;
  233.    nptr->right   = NULL;
  234.    nptr->balance = BALANCED;
  235.    nptr->dsize   = size;
  236.    alloc_data(nptr);
  237.    if(errval != OK)
  238.       return 0;
  239.  
  240.    copy_data(nptr, data);
  241.  
  242.    // Now determine where to add the new node
  243.  
  244.    if(head == NULL)
  245.       head = nptr;
  246.    else
  247.       addnode(head, nptr);
  248.  
  249.    if(errval == OK)
  250.       return 1;
  251.    else
  252.       return 0;
  253.    }
  254.  
  255. static NODE *walk_tree(NODE *nptr, int walk_side)
  256.    {
  257.    if(walk_side == RIGHT)
  258.       {
  259.       if(nptr->right == NULL)
  260.          return nptr;
  261.       else
  262.          return walk_tree(nptr->right, walk_side);
  263.       }
  264.    else     // walk_side == LEFT
  265.       {
  266.       if(nptr->left == NULL)
  267.          return nptr;
  268.       else
  269.          return walk_tree(nptr->left, walk_side);
  270.       }
  271.    }
  272.  
  273. int TREE::remove_node(NODE *currnode, void *key)
  274.    {
  275.    int retval,crval,remove_side;
  276.    NODE *new_head_ptr;
  277.    NODE worknode;
  278.  
  279.    if((crval = compare(currnode->data,key,currnode->dsize)) < 0)
  280.       {
  281.       if(currnode->right != NULL)
  282.          {
  283.          remove_side = RIGHT;
  284.          retval = remove_node(currnode->right, key);
  285.          }
  286.       else
  287.          return NODE_NOT_FOUND;
  288.       }
  289.    else if(crval > 0)
  290.       {
  291.       if(currnode->left != NULL)
  292.          {
  293.          remove_side = LEFT;
  294.          retval = remove_node(currnode->left, key);
  295.          }
  296.       else
  297.          return NODE_NOT_FOUND;
  298.       }
  299.    else     // currnode is the node to remove
  300.       {
  301.       if(currnode->left == NULL && currnode->right == NULL)    // no descendants
  302.          return DELETE_THIS_NODE;
  303.       else if( (currnode->left == NULL && currnode->right != NULL) ||
  304.                (currnode->left != NULL && currnode->right == NULL))
  305.          {     // one descendant
  306.          NODE *saveptr;
  307.  
  308.          if(currnode->left != NULL)
  309.             {
  310.             saveptr = currnode->left;
  311.             *currnode = *(currnode->left);
  312.             delete saveptr;
  313.             }
  314.          else
  315.             {
  316.             saveptr = currnode->right;
  317.             *currnode = *(currnode->right);
  318.             delete saveptr;
  319.             }
  320.  
  321.          return TREE_SHRANK;
  322.          }
  323.       else     // two descendants
  324.          {
  325.          if(currnode->balance == LEFT)
  326.             new_head_ptr = walk_tree(currnode->left,RIGHT);
  327.          else
  328.             new_head_ptr = walk_tree(currnode->right,LEFT);
  329.  
  330.          worknode.dsize = new_head_ptr->dsize;
  331.  
  332.          alloc_data(&worknode);
  333.          if(errval != OK)
  334.             return NO_CHANGE;
  335.  
  336.          copy_data(&worknode, new_head_ptr->data);
  337.          remove(new_head_ptr->data);
  338.          delete_data(currnode);
  339.          currnode->data = worknode.data;
  340.  
  341.          return NO_CHANGE;
  342.          }
  343.       }
  344.  
  345.    // we're on the way back up the recursion stack
  346.  
  347.    if(retval == DELETE_THIS_NODE)
  348.       {
  349.       if(remove_side == RIGHT)
  350.          {
  351.          delete_data(currnode->right);
  352.          delete currnode->right;
  353.          currnode->right = NULL;
  354.          currnode->balance += LEFT;
  355.          }
  356.       else
  357.          {
  358.          delete_data(currnode->left);
  359.          delete currnode->left;
  360.          currnode->left = NULL;
  361.          currnode->balance += RIGHT;
  362.          }
  363.  
  364.       if(abs(currnode->balance) > ALLOWABLE_IMBALANCE)
  365.          rebalance(currnode);
  366.  
  367.       if(currnode->balance == BALANCED)
  368.          return TREE_SHRANK;
  369.       else
  370.          return NO_CHANGE;
  371.       }
  372.    else if(retval == TREE_SHRANK)
  373.       {
  374.       if(remove_side == LEFT)
  375.          currnode->balance += RIGHT;
  376.       else
  377.          currnode->balance += LEFT;
  378.  
  379.       if(abs(currnode->balance) > ALLOWABLE_IMBALANCE)
  380.          rebalance(currnode);
  381.  
  382.       if(currnode->balance == BALANCED)
  383.          return TREE_SHRANK;
  384.       else
  385.          return NO_CHANGE;
  386.       }
  387.    else
  388.       return NO_CHANGE;
  389.    }
  390.  
  391. int TREE::remove(void *key)     // delete a node
  392.    {
  393.    int retval;
  394.  
  395.    errval = OK;
  396.  
  397.    if(head == NULL)
  398.       {
  399.       errval = TREE_EMPTY;
  400.       return 0;
  401.       }
  402.    else
  403.       {
  404.       retval = remove_node(head,key);
  405.       switch(retval)
  406.          {
  407.          case NODE_NOT_FOUND:
  408.             errval = NO_SUCH_NODE;
  409.             return 0;
  410.  
  411.          case DELETE_THIS_NODE:
  412.             delete_data(head);
  413.             delete head;
  414.             head = NULL;
  415.             return 1;
  416.  
  417.          default:
  418.             return 1;
  419.          }
  420.       }
  421.    }
  422.  
  423. NODE *TREE::findnode(NODE *currnode, void *key)
  424.    {
  425.    int cresult = compare(currnode->data, key, currnode->dsize);
  426.    if(cresult < 0)         // node < data - go right
  427.       {
  428.       if(currnode->right == NULL)
  429.          return NULL;      // node not found
  430.       else
  431.          return findnode(currnode->right, key);
  432.       }
  433.    else if(cresult > 0)    // node > data - go left
  434.       {
  435.       if(currnode->left == NULL)
  436.          return NULL;      // node not found
  437.       else
  438.          return findnode(currnode->left, key);
  439.       }
  440.    else                    // this must be the place!
  441.       return currnode;
  442.    }
  443.  
  444. void *TREE::find(void *key)     // locate a node
  445.    {
  446.    NODE *nodeptr;
  447.    void *retptr;
  448.  
  449.    errval = OK;
  450.  
  451.    if(head == NULL)
  452.       {
  453.       errval = TREE_EMPTY;
  454.       return NULL;
  455.       }
  456.    else
  457.       {
  458.       nodeptr = findnode(head,key);
  459.       if(nodeptr == NULL)
  460.          errval = NO_SUCH_NODE;
  461.       else
  462.          {
  463.          current = nodeptr;
  464.          retptr = nodeptr->data;
  465.          }
  466.  
  467.       return retptr;
  468.       }
  469.    }
  470.  
  471. void *TREE::findfirst(void)   // locate the first entry in a tree
  472.    {
  473.    errval = OK;
  474.  
  475.    if(head != NULL)
  476.       {
  477.       current = walk_tree(head, LEFT);
  478.       return current->data;
  479.       }
  480.    else
  481.       {
  482.       errval = NO_SUCH_NODE;
  483.       return NULL;
  484.       }
  485.    }
  486.  
  487. void *TREE::findlast(void)    // locate the last entry in a tree
  488.    {
  489.    errval = OK;
  490.  
  491.    if(head != NULL)
  492.       {
  493.       current = walk_tree(head, RIGHT);
  494.       return current->data;
  495.       }
  496.    else
  497.       {
  498.       errval = NO_SUCH_NODE;
  499.       return NULL;
  500.       }
  501.    }
  502.  
  503. static int TREE::getprev(NODE *currnode)
  504.    {
  505.    int side;
  506.    int retval;
  507.    int cresult = compare(currnode->data, current->data, currnode->dsize);
  508.    if(cresult < 0)         // node < data - go right
  509.       {
  510.       side = RIGHT;
  511.       retval = getprev(currnode->right);
  512.       }
  513.    else if(cresult > 0)    // node > data - go left
  514.       {
  515.       side = LEFT;
  516.       retval = getprev(currnode->left);
  517.       }
  518.    else                    // this must be the place!
  519.       {
  520.       if(current->left != NULL)
  521.          {
  522.          current = current->left;         // step to the left
  523.          while(current->right != NULL)    // then walk the right edge of the
  524.             current = current->right;     // subtree
  525.          return RETURN_CURRENT;
  526.          }
  527.       else
  528.          return RETURN_PARENT;
  529.       }
  530.  
  531.    // unwind the recursion stack
  532.  
  533.    if(retval == RETURN_PARENT)
  534.       {
  535.       if(side != LEFT)
  536.          {
  537.          current = currnode;
  538.          return RETURN_CURRENT;
  539.          }
  540.       else
  541.          return retval;
  542.       }
  543.    }
  544.  
  545. void *TREE::findprev(void)
  546.    {
  547.    int retval;
  548.  
  549.    errval = OK;
  550.  
  551.    retval = getprev(head);
  552.    if(retval == RETURN_PARENT)
  553.       {
  554.       errval = NO_SUCH_NODE;  // 'current' is pointing to first node in tree
  555.       return NULL;
  556.       }
  557.    else
  558.       return current->data;
  559.    }
  560.  
  561. static int TREE::getnext(NODE *currnode)
  562.    {
  563.    int side;
  564.    int retval;
  565.    int cresult = compare(currnode->data, current->data, currnode->dsize);
  566.    if(cresult < 0)         // node < data - go right
  567.       {
  568.       side = RIGHT;
  569.       retval = getnext(currnode->right);
  570.       }
  571.    else if(cresult > 0)    // node > data - go left
  572.       {
  573.       side = LEFT;
  574.       retval = getnext(currnode->left);
  575.       }
  576.    else                    // this must be the place!
  577.       {
  578.       if(current->right != NULL)
  579.          {
  580.          current = current->right;        // step to the right
  581.          while(current->left != NULL)     // then walk the left edge of the
  582.             current = current->left;      // subtree
  583.          return RETURN_CURRENT;
  584.          }
  585.       else
  586.          return RETURN_PARENT;
  587.       }
  588.  
  589.    // unwind the recursion stack
  590.  
  591.    if(retval == RETURN_PARENT)
  592.       {
  593.       if(side != RIGHT)
  594.          {
  595.          current = currnode;
  596.          return RETURN_CURRENT;
  597.          }
  598.       else
  599.          return retval;
  600.       }
  601.    }
  602.  
  603. void *TREE::findnext(void)    // locate the 'next' entry in the tree
  604.    {
  605.    int retval;
  606.  
  607.    errval = OK;
  608.  
  609.    retval = getnext(head);
  610.    if(retval == RETURN_PARENT)
  611.       {
  612.       errval = NO_SUCH_NODE;  // 'current' is pointing to last node in tree
  613.       return NULL;
  614.       }
  615.    else
  616.       return current->data;
  617.    }
  618.  
  619. void TREE::alloc_data(NODE *nptr)
  620.    {
  621.    nptr->data = new char[nptr->dsize];
  622.    if(nptr->data == NULL)
  623.       errval = MEM_ALLOC_FAIL;
  624.    }
  625.  
  626. void TREE::copy_data(NODE *to, void *from)
  627.    {
  628.    memcpy(to->data, from, to->dsize);
  629.    }
  630.  
  631. void TREE::delete_data(NODE *nptr)
  632.    {
  633.    delete nptr->data;
  634.    nptr->data = NULL;
  635.    }
  636.  
  637. int TREE::compare(void *data1, void *data2, size_t size)
  638.    {
  639.    return memcmp(data1,data2,size);
  640.    }
  641.  
  642. #define VERTBAR      "|      "
  643. #define BLANK        "       "
  644. #define RIGHT_DOWN   "--+    "
  645. #define LEFT_DOWN    "+------"
  646.  
  647. static unsigned char *mapptr;
  648.  
  649. static void print_bars(int level, int isright)
  650.    {
  651.    for(int i = 0 ; i < level ; ++i)
  652.       {
  653.       unsigned char bit = 0x80 >> (i % 8);
  654.       int ndx = i / 8;
  655.  
  656.       if(i < level-1)
  657.          {
  658.          if(mapptr[ndx] & bit)
  659.             printf(VERTBAR);
  660.          else
  661.             printf(BLANK);
  662.          }
  663.       else     // i == level-1
  664.          {
  665.          if(mapptr[ndx] & bit)
  666.             {
  667.             if(!isright)
  668.                {
  669.                printf(LEFT_DOWN);
  670.                mapptr[ndx] ^= bit;     // turn off the appropriate line
  671.                }
  672.             else
  673.                printf(VERTBAR);
  674.             }
  675.          else
  676.             printf(BLANK);
  677.          }
  678.       }
  679.    }
  680.  
  681. static void print_node(NODE *nptr, int level, int isright)
  682.    {
  683.    // print bars and leaders
  684.  
  685.    print_bars(level, isright);
  686.  
  687.    // print the actual node
  688.  
  689.    char balchar = (nptr->balance == BALANCED) ? 'B' :
  690.                      ((nptr->balance == LEFT) ? 'L' : 'R');
  691.  
  692.    printf("%02s(%c)",nptr->data,balchar);
  693.  
  694.    if(nptr->right != NULL)    // add trailing right extension if appropriate
  695.       printf(RIGHT_DOWN);
  696.  
  697.    printf("\n");
  698.  
  699.    // set the appropriate bits
  700.  
  701.    if(nptr->left != NULL)
  702.       {
  703.       unsigned char bit = 0x80 >> (level % 8);
  704.       int ndx = level / 8;
  705.  
  706.       mapptr[ndx] |= bit;
  707.       }
  708.  
  709.    if(nptr->right != NULL)
  710.       print_node(nptr->right, level+1, 1);
  711.  
  712.    if(nptr->left != NULL)
  713.       print_node(nptr->left, level+1, 0);
  714.  
  715.    if(!isright && nptr->left == NULL && nptr->right == NULL)
  716.       {
  717.       print_bars(level-1,1);
  718.       printf("\n");
  719.       }
  720.    }
  721.  
  722. void TREE::print_tree(void)
  723.    {
  724.    // figure out the maximum possible tree depth
  725.  
  726.    NODE *nptr = head;
  727.  
  728.    for(int maxdepth = 0 ; nptr != NULL ; ++maxdepth, nptr = nptr->right)
  729.       ;  // placed here to avoid warning message
  730.  
  731.    maxdepth += 2;    // max difference between left & right tree is 2
  732.  
  733.    // allocate bit array used for printing vertical bars
  734.  
  735.    mapptr = new unsigned char[(maxdepth/8)+1];
  736.    if(mapptr == NULL)
  737.       {
  738.       errval = MEM_ALLOC_FAIL;
  739.       return;
  740.       }
  741.  
  742.    for(int i = 0 ; i < (maxdepth/8)+1 ; ++i)
  743.       mapptr[i] = 0;
  744.  
  745.    print_node(head,0,0);
  746.  
  747.    delete mapptr;
  748.    }
  749.  
  750.