Адабиётлар

Бинар дарахтдан элементни ўчириш процедураси 
 
Тугунни ўчириб ташлаш натижасида дарахтнинг тартибланганлиги 
бузилмаслиги лозим. Тугун дарахтда ўчирилаѐтганда 3 ҳил вариант бўлиши 
мумкин: 
1) Топилган тугун терминал (барг). Бу ҳолатда тугун шунчаки ўчириб 
ташланади. 
2) Топилган тугун фақатгина битта ўғилга эга. У ҳолда ўғил ота ўрнига 
жойлаштирилади. 
3) Ўчирилаѐтган тугун иккита ўғилга эга. Бундай ҳолатда шундай қисм 
дарахтлар звеносини топиш лозимки, уни ўчирилаѐтган тугун ўрнига қўйиш 
мумкин бўлсин. Бундай звено ҳар доим мавжуд бўлади: 

---

―Маълумотлар тузилмаси ва алгоритмлар‖ фанидан маърузалар матни.
муаллиф: Б.Б.Акбаралиев 
- бу ѐки чап қисм дарахтнинг энг ўнг томондаги элементи (ушбу 
звенога эришиш учун кейинги учига чап шоҳ орқали ўтиб, навбатдаги 
учларига эса, мурожаат NIL бўлмагунча, фақатгина ўнг шоҳлари орқали 
ўтиш зарур). 
- ѐки ўнг қисм дарахтнинг энг чап элементи (ушбу звенога эришиш 
учун кейинги учига ўнг шоҳ орқали ўтиб, навбатдаги учларига эса, мурожаат 
NIL бўлмагунча, фақатгина чап шоҳлари орқали ўтиш зарур).
Ўчирлаѐтган элемент чап қисм дарахтининг энг ўнгидаги элемент 
ўчирилаѐтган элемент учун ―Предшественник‖ бўлади ( 12 учун – 11 бўлади). 
Меросхўр эса ўнг қисм дарахтнинг энг чапидаги тугуни (12 учун - 13). 
Меросхўрни топиш алгоритмини ишлаб чиқайлик (5.9 чизма). 
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 
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