Algorytmy i struktury danych/Wyszukiwanie: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
 
(Nie pokazano 6 wersji utworzonych przez 4 użytkowników)
Linia 4: Linia 4:
 
W niniejszym wykładzie opiszemy podstawowe techniki dotyczące wyszukiwania.
 
W niniejszym wykładzie opiszemy podstawowe techniki dotyczące wyszukiwania.
 
Zajmiemy się również prostymi strukturami słownikowymi, które oprócz
 
Zajmiemy się również prostymi strukturami słownikowymi, które oprócz
wyszukiwania, umożliwiają dodawanie i usuwanie elementów.
+
wyszukiwania umożliwiają dodawanie i usuwanie elementów.
  
 
__TOC__
 
__TOC__
Linia 12: Linia 12:
  
 
Jeśli nie dysponujemy żadną dodatkową wiedzą na temat zbioru, który chcemy
 
Jeśli nie dysponujemy żadną dodatkową wiedzą na temat zbioru, który chcemy
przeszukiwać, to niestety musimy sprawdzić wszystkie jego elementy.
+
przeszukiwać, niestety musimy sprawdzić wszystkie jego elementy.
  
  '''function Szukaj(''x'', ''A''[1..''n''])
+
  1 '''function Szukaj(''x'', ''A''[1..''n''])
  '''begin'''
+
  2 '''begin'''
  '''for''' i:=1 '''to''' ''n'' '''do'''
+
'''for''' i:=1 '''to''' ''n'' '''do'''
    '''if''' A[i]=x '''return''' ''i'';
+
4    '''if''' A[i]=x '''return''' ''i'';
  '''return''' ''brak poszukiwanego elementu'';
+
'''return''' ''brak poszukiwanego elementu'';
  '''end'''
+
  6 '''end'''
  
 
Oczywiście w pesymistycznym przypadku (np. gdy zbiór nie zawiera poszukiwanego elementu)
 
Oczywiście w pesymistycznym przypadku (np. gdy zbiór nie zawiera poszukiwanego elementu)
Linia 36: Linia 36:
 
o połowę.
 
o połowę.
  
  '''function''' WyszukiwanieBinarne(''x'', ''A''[1..''n''])
+
1 '''function''' WyszukiwanieBinarne(''x'', ''A''[1..''n''])
  { zakładamy, że tablica A jest uporządkowana rosnąco }
+
2 { zakładamy, że tablica A jest uporządkowana rosnąco }
  '''begin'''
+
3 '''begin'''
   l:=1;r:=n;
+
4   l:=1;r:=n;
   '''while''' (l<=r) '''do''' '''begin'''
+
5   '''while''' (l<=r) '''do''' '''begin'''
     { niezmiennik: poszukiwany element może znajdować się w zakresie A[l..r] }
+
6     { niezmiennik: poszukiwany element może znajdować się w zakresie A[l..r] }
     m:=(l+r) '''div''' 2;
+
7     m:=(l+r) '''div''' 2;
     '''if''' (A[m]<x) '''then''' l:=m+1
+
8     '''if''' (A[m]<x) '''then''' l:=m+1
     '''else if''' (A[m]>x) '''then''' r:=m-1
+
9     '''else if''' (A[m]>x) '''then''' r:=m-1
    '''else''' '''return''' ''m''; { ponieważ A[m]=x }  
+
10    '''else''' '''return''' ''m''; { ponieważ A[m]=x }  
  '''end''';
+
11  '''end''';
  '''return''' brak poszukiwanego elementu;
+
12  '''return''' brak poszukiwanego elementu;
  '''end''';
+
  13 '''end''';
  
 
== Proste słowniki: drzewa poszukiwań binarnych ==
 
== Proste słowniki: drzewa poszukiwań binarnych ==
Linia 57: Linia 57:
 
Dla dowolnego węzła ''x'':
 
Dla dowolnego węzła ''x'':
 
* wszystkie klucze w lewym poddrzewie węzła ''x'' mają wartości mniejsze niż klucz węzła ''x'',
 
* wszystkie klucze w lewym poddrzewie węzła ''x'' mają wartości mniejsze niż klucz węzła ''x'',
* wszystkie klucze w lewym poddrzewie węzła ''x'' mają wartości większe lub równe niż klucz węzła ''x''.
+
* wszystkie klucze w prawym poddrzewie węzła ''x'' mają wartości większe lub równe niż klucz węzła ''x''.
  
 
<center>[[Grafika:wyszukiwanie.1.png]]</center>
 
<center>[[Grafika:wyszukiwanie.1.png]]</center>
  
Dodatkowe wymaganie dotyczące kluczy, umożliwia nam efektywne wyszukiwanie elementów w drzewie.
+
Dodatkowe wymaganie dotyczące kluczy umożliwia nam efektywne wyszukiwanie elementów w drzewie.
  
  '''function''' Szukaj(węzeł, klucz)
