4935.二叉搜索树 III

## 题目描述

编写一个程序，对二叉搜索树$ T $执行以下操作，并在上一题（二叉搜索树II）的基础上增加删除功能：

`insert k`：向 $T$ 中插入一个包含键值 $k $的节点。

`find k`：检查 $T $中是否存在包含键值 $k$ 的节点。

`delete k`：从$ T $中删除包含键值$ k $的节点。

`print`：分别通过中序遍历和前序遍历输出二叉搜索树的键值。

删除操作的实现算法需考虑以下情况：

1. 如果待删除节点$ z $没有子节点，则直接修改其父节点 $z.p$，将对应子节点替换为$ NIL$（即删除$ z$）。

2. 如果 $z $只有一个子节点，则将$ z$ 的父节点与其子节点直接连接，从而“剪除” $z$。

3. 如果$ z $有两个子节点，则先找到 $z$ 的后继节点$ y$，将$ y $“剪除”后，用$ y $的键值替换$ z $的键值。

## 输入格式

第一行输入操作的数量 $m$。

接下来的 $m$ 行中，每行给出一个操作，格式为以下之一：

`insert k

find k

delete k

print`

## 输出格式

对于每个 `find k` 操作，如果树$ T $中包含键值$ k$ 的节点，则输出 "$yes$"，否则输出 "$no$"。

此外，对于每个 `print` 操作，分别按中序遍历和前序遍历输出树的键值序列，每个键值前加一个空格，并各自占一行。

## 数据范围

操作的总数\le500,000

$print $操作\le10

-2,000,000,000\le 节点的键值$key $ \le2,000,000,000

如果采用上述伪代码的实现方式，二叉搜索树的高度不会超过 100。

二叉搜索树中的所有键值均互不相同。

## 输入
```in1
18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print
```

## 输出
```out1
yes
no
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22
```