| « poprzedni punkt | następny punkt » |
Słownik jest jeszcze jedną strukturą, która służy do reprezentowania zbiorów skończonych. Tym razem jednak nie zakładamy żadnego porządku w zbiorze elementów. Charakterystycznymi operacjami tej struktury są operacja wstawiania, usuwania wskazanego elementu i sprawdzania, czy element należy do wskazanego zbioru.
Strukturę danych nazywamy słownikiem (ang. dictionary) wttw jej uniwersum składa się z dwóch rozłącznych zbiorów E i D oraz określone są operacje o sygnaturze:
- insert: E ´ D ® D
- delete: E ´ D ® D
- member: E ´ D ® B0
- empty : D ® B0
spełniające następujące postulaty
(D1) empty(d) º Ø ( $e) member(e,d), Ø empty(d) ® member(amb(d),d))
(D2) member(e,insert(e,d)), e ¹ e' ® member(e,d) º member(e, insert(e',d))
(D3) Ø memeber(e, delete(e,d)), e ¹ e' ® member(e,d) º member(e, delete(e',d))
(D4) instrukcja while not empty(d) do d := delete(amb(d),d) od nie zapętla się dla dowolnego słownika d
(D5) member(e,d) = true wttw po wykonaniu poniższego algorytmu zmienna bool ma wartość true.
{boo := false; while (not empty(d) and not bool) do e' := amb(d); bool := (e' = e); d := delete(e', d) od}.
W powyższych formułach użyto dodatkowej funkcji amb: D ® E, która daje w wyniku jakiś (dowolnie wybrany) element słownika. Standardowa interpretacja opisanych wyżej operacji jest taka jak dla struktury kolejki priorytetowej: słowniki interpretujemy jako skończone zbiory elementów pewnego zbioru E, a operacje insert, delete, member odpowiadają teoriomnogościowym operacjom sumy, różnicy i należenia.
D(E) = < D È E; insert, delete, member, empty >,
którego uniwersum składa się ze zbioru elementów E i zbioru D skończonych podzbiorów E, a operacje struktury są określone dla dowolnego skończonego zbioru X następująco:
member(e,X) = true wttw e Î X
insert(e,X) = {e} È X,
delete(e, X) = X \ {e},
empty(X) = true wttw X jest zbiorem pustym.
Operacja insert(e,X) pozwala powiększyć zbiór X o nowy element, a delete(e,X) usunąć wskazany element e ze zbioru X. Przyjmując, że w standardowej strukturze amb jest dowolną funkcją ze zbioru D w E, tak że amb(X) Î X (amb(X) wskazuje jakiś element zbioru X) można udowodnić, że w standardowej strukturze słowników wszystkie wyżej wymienione postulaty są prawdziwe.
Rzeczywiście, postulat pierwszy stwierdza, że zbiór pusty nie posiada żadnych elementów oraz, że wynik funkcji amb dla zbioru X, amb(X), jest jakimś elementem zbioru X. Postulat drugi charakteryzuje operację wstawiania elementu do zbioru: wynikiem insert(e,X) jest zbiór, do którego należy e oraz wszystkie te elementy, które do niego należały przed wykonaniem operacji. Postulat trzeci charakteryzuje operację delete w podobny sposób: wynikiem delete(e,X) jest zbiór X bez elementu e, ale wszystkie inne elementy, które należały do X przed wykonaniem operacji, należą też do zbioru otrzymanego w wyniku. Postulat czwarty, opisuje własność skończoności rozważanych słowników: jeżeli pewną skończoną liczbę razy wyjmiemy (usuniemy) element wskazany przez funkcję amb z dowolnego słownika, to otrzymamy zbiór pusty.
Lemat 3.1 Niech D'(E) będzie rozszerzeniem standardowej struktury słowników o funkcję amb, która dowolnemu skończonemu podzbiorowi E przypisuje jakiś z jego elementów. Tak rozszerzona standardowa struktura słowników jest modelem postulatów (D1) - (D5).
Łatwo zauważyć, że zarówno drzewa BST jak i AVL mogą być traktowane jako struktury standardowe słowników w szczególnym przypadku, gdy zbiory etykiet mają określony porządek liniowy. Operacji amb odpowiada wtedy funkcja minimum. Znane są jednak inne implementacje, które pozwalają wykonać operacje słownikowe z kosztem stałym. Są to tablice z mieszaniem.
Pytanie 3: Jaki jest koszt
znalezienia słowa w słowniku reprezentowanym przez wyważone drzewo BST
o 1024 liściach ?
| « poprzedni punkt | następny punkt » |