Qidiruv binar daraxti tushunchasi Qidiruv binar daraxtini qurish

11- MAVZU Qidiruv binar daraxti. Qidiruv binar daraxtini qurish. Tugunlar qo‘shish va o‘chirish .

REJA

Qidiruv binar daraxti tushunchasi

Qidiruv binar daraxtini qurish.

Binar daraxtda qidiruv, tugunlar qo‘shish va o‘chirish

Asosiy adabiyotlar ro‘yxati

• Alfred V. Axo., Djon E. Xopkroft, Djefri D. Ulman. Struktura dannыx i algoritmы//Ucheb.pos., M. : Izd.dom: "Vilyams", 2000, — 384 s.
• Baknell Djulian M. Fundamentalnыe algoritmы i strukturы dannыx v Delphi//SPb: OOO «DiaSoftYUP», 2003. 560s.
• Robert Sedjvik. Fundamentalnыe algoritmы na C++. Analiz, Strukturы dannыx, Sortirovka, Poisk//K.: Izd. «DiaSoft», 2001.- 688 s.
• Dinman M.I. S++. Osvoy na primerax//SPB.:BXV-Peterburg, 2006, 384.
• SHildt, Gerbert. Polnыy spravochnik po S#//M. : Izd. dom "Vilyamc", 2004, 752 s.
• Virt N. Algoritmы i strukturы programmы//M., Mir, 1985.

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 ( bunda u ildizning kaliti).

Mantiqiy bosqich
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.
U holda p1+p2+p3+q0+q1+q2+q3 = 1

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

dan ko’p bo’lmagan elementlarni ko’rib chiqadi
Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi. Bu holda qidiruv
dan ko’p bo’lmagan elementlarni ko’rib chiqadi

• 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!!!"<