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

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

---

27
v=right (p) 
s=left (v) 
WHILE s<>nil 
t=v 
v=s 
s=left (v) 
END WHILE 
IF t<>p 
THEN WRITE (v - p ни ўғли эмас) 
left (t)=right (v) 
right (v)=right (p) 
END IF 
left (v)=left (p) 
IF q=nil 
THEN WRITE (v илдиз) 
tree=v 
RETURN 
END IF 
IF p=left (q) 
THEN left (q)=v 
ELSE right (q)=v 
END IF 
END IF 
END IF 
FREENODE (p) (ушбу процедура бўш тугун ҳосил қилади, яъни ўчирилган элемент жойлашган хотира 
ячейкасини тозалайди.) 
RETURN