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

6.2. Yo’llarni (masofalarni) hisoblash 
Yo’l (ingl. path) – bu daraxt ildizidan qaysidir tugungacha bo’lgan masofa. 
Kengaytirilgan  binar  daraxtlarda  har  bir  yo’l  barglar  bilan  tugallanadi.  Agar 
barglar sonini S, qolgan tugunlar sonini N bilan belgilab olsak, u holda quyidagi 
formula to’g’ri bo’ladi: 
S = N +1 
Ya’ni, kengaytirilgan binar daraxtda barglar soni, boshqa tugunlar sonidan 
bittaga ko’p bo’ladi.  
Agar ildiz tugundan bargacha bo’lgan masofa tashqi yo’l deb olinsa, barg 
bo’lmagan tugunlargacha bo’lgan masofa ichki yo’l deb olinadi, u holda 3-rasmda 
tasvirlangan daraxt uchun barcha tashqi yo’llar yig’indisi quyidagicha bo’ladi: 
E=3+3+2+3+4+4+3+3=25, 
Ichki yo’llar yig’indisi esa: 
I=2+1+0+2+3+1+2=11. 
Va bundan quyidagi formula kelib chiqadi: 
E=I+2n 
Bu yerda n – ichki (barg bo’lmagan) tugunlar soni. 

---

100 
 
 
3-rasm. Kengaytirilgan daraxtga misol 
 
Faraz qilaylik, barglar to’plami quyidagicha berilgan bo’lsin: 
2,3,5,7,11,13,17,19,23,29,31,37,41 
Bundan quyidagicha masalalarni qo’yish mumkin: 
- binar daraxtni quyidagi shart asosida quring: yo’llar yig’indisi eng kichik 
bo’lsin. Bu turli algoritmlarda hisoblashlar uchun vaqtni qisqartiradi. 
To’liq  kengaytirilgan  binar  daraxtni  quyidagi  shart  asosida  quring:  ildiz 
tugundan barglargacha bo’lgan yo’lning barg tugun qiymati bilan ko’paytmalari 
yig’indisi eng kichik bo’lsin.  
Ushbu  masalalarni  yechish  uchun  David  Xaffman  (David  Huffman) 
tomonidan  algoritm  taklif  qilingan  bo’lib,  har  bir  qadamda  ikkita  eng  kichik 
barglar  tanlab  olinib,  yig’indisi  hisoblanadi.  Bu  4-rasmda  keltirilgan  daraxt 
bo’yicha 1-listingda berilgan. 
Listing 1. Xaffman algoritmiga misol 
  2 3 5 7 11 13 17 19 23 29 31 37 41 
    5 5 7 11 13 17 19 23 29 31 37 41 
     10 7 11 13 17 19 23 29 31 37 41 
       17    24 17 19 23 29 31 37 41 
             24 34 19 23 29 31 37 41 
             24 34    42 29 31 37 41 

---

101 
 
                      42 53 65 37 41 
                      42 53 65  78 
                         95  65  78 
                         95      143 
                             238 
 
4-rasm. Xaffman algoritmi bo’yicha binar daraxt