/****************************/
/* 二分探索木               */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;

/********************/
/* クラスListの定義 */
/********************/
class List
{
	String st;
	List left, right;
				// コンストラクタ
	List () { }

	List (String s)
	{
		st = new String(s);
	}

	/***************************************/
	/* データの追加                        */
	/*      dt : Listクラスのオブジェクト  */
	/*      return : =1 : 追加             */
	/*               =0 : 同じデータが存在 */
	/***************************************/
	int add(List dt)
	{
		List lt = this;
		int k, sw = -1;
						// トップ
		if (lt.st == null) {
			lt.st = dt.st;
			sw    = 1;
		}
						// トップでない
		else {
			while (sw < 0) {
				k = (dt.st).compareTo(lt.st);
								// 同じデータがある
				if (k == 0)
					sw = 0;
								// 大きい
				else if (k > 0) {
					if (lt.right == null) {
						lt.right = dt;
						sw       = 1;
					}
					else
						lt = lt.right;
				}
								// 小さい
				else {
					if (lt.left == null) {
						lt.left = dt;
						sw      = 1;
					}
					else
						lt = lt.left;
				}
			}
		}
	
		return sw;
	}

	/***************************************/
	/* データの削除                        */
	/*      st : 文字列                    */
	/*      return : =1 : 削除した         */
	/*               =0 : 削除できなかった */
	/***************************************/
	int del(String st)
	{
		List lt, lt1 = this, lt2 = this, dt;
		int k, rl = 0, sw = 0;
	
		if (lt2.st != null) {
			while (sw == 0 && lt2 != null) {
				k = st.compareTo(lt2.st);
						// 削除
				if (k == 0) {
					sw = 1;
					if (lt2.right == null) {
								// 子供無し
						if (lt2.left == null) {
							if (rl == 0)
								lt2.st = null;
							else {
								if (rl > 0)
									lt1.right = null;
								else
									lt1.left = null;
							}
						}
								// 右無し
						else {
							if (rl == 0) {
								lt2.st    = (lt2.left).st;
								lt2.right = (lt2.left).right;
								lt2.left  = (lt2.left).left;
							}
							else {
								if (rl > 0)
									lt1.right = lt2.left;
								else
									lt1.left = lt2.left;
							}
						}
					}
	
					else {
								// 左無し
						if (lt2.left == null) {
							if (rl == 0) {
								lt2.st    = (lt2.right).st;
								lt2.left  = (lt2.right).left;
								lt2.right = (lt2.right).right;
							}
							else {
								if (rl > 0)
									lt1.right = lt2.right;
								else
									lt1.left = lt2.right;
							}
						}
								// 左右あり
						else {
							dt = lt2.left;
							if (rl == 0) {
								lt         = lt2.right;
								lt2.st    = lt.st;
								lt2.right = lt.right;
								lt2.left  = lt.left;
							}
							else {
								if (rl > 0)
									lt1.right = lt2.right;
								else
									lt1.left = lt2.right;
							}
							lt1.add(dt);
						}
					}
				}
						// 次のデータ
				else {
					lt1 = lt2;
					if (k > 0) {
						lt2 = lt2.right;
						rl  = 1;
					}
					else {
						lt2 = lt2.left;
						rl  = -1;
					}
				}
			}
		}
	
		return sw;
	}

	/***********************************/
	/* データの探索                    */
	/*      st : 文字列                */
	/*      return : =1 : 見つかった   */
	/*               =0 : 見つからない */
	/***********************************/
	int search(String st)
	{
		List lt = this;
		int k, sw = 0;
	
		if (lt.st != null) {
			while (sw == 0 && lt != null) {
				k = st.compareTo(lt.st);
						// 見つかった
				if (k == 0)
					sw = 1;
						// 次のデータ
				else if (k > 0)
					lt = lt.right;
				else
					lt = lt.left;
			}
		}
	
		return sw;
	}

	/**********************/
	/* リストデータの出力 */
	/**********************/
	void output()
	{
		List nt = this;
						// 出力
		if (nt.st != null) {
			System.out.print(nt.st);
			if (nt.right != null)
				System.out.print(" right " + (nt.right).st);
			if (nt.left != null)
				System.out.print(" left " + (nt.left).st);
			System.out.println();
						// 次の出力
			if (nt.right != null)
				(nt.right).output();
			if (nt.left != null)
				(nt.left).output();
		}
	}
}

/****************/
/* main program */
/****************/
public class Test
{
	public static void main (String[] args) throws IOException
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		List base = new List ();
		List lt;
		String st;
		int k, sw = 1;

		while (sw > 0) {
			System.out.print("1:追加，2:削除，3:探索，4:出力，0:終了？ ");
			sw = Integer.parseInt(in.readLine());
			switch (sw) {
				case 1:   // 追加
					System.out.print("   データを入力してください ");
					st = in.readLine();
					lt = new List (st);
					k  = base.add(lt);
					if (k > 0)
						System.out.print("      " + st + " を追加しました\n");
					else
						System.out.print("      既に同じデータが存在します\n");
					break;
				case 2:   // 削除
					System.out.print("   データを入力してください ");
					st = in.readLine();
					k  = base.del(st);
					if (k > 0)
						System.out.print("      " + st + " を削除しました\n");
					else
						System.out.print("      " + st + " を削除できませんでした\n");
					break;
				case 3:   // 探索
					System.out.print("   データを入力してください ");
					st = in.readLine();
					k  = base.search(st);
					if (k > 0)
						System.out.print("      " + st + " が見つかりました\n");
					else
						System.out.print("      " + st + " は見つかりませんでした\n");
					break;
				case 4:   // 出力
					base.output();
					break;
				default :
					sw = 0;
					break;
			}
		}
	}
}