Uniwersytet Śląski

Wydział Informatyki i Nauki o Materiałach

Paweł Grzesica

Nr albumu: 251956

Analiza i złożoność obliczeniowa algorytmów

Wyszukiwanie binarne(połówkowe) oraz drzewa poszukiwań binarnych (BST)

Sosnowiec, 2013

Spis treści

Wstęp ………………………………………………………………………………………… 2

1. Pojęcie wyszukiwania ……………………………………………………………………. 3

2. Wyszukiwanie binarne …………………………………………………………………... 3

2.1. Pojęcie i algorytmy wyszukiwania binarnego ………………………………… 3

2.2. Złożoności obliczeniowe ………………………………………………………... 4

2.3. Schemat blokowy ……………………………………………………………….. 6

3. Drzewa przeszukiwań binarnych ……………………………………………………….. 7

3.1. Pojęcie i algorytmy drzew poszukiwań binarnych …………………………… 7

3.2. Złożoności obliczeniowe ………………………………………………………... 8

3.3. Drzewa AVL ……………………………………………………………………. 9

Zakończenie ………………………………………………………………………………... 11

Wstęp

Przeszukiwanie algorytmów w dużej mierze zależy od posiadanego zbioru danych i jego ustrukturyzowana. Świadomość tego pozwala na wybór najlepszego i najszybszego w danej chwili narzędzia. Praca ma na celu zaprezentowanie dwóch metod przeszukiwania posortowanych danych, ich wad oraz zalet.

Praca składa się z trzech części teoretycznych, poprzedzonych wstępem. W pierwszej części została omówiona definicja wyszukiwania oraz jego rodzaje. W drugiej części zaprezentowano wyszukiwanie binarne, algorytm i jego schemat, złożoności obliczeniowe oraz jego wady i zalety. W trzeciej części skupiono się na drzewach wyszukiwań binarnych, ich własnościach i złożoności oraz na specyficznym rodzaju drzew binarnych, jakim jest drzewo AVL.

W pracy wykorzystano analizę literatury zwartej oraz artykuły specjalistyczne udostępnione za pośrednictwem internetowych serwisów w kraju, a także analizę danych dotyczących wyszukiwania binarnego i drzew BST na stronach w sieci Internet. Najbardziej pomocne okazały się źródła internetowe, dostarczając najwięcej danych na temat problematyki pracy.

1. Pojęcie wyszukiwania

Algorytm jest ciągiem kroków obliczeniowych, mającym na celu przekształcenie danych wejściowych w wyjściowe. Jest on więc rozwiązaniem konkretnego problemu obliczeniowego. W zależności od potrzeb istnieją różne typy algorytmów, jak algorytm sortowania, selekcji, wstawiania, usuwania etc.

Algorytm wyszukiwania jest jednym z najczęściej stosowanych. Wyszukiwanie jest sposobem, za pomocą którego przeszukuje się zbiór danych (najczęściej w postaci tablicy) w celu znalezienia wymaganych zmiennych.

Istnieje wiele algorytmów wyszukiwania :

• wyszukiwanie liniowe,

• wyszukiwanie liniowe z wartownikiem,

• wyszukiwanie linowe w posortowanej tablicy,

• wyszukiwanie binarne (połówkowe/logarytmiczne),

• drzewa przeszukiwań binarnych (BST),

• haszowanie.

Uwaga w niniejszej pracy zostanie poświęcona wyszukiwaniu binarnemu (połówkowemu) oraz drzewom przeszukiwań binarnych (BST). Oba wyszukiwania oparte są na metodzie „dziel i zwyciężaj” (rekurencja opierająca się na podziale jednego poziomu rekursji na trzy etapy).

2. Wyszukiwanie binarne

2.1. Pojęcie i algorytmy wyszukiwania binarnego

Szukanie binarne, zwane również połówkowym, jest szybką metodą wyszukiwania elementów w czasie logarytmicznym w posortowanych tablicach, skąd bierze swoją nazwę. W przypadku znalezienia szukanej podaje jej indeks w tablicy. Sortowanie może być dowolne, w zależności od wymagań: rosnące, malejące etc.

Rozpoczęcie przeszukiwania tablic rozpoczyna się w momencie dzielenia na coraz mniejsze podtablice. Algorytm rozpoczyna swoje działanie od przeszukania całej tablicy. W pojedynczym kroku wyszukuje się indeksy początkowy i końcowy. Po wyznaczeniu środka przedziału tych indeksów, sprawdzana jest jego poprawność – gdy indeks środkowy jest poszukiwanym, algorytm kończy działanie. W przeciwnym wypadku algorytm sprawdza położenie poszukiwanej wartości i, w zależności od tego, czy znajduje się ona bliżej początku (lewej części badanej tablicy) czy końca indeksu (prawej strony badanej tablicy), procedura jest powtarzana od nowa.

Przykładowy algorytm wyszukiwania binarnego:

procedure wyszukiwanie binarne(x: typ klucza;

var jest: Boolean ;

var m: 1 .. n);

var lewy, prawy: 0 .. n + 1;

begin

lewy := 1; prawy := n; jest := false ; repeat

m := (lewy + prawy) div 2;

if A[m].klucz = x then

jest := true ;

else

if A[m].klucz < x then

lewy := m + 1;

else

prawy := m − 1;

end if;

end if;

until jest or (lewy > prawy);

end; {wyszukiwanie binarne}

2.2. Złożoności obliczeniowe

Złożoność obliczeniowa pozwala oszacować czas potrzebny do wykonania algorytmu. Złożoność tę wyznacza zależność czasu potrzebnego do wykonania algorytmu od rozmiaru danych wejściowych (najczęściej jest to ich ilość). Na złożoność obliczeniową algorytmu składa się złożoność czasowa i złożoność pamięciowa. W przypadku algorytmów można wyróżnić kilka rodzajów złożoności matematycznych:

• stała,

• logarytmiczna,

• liniowa,

• liniowo-logarytmiczna,

• kwadratowa,

• wykładnicza.

Złożoność czasowa jest zależnością pomiędzy liczbą operacji elementarnych wykonywanych w trakcie przebiegu algorytmu, a rozmiarem danych wejściowych. Wynika z liczby operacji elementarnych wykonywanych w trakcie przebiegu algorytmu i decyduje o tym, czy dany algorytm jest przydatny. O złożoności czasowej decyduje liczba wykonywanych iteracji

Całkowity koszt czasowy wynosi

T(N) = K1 + max( K3,K4) + K2 * lg N

W przypadku wyszukiwania binarnego złożoność obliczeniowa czasowa jest logarytmiczna i wynosi

T(N) = O (log n),

co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób logarytmiczny wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy. Zapis T(N) = O(f(n)) oznacza, że istnieją takie stałe dodatnie c oraz n₀, że dla każdego n ≥ n₀ zachodzi T(N) ≤ cf(n) T_W(n) ≤ T_A(n). Algorytm ten jest więc bardzo szybki. Logarytmiczna złożoność jest osiągana dzięki temu, że każde wykonane porównanie zmniejsza o połowę przedział, w którym może znajdować się szukana wartość.

Złożoność pamięciowa jest to cecha algorytmu, która wynika z liczby i rozmiaru struktur danych wykorzystywanych w algorytmie. Złożoność ta wyznacza zależność rozmiaru pamięci potrzebnej do realizacji algorytmu od wielkości danych wejściowych. Ten sam algorytm uruchomiony jako program na komputerach o różnych konfiguracjach może wymagać różnej wielkości pamięci. Złożoność pamięciowa jest najczęściej proporcjonalna do liczby zmiennych użytych w algorytmie. Określa ona więc ilość pamięci, którą potrzebuje algorytm na rozwiązanie problemu. Dla wyszukiwania binarnego złożoność pamięciowa wynosi O (1). Oznacza to, że algorytm zużywa stałą liczbę komórek pamięci bez względu na rozmiar danych n. Czas wykonania jest stały i nie zmienia się przy zmianie liczby przetwarzania elementów.

