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ą więdzą 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.

TODO -- przykładowe drzewo

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

 function Szukaj(wezel, klucz)
    if (wezel==nil) 
       return BRAK ELEMENTU
    if (wezel.klucz=klucz) then
       return ELEMENT ISTNIEJE
     else if (klucz < wezel.klucz) then
       return Szukaj(wezel.lewePoddrzewo, klucz)
    else if (klucz > wezel.klucz) then
       return Szukaj(wezel.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(wezel, klucz)
    if (klucz < wezel.klucz) then
       if wezel.lewePoddrzewo=nil then
           utwórz nowy węzeł z wartością klucz
           wskaźnik do nowego węzła zapisujemy w wezel.lewePoddrzewo
       else
           Dodaj(wezel.lewePoddrzewo, klucz)
    else if (klucz >= wezel.klucz) then
       if wezel.prawePoddrzewo=nil then
           utwórz nowy węzeł z wartością klucz
           wskaźnik do nowego węzła zapisujemy w wezel.prawePoddrzewo
       else
           Dodaj(wezel.prawePoddrzewo, klucz)
 end;

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

 procedure Usun(wezel, klucz) 
   if (klucz < wezel.klucz) then
       Usun(wezel.lewePoddrzewo, klucz)
    else if (klucz > wezel.klucz) then
       Usun(wezel.prawePoddrzewo, klucz)    
    else begin { klucz = wezel.klucz
       if wezel jest liściem, then
         { usuń wezel z drzewa }
         UsunProstyPrzypadek(wezel)
       else
         if wezel.lewePoddrzewo <> nil then
           niech x oznacza skrajnie prawy węzeł w poddrzewie wezel.lewePoddrzewo
           wezel.klucz:=x.klucz;
           UsunProstyPrzypadek(x);
         'else
           analogiczne postępowanie dla wezel.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(wezel)
   poddrzewo:=nil;
   ojciec:=wezel.ojciec;
   if (wezel.lewePoddrzewo) then
     poddrzewo:=wezel.lewePoddrzewo;
   else    
     poddrzewo:=wezel.prawePoddrzewo;    
   
   if (ojeciec=nil) then
     korzen:=poddrzewo;
   else if ojciec.lewePoddrzewo=wezel then { węzeł jest lewym synem }
     ojciec.lewePoddrzewo:=podrzewo;
   else { węzeł jest prawym synem }
     ojciec.prawePoddrzewo:=podrzewo;

Wszystkie podane operacje mają pesymistyczny koszt $O(h)$ gdzie $h$ oznacza wysokość drzewa. Niestety w nagorszym 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 wszyskie 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.

TODO

• prosty przykład
• metody rozwiązywania konfliktów
• haszowanie podwójne
• haszowanie doskonałe

---

powrót do strony przedmiotu