#include <stdio.h>

template <class _Ty> class node {

public:

_Ty val;

node<_Ty>* pt[2] = { 0 };

//pt[0]이 left-child이며 pt[1]이 right-child입니다.

};

template <class _Ty> class bst {

node<_Ty>* root;

node<_Ty>*& find_x(_Ty key) {

node<_Ty>** target = &root;

while (*target != nullptr && (*target)->val != key)

target = &(*target)->pt[(*target)->val < key];

return *target;

}

public:

bst() { root = nullptr; }

~bst() { while(root) remove(root->val); }

node<_Ty>* get_root() {

return this->root;

}

node<_Ty>* find(_Ty key) {

return find_x(key);

}

void insert(_Ty key) {

node<_Ty>*& target = find_x(key);

if (target != nullptr) return;

target = new node<_Ty>();

target->val = key;

}

void remove(_Ty key) {

node<_Ty>*& replace = find_x(key);

node<_Ty>** target = &replace;

if (*target == nullptr) return;

if (!(*target)->pt[0] && !(*target)->pt[1]) {

delete *target;

*target = nullptr;

return;

}

bool x = (*target)->pt[1];

target = &(*target)->pt[x];

while((*target)->pt[!x]) target = &(*target)->pt[!x];

replace->val = (*target)->val;

node<_Ty>* temp = *target;

(*target) = (*target)->pt[x];

delete temp;

return;

}

};

template <class _Ty>

void inorder(node<_Ty>* root) {

if (root == nullptr) return;

inorder(root->pt[0]);

printf("%d ", root->val);

inorder(root->pt[1]);

}

int main() {

bst<int> root;

while (1) {

int x;

printf("1: 삽입, 2: 탐색, 3: 삭제, 4: 순회, 5 : 종료\n");

scanf("%d", &x);

switch (x) {

int y;

case 1:

printf("삽입 : ");

scanf("%d", &y);

root.insert(y);

break;

case 2:

printf("탐색 : ");

scanf("%d", &y);

printf("%s", root.find(y) != nullptr ? "성공\n" : "실패\n");

break;

case 3:

printf("삭제 : ");

scanf("%d", &y);

root.remove(y);

break;

case 4:

printf("순회 : ");

inorder(root.get_root());

printf("\n");

break;

case 5:

return 0;

}

}

}