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.
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.
