28 (766)

Czas działania szukaj (więc także t wstaw) jest proporq'onalrry do głębokości wierzchołka x (zewnętrznego lub wewnętrznego), będącego wynikiem funkqi szukaj. Czas wyszukiwania, gdy poszuk/wany jest korzeń: T_m(n) = b ■ 1, b - czas wykonania poj. pętii.

Czas wyszukiwania pomyślnego:

Tp^(n) = b (H ♦ 1)    ,    H + 1 - Ib. mijanych wierzchołków, H +1 = Llog nj + 1

Tp,t(n) = b (Llog n] + 1) = b (flog n +11) - 0{logn)    _T

Czas wyszukiwania niepomyślnego (gdy nie ma elementu w zbiorze): A(n) = 1.4 log n + 0(1)

średnia liczba porównań wymaganych dla wyszukiwania wzorca w BST:

P_n = 2 H_n(n+ 1)/n - 3

Analiza wyszukiwania w drzewach binarnych podana jest w [3] na str. 20. Zajmuje ona prawie ^ (cztery) strony przekształceń rozmaitych. Przepisywać? I tak nikt się nie nauczy. AJe jezełi Szanowni Koledzy pragną lo ja oczywiście wydam upgrade z wyprowadzeniem. Ale póki co podaję lyiku wynik końcowy 1ejz& analizy.

P_n - średniajb. porównań wymaganych dla wyszukania klucza w BST, H_n * In n + 0,577 39. Podać i omówić procedurę usuwania klucza z drzewa poszukiwań binarnych.

procedura usuń (x : kl ucz; vsr C : odsyłacz) i    .r    ...

,_T.    •    ,    i    ji V — rikl +kcn rcfarr«i\

( L-suwłtuc kjuczz r z drzewa wskazanego przez /.}    ⁿ

var V, w .* odsyłacz;

beęin    " r>\\S) O r (o \

v : = c;    l> » ś. )

wniie {t"    cand (v ‘. .'ii ucz * ?.) do (szukania klucza.r) U6 Or* O* fc. ^Uu^o.

if * <    ther.    u™    o

»-X‘.-=■ 0*.

0J^ołuuvi    l^c>C4W

lĄl tO^A. LASKIM

u\m^V g**'

0'--= O ^A f>< OMy

eJ. eo

aner:; endvhile

if / = nil then (r nie występuje w drzewie} raturr.; •

else

i£ { v*. J ewy = nil) cr (    . pra^y = nil) then

(Brak lewego lub prawnego poddrzewa)

Usuń wierzchołek v* z drzewa/

else

c

v : = v

while w"' nie jest końcem ścieżki w drzewie do    .“

w :» v*.Jewy; (szukanie rnimrnŁmcgo dcmcnru w prawym pod drzewie] andwhilq

Wstaw w". klucz do v~_mklucz i usuń wierzchołek w-^A z drzewa

enci: ;

endid; end; {usuń}

Co tu opisywać? Koń, jaki jest, każdy widzi. Najpierw szukamy elementu przechodząc drzewo z góry na dół i od lewej do prawej. Gdy nic me znajdziemy, wychodzimy. Gdy znajdziemy i wierzchołek nre ma lewego lud prawego poddrzewa. to jest ostatni ,na dole* i wyrzucamy go. Jezeii jest ,w środku' drzewa to szukamy szagoKTiarejsżegojejenjentu (najbardziej .lewego’ w prawym pcddrzewia - przypominam: małe na lewo,

duże na prawo). Przepisujemy element ten w .wolne* miejsce po usuniętym. Koniec i kropka.

oI\T|^/V*Q V Iaż^n.* y Cp Lit-    U¹ C1 *y

tKłrt)

.iv^Au_r^    i uicysiYch.

;

u-

lylY --

Py7

28