Ma’lumotlar tuzilmasi va algoritmlar fanining maqsad va vazifasini izohlab bering


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



Yüklə 1,56 Mb.
səhifə30/32
tarix05.10.2023
ölçüsü1,56 Mb.
#152400
1   ...   24   25   26   27   28   29   30   31   32
MTA oraliq javoblai

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.


  • Shuni esda tutish lozimki, binar daraxt hosil qilinayotganda, otaga nisbatan chap tomondagi o’g’il qiymati kichik, o’ng tomondagi o’g’il qiymati katta bo’lishi lozim.


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.



Yüklə 1,56 Mb.

Dostları ilə paylaş:
1   ...   24   25   26   27   28   29   30   31   32




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin