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

#define UNDEF -1

typedef struct _tnode {
   int key1, key2;
   struct _tnode *L, *M, *R;
} tnode;
typedef tnode *tree;

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

   if (T == NULL) {                                 /* Create a one-node tree */
      p = (tnode *)malloc(sizeof(tnode));
      p -> key1 = x; p -> key2 = UNDEF;
      p -> L = p -> M = p -> R = NULL;
      return p;
   }

   p = T;
   while (1) {                                                /* Search for x */
      if ((p -> key1 == x) || (p -> key2 == x))     /* x already present in T */
         return T;

      if (p -> key2 == UNDEF) {   /* Reached a leaf node storing only one key */
         if (x < p -> key1) {    /* Compare x with the key stored in the leaf */
            p -> key2 = p -> key1;      /* The old key becomes the second key */
            p -> key1 = x;                         /* x becomes the first key */
         } else {            /* The old key continues to remain the first key */
            p -> key2 = x;                        /* x becomes the second key */
         }
         return T;
      }

      /* Continue search with three-way branching */
      if (x < p -> key1) q = p -> L;
      else if (x < p -> key2) q = p -> M;
      else q = p -> R;

      if (q == NULL) {     /* Search fails when a NULL pointer is encountered */
         q = (tnode *)malloc(sizeof(tnode));  /* Create a leaf storing x only */
         q -> key1 = x; q -> key2 = UNDEF;
         q -> L = q -> M = q -> R = NULL;

         if (x < p -> key1) p -> L = q; /* Connect the leaf by an appropriate */
         else if (x < p -> key2) p -> M = q;         /* pointer in the parent */
         else p -> R = q;
         return T;
      }

      p = q;                               /* Proceed one level down the tree */
   }
}

