Algorytmy i struktury danych/Wyszukiwanie

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ć, to niestety musimy sprawdzić wszystkie jego elementy.

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

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

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 $O (\log n)$ operacji, by odnaleźć poszukiwany element, lub stwierdzić jego brak.

Algorytm utrzymuje zakres $[l, \dots, r]$ , w którym może znajdować się element, przy każdym porównaniu zakres zostaje zmniejszony o połowę.

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

Drzewa poszukiwań binarnych

Drzewa poszukiwań binarnych, 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 lewym poddrzewie węzła x, mają wartości większe lub równe niż klucz węzła x.

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

 function Szukaj(węzeł, klucz)
    if (węzeł==nil) 
       return BRAK ELEMENTU
    if (węzeł.klucz=klucz) then
       return ELEMENT ISTNIEJE
     else if (klucz < węzeł.klucz) then
       return Szukaj(węzeł.lewePoddrzewo, klucz)
    else if (klucz > węzeł.klucz) then
       return Szukaj(węzeł.prawPoddrzewo, klucz)
 end;

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

 procedure Dodaj(węzeł, klucz)
    if (klucz < węzeł.klucz) then
       if węzeł.lewePoddrzewo=nil then
           utwórz nowy węzeł z wartością klucz
           wskaźnik do nowego węzła zapisujemy w węzeł.lewePoddrzewo
       else
           Dodaj(węzeł.lewePoddrzewo, klucz)
    else if (klucz >= węzeł.klucz) then
       if węzeł.prawePoddrzewo=nil then
           utwórz nowy węzeł z wartością klucz
           wskaźnik do nowego węzła zapisujemy w węzeł.prawePoddrzewo
       else
           Dodaj(węzeł.prawePoddrzewo, klucz)
 end;

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

 procedure Usuń(węzeł, klucz) 
   if (klucz < węzeł.klucz) then
       Usuń(węzeł.lewePoddrzewo, klucz)
    else if (klucz > węzeł.klucz) then
       Usuń(węzeł.prawePoddrzewo, klucz)    
    else begin { klucz = węzeł.klucz
       if węzeł jest liściem, then
         { usuń węzeł z drzewa }
         UsunProstyPrzypadek(węzeł)
       else
         if węzeł.lewePoddrzewo <> nil then
           niech x oznacza skrajnie prawy węzeł w poddrzewie węzeł.lewePoddrzewo
           wezel.klucz:=x.klucz;
           UsunProstyPrzypadek(x);
         'else
           analogiczne postępowanie dla węzeł.prawPoddrzewo 
           (jednak poszukujemy węzła na skrajnie lewej ścieżce)
    end

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

 procedure UsunProstyPrzypadek(węzeł)
   poddrzewo:=nil;
   ojciec:=węzeł.ojciec;
   if (węzeł.lewePoddrzewo) then
     poddrzewo:=węzeł.lewePoddrzewo;
   else    
     poddrzewo:=węzeł.prawePoddrzewo;    
   
   if (ojciec=nil) then
     korzen:=poddrzewo;
   else if ojciec.lewePoddrzewo=węzeł then { węzeł jest lewym synem }
     ojciec.lewePoddrzewo:=poddrzewo;
   else { węzeł jest prawym synem }
     ojciec.prawePoddrzewo:=poddrzewo;

Wszystkie podane operacje mają pesymistyczny koszt $O (h)$ gdzie $h$ oznacza wysokość drzewa. Niestety w najgorszym przypadku drzewo może mieć wysokość nawet $O (n)$ (np. dla ciągu operacji Dodaj $(1, 2, 3, \dots)$ ).

Adresowanie bezpośrednie

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

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

dodanie elementu $i$ do zbioru, wymaga jedynie ustawienia wartości $i$ -tej komórki na true,
analogicznie usunięcie elementu $i$ do zbioru, wymaga ustawienia wartości $i$ -tej komórki na false,
sprawdzenie czy element $i$ należy do zbioru wykonujemy przez sprawdzenie stanu $i$ -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 $O (n)$ , jednak w praktycznych zastosowaniach ta metoda sprawuje się doskonale.

W tym rozdziale będziemy zakładać, że elementy uniwersum $U$ , to dodatnie liczby całkowite. Dodatkowo zakładamy, że dysponujemy tablicą $A [0, \dots, m - 1]$ .

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

$h : U \to 0, \dots, m - 1$

Funkcja ta dla każdego elementu uniwersum przypisuje odpowiednie miejsce w tablicy $A$ . Jeśli $| U | > m$ , to z oczywistych względów znajdą się takie pary różnych elementów $x, y \in U$ , dla których $f (x) = f (y)$ . 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 $A$ wypełniona jest wartościami nil.

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

Dodanie elementu $x$ do tablicy, wymaga odczytania jego adresu z funkcji haszującej, a następnie dodania go na początek listy $A [h (x)]$

procedure Dodaj(x);
begin
  dodaj element  $x$  na początek listy  $A [h (x)]$ 
end;

Sprawdzenie czy element $x$ istnieje, wymaga w pesymistycznym przypadku sprawdzenia całej listy $A [h (x)]$

function Szukaj(x);
begin
  l:=A[h(x)];
  while (l!=nil) do begin
     if (l.wartość=x) then return element istnieje
     l:=l.nast;
  end;
  return brak elementu
end;

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

procedure Usuń(x);
begin
  l:=A[h(x)];p:=nil;
  while (l!=nil) do begin
     if (l.wartość=x) then begin
        { usuwamy element l z listy A[h(x)] }
        if p=nil then A[h(x)]:=l.nast;
        else p.nast:=l.nast;
        return;
     end
     p:=l; l:=l.nast;
  end;
end;

Wybór funkcji haszujących

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

Dla liczb całkowitych, możemy wybrać funkcję:

$f (x) = x mod p$ (gdzie $p$ jest liczbą pierwszą), lub
$f (x) = q x mod p$ (gdzie $p, q$ są liczbami pierwszymi).

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. Używając tej metody, każda komórka tablicy zawiera wartość NIL lub element zbioru.

Niech $m$ ozncza rozmiar tablicy haszującej. Zdefiniujmy funkcję $H (x, k)$ , która wyznacza listę pozycji $H (x, 0), \dots, H (x, m - 1)$ w których może znajdować się element $x$ .

Mając daną funkcję $h (x)$ możemy zdefiniować $H (x, k)$ , jako:

$H (x, k) = (h (x) + k) mod m$ --- adresowanie liniowe,
$H (x, k) = (h (x) + a_{1} \cdot k + a_{2} \cdot k^{2}) mod m$ --- adresowanie kwadratowe,
$H (x, k) = (h (x) + h_{2} (x) \cdot k) mod m$ --- podwójne haszowanie.

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ę $H (x, k)$

powrót do strony przedmiotu

Algorytmy i struktury danych/Wyszukiwanie

Spis treści

Wyszukiwanie liniowe

Wyszukiwanie binarne

Drzewa poszukiwań binarnych

Adresowanie bezpośrednie

Haszowanie

Rozwiązywanie kolizji metodą łańcuchową

Wybór funkcji haszujących

Adresowanie otwarte

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia