Ўзбекистон алоқа ва ахборотлаштириш агентлиги тошкент ахборот технологиялари университети

 
Бинар дарахт бўйича қидирув процедураси 
Мазкур процедуранинг вазифаси шундан иборатки, у берилган калит бўйича дарахт тугуни қидирувини 
амалга оширади. Қидирув операциясининг давомийлиги дарахт тузилишига боғлиқ бўлади. Ҳақиқатдан, агар 
элементлар дарахтга калит қийматлари ўсиш (камайиш) тартибида келиб тушган бўлса, у ҳолда дарахт бир 
томонга йўналган рўйхат ҳосил қилади (чиқиш даражаси бир бўлади, яъни ягона шоҳга эга), масалан: 
Бу ҳолда дарахтда қидирув вақти, бир томонлама йўналтирилган рўйхатдаги каби бўлиб, ўртача қараб 
чиқишлар сони N/2 бўлади. 
Агар дарахт мувозанатланган бўлса, у ҳолда қидирув энг самарали натижа беради. Бу ҳолда қидирув 
N
2
log
дан кўп бўлмаган элементларни кўриб чиқади. 
Қидирув процедурасини кўриб чиқамиз. search ўзгарувчисига топилган бўғин кўрсаткичи 
ўзлаштирилади: 
p=tree 
WHILE p<>nil DO 
IF key=k (p) 
THEN search=p 
RETURN 
END IF 
IF key<>k (p) 
THEN p=left (p) 
ELSE p=right (p) 
END IF 
END WHILE 
search=nil 
RETURN 
Дарахтга янги элемент қўшиш процедураси 
Дарахтга бирор бир элементни қўшишдан олдин дарахтда берилган калит бўйича қидирувни амалга 
ошириш лозим бўлади. Агар берилган калитга тенг калит мавжуд бўлса, у ҳолда дастур ўз ишин якунлайди, акс 
ҳолда дарахтга элемент қўшиш амалга оширилади.
Дарахтга янги ёзувни киритиш учун, аввало дарахтни шундай тугунини топиш лозимки, натижада 
мазкур тугунга янги элемент қўшиш мумкин бўлсин. Керакли тугунни қидириш алгоритми ҳам худди берилган 
калит бўйича тугунни топиш алгоритми каби бўлади. Бироқ берилган калит бўйича қидирув процедурасидан 
тўғридан-тўғри (бевосита) фойдаланиб бўлмайди, сабаби, қидирув процедурасида, қайси тугунда мурожаат NIL 
(search = nil) бўлгани фиксирланмайди.
Қидирув процедурасини шундай модификация қиламизки, қўшимча самара сифатида янги 
процедурамиз берилган калит турган тугунни фиксирласин (қидирув мувофақиятли бўлса), ёки шундай 
тугунники, ушбу тугунни қайта ишлагандан кейин қидирув якунлансин (қидирув мувофақиятли бўлса). 
Дарахтда қўшилаётган элемент калитига тенг калитли элемент йўқ бўлган ҳолда элементни қўшиш 
процедурасини келтириб ўтамиз. 
q=nil 
p=tree 
WHILE p<>nil DO 
q=p 
IF key=k (p) 
THEN search=p 

---

26
RETURN 
END IF 
IF keyTHEN p=left (p) 
ELSE p=right (p) 
END IF 
END WHILE 
{Берилган калитга тенг тугун топилмади, элемент қўшиш талаб қилинади. Ота бўлиши мумкин тугунга 
q кўрсаткич берилади.} 
V=maketree (key, rec) 
{Қўйилаётган V элемент чап ёки ўнг ўғил бўлишини аниқлаш лозим.} 
IF keyTHEN left (q)=V 
ELSE right (q)=V 
END IF
search=V 
RETURN