BST 3

Limit czasu: 1.0s | Limit pamięci: 64MB

Napisz program, który wykonuje następujące operacje na drzewie wyszukiwania binarnego $T$.

• insert $k$: Wstaw węzeł zawierający $k$ jako klucz do $T$.
• find $k$: Wypisz informację, czy $T$ zawiera węzeł zawierający klucz $k$.
• delete $k$: Usuń z $T$ węzeł zawierający klucz $k$.
• print: Wydrukuj klucze drzewa $T$ w porządku INORDER oraz w porządku PREORDER.

Drzewo $T$ jest puste w stanie początkowym.

Wstawianie węzłów do drzewa ma się odbywać zgodnie z poniższym algorytmem:

// Cormen et al. - Introduction to Algorithms
TREE-INSERT(T, z)
   y = NIL
   x = root[T]
   while x != NIL
      y = x
      if key[z] < key[x]
         x = left[x]
      else
         x = right[x]
   parent[z] = y
   if y == NIL
      root[T] = z
   else if key[z] < key[y]
      left[y] = z
   else
      right[y] = z	

Usuwanie węzłów z drzewa ma się odbywać zgodnie z poniższym algorytmem:

Załóżmy, że usuwamy węzeł $z$. Możliwe są trzy przypadki:

1. Jeśli $z$ nie ma synów, to w jego ojcu zastępujemy wskaźnik do $z$ wartością NIL
2. Jeśli $z$ ma tylko jednego syna, to wycinamy węzeł $z$ przez ustawienie wskaźnika w ojcu $z$ na syna $z$
3. Jeśli $z$ ma dwóch synów, to wycinamy następnik $y$ węzła $z$, oraz zastępujemy klucz węzła $z$ kluczem węzła $y$
   Wyjaśnienie: następnik jest to następny węzeł odwiedzany w czasie przechodzenie drzewa w porządku INORDER.

Wejście

W pierwszym wierszu podano liczbę operacji $m$. W kolejnych $m$ wierszach podano operacje reprezentowane przez insert $k$, find $k$, delete $k$ lub print.

Wyjście

Dla każdej operacji find wypisz yes jeśli $T$ zawiera węzeł zawierający klucz $k$, no - w przeciwnym razie.

Dla każdej operacji print wypisz w jednej linii listę wszystkich kluczy w porządku INORDER, w kolejnej - w porządku PREORDER.

Ograniczenia

• $1 \le m \le 500000$
• liczba operacji print $\leq 10$
• klucze są wartościami typu int
• dane są tak dobrane, że wysokość drzewa nigdy nie przekracza $100$
• wszystkie klucze są różne

Przykłady

Wejście 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

Wyjście 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