Дарахтсимон тузилмалар

Бу ҳолда дарахтда қидирув вақти, бир томонлама йўналтирилган рўйхатдаги каби бўлиб, ўртача қараб
чиқишлар сони N/2 бўлади.
Агар дарахт мувозанатланган бўлса, у ҳолда қидирув энг самарали натижа беради. Бу ҳолда қидирув
log N (2 asosli log)дан кўп бўлмаган элементларни кўриб чиқади.

Дарахтга янги элемент қўшиш процедураси
Дарахтга бирор бир элементни қўшишдан олдин дарахтда берилган калит бўйича қидирувни амалга
ошириш лозим бўлади. Агар берилган калитга тенг калит мавжуд бўлса, у ҳолда дастур ўз ишин якунлайди, акс
ҳолда дарахтга элемент қўшиш амалга оширилади.
Дарахтга янги ёзувни киритиш учун, аввало дарахтни шундай тугунини топиш лозимки, натижада
мазкур тугунга янги элемент қўшиш мумкин бўлсин. Керакли тугунни қидириш алгоритми ҳам худди берилган
калит бўйича тугунни топиш алгоритми каби бўлади. Бироқ берилган калит бўйича қидирув процедурасидан
тўғридан-тўғри (бевосита) фойдаланиб бўлмайди, сабаби, қидирув процедурасида, қайси тугунда мурожаат NIL
(search = nil) бўлгани фиксирланмайди.
Қидирув процедурасини шундай модификация қиламизки, қўшимча самара сифатида янги
процедурамиз берилган калит турган тугунни фиксирласин (қидирув мувофақиятли бўлса), ёки шундай
тугунники, ушбу тугунни қайта ишлагандан кейин қидирув якунлансин (қидирув мувофақиятли бўлса).

Бинар дарахтдан элементни ўчириш процедураси
Тугунни ўчириб ташлаш натижасида дарахтнинг тартибланганлиги бузилмаслиги лозим. Тугун
дарахтда ўчирилаётганда 3 ҳил вариант бўлиши мумкин:
1) Топилган тугун терминал (барг). Бу ҳолатда тугун шунчаки ўчириб ташланади.
2) Топилган тугун фақатгина битта ўғилга эга. У ҳолда ўғил ота ўрнига жойлаштирилади.
3) Ўчирилаётган тугун иккита ўғилга эга. Бундай ҳолатда шундай қисм дарахтлар звеносини топиш
лозимки, уни ўчирилаётган тугун ўрнига қўйиш мумкин бўлсин. Бундай звено ҳар доим мавжуд бўлади:
- бу ёки чап қисм дарахтнинг энг ўнг томондаги элементи (ушбу звенога эришиш учун кейинги учига
чап шоҳ орқали ўтиб, навбатдаги учларига эса, мурожаат NIL бўлмагунча, фақатгина ўнг шоҳлари орқали ўтиш
зарур).
- ёки ўнг қисм дарахтнинг энг чап элементи (ушбу звенога эришиш учун кейинги учига ўнг шоҳ орқали
ўтиб, навбатдаги учларига эса, мурожаат NIL бўлмагунча, фақатгина чап шоҳлари орқали ўтиш зарур).
Ўчирлаётган элемент чап қисм дарахтининг энг ўнгидаги элемент ўчирилаётган элемент учун меросхўр
бўлади ( 12 учун – 11 бўлади). Меросхўр эса ўнг қисм дарахтнинг энг чапидаги тугуни (12 учун - 13).
Меросхўрни топиш алгоритмини ишлаб чиқайлик (Қуйидаги чизмага қаранг).
p – ишчи кўрсаткич;
q - р дан бир қадам орқадаги кўрсаткич;
v – ўчиралётган тугун меросхўрини кўрсатади;
t - v бир қадам орқада юради;
s - v дан бир қадам олдинда юради (чап ўғилни ёки бўш жойни кўрсатиб боради)