Paradygmaty programowania - ćwiczenia Lista 9

Słownikiem (ang. dictionary) nazywamy abstrakcyjny typ danych z operacjami wstawiania elementu do zbioru (insert), usuwania elementu ze zbioru (delete), oraz wyszukiwania elementu w zbiorze (lookup, search).

Napisz w języku Oz (niezabezpieczony) funktor, implementujący słownik zgodnie z poniższą sygnaturą:

create : {}→ <Dict>

insert : {<Dict> K*V}→ <Dict>

lookup : {<Dict> K}→ V

delete : {<Dict> K} → <Dict>

gdzie K oznacza typ klucza, a V – typ wartości. Zakładamy, że klucze należą do zbioru liniowo uporządkowanego. Funktor dla słownika ma importować funktor Key dla klucza, w którym jest funkcja compare, porównująca klucze. Funktor Key też należy zaimplementować.

Słownik ma być reprezentowany przez drzewo poszukiwań binarnych:

<BT T> ::= leaf | node(T <BT T> <BT T>) Nie trzeba dbać o wyważanie drzewa.

Słownik ma się zachowywać dokładnie tak samo, jak słownik z wykładu 7 (Oz), w szczególności ma zgłaszać takie same wyjątki.

Najtrudniejsza do zaimplementowania jest operacja delete. Poniższy rysunek schematycznie pokazuje usuwanie węzła X z dwoma następnikami z drzewa poszukiwań binarnych. Należy znaleźć węzeł z najmniejszym kluczem w prawym poddrzewie (ma on co najwyżej jednego następnika – dlaczego?), usunąć go, a jego zawartość przenieść do X

(por. funkcja delete funktora Dictionary – OCaml z wykładu 9).

usuń zawartość X

przenieś zawartość Y

X

Y

Y