15-ma’ruza. Qidiruv usul va algoritmlarini tadqiq qilish Reja

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