#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node *l,*r,*p;
};
typedef node* tree;
tree root;
int n;
void Make_Empty(tree *a){
(*a)=NULL;
return;
}
node *Make_node(int gt){
node *P;
P=new(node);
P->data=gt;
P->l=NULL;
P->r=NULL;
P->p=NULL;
return P;
}
void cha_con(node *a,node *b,bool k){
b->p=a;
if (k) a->r=b; else a->l=b;
}
void Insert(tree *a,int gt){
node *p=Make_node(gt);
if ((*a)==NULL){
(*a)=p;
return;
}
node *t=*a;
while (1){
if (gt>t->data){
if (t->r==NULL){
cha_con(t,p,1);
break;
}
else t=t->r;
continue;
}
if (t->l==NULL){
cha_con(t,p,0);
break;
}
else t=t->l;
}
}
node *timkiem(tree *t,int gt){
node *a=*t;
while (true){
if (a==NULL) return NULL;
if (a->data==gt) return a;
if (gt<a->data) a=a->l;
else a=a->r;
}
}
void Delete(tree *a,int gt){
node *p=timkiem(a,gt);
if (p==NULL) return;
/// Neu p la nut la
if ((p->l)==NULL && (p->r)==NULL){
node *p1=p->p;
if (p==p1->l) p1->l=NULL;
else p1->r=NULL;
delete(p);
return;
}
/// Neu P co 1 con
if (p->l==NULL){
node *p1=p->p;
node *t=p;
p=p->r;
if (t==p1->l) p1->l=p;
else p1->r=p;
delete(t);
return;
}
if (p->r==NULL){
node *p1=p->p;
node *t=p;
p=p->l;
if (t==p1->l) p1->l=p;
else p1->r=p;
delete(t);
return;
}
///Neu p co 2 con
node *t=p->r;
while (t->l!=NULL) t=t->l;
p->data=t->data;
node *p1=t->p;
if (t==p1->l) p1->l=NULL;
else p1->r=NULL;
delete(t);
}
void Duyetcay(tree a){
if (a==NULL) return;
Duyetcay(a->l);
printf("%d ",a->data);
Duyetcay(a->r);
}
int main()
{
freopen("input.inp","r",stdin);
Make_Empty(&root);
cin>>n;
for(int i=1; i<=n; i++){
int x;
cin>>x;
Insert(&root,x);
}
Duyetcay(root);cout<<endl;
int k;
cin>>k;
Delete(&root,k);
Duyetcay(root);cout<<endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IG5vZGV7CiAgICBpbnQgZGF0YTsKICAgIG5vZGUgKmwsKnIsKnA7Cn07CnR5cGVkZWYgbm9kZSogdHJlZTsKdHJlZSByb290OwppbnQgbjsKCnZvaWQgTWFrZV9FbXB0eSh0cmVlICphKXsKICAgICgqYSk9TlVMTDsKICAgIHJldHVybjsKfQoKbm9kZSAqTWFrZV9ub2RlKGludCBndCl7CiAgICBub2RlICpQOwogICAgUD1uZXcobm9kZSk7CiAgICBQLT5kYXRhPWd0OwogICAgUC0+bD1OVUxMOwogICAgUC0+cj1OVUxMOwogICAgUC0+cD1OVUxMOwogICAgcmV0dXJuIFA7Cn0KCnZvaWQgY2hhX2Nvbihub2RlICphLG5vZGUgKmIsYm9vbCBrKXsKICAgIGItPnA9YTsKICAgIGlmIChrKSBhLT5yPWI7IGVsc2UgYS0+bD1iOwp9Cgp2b2lkIEluc2VydCh0cmVlICphLGludCBndCl7CiAgICBub2RlICpwPU1ha2Vfbm9kZShndCk7CiAgICBpZiAoKCphKT09TlVMTCl7CiAgICAgICAgKCphKT1wOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIG5vZGUgKnQ9KmE7CiAgICB3aGlsZSAoMSl7CiAgICAgICAgaWYgKGd0PnQtPmRhdGEpewogICAgICAgICAgICBpZiAodC0+cj09TlVMTCl7CiAgICAgICAgICAgICAgICBjaGFfY29uKHQscCwxKTsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlIHQ9dC0+cjsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIGlmICh0LT5sPT1OVUxMKXsKICAgICAgICAgICAgY2hhX2Nvbih0LHAsMCk7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgICAgICAgICAgZWxzZSB0PXQtPmw7CiAgICB9Cn0KCm5vZGUgKnRpbWtpZW0odHJlZSAqdCxpbnQgZ3QpewogICAgbm9kZSAqYT0qdDsKICAgIHdoaWxlICh0cnVlKXsKICAgICAgICBpZiAoYT09TlVMTCkgcmV0dXJuIE5VTEw7CiAgICAgICAgaWYgKGEtPmRhdGE9PWd0KSByZXR1cm4gYTsKICAgICAgICBpZiAoZ3Q8YS0+ZGF0YSkgYT1hLT5sOwogICAgICAgICAgICBlbHNlIGE9YS0+cjsKICAgIH0KfQoKdm9pZCBEZWxldGUodHJlZSAqYSxpbnQgZ3QpewogICAgbm9kZSAqcD10aW1raWVtKGEsZ3QpOwogICAgaWYgKHA9PU5VTEwpIHJldHVybjsKICAgIC8vLyBOZXUgcCBsYSBudXQgbGEKICAgIGlmICgocC0+bCk9PU5VTEwgJiYgKHAtPnIpPT1OVUxMKXsKICAgICAgICBub2RlICpwMT1wLT5wOwogICAgICAgIGlmIChwPT1wMS0+bCkgcDEtPmw9TlVMTDsKICAgICAgICAgICAgZWxzZSBwMS0+cj1OVUxMOwogICAgICAgIGRlbGV0ZShwKTsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgLy8vIE5ldSBQIGNvIDEgY29uCiAgICBpZiAocC0+bD09TlVMTCl7CiAgICAgICAgbm9kZSAqcDE9cC0+cDsKICAgICAgICBub2RlICp0PXA7CiAgICAgICAgcD1wLT5yOwogICAgICAgIGlmICh0PT1wMS0+bCkgcDEtPmw9cDsKICAgICAgICAgICAgZWxzZSBwMS0+cj1wOwogICAgICAgIGRlbGV0ZSh0KTsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgaWYgKHAtPnI9PU5VTEwpewogICAgICAgIG5vZGUgKnAxPXAtPnA7CiAgICAgICAgbm9kZSAqdD1wOwogICAgICAgIHA9cC0+bDsKICAgICAgICBpZiAodD09cDEtPmwpIHAxLT5sPXA7CiAgICAgICAgICAgIGVsc2UgcDEtPnI9cDsKICAgICAgICBkZWxldGUodCk7CiAgICAgICAgcmV0dXJuOwogICAgfQoKICAgIC8vL05ldSBwIGNvIDIgY29uCiAgICBub2RlICp0PXAtPnI7CiAgICB3aGlsZSAodC0+bCE9TlVMTCkgdD10LT5sOwogICAgcC0+ZGF0YT10LT5kYXRhOwogICAgbm9kZSAqcDE9dC0+cDsKICAgIGlmICh0PT1wMS0+bCkgcDEtPmw9TlVMTDsKICAgICAgICBlbHNlIHAxLT5yPU5VTEw7CiAgICBkZWxldGUodCk7Cn0KCnZvaWQgRHV5ZXRjYXkodHJlZSBhKXsKICAgIGlmIChhPT1OVUxMKSByZXR1cm47CiAgICBEdXlldGNheShhLT5sKTsKICAgIHByaW50ZigiJWQgIixhLT5kYXRhKTsKICAgIER1eWV0Y2F5KGEtPnIpOwp9CgppbnQgbWFpbigpCnsKICAgIGZyZW9wZW4oImlucHV0LmlucCIsInIiLHN0ZGluKTsKCiAgICBNYWtlX0VtcHR5KCZyb290KTsKICAgIGNpbj4+bjsKICAgIGZvcihpbnQgaT0xOyBpPD1uOyBpKyspewogICAgICAgIGludCB4OwogICAgICAgIGNpbj4+eDsKICAgICAgICBJbnNlcnQoJnJvb3QseCk7CiAgICB9CiAgICBEdXlldGNheShyb290KTtjb3V0PDxlbmRsOwogICAgaW50IGs7CiAgICBjaW4+Pms7CiAgICBEZWxldGUoJnJvb3Qsayk7CiAgICBEdXlldGNheShyb290KTtjb3V0PDxlbmRsOwoKICAgIHJldHVybiAwOwp9Cg==