+
'''function''' Szukaj(węzeł, klucz)
    '''if''' (węzeł=='''nil''')  
+
2    '''if''' (węzeł=='''nil''')  
        '''return''' BRAK ELEMENTU
+
3        '''return''' BRAK ELEMENTU
    '''if''' (węzeł.klucz=klucz) '''then'''
+
4    '''if''' (węzeł.klucz=klucz) '''then'''
        '''return''' ELEMENT ISTNIEJE
+
5        '''return''' ELEMENT ISTNIEJE
    ''' else if (klucz < węzeł.klucz) '''then'''
+
6    ''' else if (klucz < węzeł.klucz) '''then'''
        '''return''' Szukaj(węzeł.lewePoddrzewo, klucz)
+
7      '''return''' Szukaj(węzeł.lewePoddrzewo, klucz)
    ''' else if (klucz > węzeł.klucz) '''then'''
+
8    ''' else if (klucz > węzeł.klucz) '''then'''
        '''return''' Szukaj(węzeł.prawPoddrzewo, klucz)
+
9        '''return''' Szukaj(węzeł.prawPoddrzewo, klucz)
  '''end''';
+
10  '''end''';
  
 
Wstawianie do drzewa jest bardzo zbliżone do wyszukiwania: musimy przejść po drzewie  
 
Wstawianie do drzewa jest bardzo zbliżone do wyszukiwania: musimy przejść po drzewie  
 
(rozpoczynając w korzeniu), aby odnaleźć wolne miejsce, w którym możemy dodać nową wartość.
 
(rozpoczynając w korzeniu), aby odnaleźć wolne miejsce, w którym możemy dodać nową wartość.
  
  '''procedure''' Dodaj(węzeł, klucz)
+
'''procedure''' Dodaj(węzeł, klucz)
    '''if''' (klucz < węzeł.klucz) '''then'''
+
2    '''if''' (klucz < węzeł.klucz) '''then'''
        '''if''' węzeł.lewePoddrzewo=nil '''then'''
+
3      '''if''' węzeł.lewePoddrzewo=nil '''then'''
            utwórz nowy węzeł z wartością ''klucz''
+
4        utwórz nowy węzeł z wartością ''klucz''
            wskaźnik do nowego węzła zapisujemy w węzeł.lewePoddrzewo
+
5        wskaźnik do nowego węzła zapisujemy w węzeł.lewePoddrzewo
        '''else'''
+
6      '''else'''
            Dodaj(węzeł.lewePoddrzewo, klucz)
+
7        Dodaj(węzeł.lewePoddrzewo, klucz)
    '''else if (klucz >= węzeł.klucz) '''then'''
+
8    '''else if (klucz >= węzeł.klucz) '''then'''
        '''if''' węzeł.prawePoddrzewo=nil '''then'''
+
9      '''if''' węzeł.prawePoddrzewo=nil '''then'''
            utwórz nowy węzeł z wartością ''klucz''
+
10      utwórz nowy węzeł z wartością ''klucz''
            wskaźnik do nowego węzła zapisujemy w węzeł.prawePoddrzewo
+
11      wskaźnik do nowego węzła zapisujemy w węzeł.prawePoddrzewo
        '''else'''
+
12    '''else'''
            Dodaj(węzeł.prawePoddrzewo, klucz)
+
13      Dodaj(węzeł.prawePoddrzewo, klucz)
  '''end''';
+
14 '''end''';
  
 
Możemy również usuwać wartości z drzewa, niestety ta operacja jest bardziej skomplikowana.
 
Możemy również usuwać wartości z drzewa, niestety ta operacja jest bardziej skomplikowana.
  
  '''procedure''' Usuń(węzeł, klucz)  
+
'''procedure''' Usuń(węzeł, klucz)  
    '''if''' (klucz < węzeł.klucz) '''then'''
+
2    '''if''' (klucz < węzeł.klucz) '''then'''
        Usuń(węzeł.lewePoddrzewo, klucz)
+
3      Usuń(węzeł.lewePoddrzewo, klucz)
    '''else if (klucz > węzeł.klucz) '''then'''
+
4    '''else if (klucz > węzeł.klucz) '''then'''
        Usuń(węzeł.prawePoddrzewo, klucz)     
