#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

#define N 600000
#define NIL -1

//array
int key[N];
int parent[N];
int leftc[N];
int rightc[N];
//root
int root=NIL;

//function insert
void insert(int z){
  int x,y;
  
  y=NIL;
  x=root;

  while(x!=NIL){
    y=x;
    if(key[z]<key[x]) x=leftc[x];
    else x=rightc[x];
  }  
  
  parent[z]=y;

  if(y==NIL) root=z;
    
  else if(key[z]<key[y]) leftc[y]=z;

  else rightc[y]=z;
  
  
}

//function search
int find(int now,int data){
  if(now==NIL ||data==key[now]) return now;
  
  if(data<key[now]) return find(leftc[now],data);
  else return find(rightc[now],data);
}


int treeminimum(int x){
  while(leftc[x]!=NIL){
    x=leftc[x];
  }
  return x;
}


int treesuccessor(int x){
  int y; 
  if(rightc[x]!=NIL) return treeminimum(rightc[x]);
  y=parent[x];
  while(y!=NIL &&x==rightc[x]){
    x=y;
    y=parent[y];
  }
  return y;
}


//function delete
void treedelete(int z){
  int x,y;
  if(leftc[z]==NIL ||rightc[z]==NIL) y=z;
  else y=treesuccessor(z);

  if(leftc[y]!=NIL) x=leftc[y];
  else x=rightc[y];

  if(x!=NIL) parent[x]=parent[y];
  if(parent[y]==NIL) root=x;
  else if(y==leftc[parent[y]]) leftc[parent[y]]=x;
  else rightc[parent[y]]=x;

  if(y!=z) key[z]=key[y];

}

//print
void inorderprint(int now){
  if(now!=NIL){
    inorderprint(leftc[now]);
    printf(" %d",key[now]);
    inorderprint(rightc[now]);
  }
}

void preorderprint(int now){
  if(now!=NIL){
    printf(" %d",key[now]);
    preorderprint(leftc[now]);
    preorderprint(rightc[now]);
  }
}



int main(){

  int n,i,j,data;
  int z=0;
  int del;
  char str[10];
  //initialize array
  for(i=0;i<N;i++){
    parent[i]=NIL;
    key[i]=NIL;
    rightc[i]=NIL;
    leftc[i]=NIL;
  }
  //load n
  scanf("%d",&n);
  //load commnad and key
  for(i=0;i<n;i++){
    scanf("%s",str);
    if(strcmp(str,"insert")==0) {
      scanf("%d",&data);
      key[z]=data;
      insert(z);
      z++;
    }
    else if(strcmp(str,"find")==0){
      scanf("%d",&data);
      if(find(root,data)!=NIL) printf("yes\n");
      else printf("no\n");
    }
    else if(strcmp(str,"delete")==0){
      scanf("%d",&data);
      del=find(root,data);
      treedelete(del);
    }
    else if(strcmp(str,"print")==0){
      inorderprint(root);
      cout <<endl;
      preorderprint(root);
      cout <<endl;
    }
  }

  return 0;
}
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *parent, *left, *right;
};

Node *NIL, *root;

void insert(int x) {
    Node *p = NIL;
    Node *u = root;
    Node *in = (Node *)malloc(sizeof(Node));
    in->key = x;
    in->left = NIL;
    in->right = NIL;

    while (u != NIL) {
        p = u;
        if (in->key < u->key) {
            u = u->left;
        } else {
            u = u->right;
        }
    }

    in->parent = p;
    if (p == NIL) {
        root = in;
    } else if (in->key < p->key) {
        p->left = in;
    } else {
        p->right = in;
    }
}

bool find(Node *u, int x) {
    while (u != NIL && u->key != x) {
        if (x < u->key) {
            u = u->left;
        } else {
            u = u->right;
        }
    }

    if (u == NIL) {
        return false;
    } else {
        return true;
    }
}

Node * findP(Node *u, int x) {
    while (u != NIL && u->key != x) {
        if (x < u->key) {
            u = u->left;
        } else {
            u = u->right;
        }
    }

    return u;
}

Node * getMinimum(Node *u) {
    while (u->left != NIL) {
        u = u->left;
    }

    return u;
}

Node * getSuccessor(Node *u) {
    if (u->right != NIL) {
        return getMinimum(u->right);
    }

    Node *d = u->parent;
    while (d != NIL && u == d->right) {
        u = d;
        d = d->parent;
    }

    return d;
}

void deleteNode(Node *u) {
    Node *d, *x;
    if (u->left == NIL || u->right == NIL) {
        d = u;
    } else {
        d = getSuccessor(u);
    }

    if (d->left != NIL) {
        x = d->left;
    } else {
        x = d->right;
    }

    if (x != NIL) {
        x->parent = d->parent;
    }

    if (d->parent == NIL) {
        root = x;
    } else if (d == d->parent->left) {
        d->parent->left = x;
    } else {
        d->parent->right = x;
    }

    if (d != u) {
        u->key = d->key;
    }
}

void printPre(Node *u) {
    if (u == NIL) {
        return;
    }

    printf(" %d", u->key);
    printPre(u->left);
    printPre(u->right);
}

void printIn(Node *u) {
    if (u == NIL) {
        return;
    }

    printIn(u->left);
    printf(" %d", u->key);
    printIn(u->right);
}

int main() {
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string com;
        cin >> com;
        if (com == "insert") {
            int x;
            scanf("%d", &x);
            insert(x);
        } else if (com == "find") {
            int x;
            scanf("%d", &x);
            if (find(root, x)) {
                cout << "yes" << endl;
            } else {
                cout << "no" << endl;
            }
        } else if (com == "delete") {
            int x;
            scanf("%d", &x);
            auto u = findP(root, x);
            deleteNode(u);
        } else {
            printIn(root);
            printf("\n");
            printPre(root);
            printf("\n");
        }
    }

    return 0;
}
