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

 
Nazorat savollari 
1. Qidiruv vazifasi nimadan iborat? 
2. Noyob kalit deganda nimani tushunasiz? 
3. Ro’yxatda berilgan kalitli element yo’q bo’lganda qaysi amal bajariladi? 
4. Ketma-ket qidiruv va indeksli ketma-ket qidiruvlarning farqi nimadan 
iborat? 
5. Ulardan qaysi biri samaraliroq va nima sababdan? 
6. Jadvalni qayta tartiblashning qanday usullarini bilasiz?
7. Topilgan elementni boshiga qo’yish usulining transpozisiya usulidan asosiy 
farqlari nimalardan iborat? 
8. Mazkur usullar ma’lumotlar qanday ko’rinishda berilganda tezroq ishlaydi? 
9. Ular qanday ro’yxatlarda ishlaydi, ya’ni tartiblangan yoki ixtiyoriy?
10. Binar qidiruvning mazmun va mohiyati nimadan iborat? 
11. Qanday qilib binar daraxtni chetlab o’tish mumkin? 
12. Binar qidiruvni massivda ishlatish mumkinmi? 
13. Agar bo’sh bo’lmagan daraxtda ildiz o’chiriladigan bo’lsa, u holda uning 
o’rniga qaysi element o’tadi? 
Adabiyotlar. 

---

1. Adam Drozdek. Data structure and algorithms in C++. Fourth edition. 2013. 
Chapter 9. 

---

Document Outline

• Reja:
• 1. Ketma-ket qidiruv
• 2. Indeksli ketma-ket qidiruv
• N = 0,
• 4. Indeksli ketma-ket qidiruvni samaradorligi
• Bu yerdan
• Q = +1
• 5. Qidiruvni mukammallashtirish usullari
• 5.1 Topilgan elementni ro’yxat boshiga qo’yish orqali jadvalni qayta tartiblash
• Transpozisiya usuli
• Chizma. Qo’shni elementlarni o’rnini almashtirish
• Mukammal qidiruv daraxti
• C1 = 2r1+1r2+2r3+2q0+2q1+2q2+2q3
• Binar qidiruv (teng ikkiga bo’lish usuli)
• Agar S – taqqoslashlar soni va n – jadvaldagi elementlar soni bo’lsa, u holda
• Nazorat savollari
• Adabiyotlar.