Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali

struct node 
{ 
 
int data; 
 
struct node * left; 
 
struct node * right; 
 
struct node * parent; 
} 
Ko’rsatilgan  ota  tugun  uchun  “davomichi”  (yaqin  katta  son)  ni  qidirish 
funktsiyasi aniqlash kerak.  
Listing 2. Davomchi (merosxo’r)ni topish funktsiyasi 
static struct node * successor(struct node * x) 
{ 
 
struct node * y; 
 
if(x->right != NULL) 
 
{ 

---

139 
 
 
 
u = x->right; 
 
 
while(y->left != NULL)  
 
 
 
u = y->left; 
 
} 
 
else 
 
{ 
 
 
u = x->parent; 
 
 
while(y != NULL && x == y->right) 
 
 
{ 
 
 
 
x = y ; 
 
 
 
y = y->parent; 
 
 
} 
 
} 
 
return y; 
} 
Agar tugunda o’ng o’g’il tugunlar mavjud bo’lsa, u holda uning merosxo’ri 
sifatida  o’ng  qismdaraxtdagi  eng  kichik  qiymatli  tugun  olinadi.  2-rasmdagi 
daraxtda 8 tugunning merosxo’ri sifatid o’ng qismdaraxtdagi eng kichik qiymatli 
9 tuguni olinadi. Agar o’ng qism daraxt mavjud bo’lmasa, u holda merosxo’rni 
qidirish  yuqori  va  o’ng  tomondan  amalga  oshiriladi  (2-rasmda  11  tugunining 
merosxo’ri 12 tuguni bo’ladi). 
 
2-rasm. Muvozanatlashgan daraxt 

---

140 
 
 
Ota tugunga ko’rsatkich – bu daraxt bo’yicha o’tishni yengillashtiradigan 
yagona usul emas. Daraxtda o’g’il tugunlar bo’lmagan hol ham bo’lishi mumkin. 
Bunda  ko’rsatkichni  daraxtning  boshqa  qismda  saqlashni  qo’llash  mumkin, 
masalan,  berilgan  tugunning  ajdodi  va  merosxo’rida.  Buning  uchun  tugunga 
ikkita bitli maydon qo’shish talab etiladi (3-listingga qarang) 
Listing 3. Daraxtning tugunini tavsiflash uchun kengaytirilgan tuzilma