tree_adders.c

linked list linked list tree struc

/*
 * Wei Cui
 * 981503
 * wec924 */
 
#include <stdio.h>
#include <tree.h>


TREE treeArray[TREELEN];
NODE nodeArray[NODELEN];

TREE *freeTreePtr = NULL;    /* next available tree */
NODE *freeNodePtr = NULL;    /* next available node */

int initFlag = 0;            /* flag of initialization */

/*initialize the tree and node array */
int init()
{
  int i;
  TREEPTR temp;
  for (i=0; i<TREELEN; i++)
  {
    freeTreePtr = &treeArray[i];   
    if (i<TREELEN-1) {
      temp = &treeArray[i+1];
      freeTreePtr->last_node = (NODE *)temp;
    }
  }
  freeTreePtr = &treeArray[0];
  for (i=0; i<NODELEN; i++)
  {
    freeNodePtr = &nodeArray[i];
    if (i<NODELEN-1) freeNodePtr->next = &nodeArray[i+1];
  }
  freeNodePtr = &nodeArray[0];
  return 1;
}


TREEPTR TreeCreate()
{
  TREEPTR myTree;
  if (!initFlag) initFlag = init();
  if (!freeTreePtr)
  {
    printf("You have had %d trees, you can not creat any more!!\n", TREELEN);
    return NULL;
  }
  else
  {   
    myTree = freeTreePtr;
    freeTreePtr = (TREEPTR)myTree->last_node;
    myTree->first_node = NULL;
    myTree->last_node = NULL;
    myTree->curr_node = NULL;
    myTree->root_node = NULL;
    myTree->size = 0;
    return myTree;
  }    
}



int _height(NODE *myNode)
{
  if (myNode) return myNode->height;
  else return 0;
}

void _setHeight(NODE *myNode)
/* set the height of the node to the max subtree height plus 1*/
{
  int lHeight, rHeight;
  lHeight = _height(myNode->left);
  rHeight = _height(myNode->right);
  if (lHeight > rHeight)
  {
    myNode->height = lHeight+1;
  }
  else
  {
    myNode->height = rHeight+1;
  }
}


void _single_rotate_right(NODE *myNode)
{
  NODE *lr;
  lr = myNode->left->right;
  myNode->left->right = myNode;
  myNode->left->parent = myNode->parent;
  if (myNode->parent)
  {
    if (myNode->parent->left == myNode)   myNode->parent->left=myNode->left;
    else   myNode->parent->right=myNode->left;
  }
  myNode->parent = myNode->left;
  myNode->left = lr;
  if (lr)
  {
    lr->parent = myNode;
  }
}


void _single_rotate_left(NODE *myNode)
{
  NODE *rl;
  rl = myNode->right->left;
  myNode->right->left = myNode;
  myNode->right->parent = myNode->parent;
  if (myNode->parent)
  {
    if (myNode->parent->left == myNode)   myNode->parent->left=myNode->right;
    else   myNode->parent->right=myNode->right;
  }
  myNode->parent = myNode->right;
  myNode->right = rl;
  if (rl)
  {
    rl->parent = myNode;
  }
}


void _double_rotate_right(NODE *myNode)
{
  NODE *lrl, *lrr;
  lrl = myNode->left->right->left;
  lrr = myNode->left->right->right;
  myNode->left->right->parent = myNode->parent;
  myNode->left->right->left = myNode->left;
  myNode->left->right->right = myNode;
  if (myNode->parent)
  {
    if (myNode->parent->left == myNode)   myNode->parent->left=myNode->left->right;
    else   myNode->parent->right=myNode->left->right;
  }
  myNode->parent = myNode->left->right;
  myNode->left->parent = myNode->left->right;
  myNode->left->right = lrl;
  if (lrl)
  {
    lrl->parent = myNode->left;
  }
  _setHeight(myNode->left);
  myNode->left = lrr;
  if (lrr)
  {
    lrr->parent = myNode;
  }
}


void _double_rotate_left(NODE *myNode)
{
  NODE *rll, *rlr;
  rll = myNode->right->left->left;
  rlr = myNode->right->left->right;
  myNode->right->left->parent = myNode->parent;
  myNode->right->left->left = myNode;
  myNode->right->left->right = myNode->right;
  if (myNode->parent)
  {
    if (myNode->parent->left == myNode)   myNode->parent->left=myNode->right->left;
    else   myNode->parent->right=myNode->right->left;
  }
  myNode->parent = myNode->right->left;
  myNode->right->parent = myNode->right->left;
  myNode->right->left = rlr;
  if (rlr)
  {
    rlr->parent = myNode->right;
  }
  _setHeight(myNode->right);
  myNode->right = rll;
  if (rll)
  {
    rll->parent = myNode;
  }
}


void _rotate_if_necessary(TREEPTR mytree, NODE *myNode)
/* test if the current node needs a rotation, if it does,
choose the correct rotation routine. Set the height of
the current node at the end.*/
{
  int lHeight, rHeight;
  lHeight = _height(myNode->left);
  rHeight = _height(myNode->right);
  if ( lHeight==rHeight+2 )
  {
    if (_height(myNode->left->left) >= _height(myNode->left->right))
    {
      _single_rotate_right(myNode);
    }
    else
    {
      _double_rotate_right(myNode);
    }
  }
  else
  {
    if ( rHeight==lHeight+2 )
    {
      if (_height(myNode->right->right) >= _height(myNode->right->left))
      {
        _single_rotate_left(myNode);
      }
      else
      {
        _double_rotate_left(myNode);
      }
    }
  }
/* reset the root of the tree if necessary */
  if ((mytree->root_node == myNode) && (myNode->parent))
  {
    mytree->root_node = myNode->parent;
  }
  _setHeight(myNode);
}


int TreeAdd(TREEPTR mytree, TITEM nodeitem, int itemOrder(TITEM, TITEM))
{
/*find next available node */
  int goleft;
  NODE *myNode, *cpNode;
  if ( !freeNodePtr || !mytree)
  {
    return -1;
  }
  else
  {
    myNode = freeNodePtr;
    freeNodePtr = myNode->next;
/*initialize it, and place it after the current node */
    myNode->item = nodeitem;
    myNode->height = 1;
    myNode->left = NULL;
    myNode->right = NULL;
    myNode->next = NULL;
    myNode->prev = NULL;
    if (mytree->root_node == NULL)      /*the tree is empty before insertion. */
    {
      myNode->parent = NULL;
      mytree->first_node = myNode;
      mytree->last_node = myNode;
      mytree->root_node = myNode;
    }
    else
    {
      mytree->curr_node = mytree->root_node;
      while (mytree->curr_node)
      {
        cpNode = mytree->curr_node;
        goleft = (*itemOrder)(cpNode->item, nodeitem);
        if (goleft) {
          myNode->next = cpNode;
          mytree->curr_node = cpNode->left;
        }
        else  {
          myNode->prev = cpNode;
          mytree->curr_node = cpNode->right;
        }
      }
      if (cpNode) {
        myNode->parent = cpNode;
      }

      if (goleft) {
        cpNode->left = myNode;
      }
      else {
        cpNode->right = myNode;  
      }
      if (myNode->prev) {
        myNode->prev->next = myNode;
      }
      else {
        mytree->first_node = myNode;
      }
      if (myNode->next) {
        myNode->next->prev = myNode;
      }
      else {
        mytree->last_node = myNode;
      }
      while (cpNode)
      {  
        _rotate_if_necessary(mytree, cpNode);
        cpNode = cpNode->parent;
      }
    }
    mytree->curr_node = myNode;
    mytree->size++;
    return 0;
  }
}