#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INFINITY 1000000000
#define NONE 0
#define LL 1
#define RR 2
#define LR 3
#define RL 4

typedef struct _node {
   int key;
   struct _node *L, *R;
} tnode;

typedef tnode *BST;

BST gentree ( int n )
{
   double x;
   tnode *p;
   int nl, nr;

   if (n == 0) return NULL;
   p = (tnode *)malloc(sizeof(tnode));
   p -> L = p -> R = NULL;
   if (n == 1) return p;
   x = (double)rand() / (double)RAND_MAX;
   if (x <= 0.25) nl = 0;
   else if (x <= 0.50) nl = n-1;
   else nl = rand() % n;
   nr = n - 1 - nl;
   if (nl) p -> L = gentree(nl);
   if (nr) p -> R = gentree(nr);
   return p;
}

int populatekeys ( BST T, int last )
{
   if (T == NULL) return last;
   last = populatekeys(T->L, last);
   last = T -> key = last + 1 + rand() % 10;
   last = populatekeys(T->R, last);
   return last;
}

void preorder ( BST T )
{
   if (T == NULL) return;
   printf(" %3d", T -> key);
   preorder(T->L);
   preorder(T->R);
}

void inorder ( BST T )
{
   if (T == NULL) return;
   inorder(T->L);
   printf(" %3d", T -> key);
   inorder(T->R);
}

int rndpreorder ( BST T, int n, int *K )
{
   int nl, nr, i, j, k, x;
   int *L, *R;

   if (T == NULL) return 0;
   K[0] = T -> key;
   L = (int *)malloc(n * sizeof(int)); nl = rndpreorder(T->L,n,L);
   R = (int *)malloc(n * sizeof(int)); nr = rndpreorder(T->R,n,R);
   i = j = 0; k = 1;
   while ((i < nl) || (j < nr)) {
      if (j == nr) x = 0; else if (i == nl) x = 1; else x = rand() % 2;
      K[k++] = (x == 0) ? L[i++] : R[j++];
   }
   free(L); free(R);
   return 1 + nl + nr;
}

void prnkeyinput ( BST T, int n )
{
   int *K, cnt, i;

   K = (int *)malloc(n * sizeof(int));
   cnt = rndpreorder(T,n,K);
   for (i=0; i<cnt; ++i) printf(" %3d", K[i]);
   printf("\n");
   free(K);
}

int height ( BST T )
{
   int lht, rht;

   if (T == NULL) return -1;
   lht = height(T->L);
   rht = height(T->R);
   return 1 + ((lht >= rht) ? lht : rht);
}

int levelsum ( BST T, int l, int sum )
{
   if (T == NULL) return sum;
   sum += l;
   sum = levelsum(T->L,l+1,sum);
   sum = levelsum(T->R,l+1,sum);
   return sum;
}

int nodecnt ( BST T )
{
   if (T == NULL) return 0;
   return 1 + nodecnt(T->L) + nodecnt(T->R);
}

void prntree ( BST T )
{
   printf("    Preorder : "); preorder(T); printf("\n");
   printf("    Inorder  : "); inorder(T); printf("\n");
   printf("    height of tree = %d\n", height(T));
   printf("    Average level = %lf\n", (double)levelsum(T,0,0)/(double)nodecnt(T));
}

void chainsearch ( BST T, int *ll, int *lr, int *rl, int *rr )
{
   BST C;

   if (T == NULL) return;
   if ((T->L == NULL) && (T->R == NULL)) return;
   if (T->L != NULL) {
      if (T->R == NULL) {
         C = T->L;
         if ((C->L != NULL) && (C->R == NULL)) ++(*ll);
         else if ((C->L == NULL) && (C->R != NULL)) ++(*lr);
      }
   }
   if (T->R != NULL) {
      if (T->L == NULL) {
         C = T->R;
         if ((C->L != NULL) && (C->R == NULL)) ++(*rl);
         else if ((C->L == NULL) && (C->R != NULL)) ++(*rr);
      }
   }
   chainsearch(T->L,ll,lr,rl,rr);
   chainsearch(T->R,ll,lr,rl,rr);
}

void cntchains ( BST T )
{
   int ll, lr, rl, rr;

   ll = lr = rl = rr = 0;
   chainsearch(T,&ll,&lr,&rl,&rr);
   printf("    LL: %d, LR: %d, RL: %d, RR: %d, Total: %d\n", ll,lr,rl,rr,ll+lr+rl+rr);
}

tnode *lrot ( tnode *u )
{
   tnode *v, *T2;

   v = u -> R;
   if (v == NULL) return u;
   T2 = v -> L;
   v -> L = u;
   u -> R = T2;
   return v;
}

tnode *rrot ( tnode *u )
{
   tnode *v, *T2;

   v = u -> L;
   if (v == NULL) return u;
   T2 = v -> R;
   v -> R = u;
   u -> L = T2;
   return v;
}

int nodetype ( tnode *u )
{
   tnode *v;

   if (u == NULL) return NONE;
   if ((u -> L == NULL) && (u -> R == NULL)) return NONE;
   if ((u -> L != NULL) && (u -> R != NULL)) return NONE;
   if (u -> L) {
      v = u -> L;
      if ((v -> L == NULL) && (v -> R == NULL)) return NONE;
      if ((v -> L != NULL) && (v -> R != NULL)) return NONE;
      return (v -> L) ? LL : LR;
   } else {
      v = u -> R;
      if ((v -> L == NULL) && (v -> R == NULL)) return NONE;
      if ((v -> L != NULL) && (v -> R != NULL)) return NONE;
      return (v -> L) ? RL : RR;
   }
}

void rm2chains ( tnode *T )
{
   int childtype;

   if (T == NULL) return;
   if (T->L != NULL) {
      childtype = nodetype(T->L);
      if (childtype == LL) T->L = rrot(T->L);
      else if (childtype == RR) T->L = lrot(T->L);
      else if (childtype == LR) { T->L->L = lrot(T->L->L); T->L = rrot(T->L); }
      else if (childtype == RL) { T->L->R = rrot(T->L->R); T->L = lrot(T->L); }
      rm2chains(T->L);
   }
   if (T->R != NULL) {
      childtype = nodetype(T->R);
      if (childtype == LL) T->R = rrot(T->R);
      else if (childtype == RR) T->R = lrot(T->R);
      else if (childtype == LR) { T->R->L = lrot(T->R->L); T->R = rrot(T->R); }
      else if (childtype == RL) { T->R->R = rrot(T->R->R); T->R = lrot(T->R); }
      rm2chains(T->R);
   }
}

int main ( int argc, char *argv[] )
{
   int n;
   BST T;
   tnode *D; /* Dummy node */

   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   printf("Enter n: %d\n", n);
   if (argc > 2) srand((unsigned int)atoi(argv[2]));
   else srand((unsigned int)time(NULL));

   T = gentree(n);
   populatekeys(T, 100+rand()%100);
   printf("Enter keys:"); prnkeyinput(T,n);

   printf("\n+++ Initial tree\n");
   prntree(T);

   printf("\n+++ Counts of 2-chains\n");
   cntchains(T);

   printf("\n+++ Removing 2-chains\n");
   D = (tnode *)malloc(sizeof(tnode));
   D -> key = INFINITY; D -> L = T; D -> R = NULL;
   rm2chains(D);
   T = D -> L;

   printf("\n+++ New tree\n");
   prntree(T);

   printf("\n+++ Counts of 2-chains\n");
   cntchains(T);

   exit(0);
}