4. Dinamik ma‟lumotlar tuzilmasi haqida ma’lumot bering

46. Binar (ikkilik) daraxtlar deganda nimani tushunasi.

Buni chalkashtirib yubormaslik kerak B daraxti.

Ildiz tuguni bilan qiymati 9 bo'lgan va balandligi 3 ga teng bo'lgan ikkilik daraxt, yuqoridagi daraxt muvozanatsiz va tartiblanmagan.
Advertisement
Yilda Kompyuter fanlari, a ikkilik daraxt a daraxt ma'lumotlari tuzilishi unda har bir tugun ko'pi bilan ikkitadan bolalar deb nomlangan chap bola va o'ng bola. A rekursiv ta'rif faqat foydalanish to'plam nazariyasi tushunchalar shundan iboratki (bo'sh bo'lmagan) ikkilik daraxt a panjara (L, S, R), qaerda L va R ikkilik daraxtlar yoki bo'sh to'plam va S a singleton to'plami ildizni o'z ichiga olgan.[1] Ba'zi mualliflar ikkitomonlama daraxtga ham bo'sh to'plam bo'lishiga ruxsat berishadi.[2]
A dan grafik nazariyasi bu erda aniqlangan istiqbolli, binar (va K-ary) daraxtlar aslida daraxtzorlar.[3] Ikkilik daraxtni shunday deb ham atash mumkin ikki tomonlama daraxtzor[3]- bu juda qadimgi dasturlash kitoblarida uchraydigan atama,[4] ilgari zamonaviy informatika terminologiyasi ustun kelgan. Ikkilik daraxtni an deb talqin qilish ham mumkin yo'naltirilmagan, a o'rniga yo'naltirilgan grafik, bu holda ikkilik daraxt an buyurdi, ildiz otgan daraxt.[5] Ba'zi mualliflar foydalanadilar ikkilik daraxt o'rniga ikkilik daraxt daraxtning ildiz otganligini ta'kidlash uchun, lekin yuqorida ta'riflanganidek, ikkilik daraxt har doim ildiz otadi.[6] Ikkilik daraxt - bu buyurtma qilingan alohida holat K-ary daraxti, qayerda k 2.


47. Daraxt va unga ekvivalent tushunchalarini yoritib bering
Daraxtlar va ularga ekvivalent tushunchalar
Siklga ega bo‘lmagan orientirlanmagan bog'lamli graf daraxt deb ataladi. Ta’rifga
ko‘ra daraxt sirtmoqlar va karrali qirralarga ega emas. Siklga ega bo‘lmagan orientirlanmagan graf o‘rmon (asiklik graf) deb ataladi.
Quyidagi shaklda bog`lamli komponentli soni beshga teng bo`lgan graf tasvirlangan bo‘lib, u o‘rmondir. Bu grafdagi bog‘lamli komponentlaming har biri daraxtdir.
Q uyidagi shaklda esa to`rtta uchga ega bir biriga izomorf bo`lmagan barcha (ular bor yo`g`i ikkita)
daraxtlarning geometrik ifodalanishi ko`rsatilgan.
Beshta uchga ega bir-biriga izomorf bo‘lmagan barcha daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko‘rsatish qiyin emas.
Dasturlashda xotirani va vaqtni tejash maqsadida mantiq algebrasi funksiyalari bilam ishlaganda, ularni “tabiiy” (massivlarda) ifodalamasdan,mantiqiy amallarni bajarishga maxsus yo‘naltirilgan ko‘rinishda ifodalash samaraliroq hisoblanadi. Buning uchun n o‘zgaruvchili Bul funksiyasi rostlik jadvalini n+1 balandlikdagi to‘liq binar daraxt ko‘rinishida ifodalash mumkin. Daraxt yaruslari (qavatlari) o‘zgaruvchilarga mos keladi, daraxt shoxlari esa o‘zgaruvchilar qiymatlariga mos keladi. Har bir mulohaza o’zgaruvchisidan ikkita shih chiqib, chap shoxga – 0, o‘ng shoxga esa – 1 qiymat mos qo‘yiladi. Daraxt yaproqlari – oxirgi yarusda esa daraxt ildizidan shu yaproqgacha bo‘lgan yo‘lga mos kortejdagi funksiya qiymatlari mos qo‘yiladi. Bunday daraxt yechimlar daraxti yoki semantik daraxt deyiladi. Buni quyidagicha misolda ko‘rib chiqamiz. F(A,B,C) funksiya quyidagicha rostlik jadvali bilan.berilgan,bo‘lsin.