２分探索木III

B: Binary Search Tree II に、delete 命令を追加し、二分探索木 $T$ に対し、以下の命令を実行するプログラムを作成してください。

• insert $k$: $T$ にキー $k$ を挿入する。
• find $k$: $T$ にキー $k$ が存在するか否かを報告する。
• delete $k$: キー $k$ を持つ節点を削除する。
• print: キーを木の中間順巡回(inorder tree walk)と先行順巡回(preorder tree walk)アルゴリズムで出力する。

二分探索木 $T$ から与えられたキー $k$ を持つ節点 $z$ を削除する delete k は以下の３つの場合を検討したアルゴリズムに従い、二分探索木条件を保ちつつ親子のリンク（ポインタ）を更新します：

1. $z$ が子を持たない場合、$z$ の親 $p$ の子（つまり $z$）を削除する。
2. $z$ がちょうど１つの子を持つ場合、$z$ の親の子を $z$ の子に変更、$z$ の子の親を $z$ の親に変更し、$z$ を木から削除する。
3. $z$ が子を２つ持つ場合、$z$ の次節点 $y$ のキーを $z$ のキーへコピーし、$y$ を削除する。$y$ の削除では 1. または 2. を適用する。ここで、$z$ の次節点とは、中間順巡回で $z$ の次に得られる節点である。

入力

入力の最初の行に、命令の数 $m$ が与えられます。続く$m$ 行目に、insert $k$、find $k$、delete $k$または print の形式で命令が１行に与えられます。

出力

find $k$ 命令ごとに、$T$ に $k$ が含まれる場合 yes と、含まれない場合 no と１行に出力してください。

さらに print 命令ごとに、中間順巡回アルゴリズム、先行順巡回アルゴリズムによって得られるキーの順列をそれぞれ１行に出力してください。各キーの前に１つの空白を出力してください。

制約

• 命令の数は$500,000$を超えない。
• print命令の数は$10$を超えない。
• $-2,000,000,000 \leq キー \leq 2,000,000,000$
• 上記の疑似コードのアルゴリズムに従う場合、木の高さは $100$ を超えない。
• 二分探索木中のキーに重複は発生しない。

入力例 1

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

出力例 1

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

参考文献

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

---