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 węzły dodatkowo przechowują klucze. Dodatkowo wymagamy by klucze spełniały następującą własność:

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 ELEMENY ISTNIEJE
     else if (klucz < wezel.klucz) then
       return Szukaj(wezel.lewePoddrzewo, klucz)
    else if (klucz > wezel.klucz) then
       return Szukaj(wezel.prawPoddrzewo, klucz)
 end;

TODO

• wstawianie
• usuwanie

Haszowanie

TODO