Binary search trees - Binary Search Tree III

Time Limit : 2 sec, Memory Limit : 131072 KB

2分探索木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 は以下の3つの場合を検討したアルゴリズムに従い、二分探索木条件を保ちつつ親子のリンク(ポインタ)を更新します:

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

入力

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

出力

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

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

制約

  • 命令の数は$500,001$を超えない。
  • 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.

Note

      解説