+
5      Usuń(węzeł.prawePoddrzewo, klucz)     
    '''else''' '''begin''' { klucz = węzeł.klucz
+
6    '''else''' '''begin''' { klucz = węzeł.klucz
        '''if''' ''węzeł'' jest liściem, '''then'''
+
7      '''if''' ''węzeł'' jest liściem, '''then'''
          { usuń '''węzeł''' z drzewa }
+
8        { usuń '''węzeł''' z drzewa }
          UsunProstyPrzypadek(węzeł)
+
9        UsunProstyPrzypadek(węzeł)
        '''else'''
+
10    '''else'''
          '''if''' węzeł.lewePoddrzewo <> nil '''then'''
+
11      '''if''' węzeł.lewePoddrzewo <> nil '''then'''
            niech ''x'' oznacza skrajnie prawy węzeł w poddrzewie węzeł.lewePoddrzewo
+
12        niech ''x'' oznacza skrajnie prawy węzeł w poddrzewie węzeł.lewePoddrzewo
            wezel.klucz:=x.klucz;
+
13        wezel.klucz:=x.klucz;
            UsunProstyPrzypadek(x);
+
14        UsunProstyPrzypadek(x);
          '''else'''
+
15      '''else'''
            analogiczne postępowanie dla węzeł.prawPoddrzewo  
+
16        analogiczne postępowanie dla węzeł.prawPoddrzewo  
            (jednak poszukujemy węzła na skrajnie lewej ścieżce)
+
17        (jednak poszukujemy węzła na skrajnie lewej ścieżce)
    '''end'''
+
18 '''end'''
  
 
Procedura ''UsunProstyPrzypadek'' oznacza usuwanie z drzewa węzła, który
 
Procedura ''UsunProstyPrzypadek'' oznacza usuwanie z drzewa węzła, który
 
ma co najwyżej jednego syna.
 
ma co najwyżej jednego syna.
  
  '''procedure''' UsunProstyPrzypadek(węzeł)
+
1 '''procedure''' UsunProstyPrzypadek(węzeł)
    poddrzewo:=nil;
+
2 '''begin'''
    ojciec:=węzeł.ojciec;
+
3    poddrzewo:=nil;
    '''if''' (węzeł.lewePoddrzewo) '''then'''
+
4    ojciec:=węzeł.ojciec;
      poddrzewo:=węzeł.lewePoddrzewo;
+
5    '''if''' węzeł.lewePoddrzewo <> nil '''then'''
    '''else'''     
+
6      poddrzewo:=węzeł.lewePoddrzewo;
      poddrzewo:=węzeł.prawePoddrzewo;     
+
7    '''else'''     
 +
8      poddrzewo:=węzeł.prawePoddrzewo;     
 
      
 
      
    '''if''' (ojciec=nil) '''then'''
+
9    '''if''' ojciec=nil '''then'''
      korzen:=poddrzewo;
+
10    korzen:=poddrzewo;
    '''else''' '''if''' ojciec.lewePoddrzewo=węzeł '''then''' { węzeł jest lewym synem }
+
11  '''else''' '''if''' ojciec.lewePoddrzewo=węzeł '''then''' { węzeł jest lewym synem }
      ojciec.lewePoddrzewo:=poddrzewo;
+
12    ojciec.lewePoddrzewo:=poddrzewo;
    '''else''' { węzeł jest prawym synem }
+
13  '''else''' { węzeł jest prawym synem }
      ojciec.prawePoddrzewo:=poddrzewo;
+
14    ojciec.prawePoddrzewo:=poddrzewo;
  
 
Wszystkie podane operacje mają pesymistyczny koszt <math>O(h)</math> gdzie <math>h</math>  
 
Wszystkie podane operacje mają pesymistyczny koszt <math>O(h)</math> gdzie <math>h</math>  
Linia 137: Linia 138:
 
== Adresowanie bezpośrednie ==
 
== Adresowanie bezpośrednie ==
  
W przypadku gdy zbiór, który przechowujemy pochodzi z niewielkiego uniwersum
+
W przypadku gdy zbiór, który przechowujemy, pochodzi z niewielkiego uniwersum
 
(na przykład elementy zbioru to liczby z zakresu <math>1,\ldots,n</math>),
 
(na przykład elementy zbioru to liczby z zakresu <math>1,\ldots,n</math>),
 
możemy wszystkie operacje słownikowe (dodaj, usuń, szukaj) wykonać
 
możemy wszystkie operacje słownikowe (dodaj, usuń, szukaj) wykonać
Linia 163: Linia 164:
 
Dodatkowo zakładamy, że dysponujemy tablicą <math>A[0,\ldots,m-1]</math>.
 
Dodatkowo zakładamy, że dysponujemy tablicą <math>A[0,\ldots,m-1]</math>.
  
Ponieważ elementami mogą być bardzo duże liczby całkowite, stąd nie możemy
+
Ponieważ elementami mogą być bardzo duże liczby całkowite, nie możemy
 
zastosować metody adresowania bezpośredniego.
 
zastosować metody adresowania bezpośredniego.
 
Jednak możemy wybrać '''funkcję haszującą''':
 
Jednak możemy wybrać '''funkcję haszującą''':
Linia 185: Linia 186:
 
Początkowo tablica <math>A</math> wypełniona jest wartościami '''nil'''.
 
Początkowo tablica <math>A</math> wypełniona jest wartościami '''nil'''.
  
  '''procedure''' Inicjalizacja;
+
  1 '''procedure''' Inicjalizacja;
  '''begin'''
+
  2 '''begin'''
  '''for''' i:=0 '''to''' m-1 '''do''' A[i]:='''nil''';
+
'''for''' i:=0 '''to''' m-1 '''do''' A[i]:='''nil''';
  '''end''';
+
  4 '''end''';
  
 
Dodanie elementu <math>x</math> do tablicy wymaga odczytania jego adresu z funkcji haszującej,
 
Dodanie elementu <math>x</math> do tablicy wymaga odczytania jego adresu z funkcji haszującej,
 
a następnie dodania go na początek listy <math>A[h(x)]</math>
 
a następnie dodania go na początek listy <math>A[h(x)]</math>
  
  '''procedure''' Dodaj(x);
+
  1 '''procedure''' Dodaj(x);
  '''begin'''
+
  2 '''begin'''
  dodaj element <math>x</math> na początek listy <math>A[h(x)]</math>
+
dodaj element <math>x</math> na początek listy <math>A[h(x)]</math>
  '''end''';
+
  4 '''end''';
  
 
Sprawdzenie, czy element <math>x</math> jest w zbiorze, wymaga w pesymistycznym przypadku sprawdzenia całej listy <math>A[h(x)]</math>
 
Sprawdzenie, czy element <math>x</math> jest w zbiorze, wymaga w pesymistycznym przypadku sprawdzenia całej listy <math>A[h(x)]</math>
  
  '''function''' Szukaj(x);
+
  1 '''function''' Szukaj(x);
  '''begin'''
+
  2 '''begin'''
  l:=A[h(x)];
+
l:=A[h(x)];
  '''while''' (l!='''nil''') '''do''' '''begin'''
+
'''while''' (l!='''nil''') '''do''' '''begin'''
      '''if''' (l.wartość=x) '''then''' '''return''' element istnieje
+
5      '''if''' (l.wartość=x) '''then''' '''return''' element istnieje
      l:=l.nast;
+
6      l:=l.nast;
  '''end''';
+
'''end''';
  '''return''' brak elementu
+
'''return''' brak elementu
  '''end''';
+
  9 '''end''';
  
 
Usuwanie elementu z tablicy jest bardzo podobne do wyszukiwania i również w pesymistycznym przypadku wymaga sprawdzenia całej listy.
 
Usuwanie elementu z tablicy jest bardzo podobne do wyszukiwania i również w pesymistycznym przypadku wymaga sprawdzenia całej listy.
  
  '''procedure''' Usuń(x);
+
1 '''procedure''' Usuń(x);
  '''begin'''
+
2 '''begin'''
  l:=A[h(x)];p:=nil;
+
l:=A[h(x)];p:=nil;
  '''while''' (l!='''nil''') '''do''' '''begin'''
+
'''while''' (l!='''nil''') '''do''' '''begin'''
      '''if''' (l.wartość=x) '''then''' '''begin'''
+
5    '''if''' (l.wartość=x) '''then''' '''begin'''
        { usuwamy element l z listy A[h(x)] }
+
6      { usuwamy element l z listy A[h(x)] }
        '''if''' p='''nil''' '''then''' A[h(x)]:=l.nast;
+
7      '''if''' p='''nil''' '''then''' A[h(x)]:=l.nast;
        '''else''' p.nast:=l.nast;
+
8      '''else''' p.nast:=l.nast;
        '''return''';
+
9      '''return''';
      '''end'''
+
10    '''end'''
      p:=l; l:=l.nast;
+
11    p:=l; l:=l.nast;
  '''end''';
+
12  '''end''';
  '''end''';
+
  13 '''end''';
 +
 
 +
=== Analiza metody łańcuchowej ===
 +
 
 +
Haszowanie to metoda, która bardzo dobrze sprawdza się w praktyce, zastanówmy się przez chwilę,
 +
czy dobre własności tej metody można udowodnić.
 +
 
 +
Niech:
 +
* ''m'' oznacza rozmiar tablicy,
 +
* ''n'' oznacza liczbę elementów, które przetrzymujemy w tablicy,
 +
* przez <math>\alpha</math> oznaczamy współczynnik zapełniania tablicy <math>\frac{n}{m}</math>
 +
 
 +
Załóżmy, że dysponujemy ''idealną'' funkcją haszującą, dla której
 +
przypisanie każda wartość <math>h(x)</math> jest równie prawdopodobna, czyli
 +
<math>P(\{h(x)=i\})=\frac{1}{m}</math>.
 +
 
 +
Przy takim założeniu oczekiwana długość listy elementów <math>A[h(x)]</math>
 +
ma długość <math>\frac{n}{m}</math> (oczekiwana liczba sukcesów w ''n'' próbach Bernoulli'ego).
 +
 
 +
Stąd oczekiwana złożoność operacji ''Szukaj'', ''Dodaj'', ''Usuń'' wynosi:
 +
<center><math>T(n,m)=\frac{n}{m}+O(1)</math></center>
  
 
=== Wybór funkcji haszujących ===
 
=== Wybór funkcji haszujących ===
Linia 237: Linia 258:
 
* <math>f_{a,b}(x)=((ax+b)\,\mod\, p)\ \mod\ m</math> (gdzie <math>p</math> jest liczbą pierwszą, <math>1\le a < p</math>, <math>0 \le b < p</math>).
 
* <math>f_{a,b}(x)=((ax+b)\,\mod\, p)\ \mod\ m</math> (gdzie <math>p</math> jest liczbą pierwszą, <math>1\le a < p</math>, <math>0 \le b < p</math>).
  
Jeśli nie dysponujemy żadną dodatkową wiedzą na temat elementów które będzie zawierać tablica, to rozsądnym
+
Jeśli nie dysponujemy żadną dodatkową wiedzą na temat elementów które będzie zawierać tablica, rozsądnym
rozwiązanie jest wybór funkcji <math>f_{a,b}</math> dla losowych wartości <math>a,b</math>.
+
rozwiązaniem jest wybór funkcji <math>f_{a,b}</math> dla losowych wartości <math>a,b</math>.
  
 
=== Adresowanie otwarte ===
 
=== Adresowanie otwarte ===
Linia 259: Linia 280:
 
przez funkcję <math>H(x,k)</math>.
 
przez funkcję <math>H(x,k)</math>.
  
  '''function''' Szukaj(x);
+
  1 '''function''' Szukaj(x);
  '''begin'''
+
  2 '''begin'''
  k:=0;
+
k:=0;
  '''while''' (A[H(x,k)!='''nil''') '''do''' '''begin'''
+
'''while''' (A[H(x,k)!='''nil''') '''do''' '''begin'''
      '''if''' (A[H(x,k)].wartość=x) '''then''' '''return''' element istnieje
+
5      '''if''' (A[H(x,k)].wartość=x) '''then''' '''return''' element istnieje
      k:=k+1;
+
6      k:=k+1;
  '''end''';
+
'''end''';
  '''return''' brak elementu
+
'''return''' brak elementu
  '''end''';
+
  9 '''end''';
  
 
Wstawianie elementów możemy wykonać przez analogiczne modyfikacje; usuwanie jest zwykle znacznie trudniejsze.
 
Wstawianie elementów możemy wykonać przez analogiczne modyfikacje; usuwanie jest zwykle znacznie trudniejsze.
Linia 284: Linia 305:
 
na wartość 1.
 
na wartość 1.
  
  '''procedure''' Dodaj(x);
+
  1 '''procedure''' Dodaj(x);
  '''begin'''
+
  2 '''begin'''
  '''for''' i:=1 '''to''' k '''do''' A[<math>h_i(x)</math>]:=1;
+
'''for''' i:=1 '''to''' k '''do''' A[<math>h_i(x)</math>]:=1;
  '''end''';
+
  4 '''end''';
  
 
Analogicznie, sprawdzenie, czy element ''x'' należy do zbioru, wymaga sprawdzenia bitów <math>A[h_i(x)]</math> dla <math>i=1,\ldots,k</math>.
 
Analogicznie, sprawdzenie, czy element ''x'' należy do zbioru, wymaga sprawdzenia bitów <math>A[h_i(x)]</math> dla <math>i=1,\ldots,k</math>.
 
Jeśli wszystkie mają wartość 1, to uznajemy, że element należy do zbioru.  
 
Jeśli wszystkie mają wartość 1, to uznajemy, że element należy do zbioru.  
 
Oczywiście powoduje to pewien odsetek błędnych odpowiedzi.  
 
Oczywiście powoduje to pewien odsetek błędnych odpowiedzi.  
Jednak jeśli dobrze dobierzemy funkcje, a wypełnienie tablicy nie będzie zbyt duże,  
+
Jeśli jednak dobrze dobierzemy funkcje, a wypełnienie tablicy nie będzie zbyt duże,  
 
to taka struktura będzie dobrze sprawować się w praktyce.
 
to taka struktura będzie dobrze sprawować się w praktyce.
  
  '''function''' Szukaj(x);
+
  1 '''function''' Szukaj(x);
  '''begin'''
+
  2 '''begin'''
  '''for''' i:=1 '''to''' k '''do'''  
+
'''for''' i:=1 '''to''' k '''do'''  
    '''if''' A[<math>h_i(x)</math>]=0 '''then''' '''return''' brak elementu
+
4    '''if''' A[<math>h_i(x)</math>]=0 '''then''' '''return''' brak elementu
  '''return''' element istnieje
+
'''return''' element istnieje
  '''end''';
+
  6 '''end''';
  
==Literatura==
 
<span id="CLRS">[CLRS]</span> Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 'Wprowadzenie do algorytmów', WNT, Warszawa 2004.
 
  
----
 
  
 
[[Algorytmy_i_struktury_danych|powrót do strony przedmiotu]]
 
[[Algorytmy_i_struktury_danych|powrót do strony przedmiotu]]

Aktualna wersja na dzień 11:07, 11 sty 2007

Wyszukiwanie


W niniejszym wykładzie opiszemy podstawowe techniki dotyczące wyszukiwania. Zajmiemy się również prostymi strukturami słownikowymi, które oprócz wyszukiwania umożliwiają dodawanie i usuwanie elementów.


Wyszukiwanie liniowe

Jeśli nie dysponujemy żadną dodatkową wiedzą na temat zbioru, który chcemy przeszukiwać, niestety musimy sprawdzić wszystkie jego elementy.

1 function Szukaj(x, A[1..n])
2 begin
3   for i:=1 to n do
4     if A[i]=x return i;
5   return brak poszukiwanego elementu;
6 end

Oczywiście w pesymistycznym przypadku (np. gdy zbiór nie zawiera poszukiwanego elementu) koszt czasowy, to .

Wyszukiwanie binarne

W niektórych przypadkach czas poszukiwania możemy znacząco zmniejszyć. Dzieje się tak na przykład, gdy przeszukiwany zbiór przechowujemy w rosnąco uporządkowanej tablicy. W takim przypadku wystarczy jedynie operacji, by odnaleźć poszukiwany element lub stwierdzić jego brak.

Algorytm utrzymuje zakres , w którym może znajdować się element; przy każdym porównaniu zakres zostaje zmniejszony o połowę.

1  function WyszukiwanieBinarne(x, A[1..n])
2  { zakładamy, że tablica A jest uporządkowana rosnąco }
3  begin
4    l:=1;r:=n;
5    while (l<=r) do begin
6      { niezmiennik: poszukiwany element może znajdować się w zakresie A[l..r] }
7      m:=(l+r) div 2;
8      if (A[m]<x) then l:=m+1
9      else if (A[m]>x) then r:=m-1
10     else return m; { ponieważ A[m]=x } 
11   end;
12   return brak poszukiwanego elementu;
13 end;

Proste słowniki: drzewa poszukiwań binarnych

Podstawowe operacje słownika to wyszukiwanie, wstawianie i usuwanie klucza. Drzewa poszukiwań binarnych (bez dodatkowych specjanych wymagań) mogą być traktowane jako prosty słownik. Sa to zwykłe drzewa binarne, których klucze spełniają następujące własności:

Dla dowolnego węzła x:

  • wszystkie klucze w lewym poddrzewie węzła x mają wartości mniejsze niż klucz węzła x,
  • wszystkie klucze w prawym poddrzewie węzła x mają wartości większe lub równe niż klucz węzła x.
Wyszukiwanie.1.png

Dodatkowe wymaganie dotyczące kluczy umożliwia nam efektywne wyszukiwanie elementów w drzewie.

1  function Szukaj(węzeł, klucz)
2     if (węzeł==nil) 
3        return BRAK ELEMENTU
4     if (węzeł.klucz=klucz) then
5        return ELEMENT ISTNIEJE
6      else if (klucz < węzeł.klucz) then
7       return Szukaj(węzeł.lewePoddrzewo, klucz)
8     else if (klucz > węzeł.klucz) then
9        return Szukaj(węzeł.prawPoddrzewo, klucz)
10  end;

Wstawianie do drzewa jest bardzo zbliżone do wyszukiwania: musimy przejść po drzewie (rozpoczynając w korzeniu), aby odnaleźć wolne miejsce, w którym możemy dodać nową wartość.

1  procedure Dodaj(węzeł, klucz)
2    if (klucz < węzeł.klucz) then
3      if węzeł.lewePoddrzewo=nil then
4        utwórz nowy węzeł z wartością klucz
5        wskaźnik do nowego węzła zapisujemy w węzeł.lewePoddrzewo
6      else
7        Dodaj(węzeł.lewePoddrzewo, klucz)
8    else if (klucz >= węzeł.klucz) then
9      if węzeł.prawePoddrzewo=nil then
10       utwórz nowy węzeł z wartością klucz
11       wskaźnik do nowego węzła zapisujemy w węzeł.prawePoddrzewo
12     else
13       Dodaj(węzeł.prawePoddrzewo, klucz)
14 end;

Możemy również usuwać wartości z drzewa, niestety ta operacja jest bardziej skomplikowana.

1  procedure Usuń(węzeł, klucz) 
2    if (klucz < węzeł.klucz) then
3      Usuń(węzeł.lewePoddrzewo, klucz)
4    else if (klucz > węzeł.klucz) then
5      Usuń(węzeł.prawePoddrzewo, klucz)    
6    else begin { klucz = węzeł.klucz
7      if węzeł jest liściem, then
8        { usuń węzeł z drzewa }
9        UsunProstyPrzypadek(węzeł)
10     else
11       if węzeł.lewePoddrzewo <> nil then
12         niech x oznacza skrajnie prawy węzeł w poddrzewie węzeł.lewePoddrzewo
13         wezel.klucz:=x.klucz;
14         UsunProstyPrzypadek(x);
15       else
16         analogiczne postępowanie dla węzeł.prawPoddrzewo 
17         (jednak poszukujemy węzła na skrajnie lewej ścieżce)
18 end

Procedura UsunProstyPrzypadek oznacza usuwanie z drzewa węzła, który ma co najwyżej jednego syna.

1 procedure UsunProstyPrzypadek(węzeł)
2 begin
3    poddrzewo:=nil;
4    ojciec:=węzeł.ojciec;
5    if węzeł.lewePoddrzewo <> nil then
6      poddrzewo:=węzeł.lewePoddrzewo;
7    else    
8      poddrzewo:=węzeł.prawePoddrzewo;    
   
9    if ojciec=nil then
10     korzen:=poddrzewo;
11   else if ojciec.lewePoddrzewo=węzeł then { węzeł jest lewym synem }
12     ojciec.lewePoddrzewo:=poddrzewo;
13   else { węzeł jest prawym synem }
14     ojciec.prawePoddrzewo:=poddrzewo;

Wszystkie podane operacje mają pesymistyczny koszt gdzie oznacza wysokość drzewa. Niestety w najgorszym przypadku drzewo może mieć bardzo dużą wysokość -- nawet (np. dla ciągu operacji Dodaj ).

Adresowanie bezpośrednie

W przypadku gdy zbiór, który przechowujemy, pochodzi z niewielkiego uniwersum (na przykład elementy zbioru to liczby z zakresu ), możemy wszystkie operacje słownikowe (dodaj, usuń, szukaj) wykonać znacznie szybciej i prościej.

Dla uniwersum zbiór możemy reprezentować przez tablicę -elementową. Początkowo w każdej komórce tablicy wpisujemy wartość false.

  • dodanie elementu do zbioru wymaga jedynie ustawienia wartości -tej komórki na true,
  • analogicznie, usunięcie elementu do zbioru wymaga ustawienia wartości -tej komórki na false,
  • sprawdzenie, czy element należy do zbioru, wykonujemy przez sprawdzenie stanu -tej komórki.

Wszystkie powyższe operacje możemy wykonać używając stałej liczby kroków.

Haszowanie

Czy możemy wykorzystać adresowanie bezpośrednie do dowolnych zbiorów? Okazuje się, że tak. Co prawda w pesymistycznym przypadku koszt jednej operacji może wynosić nawet , jednak w praktycznych zastosowaniach ta metoda sprawuje się doskonale.

W tym rozdziale będziemy zakładać, że elementy uniwersum to dodatnie liczby całkowite. Dodatkowo zakładamy, że dysponujemy tablicą .

Ponieważ elementami mogą być bardzo duże liczby całkowite, nie możemy zastosować metody adresowania bezpośredniego. Jednak możemy wybrać funkcję haszującą:

Funkcja każdemu elementowi uniwersum przypisuje odpowiednie miejsce w tablicy . Jeśli , to z oczywistych względów znajdą się takie pary różnych elementów , dla których . W takim przypadku mówimy o istnieniu kolizji. Właśnie ze względu na ryzyko wystąpienia kolizji musimy nieznacznie zmodyfikować metodę adresowania bezpośredniego - zamiast przechowywać w tablicy wartość logiczną (prawda/fałsz), musimy zapisywać wartość przechowywanego elementu.

Rozwiązywanie kolizji metodą łańcuchową

Jedną z metod rozwiązywania kolizji jest utrzymywanie w każdej komórce tablicy listy elementów do niej przypisanych. Początkowo tablica wypełniona jest wartościami nil.

1 procedure Inicjalizacja;
2 begin
3   for i:=0 to m-1 do A[i]:=nil;
4 end;

Dodanie elementu do tablicy wymaga odczytania jego adresu z funkcji haszującej, a następnie dodania go na początek listy

1 procedure Dodaj(x);
2 begin
3   dodaj element  na początek listy 
4 end;

Sprawdzenie, czy element jest w zbiorze, wymaga w pesymistycznym przypadku sprawdzenia całej listy

1 function Szukaj(x);
2 begin
3   l:=A[h(x)];
4   while (l!=nil) do begin
5      if (l.wartość=x) then return element istnieje
6      l:=l.nast;
7   end;
8   return brak elementu
9 end;

Usuwanie elementu z tablicy jest bardzo podobne do wyszukiwania i również w pesymistycznym przypadku wymaga sprawdzenia całej listy.

1  procedure Usuń(x);
2  begin
3   l:=A[h(x)];p:=nil;
4   while (l!=nil) do begin
5     if (l.wartość=x) then begin
6       { usuwamy element l z listy A[h(x)] }
7       if p=nil then A[h(x)]:=l.nast;
8       else p.nast:=l.nast;
9       return;
10    end
11    p:=l; l:=l.nast;
12  end;
13 end;

Analiza metody łańcuchowej

Haszowanie to metoda, która bardzo dobrze sprawdza się w praktyce, zastanówmy się przez chwilę, czy dobre własności tej metody można udowodnić.

Niech:

  • m oznacza rozmiar tablicy,
  • n oznacza liczbę elementów, które przetrzymujemy w tablicy,
  • przez oznaczamy współczynnik zapełniania tablicy

Załóżmy, że dysponujemy idealną funkcją haszującą, dla której przypisanie każda wartość jest równie prawdopodobna, czyli .

Przy takim założeniu oczekiwana długość listy elementów ma długość (oczekiwana liczba sukcesów w n próbach Bernoulli'ego).

Stąd oczekiwana złożoność operacji Szukaj, Dodaj, Usuń wynosi:

Wybór funkcji haszujących

Od wyboru dobrej funkcji haszującej w dużej mierze zależy efektywność naszej struktury danych. Niestety, nie można podać ścisłej procedury wyboru takiej funkcji.

Dla liczb całkowitych możemy przykładowo wybrać jedną z następujących funkcji ( oznacza rozmiar tablicy):

  • (gdzie jest liczbą pierwszą);
  • (gdzie są liczbami pierwszymi);
  • (gdzie jest liczbą pierwszą, , ).

Jeśli nie dysponujemy żadną dodatkową wiedzą na temat elementów które będzie zawierać tablica, rozsądnym rozwiązaniem jest wybór funkcji dla losowych wartości .

Adresowanie otwarte

Adresowanie otwarte jest metodą pozwalającą uniknąć utrzymywania list elementów w tablicy haszującej. Oczywiście wymaga to opracowania innej metody rozwiązywania konfliktów. Każda komórka tablicy zawiera teraz wartość NIL lub element zbioru.

Niech oznacza rozmiar tablicy haszującej. Zdefiniujmy funkcję , wyznaczającą listę pozycji , na których może znajdować się element .

Mając daną funkcję , możemy zdefiniować , jako:

  • --- adresowanie liniowe;
  • --- adresowanie kwadratowe;
  • --- podwójne haszowanie, przy czym jest funkcją haszującą, która przyjmuje wartości z zakresu .

Wyszukiwanie elementów możemy wykonać nieznacznie modyfikując poprzednie rozwiązanie -- zamiast przeszukiwać listę elementów, musimy przeszukać ciąg pozycji zdefiniowany przez funkcję .

1 function Szukaj(x);
2 begin
3   k:=0;
4   while (A[H(x,k)!=nil) do begin
5      if (A[H(x,k)].wartość=x) then return element istnieje
6      k:=k+1;
7   end;
8   return brak elementu
9 end;

Wstawianie elementów możemy wykonać przez analogiczne modyfikacje; usuwanie jest zwykle znacznie trudniejsze.

Filtry Bloom'a

Ciekawym połączeniem adresowania bezpośredniego z haszowaniem są filtry Bloom'a. Polegają one na rozlużnieniu założeń naszej struktury:

  • ograniczamy się do operacji Dodaj i Szukaj,
  • pozwalamy na nieprawidłowe odpowiedzi dla operacji Szukaj (jednak z małym prawdopodobieństwem).

Nasza struktura to bitowa tablica o rozmiarze m, początkowo tablica jest wypełniona zerami. Zakładamy również, że mamy do dyspozycji k funkcji haszujących .

Dodanie elementu x sprowadza się do ustawienia wszystkich bitów dla na wartość 1.

1 procedure Dodaj(x);
2 begin
3   for i:=1 to k do A[]:=1;
4 end;

Analogicznie, sprawdzenie, czy element x należy do zbioru, wymaga sprawdzenia bitów dla . Jeśli wszystkie mają wartość 1, to uznajemy, że element należy do zbioru. Oczywiście powoduje to pewien odsetek błędnych odpowiedzi. Jeśli jednak dobrze dobierzemy funkcje, a wypełnienie tablicy nie będzie zbyt duże, to taka struktura będzie dobrze sprawować się w praktyce.

1 function Szukaj(x);
2 begin
3   for i:=1 to k do 
4     if A[]=0 then return brak elementu
5   return element istnieje
6 end;


powrót do strony przedmiotu