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

TODO

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

Wyszukiwanie binarne

TODO

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
    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;

TODO

• usuwanie

Haszowanie

TODO