Amaliy matematika va informatika” yo’nalishi 18. 06-guruh talabasi Otajonova Oyzoda Sodiqjon qizining

2§ Daraxtlarning turlari

Turli xil daraxt turlari mavjud va mavhum hamda haqiqiylik o'rtasidagi farqni berilgan dastur bilan ishlab tushunish bu juda muhimdir. Shunga ko'ra, biz turli xil daraxt turlari va ularning ishlashini ko'rib chiqamiz. Muhokamamizni daraxtlarni aniqlashdan boshlaymiz. Biz daraxtlarning turlarini norasmiy ravishda muhokama qilamiz va ko'rib chiqishimiz kerak bo'lgan narsalar:

• Daraxtlar;

• Ildizli daraxtlar;

• Daraxtlarga buyurtma berish;

• Ikkilik daraxtlar.

Daraxt – bu bog'langan ro'yxatga o'xshash ma'lumotlar tuzilishi, ammo shunchaki chiziqli shaklda keyingi tugunga ishora qiladigan har bir tugun o'rniga har bir tugun bir qator tugunlarga ishora qiladi. Daraxt – bu chiziqli bo'lmagan ma'lumotlarning tuzilishiga misol. Daraxt konstruktsiyasi – bu strukturaning daraxtsimon grafik shaklda aks ettirish usuli.

ADT daraxtlarida (Mavhum ma'lumot turi), elementlarning tartibi muhim emas. Agar bizga buyurtma ma'lumot kerak bo'lsa, bog'langan ro'yxatlar, ustunlar, navbat va boshqalar kabi chiziqli ma'lumotlar tuzilmalaridan foydalanish mumkin.

• 
  Daraxtning ildizi bu ota-onasiz tugun. Eng ko'pi bilan bitta daraxtda bitta tugun bo'lishi mumkin (yuqoridagi misolda A tugun).
  
• 
  Chegara ota-onadan bolaga bog'lanishni anglatadi (rasmdagi barcha bog’lovchi chiziqlar).
  
• 
  Bolalari bo'lmagan tugunga barg yaproqlari deyiladi (E, J, K, H va I).
  
• 
  Bitta ota-onalarning farzandlari aka-uka deyiladi (B, C, D - A ning ukalari, E, F - B ning ukalari).
  
• 
  Agar p tugun bo'lsa, q tugunning ajdodidir, agar ildizdan q ga yo'l mavjud bo'lsa va p yo'lda paydo bo'lsa, q tuguniga p ning avlodi deyiladi. Masalan, A, C va G - K ning ajdodlari.
  
• 
  Berilgan chuqurlikdagi barcha tugunlarning to'plamiga daraxt darajasi deyiladi (B, C va D bir xil darajada). Ildiz tuguni nol darajasida.
  

• 
  Tugunning chuqurligi – bu ildizdan tugungacha bo'lgan yo'lning uzunligi (G tugunning chuqurligi - 2, A - C - G).
  
• 
  Tugunning balandligi – bu tugundan eng chuqur tugungacha bo'lgan yo'lning uzunligi. Oldingi namunada B ning balandligi 2 ga teng (B - F - J).
  
• 
  Daraxtning balandligi  daraxtning barcha tugunlari orasidagi maksimal balandlik va daraxtning chuqurligi  daraxtning barcha tugunlari orasidagi maksimal chuqurlik. Berilgan daraxt uchun chuqurlik va balandlik bir xil qiymatni beradi. Ammo alohida tugunlar uchun biz farqli natijalarni olishimiz mumkin. Oldingi na’munada daraxtning balandligi va chuqurligi 3 ga teng.
  
• 
  Tugunning kattaligi  bu o'z ichiga olgan avlodlar soni (C ning o'lchami - 3).
  
• 
  Agar daraxtdagi har bir tugunning bittadan bolasi bo'lsa (barg tugunlaridan tashqari), biz bunday daraxtlarni skew trees deb ataymiz. Agar har bir tugunning faqat chap farzandi bo'lsa, biz ularni chap tomonlama daraxtlar (left trees) deb ataymiz. Shunga o'xshab, agar har bir tugunning faqat o'ng farzandi bo'lsa, biz ularni o'ng tomonlama daraxtlar (right trees) deb ataymiz.
  

Agar har bir tugunda bola bo'lmasa, bitta bola yoki ikkita bola bo'lsa, bunday daraxtlar ikkilik daraxti deb ataladi. Bo'sh daraxt yaroqli ikkilik daraxti hisoblanadi. Ikkilik daraxtni ildizning ikkita ikkilik daraxtlaridan iborat deb tasavvur qilishimiz mumkin, ular ildizning chap va o'ng pastki daraxtlari deb nomlanadi.

Umumiy ikkilik daraxti:

To'liq ikkilik daraxt: To'liq ikkilik daraxtni aniqlashdan oldin faraz qilaylik, ikkilik daraxtning balandligi h dir. To'liq ikkilik daraxtlarda, agar biz tugunlarni ildizdan boshlasak, ularni raqamlashni bersak (deylik, ildiz tugunida 1 bor), unda daraxtdagi tugunlar soniga 1 dan to'liq ketma-ketlikni olamiz. O'tish paytida biz NULL ko'rsatkichlari uchun ham raqam berishimiz kerak. Agar barcha barg tugunlari balandligi h yoki h - 1 balandlikda bo'lsa va ketma-ketlikda ruxsat berilgan raqamlarsiz bo'lsa, ikkilikli daraxt deyiladi.

Ikkilik qidiruv: Qidiruv oralig'ini yarmiga kamaytirish orqali tartiblangan massivni qidiring. To'liq qatorni o'z ichiga olgan oraliq bilan boshlang. Agar qidiruv kalitining qiymati oraliq o'rtadagi elementdan kamroq bo'lsa, oraliqni pastki yarmigacha toraytiring. Aks holda uni yuqori yarmigacha toraytiring. Qiymat topilguncha yoki oraliq bo'sh bo'lguncha takroran tekshiring.

Masalan:

n elementlarning tartiblangan massivi berilgan holda, berilgan x elementni massiv ichidan qidirish funktsiyasini hosil qilamiz.

Ikkilik qidirish g'oyasi qator tartiblangan ma'lumotlardan foydalanish va vaqtning murakkabligini O (Log n) ga kamaytirishdir.

Biz asosan bitta taqqoslashdan so'ng elementlarning yarmini e'tiborsiz qoldiramiz.

1. 
   O'rta element bilan x ni taqqoslang.
   
2. 
   Agar x o'rta elementga to'g'ri kelsa, o'rtadagi indeksni qaytaramiz.
   
3. 
   Boshqa x agar o'rtadagi elementdan katta bo'lsa, x faqat o'rta elementdan keyin o'ng yarimorolda yotishi mumkin. Shunday qilib, biz o'ng yarmida takrorlaymiz.
   
4. 
   Boshqa chap tomonda (x kichikroq) takrorlanish.