29 (741)

aQ, Dla metody mieszania otwartego podać procedury wyszukiwania, wstawiania i usuwania (elementu z tablicy mieszającej. Jaka jest średnia złożoność obik^reniowa każdej z procedur?

Mieszanie (hsszowanie) jest także rozwiązaniem problemu słownika, ale jakże odmiennym od drzew BST' 0 zgrozo! Wykorzystuje się w nim własności numeryczne przechowywanych elementów (w BST jedyna informacja o elementach pochodzi z porównań elementów).

W metodach mieszających należy obliczyć wartość pewnej funkqi odwzorowującej uniwersum [2] elementów w zbiór elementów tablicy. Funkcje tę nazywamy funkcją mieszającą h(x). Jeżeli funkcja h(x) przekształca rożne klucze w różne liczby, jest to doskonal funkcja mieszająca (1).

Obliczona wartość daje nam indeks w tablicy, pod którym możemy znaleźć poszukiwany element. Gdy okaże się. że na pozyqi o danym indeksie znajduje się kilka elementów, iu mamy do czynienia z kolizją. Elementy o tej samej wartośd funktii mieszającej są trzymane na jednej liście reprezentowanej bezpośrednio lub w sposób ukryty w jednej tablicy.

Jeżeli nie ma ograniczeń pamięciowych stosujemy mieszanie otwarte. Jeżeli r.ie ma ograniczeń czasowych -mieszanie zamknięte.

Zajmiemy się mieszaniem otwartym - w literaturze zwanym także metodą łańcud ruw-ą.

0

1

2

3

4

5

3B,! 2—% C, i 1

6    ;

7    '' i

3    i

⁹ i —B₀} |

2 każdą pozycją tablicy A związana jest lista liniowa elementów, które mają tę sama, waność funkcji mieszającej, na rysunku przedstawiono schemat struktury wstawieniu elementów A5, A2. A3, B5, A9, S2, B9, C2. Tak więc de fecto funkcja h(x) zwraca numer kubełka, gdzie przechowywana są wskaźniki do poszczególnych elementów. Funkcja h(x) powinna rozpraszać elementy równomiernie, by generować w miarę krótkie listy o jednakowej długośd

Średnia długość listy = n / a , n - liczba kluczy, a - rozmiar tablicy A

7>Jn) = 0(1 * n / a) , cis: JEST, WSTAW, USUŃ

Złożoność procedur mieszania otwartego zależy od średniej długości listy.

const	a = iGzpcwiedc.is s•-ale]
rype	słowo ~ array(l..lC) of
	eiemer.c Uszy = r&cord
	r : sżowo;
	na sc : ‘eie/nenc^i.
	enć;

typ_J i s co^y = ''eieaienc^iiscy; slcwr.ik * arrąy(C..a-l] of Łypalis zdwj-;

v"3.r A : ci o-mil*) c;.p 2iszc-y;

function JEST[x : s-łcwz va.r biedacy

begin

v bielicy := A[h(X));

x tben

while tieCicy nil do if bielicy ’-.r - .