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

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

/* Inorder traversal. Three additional integers are passed.
   lastprn : The last integer printed.
   occno   : How many times the last integer was printed so far.
   totalno : The total number of integers prints in the current line.
*/
int inorder ( BST T, int lastprn, int occno, int totalno )
{
   char str[11];

   if (T == NULL) return totalno; /* Nothing to do */

   /* Handle the left subtree */
   totalno = inorder(T->L,lastprn,occno,totalno);

   /* Print the value at this node */
   if (T -> key == lastprn) { ++occno; }
   else { occno = 1; lastprn = T -> key; }
   sprintf(str, "%d (%d)", T -> key, occno);
   printf("%9s ", str);
   ++totalno; if (totalno % 8 == 0) printf("\n");

   /* Handle the right subtree */
   totalno = inorder(T->R,lastprn,occno,totalno);

   return totalno;
}

BST insert ( BST T, int x )
{
   tnode *p, *q;

   p = NULL; q = T;
   while (q != NULL) { /* Keep on moving down the tree until the correct
                          insertion location is found. Ignore duplicate
                          values already present in the tree. */
      p = q;
      q = (x < q -> key) ? q -> L : q -> R;
   }

   /* Create the new node and adjust the pointers */
   q = (tnode *)malloc(sizeof(tnode));
   q -> key = x; q -> L = q -> R = NULL;
   if (p == NULL) return q;
   if (x < p -> key) p -> L = q; else p -> R = q;
   return T;
}

BST genTree ( int n, int max )
{
   int i;
   BST T = NULL;

   for (i=0; i<n; ++i) T = insert(T, 1 + rand() % max);
   return T;
}

BST delete ( BST T, int x )
{
   tnode *p, *q, *p1, *q1;

   /* First try to locate one occurrence of x */
   q = T; p = NULL;
   while (q != NULL) {
      if (x < q -> key) { p = q; q = q -> L; }
      else if (x == q -> key) break;   /* The topmost occurrence of x located */
      else { p = q; q = q -> R; }
   }

   /* No occurrence of x found */
   if (q == NULL) return T;

   /* At least one occurrence of x is found */

   /* First delete all the other occurrences by a single downward loop */
   p1 = q; q1 = q -> R;                /* Explore only the right subtree of q */
   while (q1 != NULL) {
      if (x == q1 -> key) {               /* Another occurrence of x is found */
                                       /* The left subtree of q1 must be NULL */
         if (x == p1 -> key) {                     /* Parent has the same key */
            p1 -> R = q1 -> R;
            free(q1);
            q1 = p1 -> R;
         } else {                                  /* Parent has a larger key */
            p1 -> L = q1 -> R;
            free(q1);
            q1 = p1 -> L;
         }
      } else {                                 /* x < q1 -> key, so move left */
         p1 = q1;
         q1 = q1 -> L;
      }
   }

   /* Now delete the first occurrence of x currently pointed to by q. */
   /* The parent is pointed to by p. It is NULL, if q is the root. */

   if (q -> L == NULL) {
      if (p == NULL) T = q -> R;                           /* Root is deleted */
      else if (x < p -> key) p -> L = q -> R;
      else p -> R = q -> R;
   } else if (q -> R == NULL) {
      if (p == NULL) T = q -> L;                           /* Root is deleted */
      else if (x < p -> key) p -> L = q -> L;
      else p -> R = q -> L;
   } else {                                       /* Find immediate successor */
      q1 = q;
      p = q; q = q -> R;
      while (q -> L != NULL) {
         p = q;
         q = q -> L;
      }
      q1 -> key = q -> key;                  /* Swap with immediate successor */
      if (p == q1) p -> R = q -> R;         /* Delete the immediate successor */
      else p -> L = q -> R;
   }
   free(q);
   return T;
}

int search ( BST T, int x )
{
   int nocc;
   tnode *q;

   q = T; nocc = 0;
   while (q != NULL) {
      if (x < q -> key) q = q -> L;                     /* Go to left subtree */
      else {
         if (x == q -> key) ++nocc;              /* Record another occurrence */
         q = q -> R;                   /* Don't quit, go to the right subtree */
      }
   }
   return nocc;
}

void freeBST ( BST T )
{
   if (T == NULL) return;
   freeBST(T -> L);
   freeBST(T -> R);
   free(T);
}

int main ( int argc, char *argv[] )
{
   int n, max, x, i;
   BST T = NULL;

   srand((unsigned int)time(NULL));
   if (argc >= 3) { n = atoi(argv[1]); max = atoi(argv[2]); }
   else scanf("%d%d", &n, &max);

   /* Insert with repetitions */
   printf("\n+++ Inserting %d random integers between 1 and %d\n", n, max);
   T = genTree(n,max);
   if (inorder(T,-1,0,0) % 8) printf("\n");

   /* Ten random searches */
   printf("\n");
   for (i=0; i<10; ++i) {
      x = 1 + rand() % max;
      printf("+++ Search (%3d) = %2d\n", x, search(T,x));
   }

   /* Five random deletions */
   printf("\n");
   for (i=0; i<5; ++i) {
      x = 1 + rand() % max;
      printf("+++ Delete (%3d):\n", x);
      T = delete(T,x);
      if (inorder(T,-1,0,0) % 8) printf("\n");
   }

   printf("\nCleaning up...\n\n");
   freeBST(T);

   exit(0);
}