[C library] AVL (auto-balanced Binary Search Tree): Insertion + Deletion + Traversal Print

avl.h

/** AVL (auto-balanced BST)
    --------
    Edit: keyType
    --------
    Rewrite: MAX function, Traversal Print
**/
#include<stdlib.h>

// Edit // typedef ... keyType;
// An AVL tree node //
typedef struct node
{
  keyType key;
  struct node *left, *right;
  int height;
} *treeType;

// A utility function to get maximum of two keyType
// Rewrite ///
/***
keyType MAX(keyType a, keyType b)
{
    return (a > b)? a : b;
}
**/

// A utility function to get height of the tree
int trheight(treeType t)
{
    if (t == NULL)
        return 0;
    return t->height;
}
 
// Helper function that allocate a new node
// with  given value;
// NULL left and right pointers;
treeType nodenew(keyType value)
{
  treeType new = (struct node*)
    malloc(sizeof(struct node));
  new->key = value;
  new->left = NULL;
  new->right = NULL;
  new->height = 1;
  return new;
}

// A utility function to right rotate subtree root
// given:
//     y
//    / \
//   x  T3
//  / \
// T1 T2
treeType rrotate(treeType y)
{
  treeType x = y->left;
  treeType T2 = x->right;

  // perform rotation
  treeType tem = T2; // store T2
  x->right = y; // we lose T2 here
  y->left = tem;

  // upgrade heights
  y->height = MAX(trheight(y->left),
		  trheight(y->right)) + 1;
  x->height = MAX(trheight(x->left),
		  trheight(x->right)) + 1;

  // return new root
  return x;
}

// A utility function to left rotate subtree rooted with x
// given:
//     x
//    / \
//   T1  y
//      / \
//    T2  T3
treeType lrotate(treeType x)
{
    treeType y = x->right;
    treeType T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    //  Update heights
    x->height = MAX(trheight(x->left), trheight(x->right))+1;
    y->height = MAX(trheight(y->left), trheight(y->right))+1;
 
    // Return new root
    return y;
}
 
// Get Balance factor of node N
int getbal(treeType N)
{
    if (N == NULL)
        return 0;
    return trheight(N->left) - trheight(N->right);
}

treeType nodeins(treeType t, keyType key)
{
  /* 1. Perform normal BST insertion */
  if (t == NULL)
    {
      return nodenew(key);
    }

  if (key < t->key)
    {
      t->left = nodeins(t->left, key);
    }
  else
    {
      t->right = nodeins(t->right, key);
    }
  
  /* 2. Update height of this ancestor node */
  t->height = MAX(trheight(t->left), trheight(t->right)) + 1;

  /* 3. Get the balance factor of this ancestor
     node to check whether node became unbalaced */
  int bal = getbal(t);
  
  // If this node becomes unbalanced, then there are 4 cases
 
  // if this node unbalanced -> there ar 4 cases

  // left left Case
  if (bal > 1 && key < t->left->key)
    {
      return rrotate(t);
    }
  
  // right right Case
  if (bal < -1 && key > t->right->key)
    {
      return lrotate(t);
    }

    // Left Right Case
    if (bal > 1 && key > t->left->key)
    {
        t->left =  lrotate(t->left);
        return rrotate(t);
    }
 
    // Right Left Case
    if (bal < -1 && key < t->right->key)
    {
        t->right = rrotate(t->right);
        return lrotate(t);
    }
 
    /* return the (unchanged) node pointer */
    return t;
}

///////// Delete ////////////////
/* Given a non-empty bst, return the node 
// with minimum key value in that tree (left-most)
// Note: entire tree does not need to be searched */
treeType minnode(treeType t)
{
  treeType cur = t;

  /* loop down to find the leftmost (min) leaf */
  while (cur->left != NULL)
    {
      cur = cur->left;
    }

  return cur;
}

treeType nodedel(treeType root, keyType value)
{
  /* STEP 1: PERFORM STANDARD BST DELETE */
  if (root == NULL)
    return root;

  // If the key to be deleted < root's key
  // then it lies in left sub-tree
  if (value < root->key)
    {
      root->left = nodedel(root->left, value);
    }

  // If the key to be deleted > root's key
  // then it lies in right sub-tree
  else if (value > root->key)
    {
      root->right = nodedel(root->right, value);
    }

  // If key is same as root's key
  // then this is the node need to be deleted
  else
    {
      // node with only one child or no child
      if (root->left == NULL || root->right == NULL)
	{
	  treeType tem = root->left ? root->left : root->right;

	  if (tem == NULL) // no child case
	    {
	      tem = root;
	      root = NULL;
	    }
	  else // one child case
	    {
	      // copy content of non-empty child
	      root = tem;
	    }
	}

      // node with two children
      else
	{
	  // get the inorder successor
	  // (smallest in the right subtree)
	  treeType tem = minnode(root->right);

	  // copy the inorder succesor's data
	  // to this node
	  // and delete it
	  root->key = tem->key;
	  tem = NULL;
	}
    }

  /* STEP 2: UPDATE HEIGHT OF CURRENT NODE */
  root->height = MAX(trheight(root->left), trheight(root->right)) + 1;

  /* STEP 3: CHECK IF THIS NODE BALANCED? */
  int bal = getbal(root);

  // If this node unbalanced, then there 4 cases

  // left left
  if (bal > 1 && getbal(root->left) >= 0)
    {
      return rrotate(root);
    }

  // right right
  if (bal < -1 && getbal(root->left) < 0)
    {
      return lrotate(root);
    }

  // left right
  if (bal > 1 && getbal(root->left) < 0)
    {
      root->left = lrotate(root->left);
      return rrotate(root);
    }

  // right left
  if (bal < -1 && getbal(root->left) >= 0)
    {
      root->right = rrotate(root->right);
      return lrotate(root);
    }

  return root;
}

////// Print functions
/****
// Inorder Print: L->M->R (Alphabetical, Increasing)
 void inorder(treeType root)
 {
   if (root != NULL)
     {
       inorder(root->left);
       // Rewrite // printf("...", root->key);
       inorder(root->right);
     }
 }

 // Postorder Print: L->R->M 
 void postorder(treeType root)
 {
   if (root != NULL)
     {
       postorder(root->left);
       postorder(root->right);
       // Rewrite // printf("...", root->key);
     }
 }

 // Preorder Print: M->L->R
void preorder(treeType root)
{
    if (root != NULL)
    {
      // Rewrite //  printf("%d ", root->key);
      preorder(root->left);
      preorder(root->right);
    }
}
****/