Najczęściej wykonywaną operacją na zbiorach jest wyszukiwanie. Jeżeli skończony zbiór jest reprezentowany przez drzewo binarnych poszukiwań, to wyszukiwanie ustalonego elementu jest bardzo proste.  Operacją, o której będzie mowa w tym punkcie, jest dwuargumentowa operacja memeber, member: Et ´ BST ® B₀. Dla danej etykiety e oraz danego drzewa binarnych poszukiwań D,  jej zadaniem jest odpowiedź na pytanie, czy element e jest, czy nie jest etykietą drzewa D,

member(e,D) = true wttw  e jest etykietą pewnego wierzchołka w drzewie D.

Warunek opisany powyżej jest oczywiście warunkiem końcowym specyfikacji poszukiwanego algorytmu. Warunek początkowy jest bardziej skomplikowany: zakładamy, że D jest drzewem binarnym, a ponadto spełniony jest warunek :

(" vÎ D)(("x) (x Î LD(v) ® et(x) < et(v))  Ù ("x) (x Î PD(v) ® et(v) < et(x))).

Metoda

Zaczynając od korzenia drzewa D, porównujemy etykietę odwiedzanego wierzchołka z e. Jeśli nie jest to e, to w dalszym ciągu szukać będziemy w lewym poddrzewie, o ile e < et(v). Jeśli et(v) < e, to poszukiwania będą kontynuowane w prawym poddrzewie wierzchołka v.  Operacja zwraca wartość false, gdy e nie jest etykietą żadnego wierzchołka drzewa D.

Algorytm

W opisanym poniżej algorytmie, zakładamy, że root jest korzeniem drzewa binarnych poszukiwań D i obiektem typu node (por. wykład VI p.4).

Przykład 3.1

Rozważmy drzewo BST przedstawione na rysunku 7.3(a). Jeśli zastosujemy algorytm member w celu zbadania, czy 3 jest etykietą tego drzewa, to wykonany następujące kroki: porównamy najpierw etykietę korzenia z 3. Ponieważ 3<5, zatem zgodnie z zasadą etykietowania drzew BST, etykieta 3 o ile znajduje się w tym drzewie, musi się znajdować w lewym poddrzewie. Teraz porównujemy 3 z 2. Ponieważ 3 jest większe od 2, to w następnym kroku przejdziemy do prawego następnika i porównamy 4 z 3. Ponieważ 3 jest mniejsze od 4, więc gdyby etykieta 3 znajdowała się w tym drzewie, musiałaby być w lewym poddrzewie wierzchołka z etykietą 4. Wierzchołek ten jest jednak liściem, zatem 3 nie jest etykietą żadnego wierzchołka w tym drzewie.
Zastosujmy teraz ten sam algorytm do znalezienia etykiety 6. Zostaną wykonane następujące porównania : 5=6, 5<6, 8=6, 8<6, 7=6,7<6, 6=6. Ponieważ 5 nie jest równe 6 oraz 5  jest mniejsze od 6, zatem pójdziemy w prawo. Ponieważ 8 nie jest równe 6  i 8 nie jest mniejsze od 6 pójdziemy pójdziemy w lewo itd. Tym razem wynikiem będzie true, gdyż 6 jest etykietą wierzchołka w rozważanym drzewie. J

Poprawność algorytmu

Chcemy udowodnić, że algorytm zawsze zatrzymuje się i wartością zmiennej result jest true tylko wtedy, gdy w drzewie D, którego korzeniem jest root, został znaleziony wierzchołek v taki, że et(v) = e. Pierwsza część jest dość prosta. Niech h będzie wysokością drzewa D. W każdym przebiegu pętli, o ile nie znajdziemy elementu e, przechodzimy do badania wierzchołka z następnego poziomu drzewa. Ponieważ z założenia  w drzewie nie ma cyklu, oraz w każdej iteracji pętli odległość od korzenia (mierzona długością ścieżki) jest większa niż w iteracji poprzedniej, to po co najwyżej h+1 krokach dojdziemy do wierzchołka v, który jest liściem i algorytm zakończy wykonywanie pętli.  Oczywiście, jeśli znaleźliśmy wierzchołek, taki że et(v) = e, to wartość zmiennej result zostanie ustalona na true i algorytm też zakończy obliczenie.

Pozostaje uzasadnić, że  wynik jest ustalony poprawnie. Zauważmy najpierw, że wynikiem jest false, jeśli drzewo jest puste. Niech V będzie zbiorem wszystkich wierzchołków drzewa D i Dv niech oznacza poddrzewo drzewa D, którego korzeniem jest wierzchołek v oraz Dv' niech będzie zbiorem wierzchołków drzewa D nie należących do poddrzewa Dv. Załóżmy, że przy kolejnym wejściu do pętli "while" spełniony jest warunek (*). Warunek ten stwierdza, że albo zmienna result ma wartość true i istnieje wierzchołek z etykietą e, albo result nadal ma wartość false i żaden z wierzchołków, które nie są w poddrzewie Dv, nie ma etykiety e:

(*)                  ( result= true  Ù ($wÎV) et(w) = e) Ú (result = false  Ù  ("wÎDv') et(w)¹ e),

Skoro powtarzamy wykonanie pętli, zatem warunek pętli  (v ¹ null and not result) jest spełniony przez aktualne wartości zmiennych. Oznacza to wobec (*), że  prawdziwa jest druga część warunku (*). Zajść mogą teraz trzy przypadki.
(1) Albo v.val = e, a wtedy spełniona będzie pierwsza część alternatywy  (*).
(2) Albo v.val ¹ e i v.val < e, a wtedy, na mocy definicji drzewa binarnych poszukiwań,  etykieta e może się znajdować jedynie w prawym poddrzewie wierzchołka v. Po wykonaniu instrukcji v := v.right, spełniony jest warunek (result = false  Ù  ("wÎDv') et(w)¹ e).
(3) Albo v.val ¹ e i  e < v.val, wtedy nadal result = false i poza wierzchołkami lewego poddrzewa wierzchołka v na pewno nie ma etykiety e, czyli po wykonaniu instrukcji  v :=v.left spełniony jest znów warunek  (result = false  Ù  ("wÎDv') et(w)¹ e).

Wynika stąd , że po wykonaniu instrukcji warunkowej nadal jest spełniona formuła (*).

Udowodniliśmy więc, że (*) jest niezmiennikiem pętli w algorytmie member. Przed rozpoczęciem pętli warunek (*) jest trywialnie spełniony przez początkowe wartości zmiennych, zatem po wykonaniu instrukcji "while"   też jest prawdziwy. Wyjście z pętli może nastąpić tylko, gdy result =true, lub gdy  v=null, więc

albo (result = true  Ù ($wÎV) et(w) = e)   albo ( v = null Ù  result = false  Ù  ("wÎDv') et(w)¹ e) .

Zauważmy, że Dv jest zbiorem pustym, gdy v= null. W konsekwencji Dv' = V\Dv = V. Czyli prawdziwe jest zdanie

   ( result= true  Ù ($wÎV) et(w) = e) Ú (result = false  Ù  ("wÎV) et(w) ¹ e),

które jest równoważne formule  (result= true wttw ($wÎV) et(w) = e).J

Koszt algorytmu

Przyjmijmy, że operacją dominującą w tym algorytmie jest porównywanie etykiet, a rozmiarem danych niech będzie liczba wierzchołków drzewa. Jest dość oczywiste, że w najgorszym przypadku, np. gdy wierzchołki drzewa tworzą jedna tylko ścieżkę, liczba wykonanych porównań może być równa liczbie wierzchołków, czyli  W(n) = O(n).

Zastanowimy się teraz nad kosztem algorytmu w przypadku średnim. Niech n będzie liczbą wierzchołków drzewa i niech etykietami wierzchołków będą liczby naturalne od 1 do n (można też przyjąć, że liczby są jedynie numerami etykiet po ich posortowaniu w porządku niemalejącym). Przyjmijmy ponadto, że prawdopodobieństwo tego, że korzeniem drzewa jest liczba i, jest takie samo dla wszystkich możliwych wartości i.  Wynika stąd, że średnia liczba porównań A(n) wykonanych dla znalezienia etykiety e wynosi

A(n) = S_i=1,..n (1/n)´ a_i,

gdzie  a_i jest średnią liczbą porównań dla znalezienia e w drzewie, którego etykietą korzenia jest i.

Zauważmy, że w lewym poddrzewie drzewa, którego korzeniem jest i znajduje się tylko (i-1) wierzchołków (bo wszystkie etykiety w lewym poddrzewie mają być mniejsze od i), a w prawym poddrzewie drzewa znajduje się dokładnie (n-i) wierzchołków (por. rysunek 7.4). Wynika stąd, że prawdopodobieństwo tego, że szukana etykieta e znajduje się w lewym poddrzewie wynosi  (i-1)/n, a prawdopodobieństwo tego, że szukana etykieta e znajduje się w prawym poddrzewie wynosi  (n-i)/n. Średnia liczba porównań dla znalezienia etykiety e w drzewie, którego etykietą korzenia jest i wynosi więc:

(A(i-1)+1)´(i-1)/n  + 1´(1/n) + (A(n-i) +1)´(n-i)/n.

Po podstawieniu, mamy

A(0) = 0 oraz A(n) = S_i=1,..n(1/n) + S_i=1,..,n-1(1/n²)´ 2iA(i) = 1 + (1/n²)S_i=1,..,n-1 i´ A(i). 

Rozwiązaniem tego równania rekurencyjnego jest funkcja A(n)= c´lg n, gdzie c jest pewną stałą. Ostatecznie, średnia liczba porównań wykonanych przez algorytm member wynosi O(lg n).

Z powyższych rozważań wynika też, że średnią wysokość drzewa BST o n wierzchołkach można oszacować przez  O(lg n). W konsekwencji średnia liczba operacji wykonywanych przez algorytmy minBST i maxBST wynosi również O(lg n).

Pytanie 5: Zbadaj, czy jest możliwe, aby w trakcie poszukiwania etykiety 23 za pomocą algorytmu member, w pewnym drzewie binarnych poszukiwań, napotkano wymienione poniżej etykiety?
(a) 50, 28, 14, 20, 23
(b)  15, 50, 45,  20, 18, 23

« poprzedni punkt

następny punkt »