Test gift and xml


Кўп ўлчамли дарахтларни бинар кўринишга келтириш амалини тушунтириб беринг


Download 1.72 Mb.
bet31/34
Sana30.04.2023
Hajmi1.72 Mb.
#1413071
1   ...   26   27   28   29   30   31   32   33   34
Bog'liq
Algaritm umumiy

63. Кўп ўлчамли дарахтларни бинар кўринишга келтириш амалини тушунтириб беринг.
Ko’p o’lchamli daraxtni binar ko’rinishga keltirishning noformal algoritmi:

  • Daraxtning xar bir tugunida katta o’g’ilga mos chetki chap shoxidan tashqari barcha shoxlari kesib tashlanadi.

  • Bitta otaga barcha o’g’illari gorizontal chiziq bilan ulanadi.

  • Hosil qilingan tuzilmaning har bir tugunida katta o’g’il mazkur tugun pastida turgan tugun xisoblanadi (agar u mavjud bo’lsa).


64. Бинар дарахтга таъриф беринг, мисоллар келтиринг.
Binar daraxt har bir tugunga ikkitadan ko’p bo’lmagan tugunlar bog’langan tartiblangan daraxt.

  • ::= ( ) |

  • ::=

  • ::=


Umumiy holda binar daraxtning har bir elementi (tuguni) to’rtta maydonga ega yozuvdan tashkil topgan bo’ladi.



65. Бинар қидирув дарахтини қуриш принципларини тушунтириб беринг.

  • Mazkur amal (algoritm)ning vazifasi shundan iboratki, u berilgan qiymat bo’yicha daraxt tugunini izlab topishga yordam beradi. Qidiruv operatsiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt bir tomonga yo’nalgan ro’yxat hosil qiladi (chiqish darajasi bir bo’ladi, ya’ni yagona shohga ega), masalan:

  • Bu holda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yxatdagi kabi bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi.

  • Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi. Bu holda qidiruv dan ko’p bo’lmagan elementlarni ko’rib chiqadi.



Download 1.72 Mb.

Do'stlaringiz bilan baham:
1   ...   26   27   28   29   30   31   32   33   34




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling