#include<stdio.h>
#include<stdlib.h>
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
 
Node root;
 
Node tree_minimum(Node x){
 
    while(x->left != NULL){
      x = x->left;
    }
    return x;
}
 
Node tree_search(Node u, int k){
 
    if(u->key > k){
        if(u->left==NIL){  /* もし左側になければ，keyはない */
            return NIL;
        }
        return tree_search(u->left, k);
    }
    /* 自分より大きい値ならば，右側 */
    if(u->key < k){
        if(u->right == NULL){
            return NULL;      /* もし右側になければ，keyはない */
        }
        return tree_search(u->right, k);
    }
 
    return u;
}

Node treeSuccessor(Node x){

   return 0;
}
int tree_position(Node z){
    int direction;
    if(z->parent->right == z){
          direction = 1;
      } else if(z->parent->left == z){
          direction = -1;
      } else {
          direction = 0;
      }
    return direction;
}
 
void tree_delete(Node z){
  Node left_max;
  int direction; //if z is left child: -1, right child: 1, other: 0
  direction = tree_position(z);
  if(z != NIL){
      if(z->left == NIL || z->right == NIL){
             /* 左か右，どちらかがNULLであった場合(両方NULLの場合も含む) */
	y = z;
          if(z->left != NIL){
              
	    x = y->right;
	  } else {
             x = y->right;
              }
              
      } else if(x != NIL) {
             
	x->parent = y->parent;
              if(direction == -1){
                  z->parent->left = z->left;
              }
              if(direction == 1){
                  z->parent->right = z->left;
              }
              if(direction == 0){
                  root = z->left;
              }
           }
             free(z);
         } else {
             /* 両者ともNULLでなかった場合 */
            left_max = tree_minimum(z);
 
             /* left_maxの値をz_keyに代入し，left_maxは左側の枝を入れる */
             z->key = left_max->key;
             if(direction==-1){
                 z->parent->left = left_max->left;
             } else {
                 z->parent->right = left_max->left;
             }
          free(left_max);
          free(z);
       }
    }
 
 
}
 
Node new_node(Node n, int k){
    Node z;
 
    z = malloc(sizeof(struct node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    z->parent = n;
    return z;
}
 
void insert(int k){
 
    Node y = NIL;
    Node x = root;
    while(x != NIL){
        y = x;
        if (z->key < x->key){
            x = x->left;
        }else {
            x = x->right;
        }
    }
    z->parent = y;

    if (y == NIL){
        root = z ; // if T is empty
    } else if (z->key < y->key){
        y->left = z;
    } else {
        y->right = z;
    }
}
 
void inorder(Node u){
    if(u != NIL){
        inorder(u->left);
        printf("%d", u->key);
        inorder(u->right);
    }
}
 
void preorder(Node u){
  printf("%d", u->key);
    if (u->left != NIL){
        preorder(u->left);
    }
 
    if (u->right != NIL){
        preorder(u->right);
    }
}
 
 
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = tree_search(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      tree_delete(tree_search(root, x));
    }
  }
 
  return 0;
}
http://www.os.cis.iwate-u.ac.jp/~shot8/pukiwiki/index.php?%A5%A2%A5%EB%A5%B4%A5%EA%A5%BA%A5%E0-%A3%B2%CA%AC%C3%B5%BA%F7%CC%DA