|
del() funksiyasining ishlash algoritmi
|
| bet | 31/47 | | Sana | 15.11.2023 | | Hajmi | 490,46 Kb. | | #99136 |
del() funksiyasining ishlash algoritmi
Funksiyaning kirishiga daraxt ildizi ko‟rsatkichi tree va o‟chirilishi kerak
bo‟lgan tugunning info maydoni qiymati key beriladi. Daraxtning key kalitli tugunini terminal tugungacha izlaymiz. Dastlab next=tree.
Toki next NULL bo‟lguncha, agar next tugunning info maydoni key ga teng bo‟lsa, izlayotgan tugunni topdik va uning adresini p ga joylaymiz va 4-
qadamga o‟tamiz. Agar next NULL bo‟lsa, 3-qadamga o‟tamiz.
Agar key next ning infosidan kichik bo‟lsa, joriy tugunning chap tomonidagi tugunga o‟tamiz, ya‟ni next=next->left, aks holda o‟ng shoxdagi tugunga o‟tamiz. 1-qadamga qaytamiz.
Agar next NULL ga teng bo‟lsa, biz izlagan tugun tuzilmada yo‟q. Tugunni o‟chirish algoritmi tugaydi va dastur bajarilishi o‟chirish funksiyasi chaqirilgan joyga qaytib boradi.
Agar p o‟chirilayotgan tugunning chap tomonida tugun yo‟q bo‟lsa (ya‟ni p->left=NULL bo‟lsa), uning o‟ng tomonidagi tugun adresini v ga o‟zlashtiramiz.
Agar p o‟chirilayotgan tugunning o‟ng tomonida tugun yo‟q bo‟lsa, uning chap tomonidagi tugun adresini v ga o‟zlashtiramiz.
Agar p o‟chirilayotgan tugunning chapi va o‟ngida element mavjud bo‟lsa, bu tugunning o‟rniga da‟vo qiladigan tugunni topish uchun shu tugundan 1 marta o‟ngga va oxirigacha chap shox tuguniga o‟tamiz. Ya‟ni v=p->right, v p ning o‟ng tomonida turibdi, t=p va s=v->left, ya‟ni s v ning chapida turibdi. Endi to s NULL bo‟lguncha chapga ketamiz, undan 1 ta orqada v va v dan 1 ta orqada t keladi. Mana endi biz p ning o‟rniga v olib borib qo‟yishimiz mumkin.
Agar t NULL bo‟lmasa va t p ga teng bo‟lmasa (agar p ning bitta farzandi mavjud bo‟lsa, uning o‟rniga keladigan tugunni izlashga xojat yo‟q, chunki uning o‟sha farzandi aynan p ning o‟rniga joylashadi. Agar o‟chirilayotgan p tugunning 2 ta farzandi mavjud bo‟lsa, shu shart bajariladi), u holda, p ning o‟rniga ketayotgan v tugunning farzandi (agar u mavjud bo‟lsa) v ning otasi bo‟lmish t ga meros qoldiriladi, ya‟ni v->right v ning o‟rniga keladi. t->left=v->right. Endigi ish p ning har ikkala tomonidagi tugunlarni v ga o‟zlashtiramiz.
Agar t p ga teng bo‟lsa (ya‟ni p o‟chayotgan tugunning o‟rniga o‟zining
farzandi kelayotgan bo‟lsa), p ning chapidagi tugunni v ning chapiga o‟zlashtiramiz.
Mana p tugunning o‟rniga v tugun keldi. Endigi vazifa v ni p ning otasi bilan ulash kerak. Buning uchun aniqlash kerak – p tugunning otasi q NULL ga teng emasmi? Agar q NULL bo‟lsa, biz daraxt ildizini o‟chirgan bo‟lamiz. Bu holda daraxt ildizi ko‟rsatkichi tree ni v ga tenglab qo‟yamiz. Aks holda, 10- qadamga o‟tamiz.
|
| |
