using System;
using System.Collections.Generic;
using System.Linq;
// Q029 二分探索木：削除 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_C&lang=jp
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("18");
WillReturn.Add("insert 8");
WillReturn.Add("insert 2");
WillReturn.Add("insert 3");
WillReturn.Add("insert 7");
WillReturn.Add("insert 22");
WillReturn.Add("insert 1");
WillReturn.Add("find 1");
WillReturn.Add("find 2");
WillReturn.Add("find 3");
WillReturn.Add("find 4");
WillReturn.Add("find 5");
WillReturn.Add("find 6");
WillReturn.Add("find 7");
WillReturn.Add("find 8");
WillReturn.Add("print");
WillReturn.Add("delete 3");
WillReturn.Add("delete 7");
WillReturn.Add("print");
//yes
//yes
//yes
//no
//no
//no
//yes
//yes
// 1 2 3 7 8 22
// 8 2 1 3 7 22
// 1 2 8 22
// 8 2 1 22
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct NodeInfo
{
internal int? ParentNode;
internal int? LeftNode;
internal int? RightNode;
}
static int? mRootNode = null;
static Dictionary<int?, NodeInfo> mTreeDict = new Dictionary<int?, NodeInfo>();
static void Main()
{
List<string> InputList = GetInputList();
foreach (string EachStr in InputList.Skip(1)) {
string[] SplitArr = EachStr.Split(' ');
if (SplitArr[0] == "insert") {
Insert(int.Parse(SplitArr[1]));
}
if (SplitArr[0] == "find") {
int? FindResult = Find(int.Parse(SplitArr[1]));
Console.WriteLine(FindResult == null ? "no" : "yes");
}
if (SplitArr[0] == "delete") {
Delete(int.Parse(SplitArr[1]));
}
if (SplitArr[0] == "print") {
var InorderNodeList = new List<int?>();
Inorder(mRootNode, InorderNodeList);
foreach (int? EachInt in InorderNodeList) {
Console.Write(" {0}", EachInt);
}
Console.WriteLine();
var PreorderNodeList = new List<int?>();
Preorder(mRootNode, PreorderNodeList);
foreach (int? EachInt in PreorderNodeList) {
Console.Write(" {0}", EachInt);
}
Console.WriteLine();
}
}
}
// Insert処理
static void Insert(int? pZ)
{
int? ParentNode = null; // 親ノード
int? CurrNode = mRootNode;
while (CurrNode != null) {
ParentNode = CurrNode; // 親ノードを設定
if (pZ < CurrNode) {
CurrNode = mTreeDict[CurrNode].LeftNode; // 左ノードへ移動
}
else {
CurrNode = mTreeDict[CurrNode].RightNode; // 右ノードへ移動
}
}
NodeInfo WillAdd;
WillAdd.ParentNode = ParentNode;
WillAdd.LeftNode = null;
WillAdd.RightNode = null;
mTreeDict[pZ] = WillAdd;
if (ParentNode == null) { // T が空の場合
mRootNode = pZ;
}
else if (pZ < ParentNode) {
NodeInfo wkTreeDict = mTreeDict[ParentNode];
wkTreeDict.LeftNode = pZ;
mTreeDict[ParentNode] = wkTreeDict;
}
else {
NodeInfo wkTreeDict = mTreeDict[ParentNode];
wkTreeDict.RightNode = pZ;
mTreeDict[ParentNode] = wkTreeDict;
}
}
// Delete処理
static void Delete(int? pZ)
{
// ノードが存在しない場合
if (mTreeDict.ContainsKey(pZ) == false) return;
// Zの子ノード数で場合分け
var ChildNodeList = new List<int?>();
if (mTreeDict[pZ].LeftNode != null) ChildNodeList.Add(mTreeDict[pZ].LeftNode);
if (mTreeDict[pZ].RightNode != null) ChildNodeList.Add(mTreeDict[pZ].RightNode);
// 子ノード数が0の場合
if (ChildNodeList.Count == 0) {
int? ParentNode = mTreeDict[pZ].ParentNode;
if (ParentNode != null) { // 親ノードがある場合
if (mTreeDict[ParentNode].LeftNode == pZ) {
NodeInfo wkTreeDict = mTreeDict[ParentNode];
wkTreeDict.LeftNode = null;
mTreeDict[ParentNode] = wkTreeDict;
}
else {
NodeInfo wkTreeDict = mTreeDict[ParentNode];
wkTreeDict.RightNode = null;
mTreeDict[ParentNode] = wkTreeDict;
}
}
// 親ノードがない場合は、ルートノードなので変更しておく
else {
mRootNode = null;
}
mTreeDict.Remove(pZ);
}
// 子ノード数が1の場合
if (ChildNodeList.Count == 1) {
int? ParentNode = mTreeDict[pZ].ParentNode;
if (ParentNode != null) { // 親ノードがある場合
if (mTreeDict[ParentNode].LeftNode == pZ) {
NodeInfo wkTreeDict1 = mTreeDict[ParentNode];
wkTreeDict1.LeftNode = ChildNodeList[0];
mTreeDict[ParentNode] = wkTreeDict1;
}
else {
NodeInfo wkTreeDict1 = mTreeDict[ParentNode];
wkTreeDict1.RightNode = ChildNodeList[0];
mTreeDict[ParentNode] = wkTreeDict1;
}
NodeInfo wkTreeDict2 = mTreeDict[ChildNodeList[0]];
wkTreeDict2.ParentNode = ParentNode;
mTreeDict[ChildNodeList[0]] = wkTreeDict2;
}
// 親ノードがない場合は、ルートノードなので変更しておく
else {
mRootNode = ChildNodeList[0];
}
mTreeDict.Remove(pZ);
}
// 子ノード数が2の場合
if (ChildNodeList.Count == 2) {
// 次接点を求めて、削除
int? Successor = DeriveSuccessor(ChildNodeList[1]);
NodeInfo SuccessorInfo = mTreeDict[Successor];
Delete(Successor);
int? ParentNode = mTreeDict[pZ].ParentNode;
if (ParentNode != null) { // 親ノードがある場合
if (mTreeDict[ParentNode].LeftNode == pZ) {
NodeInfo wkTreeDict1 = mTreeDict[ParentNode];
wkTreeDict1.LeftNode = Successor;
mTreeDict[ParentNode] = wkTreeDict1;
}
else {
NodeInfo wkTreeDict1 = mTreeDict[ParentNode];
wkTreeDict1.RightNode = Successor;
mTreeDict[ParentNode] = wkTreeDict1;
}
}
// 親ノードがない場合は、ルートノードなので変更しておく
else {
mRootNode = Successor;
}
mTreeDict.Remove(pZ);
// 次接点ノードの追加
SuccessorInfo.ParentNode = ParentNode;
SuccessorInfo.LeftNode = ChildNodeList[0];
SuccessorInfo.RightNode = ChildNodeList[1];
if (SuccessorInfo.RightNode == Successor) {
SuccessorInfo.RightNode = null;
}
mTreeDict[Successor] = SuccessorInfo;
}
}
// 次節点を返す
static int? DeriveSuccessor(int? pStartNode)
{
int? WillReturn = pStartNode;
while (mTreeDict[WillReturn].LeftNode != null) {
WillReturn = mTreeDict[WillReturn].LeftNode;
}
return WillReturn;
}
// 中間順巡回でDFS
static void Inorder(int? pCurrNode, List<int?> pPrintNodeList)
{
if (pCurrNode == null) return;
Inorder(mTreeDict[pCurrNode].LeftNode, pPrintNodeList);
pPrintNodeList.Add(pCurrNode);
Inorder(mTreeDict[pCurrNode].RightNode, pPrintNodeList);
}
// 先行順巡回でDFS
static void Preorder(int? pCurrNode, List<int?> pPrintNodeList)
{
if (pCurrNode == null) return;
pPrintNodeList.Add(pCurrNode);
Preorder(mTreeDict[pCurrNode].LeftNode, pPrintNodeList);
Preorder(mTreeDict[pCurrNode].RightNode, pPrintNodeList);
}
static int? Find(int? SearchVal)
{
int? CurrNode = mRootNode;
while (CurrNode != null && CurrNode != SearchVal) {
if (SearchVal < CurrNode) {
CurrNode = mTreeDict[CurrNode].LeftNode;
}
else {
CurrNode = mTreeDict[CurrNode].RightNode;
}
}
return CurrNode;
}
}