#include <stdio.h>

typedef char BOOLEAN;
#define TRUE 1
#define FALSE 0

typedef struct node *ref;
struct node
{
  long key,count;
  ref left,right;
  short bal;
};

ref root;
BOOLEAN dummyh;
long key;

search(x,p,h)
long x;
ref *p;
BOOLEAN *h;
{
ref p1,p2,pDeref;

pDeref=(*p);
if (!pDeref)
{ /*word is not in tree; insert it*/
  pDeref=(ref) malloc(sizeof (struct node));
  if (!pDeref) abort();
  *p=pDeref;
  *h=TRUE;
  pDeref->key=x;
  pDeref->count=1;
  pDeref->left=NULL;
  pDeref->right=NULL;
  pDeref->bal=0;
}
else if (x<pDeref->key)
{
   search(x,&pDeref->left,h);
   if (*h)     /*left branch has grown higher*/
     switch(pDeref->bal)
     {
     case 1:  pDeref->bal=0;
              *h=FALSE;
              break;
     case 0:  pDeref->bal=(-1);
              break;
     case -1: /*rebalance*/
              p1=pDeref->left;
              if (p1->bal==(-1))
              { /*single LL rotation*/
                pDeref->left=p1->right;
                p1->right=pDeref;
                pDeref->bal=0;
                pDeref=p1;
                *p=pDeref;
              }
              else
              { /*double LR rotation*/
                p2=p1->right;
                p1->right=p2->left;
                p2->left=p1;
                pDeref->left=p2->right;
                p2->right=pDeref;
                pDeref->bal=(p2->bal==(-1)) ? 1 : 0;
                p1->bal=(p2->bal==1) ? (-1) : 0;
                pDeref=p2;
                *p=pDeref;
              }
              pDeref->bal=0;
              *h=FALSE;
              break;
     }
}
else if (x>pDeref->key)
{
   search(x,&pDeref->right,h);
   if (*h)     /*right branch has grown higher*/
     switch(pDeref->bal)
     {
     case -1: pDeref->bal=0;
              *h=FALSE;
              break;
     case 0:  pDeref->bal=1;
              break;
     case 1:  /*rebalance*/
              p1=pDeref->right;
              if (p1->bal==1)
              { /*single RR rotation*/
                pDeref->right=p1->left;
                p1->left=pDeref;
                pDeref->bal=0;
                pDeref=p1;
                *p=pDeref;
              }
              else
              { /*double RL rotation*/
                p2=p1->left;
                p1->left=p2->right;
                p2->right=p1;
                pDeref->right=p2->left;
                p2->left=pDeref;
                pDeref->bal=(p2->bal==1) ? (-1) : 0;
                p1->bal=(p2->bal==(-1)) ? 1 : 0;
                pDeref=p2;
                *p=pDeref;
              }
              pDeref->bal=0;
              *h=FALSE;
              break;
     }
}
else
{
  pDeref->count++;
  *h=FALSE;
}
}  

printtree(pt,indent)
ref pt;
int indent;
{
short i;
if (pt)
{
  printtree(pt->right,indent+1);
  for (i=0;i<indent;i++)
    printf("   ");
  printf("%ld %ld %hd\n",pt->key,pt->count,pt->bal);
  printtree(pt->left,indent+1);
}
}

main()
{
root=NULL;
printf("enter key:");
while (scanf("%ld",&key)!=EOF)
{
  search(key,&root,&dummyh);
  printf("enter key:");
}
printf("\n");
printtree(root,0);
}