O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

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.