12-mavzu. Topilgan elementni ro’yxat boshiga qo’yish orqali qidiruv jadvalini qayta tartiblash. Transpozitsiya usuli

p – ishchi ko’rsatkich
q – yordamchi ko’rsatkich, p dan bitta qadam orqada bo’ladi;
s – yordamchi ko’rsatkich, p dan ikkita qadam orqada bo’ladi;
Transpozitsiya usuli bilan ro’yhatni qayta tartibga keltirish
Biz tomonimizdan topilgan uchinchi element ro’yhat boshiga bir qadam suriladi (ya’ni ikkinchi bo’lib qoladi). Birinchi element ko’rsatkichi uchinchi elementga joylashtiriladi, ikkinchi element ko’rsatkichi to’rtinchi, shunday qilib uchinchi element ikkinchi joyga joylashib qoladi. Agar mazkur elementga yana bir bor murojaat qilinsa, u holda u ro’yhat boshida bo’lib qoladi.
13-mavzu. Mukammal qidiruv daraxti. Binar daraxt bo’yicha qidiruv. Qo’yish orqali qidiruv (qo’shish orqali). O’chirish orqali qidiruv.
Reja:

• Mukammal qidiruv daraxti.
• Binar daraxt bo’yicha qidiruv.

Mukammala qidiruv daraxti.
Agar ajratib olingan elementlar qandaydir o’zgarmas to’plamni tashkil qilishsa, kelgusi qidiruvlar samaraliroq bo’lishi uchun ularni binary daraxt ko’rinishida ifodalash maqsadga muvofiq bo’lishi mumkin.
Quyida keltirilgan daraxtlarda binary qidiruvni ko’rib chiqaylik (a) va (b) chizma). Ikkala daraxt ham uchtadan elementga ega - к1, к2, к3 bo’lib bu yerda к1<к2<к3. к3 elementni qidirish (a) chizmada ikkita taqqoslashni talab qilsa, (b) chizmada esa bitta.
Biror bir yozuvni ajratib olish uchun zarur bo’lgan kalitlarni taqqoslashlar soni binary qidurv daraxtidagi ushbu yozuv bosqichiga birni qo’shganiga teng.
Faraz qilaylik:
qidiruv argumenti key = к1 bo’lishi ehtimolligi - p1,
qidiruv argumenti key = к2 bo’lishi ehtimolligi – p3,
qidiruv argumenti key = к3 bo’lishi ehtimolligi – p3,
key < к1 bo’lishi ehtimolligi – q0,
к2 > key > к1 bo’lishi ehtimolligi – q1,
к3 > key > к2 bo’lishi ehtimolligi – q2,
key > к3 bo’lishi ehtimolligi – q3,
C1 - a) chizmadagi taqqoslashlar soni,
C2 - b) chizmadagi taqqoslashlar soni.
Chizma a)
Chizma b)
U holda
р1+р2+р3+q0+q1+q2+q3 = 1
Biror bir qidiruvda kutilayotgan taqqoslashlar soni quyidagicha bo’ladi:
C1 = 2р1+1р2+2р3+2q0+2q1+2q2+2q3
C2 = 2р1+3р2+1р3+2q0+3q1+3q2+1q3
Biror bir berilgan kalitlar va ehtimolliklar to’plamida kutilayotgan taqqoslashlar sonini minimallashtiruvchi binary qidiruv daraxti mukammal deyiladi. Garchi daraxt yaratish algoritmi ancha sermashaqqat ish bo’lsada, biroq u yaratgan daraxtda qidiruvni amalga oshirish ancha samarali bo’ladi. Afsuski ko’pincha, qidiruv argumenti ehtimolligi oldindan aniq bo’lmaydi.