27 (788)

. wartości, do którego należy dany element Drzewo takie przechodzi się i tworzy z góry na dót - przecrwnie niż kopiec. [2]

Elementy w BST w zasadzie mogą się powtarzać, ale nie należy tego robić - mogą wystąpić Wędy i znacząco pogarsza to szybkość operacji wykonywanych na BST. [1]

2		4	5
/•3	1		l*._s
	4' 3
			3 •

Jak widać dla tych samych danych może wystąpić kilka rodzajów drzew BST - zależy do od kolejności ustawienia tych samych danych (dla przykładu na rysunku: dla 1: 321, 2: 312, 3: 213, 4: 132. 5: 123). Oczywiście najgorszy przypadek drzewa BST jest dla uporządkowanej serii, danych - np. 12.13,14,15,16. W takim przypadku •drzewo ‘zamienić się w listę liniową. W modelu drzew losowych BST każde drzewo (z przykładu r>a ww. rysunku) ma prawdopodobieństwo 1/5. W mooeiu permutacyjnym drzewo nr 3 ma prawd. 1/3, a pozostałe 1/6. [2]

Mówimy, ze BST jest zrównoważone, gdy różnica wysokości obu pod drze w w każdym węźle wynosi 0 lub 1. BST jest doskonale zrównoważone, jeśli jest zrównoważone, a wszystkie liście są na jeanym łub dwóch poziomach. Jeżeli umieścimy 10000 elementów w drzewie doskonale zrównoważonym, jego wysokość wyniesie flog( 10000)1 = 14. Wniosek: równoważyć drzewa ! (w skrajnie nieoptymalnym przypadku .niezrównoważonym’ wysokość drzewa wynosi 10000). (1)

typ®

wi erzcnci-k drzewa = record k J ucz .■ z yp k2 U Z Z a r 1 *vy, pra wy : ^A wi er zer* o i ek_ ćrz a wa end;

odryi acz ~ * wuarzchoiek drzswa ;

procedurę szukaj(x : klucz; var z : odsyłacz) ; {Szukrruc klucza r w drzewie wskazany przez t.} var v : odsyłacz;

begin

while (v / nil? cand (. kl ucz ? x) do if x < v"“.klucz then v w'’, lewy;

eise

v := .prawy;

enćif; enć‘-hi le;

recurr. { v) ; {J-rśii i' « nil, to x nic występuje w* drzewie} er.d; {szukaj}

proceduro wszą w (x : klucz; va r z : odsyłacz) ;

{Wstawianie klucza x do drzewa wskazanego przez (.} var v : odsyłacz;

be gin

v : = c;

while (v y nil) cand (vhJciucz / x) do (szukania klucza r) if x <. v*. klucz then v : = v*~.iewy/

else

Vm ;» \r~. prawy;

enćif; endwhile;

if* v / nil then (xjest w drzewiej re Curn;

else

wsławienie x ::a koniec ścieżki;

endi f;

..end; (wstaw)