Rozróżnia się dwa rodzaje czasowej i pesymistycznej złożoności obliczeniowej:

• Pesymistyczna złożoność obliczeniowa – określa największą ilość operacji dominujących (lub komórek pamięci), która może być wymagana dla najgorszego przypadku n danych wejściowych, dotyczy najgorszego zestawu danych. Przez pesymistyczną złożoność czasową algorytmu rozumie się funkcję:

T_W(n) = sup {t(d): d ∈ Dn}, gdzie sup oznacza kres górny zbioru. W najgorszym wypadku iteracja w algorytmie jest powtarzana 1+ log₂ N (= log N). Zatem pesymistyczna złożoność algorytmu wyszukiwania binarnego wynosi:

T_W (n) ≈ log n+1,

• Średnia (oczekiwana) złożoność obliczeniowa – jest to średnia wartość złożoności dla wszystkich problemów rozmiaru n. Określa statystycznie średnia ilość operacji dominujących (komórek pamięci), które należy wykonać dla typowego zestawu danych, aby rozwiązać problem. Wartość średnia oblicza się ze wzoru:

T_ŚR ≈ log n -1.

2.3. Schemat blokowy

Schemat blokowy jest jednym ze sposobów opisu algorytmu i zawiera plan algorytmu przedstawiony w postaci graficznej struktury elementów zwanymi blokami. Każdy blok zawiera informację o operacji, która ma być w nim wykonana, a pomiędzy blokami umieszczone są linie przepływu (strzałki) określające kolejność wykonywania bloków algorytmu.

3. Drzewa przeszukiwań binarnych

3.1. Pojęcie i algorytmy drzew poszukiwań binarnych

Drzewa binarne są rodzajem struktury danych, w których liczba synów w każdym wierzchołku nie przekracza dwóch. Drzewa binarne zawierające w wierzchołku zero lub dwóch synów noszą nazwę drzew regularnych. Drzewa ułatwiają i przyspieszają wyszukiwanie, a także pozwalają w łatwy sposób operować na posortowanych danych. Znaczenie tych struktur jest bardzo duże i ze względu na swoje własności drzewa są stosowane praktycznie w każdej dziedzinie informatyki (np. bazy danych, grafika komputerowa, przetwarzanie tekstu, telekomunikacja). Szczególną odmianą drzew binarnych są drzewa przeszukiwań binarnych.

Drzewa przeszukiwań (poszukiwań) binarnych, w skrócie BST (z ang. binary search trees), są dowolnymi drzewami binarnymi, w których elementy zbioru są wpisanego wierzchołków zgodnie z porządkiem symetrycznym. Są więc dynamicznymi strukturami, zbudowanymi z węzłów: każdy węzeł może posiadać dwóch potomków oraz jednego przodka, ponadto z każdym węzłem związany jest klucz. Dla każdego węzła (nie będącego liściem) wszystkie wartości przechowywane w lewym poddrzewie są mniejsze od wartości tego węzła, natomiast wszystkie wartości przechowywane w prawym poddrzewie są większe od wartości w tym węźle. Wysokość drzewa zależy od kolejności danych. Drzewo BST można zrealizować za pomocą struktury danych z dowiązaniami (np. listy), w której każdy węzeł jest obiektem. Jeżeli węzeł nie ma następnika albo poprzednika, to odpowiednie pole ma wartość NIL (=null).

Drzewa te są zarówno słownikiem jak i kolejką priorytetową. Można na nich wykonywać różne operacje właściwe dla zbiorów dynamicznych, jak:

• wyszukiwanie węzła w drzewie BST,

• wyszukiwanie minimalnego i maksymalnego elementu w drzewie,

• znajdowanie poprzednika/ następnika,

• wstawianie węzła do drzewa – zmienia zbiór dynamiczny reprezentowany przez drzewo, co wymaga przeorganizowania struktury drzewa tak, by została zachowana jego własność,

• usuwanie węzła z drzewa.

Algorytm drzewa przeszukiwań binarnych:

type

wierzchołek drzewa = record

klucz: typ klucza;

