// 二分探索木の削除
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

#define MAX_N 30
//const int NIL = -1;

typedef struct node
{
    // 節点の値
    int key;
    // 節点の親
    struct node *parent;
    // 節点の左の子
    struct node *left;
    // 節点の右の子
    struct node *right;
}Node;

// グローバル変数の定義
Node *p_Tree;

void preorderTreeWalk(Node *Tree);
void inorderTreeWalk(Node *Tree);
void postorderTreeWalk(Node *Tree);

void insert(int num);

Node* treeMinimum(Node *x);
Node* find(Node *tree, int num);
Node* treeSuccessor(Node *x);
void treeDelete(Node *z);

int main(void)
{

    int n, num;
    char str[10];

    cin >> n;

    for(int i = 0; i < n; i++)
    {
    	// 命令を取得
        scanf("%s", str);

        if( str[0] == 'i' )
        {
        	// --- 挿入の命令の時 ---

        	scanf("%d", &num);

            insert(num);
        }
        else if( str[0] == 'f' )
        {
            // --- 検索の命令の時 ---

        	scanf("%d", &num);

            Node *ret = find(p_Tree, num);
            if( ret != NULL )
            {
                printf("yes\n");
            }
            else
            {
                printf("no\n");
            }
        }
        else if( str[0] == 'd' )
        {
            // --- 削除の命令の時 ---

        	scanf("%d", &num);
            treeDelete(find(p_Tree, num));
        }
        else
        {
        	// --- 表示の命令 ---

            inorderTreeWalk(p_Tree);
            printf("\n");
            preorderTreeWalk(p_Tree);
            printf("\n");
        }
    }

    return 0;
}

// ----------▼▼▼▼▼ 2分探索木の操作関数　▼▼▼▼▼----------

// 2分探索木の中で, 最小値を求める関数
Node* treeMinimum(Node *x)
{
    while( x->left != NULL )
    {
        x = x->left;
    }

    return x;
}

// 二分探索木の検索関数
Node* find(Node *tree, int num)
{

    while( tree != NULL )
    {
        if( num < tree->key )
        {
            // 左の子を探索
            tree = tree->left;
        }
        else if( num > tree->key )
        {
            // 右の子を探索
            tree = tree->right;
        }
        else
        {
            // 値が見つかったので, 処理終了
            break;
        }
    }

    return tree;
}

// 2分探索木の中の次節点を検索する関数
Node* treeSuccessor(Node *x)
{
    if( x->right != NULL )
    {
        // 削除する節点の右側に子が存在する時
        return treeMinimum(x->right);
    }

    Node *y = x->parent;

    while( y != NULL && x == y->right )
    {
        x = y;
        y = y->parent;
    }

    return y;
}

// 2分探索木の削除関数
void treeDelete(Node *z)
{
    // 削除する対象
    Node *y;
    // yの子
    Node *x;

    // 削除する節点を決める
    if( z->left == NULL || z->right == NULL )
    {
        // 削除する節点が子を持たない or 子を1つ持つ時
        y = z;
    }
    else
    {
        y = treeSuccessor(z);
    }

    // yの子 x を決める
    if( y->left != NULL )
    {
        x = y->left;
    }
    else
    {
        x = y->right;
    }

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

    if( y->parent == NULL )
    {
        p_Tree = x;
    }
    else
    {
        if( y == y->parent->left )
        {
            // 削除する節点が親の左の子の時
            y->parent->left = x;
        }
        else
        {
            // 削除する節点が親の右の子の時
            y->parent->right = x;
        }
    }

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

    delete y;
}

// 二分探索木の挿入関数
void insert(int num)
{
    Node *tree, *parent;

    // 追加する要素の親
    parent = NULL;
    // 木の根 ( 先頭アドレス )
    tree = p_Tree;

    Node *newNode = new Node;

    newNode->key = num;
    newNode->parent = NULL;
    newNode->left = NULL;
    newNode->right = NULL;

    while( tree != NULL )
    {
        // 親の候補の取得
    	parent = tree;

        if( newNode->key < tree->key )
        {
            // 左の子へ移動
        	tree = tree->left;
        }
        else
        {
            // 右の子へ移動
        	tree = tree->right;
        }
    }

    // 追加する要素の親を設定
    newNode->parent = parent;

    if( parent == NULL )
    {
        // 木が空の時
    	newNode->parent = NULL;
        // 木が空のなので, 実体を入れる
        p_Tree = newNode;

    }
    else if( newNode->key < parent->key )
    {
        // 左の子にする
    	parent->left = newNode;
    }
    else
    {
        // 右の子にする
    	parent->right = newNode;
    }

    return;
}

// ----------▲▲▲▲▲ 2分探索木の操作関数　▲▲▲▲▲----------

// ----------▼▼▼▼▼ 巡回関連の関数　▼▼▼▼▼----------

// 先行順巡回
// 根節点、左部分木、右部分木の順で節点を巡回
void preorderTreeWalk(Node *Tree)
{

    if( Tree == NULL )
    {
    	return;
    }

    printf(" %d", Tree->key);
    preorderTreeWalk(Tree->left);
    preorderTreeWalk(Tree->right);

    return;
}

int pre_right = 0;

// 中間順巡回
// 左部分木、根節点、右部分木の順で節点を巡回
void inorderTreeWalk(Node *Tree)
{

    if( Tree == NULL )
    {
    	return;
    }

    inorderTreeWalk(Tree->left);
    printf(" %d", Tree->key);
    inorderTreeWalk(Tree->right);

    return;
}

// 後行順巡回
// 左部分木、右部分木、根節点の順で節点を巡回
void postorderTreeWalk(Node *Tree)
{

    if( Tree == NULL )
    {
    	return;
    }

    postorderTreeWalk(Tree->left);
    postorderTreeWalk(Tree->right);
    printf(" %d", Tree->key);

    return;
}

// ----------▲▲▲▲▲ 巡回関連の関数　▲▲▲▲▲----------



Measured memory_bytes: 21872