Reja qidiruv binar daraxti tushunchasi

Biror bir qidiruvda kutilayotgan taqqoslashlar soni quyidagicha bo’ladi:

• Biror bir qidiruvda kutilayotgan taqqoslashlar soni quyidagicha bo’ladi:
• C1 = 2p1+1p2+2p3+2q0+2q1+2q2+2q3
• C2 = 2p1+3p2+1p3+2q0+3q1+3q2+1q3
• TA”RIF .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 qidiruvni amalga oshirish ancha samarali bo’ladi. Afsuski, ko’pincha, qidiruv argumenti extimolligi oldindan aniq bo’lmaydi.
• Binar daraxt bo’yicha qidiruv prosedurasi 
• Mazkur proseduraning vazifasi shundan iboratki, u berilgan kalit bo’yicha daraxt tuguni qidiruvini amalga oshiradi.
• Qidiruv operasiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi.
• Haqiqatdan, agar elementlar daraxtga kalit 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.
• Qidiruv prosedurasini ko’rib chiqamiz:
• search o’zgaruvchisiga topilgan bo’g’in ko’rsatkichi o’zlashtiriladi:

int search(node *tree, int key){
node *next; next=tree;
while(next!=NULL) { if (next->info==key){cout<<"Binar daraxtda "< if (next->info>key) next=next->left;
else next=next->right;
}
cout<<"tuzilmada izlangan element yo’q!!!"<
return 0