Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TBDW - Binarne Drzewa Wyszukiwawcze

 

Na wejściu podana jest sekwencja instrukcji: zapytań, modyfikacji drzew oraz przeglądania węzłów drzewa (składnia każdego polecenia identyczna: duża litera oznaczająca instrukcję oraz liczba), precyzyjnie:

  • wstawienie elementu x do drzewa (I x) (1 <= x <= 10000),
  • usunięcie elementu x z drzewa (D x),
  • wyszukiwanie elementu x w drzewie (S x),
  • znajdowanie najmniejszego (X 0) oraz największego (X 1) elementu w drzewie,
  • znajdowanie następnika elementu x (N x) oraz poprzednika elementu x (P x),
  • przeglądanie wierzchołków drzewa trzema sposobami (inorder: R 0, preorder: R 1, postorder: R 2).

W zadaniu nie można stosować dodatkowych optymalizacji, podczas usuwania elementu, który posiada dwóch potomków - wstawiamy w jego miejsce jego bezpośredniego poprzednika.

Wejście

t [liczba testów = 10]
n [liczba instrukcji do wykonania <= 10000]
instrukcje... [w jednej linii jedna instrukcja]
[kolejne testy]

Wyjście

W pierwszej linijce odpowiedzi do danego testu powinien znaleźć się napis: test nr. Odpowiedzi podawane są w kolejnych linijkach. W przypadku jednej z instrukcji R należy na wyjściu wydrukować wartości kluczy w kolejnych węzłach drzewa zgodnie z porządkiem, dla zapytań należy wydrukować wartość klucza (dla Min, Max, Succ, Pred, Search (tak)) lub - dla Search (nie), Pred (nie) lub Succ (nie). Zwracam uwagę, że żądanie wydrukowania następnika lub poprzednika elementu, którego nie ma w drzewie zakończyć się powinno wydrukowaniem -.

Przykład

Wejście:
4
13
I 5
I 8
I 3
I 4
I 7
R 1
I 1
R 2
S 7
S 6
N 3
D 8
R 0
10
I 4
I 2
R 0
D 2
X 1
X 0
I 1
X 0
X 0
X 1
10
I 4
P 1
I 1
R 1
I 2
I 5
R 0
D 2
I 2
P 1
11
I 3
X 0
I 2
D 3
I 1
I 5
I 4
D 4
I 4
D 4
X 1

Wyjście:
test 1
5 3 4 8 7
1 4 3 7 8 5
7
-
4
1 3 4 5 7
test 2
2 4
4
4
1
1
4
test 3
-
4 1
1 2 4 5
-
test 4
3
5


Dodane przez:mima
Data dodania:2005-06-05
Limit czasu wykonania programu:5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

ukryj komentarze
2012-03-25 09:56:02 Piotr KÄ…kol
Ja miałem sporo błędów w usuwaniu. Radzę DOKŁADNIE przeanalizować swoje usuwanie noda. Mi pomogła rekurencja.
2011-05-29 19:43:40 Dawid Zwiewka
mój program przechodzi wszystkie testy z forum i ten z zadania, a i tak mam WA...
2011-05-29 18:18:22 Krystian Talar
Zadanie faktycznie bardzo kiepsko opisane - nieoceniona pomoc poniższych komentarzy oraz testów przykładowych na forum
2010-07-31 19:05:11 Sebastian Nowak
Dawno nie widziałem aż tak niedoprecyzowanego zadania... Drobna podpowiedź na przyszłość dla innych, aby nie marnowali czasu: w żadnym teście nie pojawia się próba wstawienia duplikatu lub usunięcia nieistniejącego elementu oraz żadna operacja nie jest wykonywana na pustym drzewie.
2010-03-06 17:20:26 Marek D±bek
Faktycznie, też mam z tym zadaniem problem. Nie jest do końca sprecyzowane jak ma się zachowywać program. Próbowałem kilku wariantów i nic nie przeszło.
2010-01-07 22:10:21 Artur Mañko
Brakuje mi informacji jak algorytm ma reagować na instrukcję R dla pustego drzewa: czy ma wydrukować pustą linię, czy tez może powinien drukować "-", a może w ogóle nie drukować linii... Niestety w przykładzie nie ma takiego przypadku a treść zadania tego nie rozstrzyga.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.