logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. Balanslangan qidiruv daraxtlari

Balanslangan qidiruv daraxtlari

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

1621.2275390625 KB
Ko'chirib olish
Balanslangan qidiruv daraxtlari MUNDARIJA KIRISH ............................................................................................................ 2 Haqiqiy ikkilik qidiruv .................................................................................. 12 ADABIYOTLAR RO’YXATI ...................................................................... 29 KIRISH Fanda daraxtlar haqida ma’lumot Daraxt - bu bog langan asiklik graf, ya‘ni sikllar yo q va uchlar juftligi orasidaʻ ʻ bitta yo l bor . Kirishning nol darajasiga ega bo lgan uch daraxtning ildizi, chiqish ʻ ʻ nol darajaga ega tugunlar esa barglar deb nomlanadi. Ulanish har qanday uchlar juftligi o rtasida marshrut mavjudligini anglatadi, aylanuvchanlik sikllar yo qligini ʻ ʻ anglatadi. Demak, xususan, shundan kelib chiqadiki, daraxtdagi qirralarning soni uchlar sonidan bitta kamroq va har qanday uchlar juftlari orasida bitta va faqat bitta yo l bor. O rmon – juda ko p daraxtlardir. Yo naltirilgan (oriyentirlangan) daraxt - ʻ ʻ ʻ ʻ bu faqat bitta vertikal kirish nol darajasiga ega bo lgan (boshqa yoylar unga olib ʻ kelmaydigan), boshqa uchlarning kirish darajasi 1 bo lgan siklik orgraf (sikllarni ʻ o z ichiga olmaydigan yo naltirilgan graf). ʻ ʻ Daraxtning asosiy tushunchalari Ildiz tuguni - daraxtning eng yuqori tuguni . Ildiz – ixtiyoriy tanlab olingan uchlardan biri. Barg yoki terminal tuguni – avlodi mavjud bo lmagan tugun. ʻ Ichki tugun - bu daraxtga avlodi mavjud bo lgan har qanday tugun va shuning ʻ uchun barg tuguni emas . Uchning darajasi - unga tushgan qirralarning soni. Daraxt osti - bu alohida daraxt sifatida namoyish etilishi mumkin bo lgan daraxtga ʻ o xshash ma‘lumotlar strukturasining bir qismidir. T daraxtining har qanday tuguni ʻ va uning barcha nasl tugunlari bilan birga T daraxtining pastki daraxti hisoblanadi. Daraxt osti har qanday tuguni uchun, yo ushbu kichik daraxtning ildiz tuguniga yo l bo lishi kerak, yo tugunning o zi ildiz bo lishi kerak. Ya‘ni, kichik daraxt ildiz ʻ ʻ ʻ ʻ tuguniga butun daraxt bilan bog lanadi va boshqa barcha tugunlar bilan daraxt ʻ osti aloqasi tegishli daraxt osti tushunchasi orqali aniqlanadi (―to plam osti" ʻ atamasi bilan o xshashlik bo yicha). ʻ ʻ Daraxt strukturasi orasida tartiblangan daraxtlar eng keng tarqalgan. Binar (Ikkilik) qidiruv daraxti - tartiblangan daraxt turidir. Daraxtlar ustida bajariladigan umumiy amallar: 1) yangi elementni ma‘lum bir joyga kiritish; 2) daraxt osti kiritish; 3) daraxt shoxini qo shish (payvandlash deb ataladi);ʻ 4) har qanday tugun uchun ildiz elementini topish; 5) ikkita uchning eng kichik umumiy ajdodini topish; 6) daraxtning barcha elementlarini sanab chiqish; 7) daraxt novdasi elementlarini sanab chiqish; 8) izomorfik daraxt osti qidirish; 9) elementni qidirish; 10) daraxt shoxini olib tashlash; 11) daraxt ostini olib tashlash; 12) elementni o chirish. ʻ Daraxtlarning qo llanish sohalari: ʻ 1) ma‘lumotlar iyerarxiyasini boshqarish; 2) axborot olishni soddalashtirish 3) ma‘lumotlarning saralangan ro yxatlarini boshqarish; ʻ 4) arifmetik ifodalarni tahlil qilish (inglizcha parsing), dasturni optimallashtirish; 5) turli xil vizual effektlarni olish uchun raqamli rasmlarni yaratish texnologiyasi sifatida; 6) ko p bosqichli qaror qabul qilish shakllarida (shaxmat). ʻ Daraxtlarda qo shnilik (A) va insidentlik (B) matritsalari.ʻ Daraxtlar uchun bunday matritsalarning o ziga xos xususiyatlarini ta‘kidlaylik. N ʻ ga teng bo lgan daraxtning qirralari sonining nisbati bog langan graf uchun ʻ ʻ minimal, shuning uchun daraxtning qo shnilik matritsasi juda kam (ularning ʻ nisbati va undagi nollar yo naltirilgan daraxt uchun va yo naltirilmagan uchun). ʻ ʻ Daraxtning insidentlik matritsasi o lchamiga ega, ya‘ni kvadratga yaqin, va aslida, ʻ agar biz uning ortiqcha ekanligini hisobga olsak. Darhaqiqat, har qanday qatorni olib tashlab, biz avvalgidek grafni to liq tavsiflaydigan kvadrat matritsani olamiz. ʻ Quyida keltirilgan insident matritsasining yana bir xususiyati quyidagicha. Satr va ustunlarni qayta tartiblash orqali har qanday daraxtning insidentlik matritsasi ustun birliklaridan biri qatorda, ikkinchisi pastki qatorlardan birida bo lganda pastkiʻ trapetsiya matritsaga tushirilishi mumkin. Daraxt ketma-ket qirralarni qo shib quriladi. Keyingi qo shilgan chekka, ʻ ʻ birinchisidan boshlab, vertikal juftlik bilan hosil bo ladi, ularning raqamlari kod ʻ satrida va antikod satrida birinchi bo ladi. Shundan so ng, ishlatilgan satr ʻ ʻ elementlari chiziladi. Agar kod satridan chiqib ketgan raqam undagi qolgan elementlar qatoriga kiritilmagan bo lsa, uning tartibini buzmasdan antikod qatoriga ʻ qo shilishi kerak. Ta‘riflangan harakatlar kod va antikod satrlarining "qoldiqlari" ʻ bilan ularning birinchisining barcha elementlari o chirilguncha takrorlanadi. ʻ Bunday holda, antikod chizig ida hosil qilingan ro yxatga qo shiladigan so nggi ʻ ʻ ʻ ʻ chekkani belgilaydigan ikkita element bo ladi, natijada biz Pryufer kodi bilan ʻ belgilangan daraxtga mos keladigan n - 1 qirralarning ro yxatini olamiz. 3-misol. ʻ Masalan, 1-misolda berilgan 14166 kodi yordamida daraxtni tiklaylik. Yuqorida 1- misolda ko rsatilgandek mos keladigan antikod 2357 ni tashkil qiladi. Shuning ʻ uchun daraxtning birinchi qirrasi {1; 2}. 1 va 2-ni kesib o tib, biz kod satrida 4166 ʻ va antikod satrida 357 olamiz. Keyingi takrorlashda {4; 3} juftligini kesib tashlaymiz va qatorga antikod 4 ni kiritamiz va hokazo. Takrorlashlar ketma- ketligi 8- jadvalda keltirilgan. Qirralarning ro yxatini tahlil qilib, asl daraxt olinganligiga ishonch hosil qilamiz.ʻ E‘tibor bering, qirralarning tartibi avvalgi jadvaldagi kabi. AVL daraxt. AVL-daraxt (inglizcha AVL-Tree) bu muvozanatlashgan ikkilik qidiruv daraxti bo lib, unda quyidagi xususiyat qo llab-quvvatlanadi: uning har bir ʻ ʻ uchlari uchun uning ikkita ostki daraxtining balandligi 1 dan ko p bo lmagan ʻ ʻ qiymatga farq qiladi. AVL daraxtlari birinchi marta 1962-yilda AVL daraxtlaridan foydalanishni taklif qilgan G. M. Adelson-Velskiy va E. M. Landisning ismlarining birinchi harflari bilan nomlangan. Uchlarni muvozanatlash - bu | | chap va o ng pastki daraxtlari balandliklari farqi bo lgan taqdirda, | | daraxtining ʻ ʻ xususiyati tiklanishi uchun ushbu uchlarning pastki daraxtidagi ajdod va avlod munosabatlarini o zgartiradigan amal, aks holda hech narsani o zgartirilmaydi. ʻ ʻ Muvozanatlash uchun biz har bir uch uchun uning chap va o ng pastki daraxtlari ʻ balandliklari orasidagi farqni saqlaymiz. Daraxtning balandligi uning maksimal darajasi, ildizdan tashqi tugunga qadar eng uzun yo lning uzunligi sifatida ʻ aniqlanadi. Ikkilik qidiruv daraxti muvozanatli deyiladi, agar biron bir tugunning chap pastki daraxtining balandligi o ng pastki daraxtning balandligidan ± 1 dan ʻ oshmasa. Keyingi 36-rasmda ko rsatilgan 5 ta balandlikdagi 17 ta ichki tugunli ʻ muvozanatli daraxt; muvozanat koeffitsiyenti har bir tugun ichida belgilar bilan va o ng va chap pastki daraxtlar (+1, 0 yoki -1) balandliklari orasidagi farq kattaligiga ʻ muvofiq belgilanadi. “Daraxt” kalit so'zi bo'yicha qidiruv natijalari Qisqacha nazariy ma’lumot Binar daraxt – bu har biri boshqa turlicha binar daraxtlarga ikkitako’rsatkichlarni saqlab turuvchitugunlardan iborat dinamik ma’lumotlar tuzilmasi.Har bir tugunga bitta ko’rsatkich mavjud.Bunday tuzilmani quyidagicha shaklda tavsiflash mumkin: struct point {int data;//ma’lumot maydoni point *left;//chap qism daraxt manzili point *right;// o’ng qism daraxt manzili}; Boshlang’ich tugun daraxtning ildizi deyiladi. Qism daraxtga ega bo’lmagan tugun barg deb nomlanadi. Chiquvchiga ega bo’lgan tugunlar ajlod tugun, kiruvchiga ega bo’lgan tugunlar avlod tugun deyiladi. Daraxt balandligi uning tugunlari joylashgan bosqichlari soni bilan aniqlanadi.Agar daraxtning chap qism daraxtining barcha tugunlari qiymati ildiz tugun qiymatidan kichik, o’ng qism daraxti barcha tugunlari qiymati katta bo’lsa,qidiruv daraxti deyiladi. Bir xil qiymatli kalitlarga ruxsat etilmaydi. Qidiruv daraxtida elementni kaliti bo’yicha qidirish uchun ildizdan chap qismdaraxt yoki o’ngqismdarxtga harakatlanish orqali amalga oshiriladi. Bunda qidirilayotgan kalit qiymatining ildiz qiymatiga nisbatan kichik yoki katta ekanligi e’tiborga olinadi.Kichik bo’lsa, chap qism darxatdan, aks xolda o’ng qism daraxtdan qidiriladi. Bunday qidirish ro’yxatdan qidirishga nisbatan juda ham samarali, chunki, qidiruv vaqti daraxt tugunlar sonining ikkilik logarifmga proportsional bo’lgan daraxt balandligi bilan aniqanadi.Ideal muvozanatlashtirilgan daraxtning chap va o’ng tugunlari soni 1 tadan ko’p tugunga farq qilmaydi.Chiziqli ro’yxatni har bir tuguni bitta ko’p bo’lmagan ko’rsatkichli binar daraxt shaklda ifodalash mumkin. Ro’yxat uchun o’rtacha qidirish vaqti ro’yxatuzunligining yarmiga teng bo’ladi. Ikkilik qidirish algoritmi ishlash prinsipi Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter bilan o’yin o’ynab ko’ramiz. O’yin shartlari quyidagicha: Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish. Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o’ylagan sondan katta yoki kichikligini aytadi. Agar sizning taxminingiz kompyuter o’ylagan son bilan bir xil bo’lsa, o’yin tugaydi. Xo’sh, bunda kamroq yo’l tutish uchun nima qilgan bo’lar edingiz? Albatta, birinchi navbatda o’rtadagi sonni taxmin qilib ko’ramiz, ya’ni 50 ni Aytaylik kompyuter bizga taxminimiz o’ylangan sondan kichikroq ekanligini aytdi. Demak, endi biz 50 va undan kichik barcha son o’ylangan sondan kichik ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar o’rtasidagi sonni olamiz, ya’ni 75 ni Kompyuter bizga 75 o’ylangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham o’ylangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz o’ylangan sonni topishimiz mumkin. Sonlar 100 ta bo’lgan holatda, biz har qanday tahminni ko’pi bilan 7 ta qadamda topishimiz mumkin bo’ladi. Ikkilik qidirish algoritmi ham huddi shunday prinsipda ishlaydi! Quyida daraxtga oid muhim shartlar keltirilgan.  Yo'l - Yo'l daraxtning qirralari bo'ylab tugunlar ketma-ketligini bildiradi.  Ildiz - Daraxtning tepasidagi tugun ildiz deb ataladi. Har bir daraxtda faqat bitta ildiz va ildiz tugunidan istalgan tugungacha bitta yo'l mavjud.  Ota -ona - Ildiz tugunidan tashqari har qanday tugun ota-ona deb ataladigan tugunga bir qirraga ega.  Child - Berilgan tugun ostidagi qirrasi bilan pastga bog'langan tugun uning tugunlari deb ataladi.  Barg - Hech qanday yordamchi tugunga ega bo'lmagan tugun barg tugunlari deb ataladi.  Subtree - Subtree tugunning avlodlarini ifodalaydi.  Tashrif - tashrif, nazorat tugunda bo'lganda tugun qiymatini tekshirishni anglatadi.  O'tish - O'tish ma'lum bir tartibda tugunlardan o'tishni anglatadi.  Darajalar - Tugun darajasi tugunni yaratishni anglatadi. Agar ildiz tugun 0- darajada bo lsa, uning keyingi tugun 1-darajada, nevarasi 2-darajada va hokazo.ʻ  kalitlar - Kalit tugun uchun qidiruv operatsiyasi amalga oshirilishi kerak bo'lgan tugun qiymatini ifodalaydi. Binar daraxtlarni qurish Binar daraxtda har bir tugun-elementdan ko pi bilan 2 ta shox chiqadi. Daraxtlarni ‟ xotirada tasvirlashda uning ildizini ko rsatuvchi ko rsatkich berilishi kerak. ‟ ‟ Daraxtlarni kompyuter xotirasida tasvirlanishiga ko ra har bir element (binary ‟ daraxt tuguni) to rtta maydonga ega yozuv shaklida bo ladi, ya ni kalit maydon, ‟ ‟ ‟ informatsion maydon, ushbu elementni o ngida va chapida joylashgan ‟ elementlarning xotiradagi adreslari saqlanadigan maydonlar. Shuni esda tutish lozimki, daraxt hosil qilinayotganda, otaga nisbatan chap tomondagi o g il qiymati ‟ ‟ kichik kalitga, o ng tomondagi o g il esa katta qiymatli kalitga ega bo ladi. Har ‟ ‟ ‟ ‟ safar daraxtga yangi element kelib qo shilayotganda u avvalambor daraxt ildizi ‟ bilan solishtiriladi. Agar element ildiz kalit qiymatidan kichik bo lsa, uning chap ‟ shoxiga, aks holda o ng shoxiga o tiladi. Agar o tib ketilgan shoxda tugun mavjud ‟ ‟ ‟ bo lsa, ushbu tugun bilan ham solishtirish amalga oshiriladi, aks holda, ya ni u ‟ ‟ shoxda tugun mavjud bo lmasa, bu element shu tugunga joylashtiriladi. ‟ Daraxt “ko’rigi” funksiyalari Binar daraxtlari ko rigini uchta tamoyili mavjud. Ularni berilgan daraxt misolida ‟ ko’rib chiqaylik: 1) Yuqoridan pastga ko’rik (daraxt ildizini qism daraxtlarga nisbatan oldinroq ko rikdan o tkaziladi): A, B, C ;‟ ‟ 2) Chapdan o ngga: B, A, C ; ‟ 3) Quyidan yuqoriga (ildiz qism daraxtlardan keyin ko riladi): B, C, A . Daraxt ‟ ko rigi ko pincha ikkinchi usul bilan, ya’ni tugunlarga kirish ularning kalit ‟ ‟ qiymatlarini o sish tartibida amalga oshiriladi. ‟ Daraxt ko rigining rekursiv funksiyalari ‟ 1. int pretrave(node *tree){ if(tree!=NULL) {int a=0,b=0; if(tree->left!=NULL) a=tree->left->info; if(tree->right!=NULL) b=tree->right->info; cout<<tree->info<<" - chapida "<<a<<" - o’ngida "<<b<<" \n"; pretrave(tree->left); pretrave(tree->right); } return 0; 2. int intrave(node *tree){ if(tree!=NULL) { intrave(tree->left); cout<<tree->info; intrave(tree->right); } return 0; }; 3. int postrave(node *tree){ if(tree!=NULL) { postrave(tree->left); postrave(tree->right); cout<<tree->info; } return 0; }; Daraxtsimon tuzilma 1. Agar tugunning otasi yo q bo lsa, bu tugun ildiz hisoblanadi. Buni aniqlash‟ ‟ uchun dastur kodini keltiramiz. Dasturda p izlanayotgan tugun. if(p==tree) cout<<”bu tugun ildiz ekan”; else cout<<”bu tugun ildiz emas”; 2. Biz izlayotgan element daraxtda oraliq tugun ekanligini tekshirish uchun uning yoki o ng shoxi, yoki chap shoxi, yoki ikkalasiyam mavjudligini tekshirish kerak. ‟ Agar ikkala shoxi NULL dan farqli bo lsa, bu 2 ta farzandga ega oraliq tugun ‟ hisoblanadi, yoki ikkalasidan bittasi NULL ga teng bo lsa, bu tugun 1 ta farzandga ‟ ega oraliq tugun hisoblanadi. Berilgan p element daraxtning oraliq tugun ekanligini aniqlash dastur kodini keltiramiz. if(p!=tree){ if((p->left!=NULL)&&(p->right!=NULL)) cout<<”bu tugun 2 ta farzandga ega oraliq tugun”; else if((p->left!=NULL)||(p->right!=NULL) cout<<”bu 1 ta farzandga ega oraliq tugun”; } else cout<<”bu tugun oraliq tugun emas”; 3. Biz izlayotgan tugun terminal tugunligini tekshirishni ko rib chiqamiz. ‟ Agar tugunning har ikkala shoxi NULL ga teng bo lsa, bu terminal tugun ‟ hisoblanadi. Dastur kodini keltiramiz. if((p->left==NULL)&&(p->right==NULL)) cout<<”bu tugun terminal tugun”; else cout<<”bu terminal tugun emas”; Haqiqiy ikkilik qidiruv Binar qidirish — (eng: Binary search — ikkilik qidirish)- saralangan elementlar ro yxatidan elementni topish uchun samarali algoritm. Ikkilik qidirish algoritmiʻ ishlash g oyasiga ko ra „bo lib tashla va hukmronlik qil“ paradigmasi asosida ʻ ʻ ʻ ishlaydi. Ikkilik qidiruvdan foydalanishning eng keng tarqalgan usullaridan biri bu massivdagi elementni topishdir. Misol uchun, Tycho-2 yulduzlar katalogida bizning galaktikamizdagi eng yorqin 2 539 913 ta yulduz haqida ma lumot ʼ mavjud. Aytaylik, siz yulduz nomidan kelib chiqib, katalogdan ma lum bir ʼ yulduzni qidirmoqchisiz. Agar dastur yulduzlar katalogidagi har bir yulduzni birinchisidan boshlab, chiziqli qidiruv algoritmida tekshirgan bo lsa, eng yomon ʻ holatda kompyuter siz izlayotgan yulduzni topish uchun barcha 2 539 913 ta yulduzni tekshirishi kerak bo lishi mumkin. Agar katalog yulduz nomlari bo yicha ʻ ʻ alifbo tartibida tartiblangan bo lsa, ikkilik qidiruv, hatto eng yomon holatda ham ʻ 22 dan ortiq yulduzni tekshirishi shart emas edi. Dasturi #include <bits/stdc++.h> using namespace std; int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); return binarySearch(arr, mid + 1, r, x); } return -1; } int main(void) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = binarySearch(arr, 0, n - 1, x); (result == -1) ? cout << "Element massivda mavjud emas" : cout << "Element indeksda mavjud " << result; return 0; } "Dasturlashning eng asosiy muammosi — bu murakkablik. Murakkablikni hal qilishning faqatgina bitta asosiy yo'li bor: Bo'lib tashla va hukmronlik qil" — Bjarne Stroustrup Yuqorida siz bilan bo'lib tashla va hukmronlik qil paradigmasi haqida gaplashgan edik. Bu paradigma asosida ishlaydigan eng mashhur algoritm — bu ikkilik qidirish (binary search). Ikkilik qidirish algoritmi saralangan arraydan element topishning eng samarali algoritmlaridan biri. Bu algoritmni tushunishdan oldin oddiy chiziqli qidirish haqida gaplashsak. Ma lumotlar tuzilmasi va algoritmlarda ikkilik qidirish haqidaʼ Ikkilik qidirish — Ο(log n) vaqti murakkabligi bilan tezkor qidiruv algoritmi. Ushbu qidirish algoritmi bo linish (divide) va yengish (conque) prinsipi asosida ʻ ishlaydi. Ushbu algoritm to g ri ishlashi uchun ma lumotlar to planishi ʻ ʻ ʼ ʻ tartiblangan shaklda bo lishi kerak. ʻ Ikkilik qidirish to plamning ko p qismini o rtasini taqqoslash orqali ma lum bir ʻ ʻ ʻ ʼ narsani qidiradi. Agar mos kelsa, unda element indeksi qaytariladi. Agar o rta qism ʻ elementdan kattaroq bo lsa, u holda ushbu element o rta qismning chap ʻ ʻ tomonidagi pastki qatorda qidiriladi. Aks holda, element o rta elementning pastkiʻ qismidagi pastki qatorda qidiriladi. Ushbu jarayon pastki massivda, shuningdek sub-massivning kattaligi nolga tushguncha davom etadi. Ikkilik qidirsh qanday ishlaydi? Ikkilik qidirish ishlashi uchun maqsad qatorini tartiblash kerak. Ikkilik qidirish jarayonini tasvirli misol yordamida bilib olamiz. Quyidagi tartiblangan massivimiz bo lib, ikkilik qidirishdan foydalanib, 31 qiymatni qidirish kerakligini taxmin ʻ qilaylik. Birinchidan, ushbu formuladan foydalanib, massivning yarmini aniqlaymiz: mid = low + (high - low) / 2 Bu yerda, 0 + (9 - 0 ) / 2 = 4 (4.5 ning butun qiymati). Shunday qilib, 4 qatorning o rtasida. ʻ Endi biz 4-chi joyda saqlangan qiymatni, ya ni qidirilayotgan qiymat bilan ʼ taqqoslaymiz, ya ni 31-chi joyda 27-ning qiymati mos kelmasligini aniqladik. ʼ Qiymat 27 dan katta bo lsa va bizda tartiblangan qator mavjud bo lsa, biz shuni ʻ ʻ ham bilamizki, maqsad qiymati massivning yuqori qismida bo lishi kerak. ʻ Biz pastligimizni + 1 o rtasiga o zgartiramiz va yana yangi o rtacha qiymatni ʻ ʻ ʻ topamiz. low = mid + 1 mid = low + (high - low) / 2 Bizning yangi o rtamiz endi 7 ga chiqdi. Biz 7-joyda saqlangan qiymatni maqsadli ʻ qiymatimiz 31 bilan taqqoslaymiz. 7-joyda saqlangan qiymat mos kelmaydi, aksincha biz qidirayotgan narsadan ko proqdir. Shunday qilib, qiymat ushbu joyning pastki qismida bo lishi kerak. ʻ ʻ Shunday qilib, biz yana o rtani hisoblaymiz. Bu safar 5 ga. 31 maqsadli qiymat 5 ʻ manzilda saqlanadi degan xulosaga keldik. Ikkilik qidirish qidiriladigan qismlarni ikki baravar qisqartiradi va shu bilan juda kam sonlar uchun taqqoslash sonini kamaytiradi. Pseudocode Ikkilik qidirish algoritmlarining kodi quyidagicha ko rinishi kerak:ʻ Procedure binary_search A ← sorted array n ← size of array x ← value to be searched Set lowerBound = 1 Set upperBound = n while x not found if upperBound < lowerBound EXIT: x does not exists. set midPoint = lowerBound + ( upperBound - lowerBound ) / 2 if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x set upperBound = midPoint - 1 if A[midPoint] = x EXIT: x found at location midPoint end while end procedure Ikkilik qidirish algoritmi ishlash prinsipi Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter bilan o'yin o'ynab ko'ramiz. O'yin shartlari quyidagicha: Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish. Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o'ylagan sondan katta yoki kichikligini aytadi. Agar sizning taxminingiz kompyuter o'ylagan son bilan bir xil bo'lsa, o'yin tugaydi. Xo'sh, bunda kamroq yo'l tutish uchun nima qilgan bo'lar edingiz? Algoritm qadamlari Algoritm qanday ishlashini tushundingiz degan umiddaman. Endi uning qadamlariga o'tadigan bo'lsak. Eslatma: Ikkilik qidirish algoritmi to'g'ri ishlashi uchun array saralangan bo'lishi shart! Bizda n ta elementli saralangan massiv bor va biz undan x elementni qidirmoqdamiz. Biz qidirish chegarasini belgilash uchun l (left) va r (right) ko'rsatkichlardan foydalanamiz. Ular array indekslarini ko'rsatib turadi. mid o'zgaruvchi bizda qidirilayotgan sohaning o'rtadagi elementi indeksini ko'rsatadi Avvaliga l = 0 va r=n-1 bo'ladi (butun boshli array) O'rtadagi element indeksi hisoblanadi: mid = (l + r)/2; O'rtadagi element indeksi bilan qidirilayotgan son x solishtirib ko'riladi Agar son mos kelsa, algoritm shu joyida to'xtaydi. Agar x o'rtadagi sondan katta bo'lsa, left ko'rsatkichni o'rtadan bitta keyingi elementga suramiz: l=mid + 1; Agar x o'rtadagi sondan kichik bo'lsa, right ko'rsatkichni o'rtadan bitta oldingi elementga suramiz: r=mid — 1; 2-qadamga qaytiladi. Ikkilik qidirish algoritmi har bir qadamda n ni ikki baravarga kamaytirgani uchun algoritm ishlash tezligi O(logn) hisoblanadi. Solishtirish uchun Facebook misolidagi 1 mlrd login ichidan ikkilik qidirish algoritmi 30 ta (!) qadam bilan topishi mumkin. Oddiy qidirishdan tashqari bu algoritmni yana boshqa juda ko'p joyda qo'llash mumkin. Informatika fanida ikkilik qidiruv, yarim intervalli qidiruv, logarifmik qidiruv yoki ikkilik chop deb ham ataladi, tartiblangan massiv ichida maqsadli qiymatning o'rnini topadigan qidiruv algoritmidir. Ikkilik qidiruv maqsadli qiymatni massivning o'rta elementi bilan taqqoslaydi. Agar ular teng bo'lmasa, nishon yotolmaydigan yarmi yo'q qilinadi va qolgan yarmida qidirish davom etadi, yana o'rta elementni maqsad qiymat bilan taqqoslash uchun olib, maqsad qiymat topilgunga qadar takrorlanadi. Agar qidiruv qolgan yarmi bo'sh bo'lishi bilan tugasa, maqsad massivda emas. Ikkilik qidiruv logarifmik vaqt ichida eng yomon holatda ishlaydi ( jurnal ⁡ ) O(\log n) taqqoslashlari, bu yerda n - massivdagi elementlar soni. Ikkilik qidiruv chiziqli qidiruvga qaraganda tezroq, kichik massivlardan tashqari. Biroq, ikkilik qidiruvni qo'llash uchun massiv avval tartiblangan bo'lishi kerak. Tez qidirish uchun mo'ljallangan maxsus ma'lumotlar tuzilmalari mavjud, masalan, xesh-jadvallar, ularni ikkilik qidiruvdan ko'ra samaraliroq qidirish mumkin. Shu bilan birga, ikkilik qidiruv kengroq muammolarni hal qilish uchun ishlatilishi mumkin, masalan, massivda bo'lmasa ham, maqsadga nisbatan massivdagi keyingi eng kichik yoki keyingi eng katta elementni topish. Ikkilik qidiruvning ko'plab variantlari mavjud. Xususan, kasrli kaskad bir nechta massivlarda bir xil qiymat uchun ikkilik qidiruvlarni tezlashtiradi. Fraksiyonel kaskad hisoblash geometriyasi va boshqa ko'plab sohalarda bir qator qidiruv muammolarini samarali hal qiladi. Eksponensial qidiruv ikkilik qidiruvni cheklanmagan ro'yxatlargacha kengaytiradi. Ikkilik qidiruv daraxti va B-daraxt ma'lumotlar tuzilmalari ikkilik qidiruvga asoslangan. Ikkilik qidiruv tartiblangan massivlarda ishlaydi. Ikkilik qidiruv massivning o'rtasida joylashgan elementni maqsadli qiymat bilan solishtirishdan boshlanadi. Agar maqsadli qiymat elementga mos kelsa, uning massivdagi o'rni qaytariladi. Agar maqsadli qiymat elementdan kichik bo'lsa, qidiruv massivning pastki yarmida davom etadi. Agar maqsadli qiymat elementdan katta bo'lsa, qidiruv massivning yuqori yarmida davom etadi. Shunday qilib, algoritm har bir iteratsiyada maqsadli qiymat yotolmaydigan yarmini yo'q qiladi. Taqqoslashlar soni bo'yicha, ikkilik qidiruvning ishlashini ikkilik daraxtda protseduraning bajarilishini ko'rish orqali tahlil qilish mumkin. Daraxtning ildiz tuguni massivning o'rta elementidir. Pastki yarmining o'rta elementi ildizning chap tuguni, yuqori yarmining o'rta elementi esa ildizning o'ng tugunidir. Daraxtning qolgan qismi xuddi shunday tarzda qurilgan. Ildiz tugunidan boshlab, maqsadli qiymat ko'rib chiqilayotgan tugundan kam yoki ko'p bo'lishiga qarab, chap yoki o'ng pastki daraxtlar kesib o'tiladi.[6][14] Eng yomon holatda, ikkilik qidiruv qiladi jurnal ⌋ {\textstyle \lfloor \log _{2}(n)+1\rfloor } solishtirish siklining takrorlanishi, bunda ⌋ {\textstyle \lfloor \rfloor } yozuvi argumentdan kichik yoki unga teng eng katta butun sonni beradigan qavat funksiyasini bildiradi va Jurnal {\textstyle \log _{2}} ikkilik logarifmdir. Buning sababi shundaki, qidiruv daraxtning eng chuqur darajasiga etganida eng yomon holatga erishiladi va har doim ham bor ⌊ jurnal ⌋ {\textstyle \lfloor \log _{2}(n)+1\rfloor } har qanday ikkilik qidiruv uchun daraxtdagi darajalar. Balanslangan ko'p yo'lli qidiruv daraxtlari Balanslangan ko'p yo'lli qidiruv daraxtlari Tashqi xotiradan (masalan, diskdan) ma'lumot olish uchun zarur bo'lgan vaqt bir xil ma'lumotni operativ xotiradan olishdan minglab marta ko'p. Tashqi qidiruvning maqsadi diskka kirishlar sonini kamaytirishdir, chunki unga kirish hisoblashdan ko'ra ko'proq vaqt talab etadi. Bu tezroq, asosiy xotirada joylashgan ma'lumotlarni topishda hisob-kitoblar sonini (ya'ni, taqqoslash) minimallashtirish maqsadidan farq qiladi. Shu sababli, tashqi xotiradan odatiy yozish huquqi bir vaqtning o'zida butun sahifani yoki ma'lumotlar blokini o'qiydi. B+-daraxt ko p yo l izlovchi daraxtlar oilasidan biri (boshqalar: B-daraxt, 2-3-4ʻ ʻ daraxt, B*-daraxtlar). Ushbu daraxtlar birinchi marta 1972 yilda Rudolf Bayer va Ed McCreight tomonidan taklif qilingan va bir necha yil ichida xeshlashdan tashqari deyarli barcha asosiy fayllarga kirish usullarini almashtirgan. Ushbu ko'p o'tishli muvozanatli qidiruv daraxtlari hozirda asosiy diapazonli ilovalar uchun fayllarni tashkil etish standarti hisoblanadi. B+ daraxt tuzilishi B+ daraxti ba zi jihatlarda ikkilik qidiruv daraxtining (BST) umumlashtirilishi ʼ hisoblanadi. Asosiy farq shundaki, B + daraxt tugunlari faqat ikkitasi bilan cheklangan emas, balki ko'p bolalarga ega. Maqsadimiz diskka kirishni minimallashtirish bo'lganligi sababli, yozuvni samarali qidirish uchun ko'p yo'nalishli qidiruv daraxtining balandligini imkon qadar kichikroq qilishimiz kerak. Bu maqsadga har bir tugunning ko'p sonli shoxchalar mavjudligi tufayli erishiladi. A B+-tartibli daraxt daraxti har bir ichki tugun b/2 dan b gacha bo'lgan tugunlarni o'z ichiga oladi va har bir tugundagi kalitlar soni (ildizdan tashqari) b - 1 va 2b - 1 orasida bo'lishi kerak. b ham daraxtning shoxlanish yoki shoxlanish omili sifatida tanilgan. Rasmda (1-rasm) 4-tartibdagi B+daraxt ko'rsatilgan. Xususiyatlari B+-daraxtlar ko'rsatkichlarni faqat barg tugunlarida haqiqiy yozuvlarga saqlaydi. Har bir tugundagi kalitlar soni (ildizdan tashqari) b - 1 va 2b - 1 orasida bo'lishi kerak, bu erda b - daraxtning tartibi. Ildiz tuguni barg yoki kamida ikkita bolaga ega. Ichki tugunlar faqat qidiruv "yo'riqnomasi" uchun to'ldiruvchi sifatida ishlatiladi. Har bir ichki tugundagi kalitlar soni bo'sh bo'lmagan bolalar sonidan bitta kam. Kalitlar kamayish tartibida saqlanadi (ya'ni leksikografik tartibda tartiblangan). B+ daraxtidagi barg tugunlari bir-biriga bog'langan bo'lib, bog'langan ro'yxatni tashkil qiladi. Bu B+ daraxtiga qayta kirishsiz yozuvlarni ketma-ket olish uchun amalga oshiriladi. Shuningdek, u bir qator qidiruv yozuvlarini tezkor qayta ishlashni qo'llab-quvvatlaydi. Balandlik talabi daraxt qidirish balandligi rekordi Bayonot. N ≥ 1 tugmachali va minimal daraja b ≥ 2 bo'lgan B + daraxtining balandligi eng yomon holatda logb ((n + 1) / 2) dan oshmaydi. Isbot. B+daraxtning balandligini h deb belgilaymiz. Mumkin bo'lgan eng yuqori B + daraxtini ko'rib chiqing: 1 ta kalit bunday daraxtning ildizida saqlanadi va 1 ta kalit qolgan b tugunlarida saqlanadi (eng kam mumkin bo'lgan raqam) 0-darajada 1 kalit bilan bitta tugun (ildiz) mavjud 1-darajada: 2 tugun (har biri b - 1 kalit bilan) 2-darajada: 2b tugunlari 3-darajada: 2b2 tugunlari … h darajasida: 2bh-1 tugun Keyin kalitlarning umumiy soni: n = 1 + (b – 1)(2 + 2b + 2b2 + 2b3 + ⋯ + 2bh−1) = = 1 + 2(b – 1)(1 + b + b2 + ⋯ + bh−1) Geometrik progressiyaning birinchi a'zolarining yig'indisi h: Sh =d1(qh - 1)/(q - 1) Binobarin, n = 1 + 2(b – 1) (bh – 1)/(b – 1) = 2b ℎ - 1 n + 1 = 2bh (n + 1) / 2 = bh h = log b((n + 1) / 2) Da'vo isbotlangan. 2. Asosiy B+daraxt operatsiyalari Yozuvni qidirish B + daraxtidan yozuvlarni olish uchun so'rovlar kerakli qiymatni tavsiflovchi shartlar bilan yoziladi. B+ daraxtini qidirish ildiz tugunidan boshlab bosqichma- bosqich jarayondir: Joriy tugundagi kalitni ikkilik qidirish - qidiruv qiymatlari tartiblanganligini yodda tutish kerak. Biz Ki ≤ K < Ki1 bo'ladigan kalitni qidiramiz. Agar joriy tugun ichki bo'lsa, Ki kaliti bilan bog'liq bo'lgan tegishli filialga o'tish amalga oshiriladi va "bosqichi takrorlanadi 1”. Agar joriy tugun barg bo'lsa, unda: Agar K = Ki bo'lsa, u holda yozuv jadvalda mavjud va biz Ki bilan bog'langan yozuvni qaytarishimiz mumkin Aks holda, Ki varaqdagi asosiy qiymatlar orasida topilmaydi, ya'ni jadvalda kerakli qiymatga ega kalitlar yo'q. Ushbu operatsiyani hisoblash murakkabligi eng yomon holatda TFind = O (logb / 2n), bu erda b - daraxtning tartibi yoki dallanish omili; n - daraxtdagi elementlar soni. Isbot. Ikkilik muvozanatli daraxtda elementni izlash O(log2n) ga teng mehnatkashlikka ega, B+daraxtdagi izlash jarayonining asosiy farqi shundaki, ichki tugun b/2 dan b gacha bo‘lgan bolalarga ega bo‘lishi mumkin (cheklanmagan holda ikkita). Bundan kelib chiqadiki, eng yomon holatda, B + daraxtida qidirishning hisoblash murakkabligi TFind = O (logb/2n) ga teng bo'ladi. Balanslangan qidiruv daraxtlari Balanslangan daraxtda barcha barg tugunlari joylashgan (taxminan) bir xil darajada. • AVL daraxtlari birinchi bo'lib (1962). • Splay daraxtlari o'z-o'zini tashkil etadigan daraxtlardan (1978+) kelib chiqadi. • B-daraxtlar ma'lumotlar bazalari uchun ishlatiladigan ko'p tomonlama qidiruvdir (1972+) Balanslangan ikkilik qidiruv daraxti Balanslangan ikkilik daraxt, shuningdek, balandlik bo'yicha muvozanatli ikkilik daraxt deb ham ataladi, har qanday tugunning chap va o'ng pastki daraxtining balandligi 1 dan ko'p bo'lmagan farq qiladigan ikkilik daraxt sifatida aniqlanadi. Daraxt/tugunning balandligi haqida ko'proq ma'lumot olish uchun Daraxt ma'lumotlarining tuzilishiga tashrif buyuring . Quyida balandlik muvozanatli ikkilik daraxt uchun shartlar keltirilgan: 1. har qanday tugun uchun chap va o'ng pastki daraxt o'rtasidagi farq bittadan ko'p emas 2. chap pastki daraxt muvozanatli 3. o'ng pastki daraxt muvozanatli Ikkilik qidirish algoritmi ishlash prinsipi Kalit so’zlari:binar daraxt, o’ng va chap qismdaraxtlar, qidiruv daraxti,daraxtdan o’tishlar (daraxtni ko’rib chiqish), binar heap, ikkilik piramida, maxHeap,minHeap. Qisqacha nazariy ma’lumotBinar daraxt – bu har biri boshqa turlicha binar daraxtlarga ikkitako’rsatkichlarni saqlab turuvchitugunlardan iborat dinamik ma’lumotlar tuzilmasi.Har bir tugunga bitta ko’rsatkich mavjud.Bunday tuzilmani quyidagicha shaklda tavsiflash mumkin: struct point {int data;//ma’lumot maydoni point *left;//chapqism daraxt manzili point *right;// o’ngqism daraxt manzili}; Boshlang’ich tugun daraxtning ildizi deyiladi. Qism daraxtga ega bo’lmagan tugunbarg deb nomlanadi. Chiquvchiga ega bo’lgan tugunlar ajlod tugun, kiruvchiga ega bo’lgan tugunlar avlodtugun deyiladi. Daraxt balandligi uning tugunlari joylashgan bosqichlari soni bilan aniqlanadi.Agar daraxtning chap qism daraxtining barcha tugunlari qiymati ildiz tugun qiymatidan kichik, o’ng qismdaraxti barcha tugunlari qiymati katta bo’lsa,qidiruv daraxti deyiladi. Bir xil qiymatli kalitlarga ruxsat etilmaydi. Qidiruv daraxtida elementni kaliti bo’yicha qidirish uchun ildizdan chap qism daraxt yoki o’ng qism darxtga harakatlanish orqali amalga oshiriladi. Bunda qidirilayotgan kalit qiymatining ildiz qiymatiga nisbatan kichik yoki katta ekanligi e’tiborga olinadi.Kichik bo’lsa, chap qism darxatdan, aks xolda o’ng qismdaraxtdan qidiriladi. Bunday qidirish ro’yxatdan qidirishga nisbatan juda ham samarali, chunki, qidiruv vaqti daraxt tugunlar sonining ikkilik logarifmga proportsional bo’lgan daraxt balandligi bilan aniqanadi.Ideal muvozanatlashtirilgan daraxtning chap va o’ng tugunlari soni 1 tadanko’p tugunga farq qilmaydi.Chiziqli ro’yxatni har bir tuguni bitta ko’p bo’lmagan ko’rsatkichli binar daraxtshaklda ifodalash mumkin. Ro’yxat uchun o’rtacha qidirish vaqti ro’yxat uzunligining yarmiga teng bo’ladi. Ikkilik qidirish algoritmi ishlash prinsipi Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter bilan o’yin o’ynab ko’ramiz. O’yin shartlari quyidagicha: Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish. Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o’ylagan sondan katta yoki kichikligini aytadi. Agar sizning taxminingiz kompyuter o’ylagan son bilan bir xil bo’lsa, o’yin tugaydi. Xo’sh, bunda kamroq yo’l tutish uchun nima qilgan bo’lar edingiz? Albatta, birinchi navbatda o’rtadagi sonni taxmin qilib ko’ramiz, ya’ni 50 ni Aytaylik kompyuter bizga taxminimiz o’ylangan sondan kichikroq ekanligini aytdi. Demak, endi biz 50 va undan kichik barcha son o’ylangan sondan kichik ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar o’rtasidagi sonni olamiz, ya’ni 75 ni Kompyuter bizga 75 o’ylangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham o’ylangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz o’ylangan sonni topishimiz mumkin. Sonlar 100 ta bo’lgan holatda, biz har qanday tahminni ko’pi bilan 7 ta qadamda topishimiz mumkin bo’ladi. Ikkilik qidirish algoritmi ham huddi shunday prinsipda ishlaydi! Balanslangan ikkilik daraxt Ushbu qo'llanmada siz muvozanatli ikkilik daraxt va uning turli xil turlari haqida bilib olasiz. Shuningdek, siz C, C++, Java va Python tillarida muvozanatli ikkilik daraxtning ishchi misollarini topasiz. Balanslangan ikkilik daraxt, shuningdek, balandlik bo'yicha muvozanatli ikkilik daraxt deb ham ataladi, har qanday tugunning chap va o'ng pastki daraxtining balandligi 1 dan ko'p bo'lmagan farq qiladigan ikkilik daraxt sifatida aniqlanadi. Daraxt/tugun balandligi haqida ko'proq ma'lumot olish uchun Tree Data Structure- ga tashrif buyuring. Quyida balandlik muvozanatli ikkilik daraxt uchun shartlar keltirilgan: 1.har qanday tugun uchun chap va o'ng pastki daraxt o'rtasidagi farq bittadan ko'p emas. 2.chap pastki daraxt muvozanatli. 3.o'ng pastki daraxt muvozanatli. Ikkilik daraxt, agar daraxtning balandligi O (Log n) bo'lsa, bu erda n - tugunlar soni muvozanatlangan. Misol uchun, AVL daraxti chap va o'ng pastki daraxtlarning balandliklari orasidagi farq ko'pi bilan 1 bo'lishiga ishonch hosil qilish orqali O (Log n) balandligini saqlaydi. Qizil-qora daraxtlar sonning o'zgarishiga ishonch hosil qilish orqali O (Log n) balandligini saqlaydi. Har bir ildizdan barggacha bo'lgan yo'lda qora tugunlar bir xil va qo'shni qizil tugunlar yo'q. Balanslangan ikkilik qidiruv daraxtlari unumdorligi jihatidan yaxshi, chunki ular qidirish, kiritish va o chirish uchun O(log n) vaqtini ta minlaydi.ʻ ʼ Balanslangan ikkilik daraxt ikkilik daraxt bo'lib, 3 shartga amal qiladi: 1. Har qanday tugun uchun chap va o'ng daraxtning balandligi 1 dan ortiq farq qilmaydi. 2. Ushbu tugunning chap pastki daraxti ham muvozanatlangan. 3. Ushbu tugunning o'ng pastki daraxti ham muvozanatlangan. Bitta tugun har doim muvozanatli. U balandlikda muvozanatlangan ikkilik daraxt deb ham ataladi. Misol: Bu ikkilik daraxtning bir turi bo'lib, unda har bir tugun uchun chap va o'ng pastki daraxt balandligi o'rtasidagi farq 0 yoki 1 ga teng. Yuqoridagi rasmda 0 qiymatiga ega bo'lgan ildiz tugun 2 birlik chuqurlik bilan muvozanatsizdir. Balanslangan ikkilik daraxtning afzalliklari: Buzilmaydigan yangilanishlar bir xil asimptotik samaradorlikka ega Balanslangan Ikkilik daraxt tomonidan qo'llab-quvvatlanadi. Diapazon so'rovlari va to'g'ri ketma-ketlikda iteratsiya muvozanatli ikkilik daraxt tomonidan amalga oshiriladi. Balansli daraxtlar Balanslangan daraxt - bu faqat tugunlar orasidagi tartibni saqlamaydigan qidiruv daraxti. Shuningdek, u balandligini boshqaradi va qo'yish yoki o'chirishdan keyin \ boldsymbol{O(\log n)} qolishiga ishonch hosil qiladi. Buning uchun tugunni qo'shganimiz yoki o'chirganimizdan so'ng muvozanatli daraxt o'zini qayta muvozanatlashi kerak. Bu hisoblash qo'shimchasiga olib keladi va kiritish va o'chirish algoritmlarini murakkablashtiradi. Biroq, bu biz tezkor qidiruv, kiritish va o'chirish operatsiyalari bilan logarifmik balandlikdagi qidiruv daraxti uchun to'lashga tayyormiz. Biz ushbu maqolada qayta muvozanatlash algoritmlarini ko'rib chiqmaymiz. Bunday daraxtlarning bir nechta turlari mavjud. Ular o'zlarining barcha tugunlarining muvozanatli bo'lishini talab qiladilar, ammo muvozanat tushunchasi turdan turga farq qiladi. Xulosa Xulosa qilib aytish joizki , men balanslangan qidiruv daraxtini ishlash prinsiplarini ko’rib chiqdim va avfzaliklarini o’rganib chiqdim avfzalliklari shundan iboratki: Balanslangan ikkilik daraxtning afzalliklari: Buzilmaydigan yangilanishlar bir xil asimptotik samaradorlikka ega Balanslangan Ikkilik daraxt tomonidan qo'llab-quvvatlanadi. Diapazon so'rovlari va to'g'ri ketma-ketlikda iteratsiya muvozanatli ikkilik daraxt tomonidan amalga oshiriladi. Lekin balanslangan qidiruv daraxtida tartiblanmagan bo’lar ekan. Balanslangan ikkilik daraxt, shuningdek, balandlik bo'yicha muvozanatli ikkilik daraxt deb ham ataladi. Ikkilik daraxt, agar daraxtning balandligi O (Log n) bo'lsa, bu erda n - tugunlar soni muvozanatlangan. Misol uchun, AVL daraxti chap va o'ng pastki daraxtlarning balandliklari orasidagi farq ko'pi bilan 1 bo'lishiga ishonch hosil qilish orqali O (Log n) balandligini saqlaydi. Qizil-qora daraxtlar sonning o'zgarishiga ishonch hosil qilish orqali O (Log n) balandligini saqlaydi. Har bir ildizdan barggacha bo'lgan yo'lda qora tugunlar bir xil va qo'shni qizil tugunlar yo'q. Balanslangan ikkilik qidiruv daraxtlari unumdorligi jihatidan yaxshi, chunki ular qidirish, kiritish va o chirish uchun O(log n) vaqtini ta minlaydi.ʻ ʼ Shunday qilib bu qidiruv tizimi bizga ancha qulayliklarni keltirib chiqarib berar ekan.Bundan biz turmush tarzimizda ham ko’p foydalanar ekanmiz. ADABIYOTLAR RO’YXATI 1. Kulakov A.G., Lando S.K., Semyonov A.L., Shen A.X.. Algoritmika. V-V II sinflar. Moskva: Drofa, 1997. 2. Boltayev B . Abduqodirov A., Taylaqov N., Mahkamov M., Azamalov A., Xafizov S. Informatika va hisoblash texnikasi asoslari. 9-sinf. T.: Cho lpon, 2006. 3. Boltayev B., Mahkamov M., Azamatov A. Informaiikadan olimpiada masalalarini yechish. Metodik qo'llanma, T : 2004. 4. Boltayev B., Mahkamov M., Azamatov A. Informalikadan olimpiada masalalarini yechish-2. Melodik qo'llanma, Toshkent, 2004. 5. B.Boltayev, A.Abduqodirov, N.Taylaqov, M.Mahkamov, A.Azamalov, S.Xafizov. Informatika va hisoblash texnikasi asoslari. 9-sinf. T.: Cho'lpon, 2006. 6. B.Boltayev, Mahkamov M., Azamatov A., Ahduqodirov A., Daliyev A., Azlarov T., Taylaqov N. 8-sinf. T.: O'qituvchi, 2006. 7. B.Boltayev, M.Mahkamov, A.Azamatov. 8-sinf masalalar to‘plami va ularni yechish usullari. Metodik qo‘llanma. T.: 2005. 8. B.Boltayev, M ahkam ov M., Azamatov A. Paskal dasturlash tili. Metodik qo’llanma. T.: 2007. 9.Ingliz adabiyotlari.

Balanslangan qidiruv daraxtlari MUNDARIJA KIRISH ............................................................................................................ 2 Haqiqiy ikkilik qidiruv .................................................................................. 12 ADABIYOTLAR RO’YXATI ...................................................................... 29

KIRISH Fanda daraxtlar haqida ma’lumot Daraxt - bu bog langan asiklik graf, ya‘ni sikllar yo q va uchlar juftligi orasidaʻ ʻ bitta yo l bor . Kirishning nol darajasiga ega bo lgan uch daraxtning ildizi, chiqish ʻ ʻ nol darajaga ega tugunlar esa barglar deb nomlanadi. Ulanish har qanday uchlar juftligi o rtasida marshrut mavjudligini anglatadi, aylanuvchanlik sikllar yo qligini ʻ ʻ anglatadi. Demak, xususan, shundan kelib chiqadiki, daraxtdagi qirralarning soni uchlar sonidan bitta kamroq va har qanday uchlar juftlari orasida bitta va faqat bitta yo l bor. O rmon – juda ko p daraxtlardir. Yo naltirilgan (oriyentirlangan) daraxt - ʻ ʻ ʻ ʻ bu faqat bitta vertikal kirish nol darajasiga ega bo lgan (boshqa yoylar unga olib ʻ kelmaydigan), boshqa uchlarning kirish darajasi 1 bo lgan siklik orgraf (sikllarni ʻ o z ichiga olmaydigan yo naltirilgan graf). ʻ ʻ Daraxtning asosiy tushunchalari Ildiz tuguni - daraxtning eng yuqori tuguni . Ildiz – ixtiyoriy tanlab olingan uchlardan biri. Barg yoki terminal tuguni – avlodi mavjud bo lmagan tugun. ʻ Ichki tugun - bu daraxtga avlodi mavjud bo lgan har qanday tugun va shuning ʻ uchun barg tuguni emas . Uchning darajasi - unga tushgan qirralarning soni. Daraxt osti - bu alohida daraxt sifatida namoyish etilishi mumkin bo lgan daraxtga ʻ o xshash ma‘lumotlar strukturasining bir qismidir. T daraxtining har qanday tuguni ʻ va uning barcha nasl tugunlari bilan birga T daraxtining pastki daraxti hisoblanadi. Daraxt osti har qanday tuguni uchun, yo ushbu kichik daraxtning ildiz tuguniga yo l bo lishi kerak, yo tugunning o zi ildiz bo lishi kerak. Ya‘ni, kichik daraxt ildiz ʻ ʻ ʻ ʻ tuguniga butun daraxt bilan bog lanadi va boshqa barcha tugunlar bilan daraxt ʻ osti aloqasi tegishli daraxt osti tushunchasi orqali aniqlanadi (―to plam osti" ʻ atamasi bilan o xshashlik bo yicha). ʻ ʻ Daraxt strukturasi orasida tartiblangan daraxtlar eng keng tarqalgan.

Binar (Ikkilik) qidiruv daraxti - tartiblangan daraxt turidir. Daraxtlar ustida bajariladigan umumiy amallar: 1) yangi elementni ma‘lum bir joyga kiritish; 2) daraxt osti kiritish; 3) daraxt shoxini qo shish (payvandlash deb ataladi);ʻ 4) har qanday tugun uchun ildiz elementini topish; 5) ikkita uchning eng kichik umumiy ajdodini topish; 6) daraxtning barcha elementlarini sanab chiqish; 7) daraxt novdasi elementlarini sanab chiqish; 8) izomorfik daraxt osti qidirish; 9) elementni qidirish; 10) daraxt shoxini olib tashlash; 11) daraxt ostini olib tashlash; 12) elementni o chirish. ʻ Daraxtlarning qo llanish sohalari: ʻ 1) ma‘lumotlar iyerarxiyasini boshqarish; 2) axborot olishni soddalashtirish 3) ma‘lumotlarning saralangan ro yxatlarini boshqarish; ʻ 4) arifmetik ifodalarni tahlil qilish (inglizcha parsing), dasturni optimallashtirish; 5) turli xil vizual effektlarni olish uchun raqamli rasmlarni yaratish texnologiyasi sifatida; 6) ko p bosqichli qaror qabul qilish shakllarida (shaxmat). ʻ

