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

6.1. Binar daraxtlar klassifikatsiyasi 
Binar  daraxtlarning  turlarini  o’rganishdan  oldin  qidiruv  algoritmlarining 
klassifikatsiyasi bilan tanishamiz.  
Chiziqli  qidiruvda  qidirilayotgan  element  ro’yxatning  barcha  elementlari 
bilan  qadamma-qadam  solishtirib  chiqiladi.  Bunday  qidirish  tezligi  ro’yxatning 
o’lchami (uzunligi) bilan bog’liq: ro’yxat qancha uzun bo’lsa, tezlik shuncha kam 
bo’ladi,  ya’ni  tezlik  ro’yxat  uzunligi  bilan  teskari  proportsional.  Bunday 
qidiruvda tezlikni oshirish uchun ro’yxatni oldin saralab olish kerak bo’ladi.  
Saralangan  ro’yxatlar  uchun  bundan  samaraliroq  algoritmlar  mavjud. 
Saralangan  ro’yxatning  o’rtasida  joylashgan  element  bilan  qidirilayotgan 
elementni solishtirish zarur bo’ladi. Agar o’rta element qidirilayotgan elementdan 
katta bo’lsa, demak, qidirilayotgan element ro’yxatning chap yarmida joylashgan 
bo’ladi.  Aks  holda  o’ng  yarmida.  Keyin  ajratib  olingan  yarmidagi  elementlar 
qidirilayotgan elementga solishtirish amali boshlanadi. Bunda ham tanlab olingan 
yarim  ro’yxatning  o’rta  elementi  solishtirladi  va  zarur  bo’lgan  yarim  ro’yxat 
ajratiladi.  Bunday  qidiruv  usuli  ikkilik  qidiruv  deb  ataladi.  Bu  qidiruv  chiziqli 
qidiruvga  nisbatan  tezroq  bajariladi.  Ro’yxat  n  ta  elementdan  tashkil  topgan 
bo’lsa, uni teng ikkiga bo’lib olish kerak, bu 2 asosga ko’ra n ning logarifmiga 

---

97 
 
teng  bo’ladi.  Ikkilik  qidiruv  ikki  asosga  ko’ra  O(log)  darajali  algoritm 
hisoblanadi.  
Ammo an’anaviy bog’langan ro’yxatlar ikkilik qidiruv uchun qulay emas, 
shuning uchun ham 1-rasmda ko’rsatilgan misoldagi kabi ikkilik (binar) daraxtni 
qo’llash tavsiya etiladi.  
 
1-rasm. Binar daraxtga misol 
 
Umumiy  holda  daraxtdagi  har  bir  tugun  cheklanmagan  sondagi  o’g’il 
tugunlarga ega bo’lishi mumkin. Daraxtlarning qolgan turlaridan binar daraxtning 
farqli tomoni, binar daraxtning har bir tugunida ikkitadan ko’p bo’lmagan o’g’il 
tugunlar bo’ladi. Oddiy binar daraxt- bu har biri ba’zi qiymatlarni hamda chap va 
o’ng  qismdaraxtlarga  ko’rsatkichlarni  saqlovchi  tugunlardan  tashkil  topgan 
tuzilma hisoblanadi. Bu qismdaraxtlarning bitta yoki ikkala ko’rsatkichlari ham 
NULL  qiymatiga  ega  bo’lishi  mumkin.  Ikkilik  daraxtlar  ham  bog’langan 
ro’yxatlar kabi rekursiv tuzilma hisoblanadi.  
2-rasmda  bir  xil  tugunlar  to’plamiga  ega,  lekin  ularning  ketma-ketligi 
turlicha  bo’lgan  binar  daraxtlarga  misol  keltirilgan.  Oxirgi  holatda  daraxt 
bog’langan ro’yxat shaklida tasvirlangan.  

---

98 
 
 
2-rasm. Bitta binar daraxtning turlicha talqin qilinishiga misollar 
 
Binar daraxtlarning quyidagicha ko’rinishlari mavjud: 
- to’liq binar daraxt – barglardan tashqari har bir tuguni 2 ta o’g’il tugunga 
ega bo’lgan daraxt; 
- ideal binar daraxt – bu barcha barg tugunlari bir xil balandlikda joylashgan 
to’liq binar daraxt; 
-  muvozanatlashgan  binar  daraxt  –  bu  2  ta  qismdaraxtlarining  har  bir 
tugunlaridagi o’g’il tugunlar soni 1 dan ko’p farq qilmaydi. Bunday daraxtlarning 
chuqurligi  ikkilik  logarifm  log(n)  bilan  hisoblanadi,  bu  yerda  n  –  tugunlarning 
umumiy soni; 
- nasl daraxti – bu har bir tugunida faqat bitta o’g’il tugun bo’lgan binar 
daraxt, aslida bu tuzilma bog’langan ro’yxat bo’ladi; 

---

99 
 
-  binar  qidiruv  daraxti  (BST)  –  har  bir  tuguni  aniq  bir  shart  asosida 
yaratiladi,  ya’ni  ushbu  tugunning  chap qismdaraxtning barcha  tugunlari kichik, 
o’ng qism daraxtning barcha tugunlari katta qiymatli elementlardan tashkil topgan 
binar daraxt.