lewy, prawy: ˆwierzchołek drzewa;

end;

odsyłacz =ˆwierzchołek drzewa;

procedure szukaj (x: klucz ; var t: odsyłacz);

{Szukanie klucza x w drzewie wskazanym przez t.}

var v: odsyłacz ;

begin

v := t ;

while (v = nil) cand (vˆ.klucz = x) do

if x < vˆ.klucz then

v := vˆ.lewy;

else

v := vˆ.prawy;

end if;

end while;

return(v); {jeśli v = nil to x nie występuje w drzewie}

end; {szukaj}

procedure wstaw (x: klucz ; var t: odsyłacz);

{Wstawianie klucza x do drzewa wskazanego przez t.}

var v: odsyłacz ;

begin

v := t ;

while (v = nil) cand (vˆ.klucz = x) do {szukania klucza x}

if x < vˆ.klucz then

v := vˆ.lewy;

else

v := vˆ.prawy;

end if;

end while;

if v = nil then {x jest w drzewie}

13

return;

else

Wstawienie x na koniec ścieżki;

end if;

end; {wstaw}

procedure usuń (x: klucz ; var t: odsyłacz);

{Usuwanie klucza x z drzewa wskazanego przez t.}

var v, w: odsyłacz ;

begin

v := t ;

while (v = nil) cand (vˆ.klucz = x) do {szukania klucza x}

if x < vˆ.klucz then

v := vˆ.lewy;

else

v := vˆ.prawy;

end if;

end while;

if v = nil then {x nie występuje w drzewie}

return;

else

if (vˆ.lewy = nil) or (vˆ.prawy = nil) then {brak lewego lub prawego poddrzewa}

Usuń wierzchołek vˆ z drzewa;

else

w := vˆ.prawy;

while wˆ nie jest końcem ścieżki w drzewie do

w := wˆ.lewy; {szukanie minimalnego elementu w prawym poddrzewie}

end while;

Wstaw wˆ.klucz do vˆ.klucz i usuń wierzchołek wˆ z drzewa;

end if;

end if;

end {usuń}

3.2. Złożoności obliczeniowe

Do reprezentacji drzew BST można wykorzystać różne struktury tworzone w oparciu o zmienne dynamiczne. Podstawowe operacje na drzewach poszukiwań binarnych wymagają czasu proporcjonalnego do wysokości drzewa– o czasie operacji wykonywanych na drzewach decyduje ich wysokość.

Aby obliczyć oczekiwaną złożoność czasową należy oznaczyć przez G(n) oczekiwaną sumę głębokości wierzchołków zewnętrznych w BST, utworzonym z drzewa pustego. Ponieważ lewe i prawe poddrzewa od korzenia drzewa losowego BST są losowe mamy

