/*
二つの子がいる節点をdeleteするときは、
「左の部分木の中で最大のkeyをもつ節点（左の部分木の中で一番右下）」　もしくは、
「右の部分木の中で最少のkeyをもつ節点（右の部分木の中で一番左下）」
の節点が、消した位置に来るようにすればよい。

今回は小難しい節点の入れ替えの処理をしなくても
キーだけ変えて、左下or右下　の節点を消しておけばよい。

*/


/*
キーの重複がないそうなので、
配列の添え字をそのままキーにするのが最速っぽい。
（vectorは添え字の指定ができないからダメ、キーがｚの時　left[z]、right[z]みたいに使えるのが最速 ）

でも重複に備えるorキーがデカいなら、上のやり方は使えない。
（代わりにハッシュにしようかとも思ったが、それだと混ざって複雑なので却下）
*/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>


using namespace std;

class Binary_Search_Tree
{

public:
	//int id;  //idはなくす。　全部添え字で管理　そうしないと配列内でidに対してfindしないといけなくなり、実行時間増えるので
	//bstなら、idでなくkeyて名前にしとこうか...面倒なのでやっぱりいい。

	int key;
	Binary_Search_Tree *parent; 
	//int degree;
	Binary_Search_Tree *left;
	Binary_Search_Tree *right; 

	Binary_Search_Tree()
    {
        parent = left = right = NULL;
    }

};

//最後に同じところでキーの大小比較を二回やるので無駄なように思えるが、多分これが一番すっきりしていて早いのだろう。
void TREE_INSERT(Binary_Search_Tree *&T, Binary_Search_Tree *z){
	Binary_Search_Tree *y, *x;

	y=NULL;
	x=T;
	while(x!=NULL){
		y=x;
		if(z->key < x->key) x=x->left;
		else x=x->right;
	}
	z->parent = y;
	if(y==NULL) T=z; //if T is empty
	else{ 
		if(z->key < y->key) y->left=z;
		else y->right=z;
	}
}

Binary_Search_Tree *TREE_FIND(Binary_Search_Tree *node, int k){
	Binary_Search_Tree *hoge=node, *ans=NULL;
	
	while(hoge != NULL){
		if(hoge->key==k){
			ans=hoge;
			break;
		}
		if(hoge->key < k) hoge=hoge->right;
		else hoge=hoge->left;
	}
	return ans;

}


/*節点xを根とする部分木の中で最小のキーを持つ節点を返す*/
Binary_Search_Tree *TREE_MINIMUM(Binary_Search_Tree *x){
	while (x->left != NULL) x=x->left;
	return x;
}


/*２分探索木の節点xに次節点がある場合はその次節点を返す*/
/*ただし、木の中でxが最大のキーを持つ場合はNILを返す*/
Binary_Search_Tree *TREE_SUCCESSOR(Binary_Search_Tree *x){
	Binary_Search_Tree *y;

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


void TREE_DELETE(Binary_Search_Tree *&T, Binary_Search_Tree *z){
	Binary_Search_Tree *x, *y;

	/* 削除する節点yを決定する */
	if( z->left == NULL || z->right == NULL ){
		y=z; /* zが子を最大１つ持つ場合は入力節点のz */
	}
	else y = TREE_SUCCESSOR(z); /* z が子を2つ持つ場合はzの次節点 */

	/* xをyのNILではない子またはyが子を持たない場合はNILに設定 */
	if(y->left != NULL) x=y->left;
	else x=y->right;

	/*yの親とxのポインタを変更しyを削除する*/
	/*xがNILまたはyが根のときの境界条件を処理*/
	if(x!=NULL) x->parent = y->parent;  /*zが子を１つ持つ場合*/
	if(y->parent==NULL) T=x;
	else if(y == y->parent->left) y->parent->left = x;
	else y->parent->right = x;

	/* zの次節点が削除されたときにyの内容をzに移動する */
	if(y!=z) z->key = y->key;
}


void Preorder(Binary_Search_Tree *node){

	cout << " " << node->key;
	if(node->left!=NULL) Preorder(node->left);
	if(node->right!=NULL) Preorder(node->right);
}

void Inorder(Binary_Search_Tree *node){

	if(node->left!=NULL) Inorder(node->left);
	cout << " " << node->key;
	if(node->right!=NULL) Inorder(node->right);
}

void Postorder(Binary_Search_Tree *node){

	if(node->left!=NULL) Postorder(node->left);
	if(node->right!=NULL) Postorder(node->right);
	cout << " " << node->key;
}


int main() {
	int i,j;
	int n,k;
	string s_buf;
	Binary_Search_Tree *bst=NULL; //in root address 

	//input
	// 標準入力をファイルに変更////////////////////////////////////////////////////////
    //FILE* fp_in = freopen("\\\\k1300\\k1300\\s1350010\\.windows\\Desktop\\input_data.txt", "r", stdin);
	/////////////////////////////////////////////////////////////////////////////////////
	cin >> n;
	for(i=0; i<n; i++){
		Binary_Search_Tree *buf;
		buf = new Binary_Search_Tree;

		cin >> s_buf;
		if(s_buf=="insert"){
			cin >> buf->key;
			TREE_INSERT(bst, buf);
		}
		else if(s_buf=="find"){
			cin >> k;
			if(NULL != TREE_FIND(bst,k)) cout << "yes" << endl;
			else cout << "no" << endl;

		}
		else if(s_buf=="delete"){
			cin >> k;
			TREE_DELETE(bst, TREE_FIND(bst,k));
		}
		else if(s_buf=="print"){
			Inorder(bst);
			cout << endl;

			Preorder(bst);
			cout << endl;
		}
	}
	// ファイルを閉じる//////////////////////////////////////////////////////////////////
    //fclose(fp_in);
	/////////////////////////////////////////////////////////////////////////////////////

	
	return 0;
}

Measured memory_bytes: 24648