Tuguni to’rtta maydonga ega yozuv shaklida bo’ladi, ya’ni kalit maydon

9.1.Daraxtlar.Ikkilangan Daraxt 
Binar daraxtda har bir tugun-elementdan ko’pi bilan 2 ta shox chiqadi. Daraxtlarni 
xotirada tasvirlashda uning ildizini ko’rsatuvchi ko’rsatkich berilishi kerak. 
Daraxtlarni kompyuter xotirasida tasvirlanishiga ko’ra har bir element (binar daraxt 
tuguni) to’rtta maydonga ega yozuv shaklida bo’ladi, ya’ni kalit maydon, 
informatsion maydon, ushbu elementni o’ngida va chapida joylashgan 
elementlarning xotiradagi adreslari saqlanadigan maydonlar. 
Shuni esda tutish lozimki, daraxt hosil qilinayotganda, otaga nisbatan chap 
tomondagi o’g’il qiymati kichik kalitga, o’ng tomondagi o’g’il esa katta qiymatli 
kalitga ega bo’ladi. Har safar daraxtga yangi element kelib qo’shilayotganda u 
avvalambor daraxt ildizi bilan solishtiriladi. Agar element ildiz kalit qiymatidan 
kichik bo’lsa, uning chap shoxiga, aks holda o’ng shoxiga o’tiladi. Agar o’tib ketilgan 
shoxda tugun mavjud bo’lsa, ushbu tugun bilan ham solishtirish amalga oshiriladi, 
aks holda, ya’ni u shoxda tugun mavjud bo’lmasa, bu element shu tugunga 
joylashtiriladi. 
Masalan, daraxt tugunlari quyidagi qiymatlarga ega 6, 21, 48, 49, 52, 86, 101. 
9.2.Algoritmlarning to’g’riligi. 
Algoritmning to'g'riligi 

Barcha vazifalar uchun emas, hasis algoritm eng maqbul echimni beradi, lekin 
biznikiga beradi.Buni tekshiramiz. 
Teorema 1.Greedy-Activity-Selector algoritmi mumkin bo'lgan eng ko'p sonli 
qo'shma dasturlarning to'plamini beradi. 
Isbot.Eslatib o'tamiz, ilovalar tugash vaqtini ko'paytirish orqali tartiblangan. 
Birinchidan, biz 1-ilovani o'z ichiga olgan dasturlarni tanlashning eng maqbul 
yechimi borligini isbotlaymiz (eng tugash vaqti bilan). Aslida, agar biron-bir 
maqbul dasturlar to'plamida 1-ilova bo'lmasa, u holda dasturni 1-sonli ilova 
bo'lmagan eng erta tugash vaqti bilan almashtirish mumkin, bu dasturlarning 
muvofiqligini buzmaydi (chunki 1-ilova avvalgisidan oldinroq tugaydi). Va hech 
narsa bilan kesib o'tolmaydi) va ularning umumiy sonini o'zgartirmaydi. Shuning 
uchun, siz hasis tanlovdan boshlab, eng yaxshi echimni izlashingiz mumkin. 
Biz faqat 1-ilovani o'zichiga olgan to'plamlarni ko'rib chiqishga kelishib 
olganimizdan so'ng, unga mos bo'lmagan barcha dasturlarni tashlab yuborish 
mumkin va vazifa qolgan ilovalar to'plamidan eng maqbul ilovalarni tanlash 
vazifasini qisqartirishga imkon beradi (1-sonli ilovabilanqo'shiladi). Boshqacha 
qilib aytganda, biz muammoni kamroq dasturlar
 bilan o'xshash muammoga kamaytirdik. Induktsiya asosida mulohaza qilib, 
biz harqadamda hasis tanlov qilsak, eng maqbul echimga erishamiz. 
 
10.1. Minimal qoldiq daraxtlar. 
Minimal oraliq daraxti (MST) yoki minimal og‘irlik oralig‘i daraxti bir-biriga 
bog‘langan, chekka og‘irligi bo‘lgan yo‘naltirilmagan grafikning chekkalarining 
kichik to‘plami bo‘lib, u barcha cho‘qqilarni bir-biriga bog‘laydi, hech qanday 
aylanishlarsiz va chekkaning mumkin bo‘lgan minimal umumiy og‘irligi bilan.[1] 
Ya'ni, u chekka og'irliklari yig'indisi imkon qadar kichik bo'lgan yoyilgan 
daraxtdir.[2] Umuman olganda, har qanday chekka og'irlikdagi yo'naltirilmagan 

grafik (ulanish shart emas) minimal o'rmonga ega bo'lib, u bog'langan 
komponentlar uchun minimal kenglikdagi daraxtlarning birlashmasi hisoblanadi. 
 
Minimal kenglikdagi daraxtlar uchun ko'plab foydalanish holatlari mavjud. 
Masalan, telekommunikatsiya kompaniyasi yangi mahallada kabel 
yotqizmoqchi. Agar kabelni faqat ma'lum yo'llar (masalan, yo'llar) bo'ylab 
ko'mib tashlash cheklangan bo'lsa, u holda bu yo'llar bilan bog'langan 
nuqtalarni (masalan, uylar) o'z ichiga olgan grafik mavjud bo'ladi. Ba'zi yo'llar 
qimmatroq bo'lishi mumkin, chunki ular uzunroq yoki kabelni chuqurroq 
ko'mishni talab qiladi; bu yo'llar kattaroq og'irlikdagi qirralar bilan ifodalanadi. 
Valyuta chekka og'irligi uchun maqbul birlikdir - uchburchak tengsizligi kabi 
oddiy geometriya qoidalariga bo'ysunish uchun chekka uzunliklariga hech 
qanday talab yo'q. Ushbu grafik uchun chiziqli daraxt hech qanday tsiklga ega 
bo'lmagan, lekin baribir har bir uyni bog'laydigan yo'llarning kichik to'plami 
bo'ladi; bir nechta keng tarqalgan daraxtlar bo'lishi mumkin. Minimal 
kenglikdagi daraxt eng kam umumiy xarajatga ega bo'lib, kabelni yotqizish 
uchun eng arzon yo'lni ifodalaydi.