Wstęp do programowania w C++

Celem zadania jest implementacja słownika umożliwiającego wstawianie, wyszukiwanie i usuwanie słów. Słowniki mogą zawierać bardzo dużo słów, a użytkownicy chcieliby, aby wyszukiwanie haseł odbywało się możliwie szybko. Postanowiliśmy zatem użyć binarnego drzewa wyszukiwawczego. Każdy węzeł tego drzewa zawiera dwa słowa (każde o długości co najwyżej 10 znaków): jedno w języku polskim oraz jedno w języku angielskim. Drzewo jest organizowane na podstawie słów polskich: dla danego węzła x

• każdy węzeł y należący do poddrzewa zakorzenionego w prawym potomku x zawiera słowo polskie alfabetycznie większe od słowa polskiego w x
• każdy węzeł y należący do poddrzewa zakorzenionego w lewym potomku x zawiera słowo polskie alfabetycznie mniejsze od słowa polskiego w x

Wejście/Wyjście

Pierwsza linia na wejściu zawiera liczbę całkowitą równą liczbie dalej podanych poleceń. Następnie, w osobnych liniach, znajdują się polecenia. Program powinien reagować na następujące polecenia użytkownika:

• insert slowo_pl slowo_en
  wstawienie hasła do słownika; slowo_pl jest słowem polskim, wg którego wstawiamy hasło. Jeśli w słowniku jest już hasło o takim samym słowie polskim jak slowo_pl, to nie zmieniamy zawartości słownika i jednocześnie wypisujemy na ekran w osobnej linii napis:
  already in dictionary
• list
  wypisanie wszystkich haseł w porządku alfabetycznym (względem polskich wyrazów). Wypisujemy je w jednej linii, oddzielone spacjami, każde w postaci: slowo_pl(slowo_en) W przypadku, gdy słownik jest pusty wypisujemy w osobnej linii:
  empty
• reverse_list
  wypisanie wszystkich haseł w odwrotnym porządku alfabetycznym (względem polskich wyrazów). Wypisujemy je w jednej linii, oddzielone spacjami, każde w postaci: slowo_pl(slowo_en)
  W przypadku, gdy słownik jest pusty wypisujemy w osobnej linii:
  empty
• find slowo_pl
  wyszukanie polskiego słowa w słowniku. Jeśli słowo znajduje się w słowniku, to na wyjście wypisujemy napis:
  slowo_en(i)
  gdzie slowo_en to odpowiednik angielski znaleziony w slowniku dla slowo_pl, natomiast liczba i podana w nawiasie jest liczbą węzłów odwiedzonych w drzewie (włącznie z węzłem wyszukiwanym) w celu wyszukania węzła zawierającego slowo_pl. Jeśli szukanego słowa polskiego nie ma w słowniku, to w osobnej linii drukujemy napis:
  cannot find
• remove slowo_pl
  usuwanie hasła, którego polskie słowo jest równe slowo_pl. Jeśli takiego hasła nie ma w słowniku, to na ekran wypisujemy w osobnej linii:
  cannot find
  W przeciwnym wypadku niczego nie wypisujemy na ekran. UWAGA: gdy z drzewa wyszukiwawczego usuwamy węzeł posiadający dwóch potomków, to zamieniamy ten węzeł z elementem największym w lewym poddrzewie, a następnie usuwamy węzeł z lewego poddrzewa.

Testy

• Test 1 (2 pkt.) implementacja operacji insert i find
• Test 2 (3 pkt.) implementacja operacji list, reverse_list oraz powyższych
• Test 3 (5 pkt.) implementacja wszystkich operacji

Przykład

Wejście:
26
insert mewa seagull
insert gorzko bitterly
insert pelikan pelican
insert gniazdko socket
insert oprawca torturer
list
insert niejasno vaguely
insert kucyk pony
find pelikan
find pelican
insert desperacki desperate
insert pesymizm pessimism
find koniec
insert tragiczny tragic
insert koniec end
find koniec
find kucyk
remove kuniec
remove mewa
find kucyk
remove oprawca
find oprawca
remove koniec
insert mewa seagull
insert mewa gull
find mewa


Wyjście:
gniazdko(socket) gorzko(bitterly) mewa(seagull) oprawca(torturer) pelikan(pelican)
pelican(2)
cannot find
cannot find
end(4)
pony(3)
cannot find
pony(1)
cannot find
already in dictionary
seagull(4)