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

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

struct Node *root, *NIL;

struct Node * treeMinimum(struct Node *x){
    while(x->left != NIL) {
        x = x->left;
    }
    return x;
}

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

struct Node * treeSuccessor(struct Node *x){
    if(x->right != NIL) return treeMinimum(x->right);
    struct Node *y = x->parent;
    while(y != NIL && x == y->right){
        x = y;
        y = y->parent;
    }

    return y;
}

void treeDelete(struct Node *z){
    struct Node *y;
    struct Node *x;

    if(z->left != NIL || z->right != NIL) y = z;
    else y = treeSuccessor(z); //どこに継ぎ足すか
    
    if(y->left != NIL){
        x = y->left;
    } else{
        x = y->right;
    }

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

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

    if(y != z){
        z->key = y->key;
    }

    free(y);
}



void inorder(struct Node *u){
    if(u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(struct Node *u){
    if(u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main(){
    int n, i, x;
    char com[10];
    scanf("%d", &n);

    for(i = 0; i < n; i++){
        scanf("%s", com);
        if(com[0] == 'i'){
            scanf("%d", &x);
            insert(x);
        } else if(com[0] == 'f'){
            scanf("%d", &x);
            struct Node * t = find(root, x);
            if(t != NIL) printf("yes\n");
            else printf("no\n");
        } else if(com[0] == 'd'){
            scanf("%d", &x);
            treeDelete(find(root, x));
        } else{
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}


