26 (818)

w wy szuKi wam u liniowym me jest wymagane uporządkowanie, czyli U{ I)

W wyszukiwuniu binarnym wymagane jest uporządkowanie rekordów (po lewej szronie rodzica mniejsze, po prawej większe). T_ir(n) ~ n/2 * 0(n)

Jeżeli jedyną operacją na kluczu jest porównanie to nie da się tego zrobić szybciej niż w C2zisie iogn (najlepsze jest wyszukiwanie binarne)

a.t-c / —

/J—-b(;lognrH)

/

/ ✓ ;'

i'/'

i .<    ¹

2    4 g N

38. Podać własności drzewa poszukiwań binarnych oraz procedury szukaj i wstaw operujące na drzewie. Jaki jest kosz: wyszukiwania klucza w drzewie?

Implementaq'a dotycząca tzw. problemu słownika. Problem słownika to: podać strukturę danych umożliwiającą wykorrywanre nast. operacji: konstruuj, szukaj, wstaw, usuń. Wyszukiwać można liniowo i binarnie, ja* omówiono wcześniej oraz_____

CStukinan

Pewnym ucgólnieniem poszukiwań elementu w tablicy jest wyszukiwanie elementu w drzew-,* p binarnych 3S7 (Binary Saarch Trea).

v-V    OLfU' »'T^łT:v C" ,-n

JAK ROZPOZNAWAĆ DRZEWA BINARNE Z DUŻEJ ODLEGŁOŚCI ?r?

Zakładamy, że każdy węzei x drzewa ma trzy atrybuty: tewy{x), kJuczix), prawy{x). W BS i elementy uporządkowane są w porządku symetrycznym, czyli spełnione są następujące warunki:

, t, jeśli węzeł y leży w lewym poddrzewie x, to kJucziy) ś kJucz{x)

2. jeśli węzeł y leży w prawym poddrzewie x, to kiucz(x) < kluczjy)

V

£"‘Q'ls o

-O* Ó <

	’^%‘Y\	/
5	■	12	18
/ \	/ \ / N	/ \	// \
2 * / \ / \ * H	$ *) / \ ■ ■	» 14 / \ / \ ■ ■	w t

Drzewem poszukiwań brn^rrrych (5ST) nazywamy dowolne drzewo binarne, w którym elementy zbiory są wpisane do wierzchołków zgodnie z porządkiem symetrycznym. Wierzchołki oznaczone B), to wierzchołki zewnętrzne. W strukturze dowiązań i owej reprezentowane przez nil. Wierzchołkom zewnętrznym odpowiadają przedziały wartości, na które zostania podzielona przestrzeń wszystkich kluczy przez kiucze znajdujące się w Orzecie.    iiwy ćńśiłwU, uiuwrizczferriy go w wierzchołku zewnętrznym reprezentującym przedziel