#include <iostream>

using namespace std;

class TreeNode
{
public:
	TreeNode(int key) :
		key(key), pParent(0), pLeftChild(0), pRightChild(0) {}

public:
	int key;
	TreeNode* pParent;
	TreeNode* pLeftChild;
	TreeNode* pRightChild;
};

class BST
{
public:
	bool Insert(int key)
	{
		{
			if (!m_pRoot)
			{
				m_pRoot = new TreeNode(key);
				return true;
			}
			else
				return Insert(m_pRoot, key);
		}
	}

	void Delete(int key)
	{
		Delete(m_pRoot, key);
	}

	TreeNode* Find(int key)
	{
		return Find(m_pRoot, key);
	}

	TreeNode* FindMin(TreeNode* currentNode)
	{
		if (!currentNode) return 0;
		if (!currentNode->pLeftChild) return currentNode;
		return FindMin(currentNode->pLeftChild);
	}

	void PreOrder()
	{
		PreOrder(m_pRoot);
	}

	void InOrder()
	{
		InOrder(m_pRoot);
	}

private:
	bool Insert(TreeNode* currentNode, int key)
	{
		if (key == currentNode->key) return false;
		else if (key < currentNode->key)
		{
			if (currentNode->pLeftChild) return Insert(currentNode->pLeftChild, key);
			else
			{
				currentNode->pLeftChild = new TreeNode(key);
				currentNode->pLeftChild->pParent = currentNode;
				return true;
			}
		}
		else
		{
			if (currentNode->pRightChild) return Insert(currentNode->pRightChild, key);
			else
			{
				currentNode->pRightChild = new TreeNode(key);
				currentNode->pRightChild->pParent = currentNode;
				return true;
			}
		}
	}

	void Delete(TreeNode* currentNode, int key)
	{
		TreeNode* deleteNode = Find(currentNode, key);
		if (!deleteNode) return;

		// 根节点
		if (!deleteNode->pParent)
		{
			if (!m_pRoot->pLeftChild && !m_pRoot->pRightChild)
			{// 删除的根节点没有子节点
				m_pRoot = 0;
				delete deleteNode;
			}
			else if (deleteNode->pLeftChild && deleteNode->pRightChild)
			{// 删除的根节点有2个子节点
				TreeNode* minNode = FindMin(deleteNode->pRightChild);
				deleteNode->key = minNode->key;
				Delete(deleteNode->pRightChild, deleteNode->key);
			}
			else
			{// 删除的根节点有1个子节点
				if (m_pRoot->pLeftChild)
				{
					m_pRoot = m_pRoot->pLeftChild;
					m_pRoot->pParent = 0;
					delete deleteNode;
				}
				else if(m_pRoot->pRightChild)
				{
					m_pRoot = m_pRoot->pRightChild;
					m_pRoot->pParent = 0;
					delete deleteNode;
				}
			}
		}
		else
		{
			TreeNode* parentNode = deleteNode->pParent;

			if (!deleteNode->pLeftChild && !deleteNode->pRightChild)
			{// 删除的节点没有子节点
				if (parentNode->pLeftChild == deleteNode)
					parentNode->pLeftChild = 0;
				else
					parentNode->pRightChild = 0;
				delete deleteNode;
			}
			else if (deleteNode->pLeftChild && deleteNode->pRightChild)
			{// 删除的节点有2个子节点
				// 从删除的节点的右子树中查找最小值节点
				TreeNode* minNode = FindMin(deleteNode->pRightChild);
				// 将删除的节点数据改为右子树最小值节点数据
				deleteNode->key = minNode->key;
				// 删除右子树最小值节点数据
				Delete(deleteNode->pRightChild, deleteNode->key);
			}
			else
			{// 删除的节点有1个子节点
				if (deleteNode->pLeftChild)
				{
					if (parentNode->pLeftChild == deleteNode)
					{
						parentNode->pLeftChild = deleteNode->pLeftChild;
						deleteNode->pLeftChild->pParent = parentNode;
					}	
					else
					{
						parentNode->pRightChild = deleteNode->pLeftChild;
						deleteNode->pLeftChild->pParent = parentNode;
					}
					delete deleteNode;
				}
				else if (deleteNode->pRightChild)
				{
					if (parentNode->pLeftChild == deleteNode)
					{
						parentNode->pLeftChild = deleteNode->pRightChild;
						deleteNode->pRightChild->pParent = parentNode;
					}
					else
					{
						parentNode->pRightChild = deleteNode->pRightChild;
						deleteNode->pRightChild->pParent = parentNode;
					}
						
					delete deleteNode;
				}
			}
		}
	}

	TreeNode* Find(TreeNode* currentNode, int key)
	{
		if (!currentNode) return 0;

		if (key == currentNode->key) return currentNode;
		else if (key < currentNode->key)
			return Find(currentNode->pLeftChild, key);
		else
			return Find(currentNode->pRightChild, key);
	}

	void PreOrder(TreeNode* currentNode)
	{
		if (!currentNode) return;

		cout << " " << currentNode->key;
		PreOrder(currentNode->pLeftChild);
		PreOrder(currentNode->pRightChild);
	}

	void InOrder(TreeNode* currentNode)
	{
		if (!currentNode) return;

		InOrder(currentNode->pLeftChild);
		cout << " " << currentNode->key;
		InOrder(currentNode->pRightChild);
	}

private:
	TreeNode* m_pRoot = 0;
};

int main()
{
	BST tree;
	int n; cin >> n;
	string oper;
	int key;
	for (int i = 0; i < n; ++i)
	{
		cin >> oper;
		if (0 == oper.compare("insert"))
		{
			cin >> key;
			tree.Insert(key);
		}
		else if (0 == oper.compare("print"))
		{
			tree.InOrder();
			cout << endl;
			tree.PreOrder();
			cout << endl;
		}
		else if (0 == oper.compare("find"))
		{
			cin >> key;
			cout << (tree.Find(key) ? "yes" : "no") << endl;
		}
		else if (0 == oper.compare("delete"))
		{
			cin >> key;
			tree.Delete(key);
		}
	}

	return 0;
}


Measured memory_bytes: 21944