Algoritmi. Guruh : 212-17 Bajardi : Boltaboyev n tekshirdi : Atadjanova. M

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI
VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Sun’iy intellekt fani bo`yicha

Amaliy ish №7
Mavzu: Qidiruv “Optimal search” algoritmi.


Guruh : 212-17
Bajardi : Boltaboyev N
Tekshirdi : Atadjanova.M

7-Mavzu: Qidiruv “Optimal search” algoritimi.
Ishdan maqsad: Mantiqiy masalalar uchun Optimal qidiruvni o’rganish.
Masalaning qo’yilishi: Optimal search algortimi orqali x o o`yinini tahlil qilish.
Nazorat savollari

1. 
   Ikkilik daraxt nima?
   
2. 
   Qidiruv daraxtini tushuntiring?
   
3. 
   Kichik solishtirishlar amali haqida gapirib bering?
   

Javoblar.
1.Ikkilik daraxt - bu har bir tugun nolga teng, bitta yoki ko'pi bilan ikkita boladan iborat bo'lgan ierarxik ma'lumotlar tuzilishi. Har bir tugun "chap" ko'rsatkichni, "o'ng" ko'rsatkichni va ma'lumotlar elementini o'z ichiga oladi. "Ildiz" ko'rsatkichi daraxtning eng yuqori tugunini anglatadi. Ma'lumotlar tarkibidagi har bir tugun to'g'ridan-to'g'ri bolalar deb ataladigan har ikki tomonning o'zboshimchalik bilan soniga bog'liq. Null ko'rsatkichi ikkilik daraxtni anglatadi. Ikkilik daraxtda tugunlarni qanday tashkil qilish bo'yicha aniq tartib yo'q. Bolalar tugunlari bo'lmagan tugunlarga barg tugunlari yoki tashqi tugunlar deyiladi.


2.Qidirish daraxti - bu "buyurtma qilingan ikkilik daraxti" deb nomlanadigan tugunlar tartibda joylashtirilgan ikkilik daraxtlar ma'lumotlari tizimining bir turi. Bu tugunlarga asoslangan ma'lumotlarning tuzilishi bo'lib, u ma'lumotlarni saralash, olish va qidirishning samarali va tezkor usulini ta'minlaydi. Har bir tugun uchun chap pastki qismning elementlari uning asosiy tugunidagi kalitdan kam yoki unga teng bo'lishi kerak. Ikkilamchi kalitlar bo'lmasligi kerak. Oddiy qilib aytganda, bu elementlarni xotirada samarali saqlaydigan va boshqaradigan ikkilik daraxt ma'lumotlari tuzilmasining maxsus turi.
3.Ikkilik daraxt va ikkilik qidiruv daraxti ta'rifi - ikkilik daraxt - bu bolada nol, bitta yoki maksimal ikkita bola tugunlari bo'lishi mumkin bo'lgan ierarxik ma'lumotlar tuzilishi; har bir tugun chap ko'rsatgichni, o'ng ko'rsatgichni va ma'lumotlar elementini o'z ichiga oladi. Daraxtda tugunlarni qanday tashkil qilish kerakligi to'g'risida alohida tartib yo'q. O'z navbatida, ikkilik qidirish daraxti - bu tugunlarni qanday tartibga solish kerakligi haqida nisbatan buyurtma mavjud bo'lgan buyurtma qilingan ikkilik daraxti.
Ikkilik daraxt va ikkilik qidiruv daraxtining tuzilishi - Daraxtdagi eng yuqori tugun ikkilik daraxtdagi ildiz ko'rsatkichini, chap va o'ng tomondagi chiziqlar ikkala tomonning kichik daraxtlarini bildiradi. Bu daraxt tuzilishidagi ma'lumotlarni aks ettiradigan ixtisoslashgan daraxt shakli. O'z navbatida, ikkilik qidiruv daraxti - bu chap qismdagi barcha tugunlar ildiz tugunining qiymatidan kam yoki unga teng bo'lgan va o'ng pastki satrning qiymatidan kattaroq yoki unga teng bo'lgan ikkilik daraxt turi. ildiz tugunidan.
Ikkilik daraxt va ikkilik qidiruv daraxti ishlashi - Ikkilamchi daraxt ikkita bolasi va bitta ota-onasi bo'lgan har qanday narsa bo'lishi mumkin. Ikkilik daraxtda bajarilishi mumkin bo'lgan keng tarqalgan operatsiyalar qo'shilish, o'chirish va ayirishdir. Ikkilamchi qidirish daraxtlari - bu tezkor va samarali qidirish, kiritish va o'chirishga imkon beradigan saralangan ikkilik daraxtlar. Ikkilik daraxtlardan farqli o'laroq, ikkilik qidirish daraxtlari kalitlarini tartiblashtiradi, shuning uchun izlash odatda operatsiyalar uchun ikkilik qidiruvni amalga oshiradi.
Ikkilik daraxt va ikkilik qidiruv daraxti turlari - "Ikkilamchi daraxt", "to'liq binar daraxt", "mukammal binar daraxti" va "kengaytirilgan ikkitali daraxt" kabi turli xil turlari mavjud. Ikkilamchi qidirish daraxtlarining ba'zi keng tarqalgan turlari orasida daraxtlar, AVL daraxtlari, splay daraxtlari, tanang daraxtlari, qizil-qora daraxtlar va boshqalar mavjud.
Optimal search algortimi orqali x o o`yinini tahlili.