“Dasturiy injiniring” fakulteti “MA‟lumotlar tuzilmasi va algoritmlar”

del() funksiyasining ishlash algoritmi 
Funksiyaning kirishiga daraxt ildizi ko‟rsatkichi tree va o‟chirilishi kerak

---

87 
bo‟lgan tugunning info maydoni qiymati key beriladi. Daraxtning key kalitli 
tugunini terminal tugungacha izlaymiz. Dastlab next=tree. 
1. 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. 
2. 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. 
3. 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. 
4. 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. 
5. Agar p o‟chirilayotgan tugunning o‟ng tomonida tugun yo‟q bo‟lsa, uning 
chap tomonidagi tugun adresini v ga o‟zlashtiramiz. 
6. 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.
7. 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