/* bst.c - Don Yang (uguu.org)

   03/10/04
                                                                           */
/*@ -nullpass -nullret -nullstate -onlytrans -temptrans @*/
/*@ -branchstate -compdestroy @*/

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


typedef struct _node
{
   int key, data;
   struct _node *left, *right;
} Node;

static void BSTDelete(Node **root, int key);
static void BSTDeleteTree(Node *root);
static void BSTDump(Node *root);
static int BSTFind(Node *root, int key);
static int BSTInsert(Node **root, int key, int data);

int main(void)
{
   Node *root;
   int op, key, value;

   root = NULL;
   while( scanf("%d %d %d", &op, &key, &value) == 3 )
   {
      if( op == 0 )
         break;
      switch( op )
      {
         case 1:
            printf("insert %d, %d\n", key, value);
            (void)BSTInsert(&root, key, value);
            break;
         case 2:
            printf("delete %d\n", key);
            (void)BSTDelete(&root, key);
            break;
         case 3:
            (void)puts("dump");
            BSTDump(root);
            break;
         default:
            printf("find %d -> %d\n", key, BSTFind(root, key));
            break;
      }
   }

   BSTDeleteTree(root);
   return 0;
}


static void BSTDelete(Node **root, int key)
{
   Node *d, *l, *r, *p;

   while( *root != NULL )
   {
      if( (*root)->key == key )
      {
         d = *root;
         if( d->left == NULL )
         {
            *root = d->right;
         }
         else if( d->right == NULL )
         {
            *root = d->left;
         }
         else
         {
            p = l = d->left;
            if( (r = l->right) == NULL )
            {
               l->right = d->right;
               *root = l;
            }
            else
            {
               while( r->right != NULL )
               {
                  assert(p->right == r);
                  p = r;
                  r = r->right;
               }
               p->right = r->left;
               r->left = l;
               r->right = d->right;
               *root = r;
            }
         }
         free(d);
      }
      else
      {
         root = ((*root)->key > key) ? &((*root)->left) : &((*root)->right);
      }
   }
}

static void BSTDeleteTree(Node *root)
{
   Node *x;

   while( root != NULL )
   {
      BSTDeleteTree(root->left);
      x = root->right;
      free(root);
      root = x;
   }
}

static void BSTDump(Node *root)
{
   while( root != NULL )
   {
      BSTDump(root->left);
      printf("\t%d -> %d\n", root->key, root->data);
      root = root->right;
   }
}

static int BSTFind(Node *root, int key)
{
   while( root != NULL )
   {
      if( root->key == key )
         return root->data;
      root = (root->key > key) ? root->left : root->right;
   }
   return -1;
}

static int BSTInsert(Node **root, int key, int data)
{
   Node *node;

   while( *root != NULL )
   {
      if( (*root)->key == key )
      {
         (*root)->data = data;
         return 0;
      }
      root = ((*root)->key > key) ? &((*root)->left) : &((*root)->right);
   }
   if( (*root = node = (Node*)malloc(sizeof(Node))) == NULL )
      return 1;
   node->key = key;
   node->data = data;
   node->left = node->right = NULL;
   return 0;
}