Ikkkilik qidruv daraxti

![KIRISH
Mavzuning dolzarbligi .Bugungi kunda ma‘lumotlar oqimining ko‘pligi
tufayli ularni qisqa vaqt ichida qayta ishlash muommosi ham ortib bormoqda.
Hozirgi vaqtda axborot- kommunikasiya vositalari barcha turdagi tashkilot va
muassasalarga shiddat bilan kirib kelmoqda. Axborotlarning haddan tashqari
ko‘pligi bu axborotlarni saqlashda, qayta ishlashda, hamda har xil turdagi
tizimlarni yaratish, ulardan keng foydalanishni va axborot tizimlari yaratishni talab
qiladi. O‘zbekiston Respublikasi Prezidentining 2017 yil 7 fevraldagi PF-4947-son
Farmoni bilan tasdiqlangan 2017-2021 yillarda O‘zbekiston Respublikasini
rivojlantirishning beshta ustuvor yo‘nalishi bo‘yicha harakatlar strategiyasi
mamlakatning davlat va jamiyat rivojlanishi istiqbolini strategik rejalashtirish
tizimiga sifat jihatdan yangi yondashuvlarni boshlab berdi[1]. Unda belgilangan
vazifalar sirasida ta‘lim va fan sohasini rivojlantirish ham aloxida ko‘zda tutilgan.
O‘zbekiston Respublikasi birinchi Prezidentining 2012 yil 21 martdagi
“Zamonaviy axborot-kommunikasiya texnologiyalarini yanada joriy etish va
rivojlantirish chora-tadbirlari to‘g‘risida”gi PQ-1730 Qarori hamda “O‘zbekiston
Respublikasida —Elektron ta‘lim milliy tarmog‘ini yaratish” investision loyihasini
amalga oshirish chora-tadbirlari to‘g‘risida” gi PQ-1740 Qarori va me‘yoriy
hujjatlar asosida algoritmik ta‘minot ishlab chiqish va joriy etish keng ko‘lamli
hisoblanadi. Barcha tashkilot va muassasalarda avtomatlashtirilgan tizimlar
yaratish ulardan keng ko‘lamda foydalanish uchun algoritmlash tillarini o‘rni katta
hisoblanadi.
Axborot tizimlari axborotni to‘plash, saqlash va qayta ishlash uchun, keng
imkoniyatli maqsadlarda samarali foydalanish uchun xizmat qiladi. Zamonaviy
axborotlashtirish tizimi, ma‘lumotlar integratsiyasi konsepsiyasiga asoslangan
katta hajmdagi ma‘lumotlarni saqlash bilan tavsiflanadi va ko‘p sondagi
foydalanuvchilarning turli xildagi talablariga javob berishi kerak bo‘ladi. Axborot
tizimi va axborot texnologiyalarining avtomatlashtirilgan elementlarini qo‘llash va
avtomatlashtirish asosida yangi axborot texnologiyasini yaratish avtomatlashtirish
tizimlarini loyihalashtiruvchilarning asosiy vazifalaridan biri hisoblanadi.
Avtomatlashtirilgan tizimlarni yaratish uchun albatta birinchi navbatda muommo
obektini infologik yoki diskretli modelini qurish dolzarb hisoblanadi. Infologik
yoki diskretli modelni muommo obektiga qarab algoritmlash tillarini qaysi biri
asosida yaratish kerakligini tanlab olinish kerak. Elektron hisoblash mashinalarini
birinchi avlodlari yaratilishi bilan algoritmlash tillarini rivojlanishi ham boshlandi.
2](/data/documents/a3dcf1ad-a280-45d2-a5f1-ebe663381ab0/page_2.png)
Mavzu: “Ikkkilik qidruv daraxti ” MUNDARIJA Mavzu: “Ikkkilik qidruv daraxti ” ............................................................... 1 MUNDARIJA ................................................................................................. 1 KIRISH ............................................................................................................ 2 1.1.Boshlang’ich tushunchalar va ta’riflar .................................................. 4 Misol: ........................................................................................................... 8 1.3.Ma’lumotlar tuzilmasi va ularning klassifikatsiyasi ........................... 10 Misol: Ketma-ket qidiruv va Binar qidiruv algoritmlarini solishtirishga misol.(C++ tilida) .................................................................................................... 20 Xulosa ............................................................................................................ 22 Foydalanilgan adabiyotlar va internet saytlari nomlari ................................ 29
KIRISH Mavzuning dolzarbligi .Bugungi kunda ma‘lumotlar oqimining ko‘pligi tufayli ularni qisqa vaqt ichida qayta ishlash muommosi ham ortib bormoqda. Hozirgi vaqtda axborot- kommunikasiya vositalari barcha turdagi tashkilot va muassasalarga shiddat bilan kirib kelmoqda. Axborotlarning haddan tashqari ko‘pligi bu axborotlarni saqlashda, qayta ishlashda, hamda har xil turdagi tizimlarni yaratish, ulardan keng foydalanishni va axborot tizimlari yaratishni talab qiladi. O‘zbekiston Respublikasi Prezidentining 2017 yil 7 fevraldagi PF-4947-son Farmoni bilan tasdiqlangan 2017-2021 yillarda O‘zbekiston Respublikasini rivojlantirishning beshta ustuvor yo‘nalishi bo‘yicha harakatlar strategiyasi mamlakatning davlat va jamiyat rivojlanishi istiqbolini strategik rejalashtirish tizimiga sifat jihatdan yangi yondashuvlarni boshlab berdi[1]. Unda belgilangan vazifalar sirasida ta‘lim va fan sohasini rivojlantirish ham aloxida ko‘zda tutilgan. O‘zbekiston Respublikasi birinchi Prezidentining 2012 yil 21 martdagi “Zamonaviy axborot-kommunikasiya texnologiyalarini yanada joriy etish va rivojlantirish chora-tadbirlari to‘g‘risida”gi PQ-1730 Qarori hamda “O‘zbekiston Respublikasida —Elektron ta‘lim milliy tarmog‘ini yaratish” investision loyihasini amalga oshirish chora-tadbirlari to‘g‘risida” gi PQ-1740 Qarori va me‘yoriy hujjatlar asosida algoritmik ta‘minot ishlab chiqish va joriy etish keng ko‘lamli hisoblanadi. Barcha tashkilot va muassasalarda avtomatlashtirilgan tizimlar yaratish ulardan keng ko‘lamda foydalanish uchun algoritmlash tillarini o‘rni katta hisoblanadi. Axborot tizimlari axborotni to‘plash, saqlash va qayta ishlash uchun, keng imkoniyatli maqsadlarda samarali foydalanish uchun xizmat qiladi. Zamonaviy axborotlashtirish tizimi, ma‘lumotlar integratsiyasi konsepsiyasiga asoslangan katta hajmdagi ma‘lumotlarni saqlash bilan tavsiflanadi va ko‘p sondagi foydalanuvchilarning turli xildagi talablariga javob berishi kerak bo‘ladi. Axborot tizimi va axborot texnologiyalarining avtomatlashtirilgan elementlarini qo‘llash va avtomatlashtirish asosida yangi axborot texnologiyasini yaratish avtomatlashtirish tizimlarini loyihalashtiruvchilarning asosiy vazifalaridan biri hisoblanadi. Avtomatlashtirilgan tizimlarni yaratish uchun albatta birinchi navbatda muommo obektini infologik yoki diskretli modelini qurish dolzarb hisoblanadi. Infologik yoki diskretli modelni muommo obektiga qarab algoritmlash tillarini qaysi biri asosida yaratish kerakligini tanlab olinish kerak. Elektron hisoblash mashinalarini birinchi avlodlari yaratilishi bilan algoritmlash tillarini rivojlanishi ham boshlandi. 2
Yuqoridagi keltirilgan vazifalarni amalga oshirish uchun algoritmlar va ma‘lumotlar strukturasi fani asosiy fan sifatida xizmat qiladi. Katta hajmdagi ma‘lumotlarni kompyuterda saqlash muommosini hal etish yo‘llari, algoritmlar va ma‘lumotlar strukturasi fanining maxsus algoritmlari orqali amalga oshiriladi. Ikkilik (binar) qidirish algoritmi Qidirilayotgan elementni saralangan ro‘yxatning o‘rtasidagi element bilan taqqoslash natijasida quyidagi uchta holatdan biri bo‘lishi mumkin: qidirilayotgan element topildi, o‘rtadagi elementdan kichik yoki katta. Birinchi (eng yaxshi) holatda qidiruv tugallanadi. Qolgan ikki holatda ro‘yxatning yarmini tashlab yuborish mumkin. Qidirilayotgan qiymat o‘rta elementdan kichik bo‘lsa, u holda bu qiymat o‘rta qiymatdan oldin, aks holda (katta bo‘lsa), o‘rta qiymatdan keyin joylashganbo‘ladi. Bu protsedura yana takrorlanishi natijasida ajratib olingan qismro‘yxatning yana yarmini tashlab yuborish mumkin bo‘ladi. Kurs ishining maqsadi: Tasodifiy ikkilik qidiruv daraxti mavzusini o’rganish Kurs ishining tuzilishi : Kurs ish kirish, 2 bob, 6 bo‘lim, umumiy xulosalar va tavsiyalar, foydalanilgan adabiyotlar ro‘yhatidan iborat bo‘lib, jami 30 sahifani tashkil qiladi 3
I Bob. MA’LUMOTLAR TUZILMASI VA ALGORITMLAR NAZARIYASIGA KIRISH 1.1. Boshlang’ich tushunchalar va ta’riflar Kompyuter - bu ma‘lumotlarni qayta ishlovchi mashina. EHM (kompyuter) haqidagi fanlarni o‘rganishda, shunday savollar tug‘iladi: axborotlar kompyuter ichida qanday ko‘rinishda tashkil etiladi, uni qanday qayta ishlaydi va qanday ko‘rinishda tasvirlaydi? SHu bilan birgalikda fanni o‘rganishda asosan ma‘lumotlar bilan ishlash va ma‘lumotlarni tashkil etish kontseptsiyalarini o‘rganishimiz zarur bo‘ladi. Demak, kompyuterning asosiy tushunchalaridan biri axborot tushunchasi bo‘ladigan bo‘lsa, axborot (ma‘lumot) nima? - degan savol tug‘iladi. Bu savolga bir qiymatli javob topish mushkuldir. CHunki bu tushuncha informatika va informatsion texnologiyalari sohasidagi fanlarning asosiy tushunchasi hisoblanadi. Ma‘lumki, fanning asosiy tushunchalari ta‘riflarsiz, izohlarsiz qabul qilinadi. Masalan, geometriya fanidagi «nuqta», «to‘g‘ri chiziq», «tekislik» kabi tushunchalar bunga misoldir. Sababi, bu kabi tushunchalarni ularga nisbatan elementar bo‘lgan tushunchalar orqali izohlash mumkin emas. Axborotning asosiy birligi sifatida, o‘zaro bir-biriga bog‘liq bo‘lmagan ikkita qiymatni qabul qilishi mumkin bo‘lgan bit tushunchasi kiritilgan. Bu birlik qabul qila oladigan qiymatlar ikkilik sanoq sistemasida - nol va bir hisoblanadi. Aniq bir kompyuterda belgilarni kodlashtirish uchun bitning bir nechtasi orqali guruhlarga ajratib olinadi. Ajratilgan guruhdagi bitlar to‘plami bayt deb ataladi. Ko‘pchilik kompyuterlarda bayt o‘lchami 8 bitdan tashkil topadi. Hisoblash mashinasining xotira qurilmalari bitlar majmuasidan tashkil topadi, ya‘ni ixtiyoriy vaqt momentida kompyuter xotirasida 0 yoki 1 qiymat mavjud bo‘ladi. Bit holati uning qiymati yoki mazmunini bildiradi. Bitlar guruhi EHM xotirasida katta hajmdagi elementlarni ifodalaydi. Masalan, baytlarda o‘lchanadigan elementlar. Ba‘zi bir kompyuterlarda baytlar guruhlarga ajratilib mashina so’zi deb nomlanadi. Har bir shunday element o‘z nomi (identifikatori)ga ega bo‘lgan adreslarni ifodalaydi. Bu adreslar odatda sonli formatga ega bo‘ladi. U yacheyka deb ataladi, bu yacheykalar o‘zida bitlar majmuasini saqlab turadi. 4