#include <stdio.h>
#include <stdlib.h>
#define A NULL
????
struct node{
????struct node *left;
????struct node *right;
????struct node *parent;
????int key;
};
typedef struct node * Node;
Node root;
????
Node treeMinimum(Node x){
????while(x->left != A){
????????x = x->left;
????}
????return x;
}
????
Node treeSearch(Node u, int k){
????while(u != A && k != u->key){
????????if(k < u->key){
????????????u = u->left;
????????}else{
????????????u = u->right;
????????}
????}
????return u;
}
????
Node treeSuccessor(Node x){
????Node y;
????if(x->right != A) return treeMinimum(x->right);
????y = x->parent;
????
????while(y !=A && x == y->right){
????????x = y;
????????y = y->parent;
????}
????return y;
}
????
??
????
void inorder(Node u){
????if(u != A){
????????if(u->left != A) inorder(u->left);
????????printf(" %d", u->key);
????????if(u->right != A) inorder(u->right);
????}
}
????
void preorder(Node u){
????if(u != A){
????????printf(" %d", u->key);
????????if(u->left != A) preorder(u->left);
????????if(u->right != A) preorder(u->right);
????}
}
????
int main(){
????int y, i, x;
????char com[20];
????scanf("%d", &y);
????????
????for ( i = 0; i < y; i++ ){
????????scanf("%s", com);
????????if ( com[0] == 'f' ){
????????????scanf("%d", &x);
????????????Node t = treeSearch(root, x);
????????????if ( t != A ) printf("yes\n");
????????????else printf("no\n");
????????} else if ( com[0] == 'i' ){
????????????scanf("%d", &x);
????????????insert(x);
????????} else if ( com[0] == 'p' ){
????????????inorder(root);
????????????printf("\n");
????????????preorder(root);
????????????printf("\n");
????????} else if ( com[0] == 'd' ){
????????????scanf("%d", &x);
????????????treeDelete(treeSearch(root, x));
????????????}
????}
????????
????return 0;
}
void treeDelete(Node z){
????Node y; // node to be deleted
????Node x; // child of y
????
????if(z->left == A || z->right == A) y = z;
????else y = treeSuccessor(z);
????
????if(y->left != A) x = y->left;
????else x = y->right;
????
????if(x != A) x->parent = y->parent;
????if(y->parent == A) root = x;
????else if( y == y->parent->left) y->parent->left = x;
????else y->parent->right = x;
????
????if(y != z) z->key = y->key; 
}
????
void insert(int k){
????Node y = A;
????Node x = root;
????Node z;
????z = malloc(sizeof(struct node));
????z->key = k;
????z->left = A;
????z->right = A;
????
????while(x != A){
????????y = x;
????????if(z->key < x->key){
????????????x = x->left;
????????}else{
????????????x = x->right;
????????}
????}
????z->parent = y;
????if(y == A){
????????root = z;
????}else if(z->key < y->key){
????????y->left = z;
????}else{
????????y->right = z;
????}
}