tree delete ( tree T, int x )
{
   tnode *p, *q, *P, *Q;
   int y, prevcase = 5;

   /* Search for x in the tree */
   q = T; p = NULL;
   while (q != NULL) {            /* Three-way branching at each visited node */
      if ((x == q -> key1) || (x == q -> key2)) break;
      p = q;
      if (x < q -> key1) q = q -> L;
      else if (x < q -> key2) q = q -> M;
      else q = q -> R;
   }

   /* Case 1: x not found */
   if (q == NULL) return T;

   while (1) {
      /* Case 2: Deletion at a leaf node */
      if ((q -> L == NULL) && (q -> M == NULL) && (q -> R == NULL)) {
         /* Case 2(a): To delete key2 */
         if (x == q -> key2) {
            q -> key2 = UNDEF;              /* Make key2 undefined and return */
            return T;
         }

         /* Case 2(b): To delete key1 */
         if (q -> key2 != UNDEF) {                         /* key2 is defined */
            q -> key1 = q -> key2;                      /* Store key2 in key1 */
            q -> key2 = UNDEF;              /* Make key2 undefined and return */
            return T;
         }

         /* If key2 is not defined, delete the node altogether */
         if (p == NULL) { free(q); return NULL; }             /* root deleted */

         if (prevcase == 4) {
            /* In case 4 (see below), a smaller value is copied at an upper
               level. So three-way branching requires <= instead of <. */
            if (x <= p -> key1) p -> L = NULL;
            else if (x <= p -> key2) p -> M = NULL;
            else p -> R = NULL;
         } else {
            /* In case 5 (see below), a larger value is copied at an upper
               level. So three-way branching continues to use <. */
            if (x < p -> key1) p -> L = NULL;
            else if (x < p -> key2) p -> M = NULL;
            else p -> R = NULL;
         }
         free(q);                         /* Free the leaf node being deleted */
         return T;
      }

      /* Case 3: Neither the immediate predecessor nor the immediate successor
         of x lies below q. This is an interesting case. First, q is not a
         leaf node here, but has exactly one non-empty subtree. We cannot
         copy a value (immediate predecessor or successor from below the
         tree, but we can delete the entire node altogether by letting an
         appropriate pointer of the parent p point to the only non-empty
         subtree of q. But being a non-leaf node, q contains two key values,
         of which only one is deleted. The other key too is deleted if we
         eliminate the node completely. So we need to re-insert this other
         key back to the tree. */
      if (((x == q -> key1) && (q -> L == NULL) && (q -> M == NULL)) ||
         ((x == q -> key2) && (q -> M == NULL) && (q -> R == NULL))) {

         /* Locate the non-null pointer of q */
         Q = (x == q -> key1) ? q -> R : q -> L;

         /* Remove the entire node q from the tree */
         if (p == NULL) T = Q;                             /* q has no parent */
         else if (prevcase == 4) {                          /* q has a parent */
            if (x <= p -> key1) p -> L = Q;
            else if (x <= p -> key2) p -> M = Q;
            else p -> R = Q;
         } else {                                  /* here too q has a parent */
            if (x < p -> key1) p -> L = Q;
            else if (x < p -> key2) p -> M = Q;
            else p -> R = Q;
         }

         /* Remember the key that needs to be reinserted */
         y = (x == q -> key1) ? q -> key2 : q -> key1;

         free(q);                            /* Free the space allocated to q */

         return insert(T,y);         /* Re-insert y in T and then we are done */
      }

      /* Case 4: The immediate predecessor y of x exists below x. In this case,
         we copy y to x, and delete y in the next iteration. */
      if (((x == q -> key1) && (q -> L != NULL)) ||
         ((x == q -> key2) && (q -> M != NULL))) {

         /* Search for y. Q will point to y, and P will be the parent of Q. */
         P = q;
         Q = (x == q -> key1) ? q -> L : q -> M;
         while (Q -> R != NULL) {
            P = Q; Q = Q -> R;
         }

         /* If y is found in a leaf node with only one key */
         y = (Q -> key2 == UNDEF) ? Q -> key1 : Q -> key2;

         /* Replace x by y */
         if (x == q -> key1) q -> key1 = y; else q -> key2 = y;

         /* Prepare for deleting y in the next iteration */
         q = Q; p = P; x = y; prevcase = 4; continue;
      }

      /* Case 5: The immediate suvvessor y of x exists below x. In this case,
         we copy y to x, and delete y in the next iteration. */
      if (((x == q -> key1) && (q -> M != NULL)) ||
         ((x == q -> key2) && (q -> R != NULL))) {

          /* Search for y. Q will point to y, and P will be the parent of Q. */
         P = q;
         Q = (x == q -> key1) ? q -> M : q -> R;
         while (Q -> L != NULL) {
            P = Q; Q = Q -> L;
         }
         y = Q -> key1;

         /* Replace x by y */
         if (x == q -> key1) q -> key1 = y; else q -> key2 = y;

         /* Prepare for deleting y in the next iteration */
         q = Q; p = P; x = y; prevcase = 5;
      }
   }
}

void sortedPrint ( tree T, int *cnt )
{
   if (T == NULL) return;                                 /* Nothing to print */

   sortedPrint(T -> L,cnt);                 /* Print values smaller than key1 */
   printf("%4d", T -> key1);                                    /* Print key1 */
   if (++(*cnt) % 20 == 0) printf("\n");
   sortedPrint(T -> M,cnt);             /* Print values between key1 and key2 */
   if (T -> key2 != UNDEF) {                       /* Print key2 (if defined) */
      printf("%4d", T -> key2);
      if (++(*cnt) % 20 == 0) printf("\n");
   }
   sortedPrint(T -> R,cnt);                  /* Print values larger than key2 */
}

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

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

   for (i=0; i<n; ++i) {
      x = 1 + rand() % 999;
      T = insert(T,x);
      printf("+++ Insert %d done\n", x);
      cnt = 0; sortedPrint(T,&cnt);
      if (cnt % 20) printf("\n");
   }

   printf("\n\n");

   while (T != NULL) {
      if ((rand() % 2) && (T -> key2 != UNDEF)) x = T -> key2;
      else x = T -> key1;
      T = delete(T,x);
      printf("+++ Delete %d done\n", x);
      cnt = 0; sortedPrint(T,&cnt);
      if (cnt % 20) printf("\n");
   }

   exit(0);
}