$$\left\{ \begin{matrix} G\left( 0 \right) = 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ G\left( n \right) = \left( n + 1 \right) + \frac{1}{n\ }\sum_{j = 1}^{n}\left( G\left( j - 1 \right) + G\left( n - j \right) \right) \\ \end{matrix} \right.\ $$

Rozwiązanie równania jest więc:

T_A(n) = $\ \frac{G(n)}{(n + 1)}$ = 1,4 log n + O(1)

Tyle samo wynosi oczekiwana złożoność czasowa operacji search w przypadku, gdy element znajdzie się w drzewie.

W pełnym (tzw. zrównoważonym) drzewie binarnym o n węzłach elementarne operacje takie wyszukiwania, wstawianie węzła czy jego usuwanie działają w pesymistycznym czasie O(n), gdzie n jest wysokością drzewa (przechodzi się po ścieżce w dół drzewa). Notacja ta ogranicza funkcję T(n) od góry. W literaturze często też podaje się koszt ten w uzależnieniu od wysokości drzewa h - wynosi on O(h).

Czas działania poszczególnych procedur w drzewach BST:

Operacje	Średnia zł. obl.	Pesymistyczna zł. obl.
Space	O (n)	O (n)
Search	O (log n)	O (n)
Insert	O (log n)	O (n)
Delete	O (log n)	O (n)

Źródło: opracowanie własne na podst. L. Bałachowski, K. Diks, W. Rytter, Algorytmu i struktury danych, WNT Warszawa 1996, 2001, str. 100- 112.

Przykładowy schemat drzewa BST:

3.3. Drzewa AVL

Wraz ze wzrostem wartości h wysokości drzewa BST w stosunku do całkowitej liczby jego wierzchołków, opłacalność stosowania klasycznych drzew wyszukiwań binarnych stopniowo maleje – w skrajnym przypadku takie drzewo jest tyle samo warte, co zwykła lista.  Drzewa BST mogą degenerować się do list liniowych, co powoduje wzrost klasy złożoności obliczeniowej dla operacji wstawiania, usuwania oraz wyszukiwania do O(n). Aby uniknąć degeneracji (przez które zanikają zalety drzew BST), stworzono wiele różnych odmian drzew BST. Jedną z prostszych z nich są drzewa AVL.

Drzewo AVL, jest drzewem BST, w którym poddrzewa każdego węzła różnią się wysokością (ilością poziomów) co najwyżej o 1 – gwarantuje to zrównoważenie drzewa AVL. Mają na celu gwarantowanie wysokości czasu działania na poziomie O (log n)
(n – liczba wierzchołków) podczas operacji serach, insert i delete.

Współczynniki równowagi w drzewie AVL mogą się zmienić tylko w przypadku, gdy zmianie ulega wysokość jakiegoś poddrzewa jednego z węzłów. Z kolei do sytuacji tej może dojść tylko przy wstawianiu nowego węzła lub przy usuwaniu węzła. Pozostałe operacje nie zmieniają wysokości poddrzew, mogą więc być identyczne jak w zwykłym drzewie BST.

Jeśli losowo zbudowane drzewo BST ma co najwyżej n węzłów, to prawdopodobieństwo, że dowolny węzeł ma głębokość co najmniej 2(β + 1)H_n , wynosi co najwyżej n(2/n2) = 2/n. Stąd wynika, że z prawdopodobieństwem co najmniej 1-2/n wysokość losowo zbudowanego drzewa BST jest mniejsza niż 2(β + 1)H_n, a z prawdopodobieństwem co najwyżej 2/n wynosi co najmniej (2β + 1)H, ale nie więcej niż n. Jej wartość oczekiwana jest więc nie większa niż (2(β + 1)H_n) ($\frac{1 - 2}{n}$)+n($\frac{2}{n}$) = O(lg n).

Zakończenie

Sposobów na przeszukiwanie algorytmów jest wiele i tak naprawdę wybór odpowiedniego zależy od struktury i usystematyzowania algorytmu. Ułatwieniem dla użytkownika jest z pewnością uporządkowanie algorytmu, gdyż łatwiej wybierać metodę.

Wyszukiwanie binarne jest metodą nie tylko szybką. Algorytm zużywa stałą liczbę komórek pamięci, co oznacza, że czas wykonania jest stały i nie zmienia się przy zmianie liczby przetwarzania elementów.

Z kolei drzewa BST są bardzo wygodną strukturą do poszukiwań danych: stosując je można w krótkim czasie wykonać operacje szukania, dodawania i usuwania elementów w zbiorze. Operacje te posiadają dla drzew BST złożoność obliczeniową klasy O(log n), jeśli drzewo BST jest zrównoważone.  Działają one tym szybciej, im mniejszą wysokość posiada drzewo BST.

Bibliografia:

1. Bałachowski L., Diks K., Rytter W., „Algorytmy i Struktury Danych”, WNT, Warszawa 1996.

2. Carmen T.H., Leiserson C.E., Rivest R.L., Stein C., „Wprowadzenie do algorytmów“, WNT, Warszawa 1997,2001.

3. Czech Z.J., „Algorytmy i struktury danych, materiały dydaktyczne”

4. www.cs.put.poznan.pl

5. www.edu.i-lo.tarnow.pl

6. www.iair.mchtr.pw.edu.pl

7. www.oxygene.ibspan.waw.pl

8. www.we.pb.edu.pl