Daraxtlarda qo shnilik (A) va insidentlik (B) matritsalari.ʻ Daraxtlar uchun bunday matritsalarning o ziga xos xususiyatlarini ta‘kidlaylik. N ʻ ga teng bo lgan daraxtning qirralari sonining nisbati bog langan graf uchun ʻ ʻ minimal, shuning uchun daraxtning qo shnilik matritsasi juda kam (ularning ʻ nisbati va undagi nollar yo naltirilgan daraxt uchun va yo naltirilmagan uchun). ʻ ʻ Daraxtning insidentlik matritsasi o lchamiga ega, ya‘ni kvadratga yaqin, va aslida, ʻ agar biz uning ortiqcha ekanligini hisobga olsak. Darhaqiqat, har qanday qatorni olib tashlab, biz avvalgidek grafni to liq tavsiflaydigan kvadrat matritsani olamiz. ʻ Quyida keltirilgan insident matritsasining yana bir xususiyati quyidagicha. Satr va ustunlarni qayta tartiblash orqali har qanday daraxtning insidentlik matritsasi ustun

birliklaridan biri qatorda, ikkinchisi pastki qatorlardan birida bo lganda pastkiʻ trapetsiya matritsaga tushirilishi mumkin. Daraxt ketma-ket qirralarni qo shib quriladi. Keyingi qo shilgan chekka, ʻ ʻ birinchisidan boshlab, vertikal juftlik bilan hosil bo ladi, ularning raqamlari kod ʻ satrida va antikod satrida birinchi bo ladi. Shundan so ng, ishlatilgan satr ʻ ʻ elementlari chiziladi. Agar kod satridan chiqib ketgan raqam undagi qolgan elementlar qatoriga kiritilmagan bo lsa, uning tartibini buzmasdan antikod qatoriga ʻ qo shilishi kerak. Ta‘riflangan harakatlar kod va antikod satrlarining "qoldiqlari" ʻ bilan ularning birinchisining barcha elementlari o chirilguncha takrorlanadi. ʻ Bunday holda, antikod chizig ida hosil qilingan ro yxatga qo shiladigan so nggi ʻ ʻ ʻ ʻ chekkani belgilaydigan ikkita element bo ladi, natijada biz Pryufer kodi bilan ʻ belgilangan daraxtga mos keladigan n - 1 qirralarning ro yxatini olamiz. 3-misol. ʻ Masalan, 1-misolda berilgan 14166 kodi yordamida daraxtni tiklaylik. Yuqorida 1- misolda ko rsatilgandek mos keladigan antikod 2357 ni tashkil qiladi. Shuning ʻ uchun daraxtning birinchi qirrasi {1; 2}. 1 va 2-ni kesib o tib, biz kod satrida 4166 ʻ va antikod satrida 357 olamiz. Keyingi takrorlashda {4; 3} juftligini kesib tashlaymiz va qatorga antikod 4 ni kiritamiz va hokazo. Takrorlashlar ketma- ketligi 8- jadvalda keltirilgan.

O'xshashlar

Qidiruv algoritmlari
INTERPOLATSION QIDIRUV
Matritsada qidiruv algoritmlari
Haqiqiy ikkilik qidiruv
Matritsa qidiruv algoritmlari