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

7.1. Binar qidiruv daraxti 
Binar  qidiruv  daraxti  (ingl.  binary  search  tree  yoki  qisqacha  BST)  –  bu 
binar daraxtning bir ko’rinishi bo’lib, quyidagi xussiyatlari bilan boshqalaridan 
farq qiladi: 
-  har  bir  X  tugun  uchun  (agar  X  NULL  ga  teng  bo’lmasa)  uning  chap 
qismdaraxtdagi  barcha  tugunlaridagi  qiymatlar  hamma  vaqt  X  tugunning 
qiymatidan kichik bo’ladi.  
- X tugunning o’ng qism daraxtidagi barcha tugunlar qiymati hamma vaqt 
X tugunning qiymatidan katta bo’ladi.  
-  bunday  daraxtdagi  har  bir  tugun  o’zining  qismdaraxti  uchun  ota  tugun 
hisoblanadi. 
Ikkilik  qidiruv  daraxtining  afzalligi  uning  tugunlaridagi  qiymatlar 
saralangan tartibda joylashgan bo’ladi. Umumiy holda binar qidiruv daraxtining 
tugunlarini  oldindan  saralash  shart  emas.  Bunday  daraxtlarga  tugunlar  erkin 
tartibda olinadi, saralash esa daraxt tugunlariga qiymatlarni joylashtirish vaqtida 
amalga oshirilishi mumkin.  
Binar qidiruv daraxtiga tugunlarni qo’yish natijasini oldindan bashorat qilib 
bo’lmaydi. Agar bunday daraxtga oldindan saralangan tugunlarni joylashtirsak, 
unda  nasl  daraxti  (bog’langan  ro’yxat)  hosil  bo’ladi.  1-rasmda  binar  qidiruv 
daraxtining turli ildizga ega bo’lgan ikkita ko’rinishi tasvirlangan. 

---

110 
 
 
1-rasm. Binar qidiruv daraxtining ikkita ko’rinishi 
 
1-listingda C tilida binar daraxt tuguni uchun tuzilmani va daraxtning o’zini 
e’lon qilishga misol keltirilgan.  
Listing 1. Daraxt va uning tugunlarni taqdim etish uchun tuzilmani aniqlash