ASD e 02 2005 3

Egzamin ASD

Studia dzienne, 7go lutego 2005

Nazwisko

Nr studenta............Nr grupy

Zadanie 3 (lOpunktów) Drzewa BST

W pewnym edytorze tekstowym rozpatrzmy narzędzie sprawdzające pisownię. Zawiera ono zbiór różnych, poprawnych słów. Podstawowe działanie tego narzędzia polega na:

1)    sprawdzaniu, czy zadane słowo występuje w zbiorze,

2)    jeśli odpowiedź jest negatywna, edytor sygnalizuje błąd, proponując słowa do zamiany, zgodnie ź prosta regułą: są to co najwyżej dwa najbliższe danemu słowu słowa ze zbioru, które występowałyby bezpośrednio przed i po błędnym słowie, gdyby błędne słowo znajdowało się w zbiorze.

Możliwa jest sytuacja, kiedy jest tylko jedno słowo ze zbioru spełniające ten warunek.

Założenia: Wszystkie słowa zbioru są przechowywane jako klucze węzłów w drzewie BST, w którym elementy są uporządkowane zgodnie z porządkiem leksykograiicznym.

Każdy węzeł, oprócz klucza, posiada tylko wskaźniki do jego lewego i prawego poddrzewa. Dana jest operacja dwuargumentowa porównaj, taka że porownaj(w 1 ,w2) zwraca 0, gdy słowa są identyczne, zwraca 1, gdy wl jest w porządku leksykograficznym wcześniej niż słowo w2, i zwraca -1 w przeciwnym przypadku.

Polecenia:

Dla zadanego słowa W i korzenia drzewa T podanych jako parametry:

1)    Napisz w pseudokodzie procedurę realizującą podstawowe działanie w/w narzędzia.

2)    Oszacuj złożoność czasową podanego algorytmu.