1. Dasturiy ta’minot va uning turlari

Qo’shnilik matritsasi
1 dan n gacha raqamlangan G grafning qo'shnilik matritsasi kvadrat kattalikdagi A matritsasi bo'lib, unda a [i][j] elementining qiymati 1 ga teng bo'lsa, grafning i- va j- uchlari qo’shni bo‘ladi, aks holda qiymati nolga teng bo‘ladi. Bunday matritsa binar matritsa deb ham ataladi. Oddiy graf uchun asosiy diagonal elementlari 0 ga teng bo‘ladi.
Qo'shnilik matritsasi orgrafni tavsiflash uchun ham, yo'naltirilmagan grafni tasvirlash uchun ham mos keladi. Yo'naltirilmagan graf uchun elementlarning qiymatlari asosiy diagonalga nisbatan nosimmetrikdir.
Qo'shnilik matritsadan foydalanish faqat qirralari ko'p bo'lmagan hamda murakkab bo‘lmagan graflar uchun afzalroqdir, chunki u har bir element uchun bitta bit saqlashni talab qiladi. Agar graf murakkab bo'lsa, unda xotiraning katta qismi nollarni saqlashga sarflanadi, ammo murakkab graflarda qo'shnilik matritsasi grafni xotirada ixchamroq ifodalaydi va taxminan bit xotiradan foydalanadi. 
Insidentlik matritsasi - bu grafning elementlari (qirra - uch) orasidagi bog'lanishlar ko'rsatiladigan grafni tasvirlash shakli. Matritsaning ustunlari qirralarga, satrlar uchlarga to'g'ri keladi. Demak, matritsa kvadrat bo‘lmaydi. Matritsa yacheykasidagi nolga teng bo'lmagan qiymat uch va qirra (ularning insidentligi) o'rtasidagi munosabatni bildiradi.
Y o'naltirilgan graf holatida tegishli ustundagi har bir uch chiquvchi x vertikal qatorida "−1" va kiruvchi y uch qatorida "1" qiymatiga ega; agar uch va qirra o'rtasida hech qanday bog'liqlik bo'lmasa, unda mos keladigan katak "0" qiymatiga ega bo‘ladi.
Qo’shnilik ro'yxati - bu grafni uchlar ro'yxati ("ro'yxatlar ro'yxati") to'plami sifatida ko'rsatish usuli - grafning har bir uchi qo'shni uchlar ro'yxatiga to'g'ri keladi.
63. Grafda o’tish algoritmlari (BFS algoritmi, DFS algoritmi)
Grafni ko‘rikdan o‘tkazish (Graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni ko‘rib chiqish prosedurasidir.
Ikkita usuli mavjud:
Tubiga qarab(Depth-First Search – DFS)
Eniga qarab(Breadth-First Search – BFS)
Bu usullar berilgan V tugundan boshlab bironta konteynerni qo‘llagan xolda barcha tugunlarni ko‘rib chiqadi.
Tubiga qarab ko‘rishda stek qo‘llaniladi.
Eniga qarab ko‘rishda navbat ishlatiladi.
Depth first search (DFS) algoritmi oson klassik graph algoritmlaridan biri bo’lib, u rekursiya ichida graph’dagi barcha vertex’larni tekshirib chiqishga yordam beradi. Depth first search algoritmining klassik deyilishiga sabab, qadimda undan labirintdan chiqish yo’lini topish uchun foydalanishgan. Labirintning boshlanish joyida g’altak – koptok qilib o’ralgan ipni ochib, yo’lni topishga kirishishgan. Berk ko’chaga kirib qolishganda, ip bo’yicha orqaga qaytib, kirilmagan yo’ldan davom ettirishgan. Shu tariqa ip orqali yurilgan yo’llarga qayta kirmaslik uchun ularni belgilab borishgan. Ip orqali yo’l topishni Trémaux maze exploration deb ham ataladi. Depth first search algoritmi labirintdan tez chiqib ketish uchun eng yaxshi yechim emas, u qisqa yo’lni topmaydi. Algoritm shunchaki «boshi oqqan ko’chaga» kirib chiqib, yo’l bor yo’qligini tekshiradi.
Kenglik bo'yicha birinchi qidiruv (BFS) grafika uchun daraxtlar / grafalar ma'lumotlari tarkibidagi o'tish yoki qidirish algoritmi. U ma'lum bir tepalikdan boshlanadi (har qanday ixtiyoriy vertex) va barcha bog'langan tepaliklarni o'rganadi va shundan so'ng eng yaqin cho'qqiga o'tadi va o'rganilmagan barcha tugunlarni o'rganadi va hech qanday vertex / tugunlari ikki marta tashrif buyurmasliklariga e'tibor beradi.
64. Daraxtlar grafning xususiy holi sifatida (daraxt, yo’naltirilgan daraxt, ildiz tuguni, ildiz, barg, ichki tugun, daraxt osti, daraxt ustida bajariladigan amallar)
Daraxt - bu bogʻlangan asiklik graf, ya’ni sikllar yoʻq va uchlar juftligi orasida bitta yoʻl bor (29-rasm). 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.
Sentroid - uch, u olib tashlanganida hosil boʻlgan ulanish komponentlarining oʻlchamlari n:2 dan oshmaydi (asl daraxtning yarmi kattaligi).
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.
65. Binar daraxtlar (ikkilik daraxtlar, daraxtlarni mashinada tasvirlash usullari, Pryufer kodi)
 Daraxt – bu chiziqsiz bog‘langan ma’lumotlar tuzilmasidir. Binar daraxtlar eng ko‘p foydalaniladigan daraxtlar turi xisoblanadi.
Daraxtlarni EXM xotirasida tasvirlanishiga ko‘ra xar bir element to‘rtta maydonga ega yozuv xisoblanadi. Mazkur maydonlar qiymati mos ravishda yozuv kaliti bo‘lib, boshqa elementlarga murojaatni ifodalaydi, ya’ni chapga-pastga, o‘nga-pastga va yozuv matniga.
SHuni esda tutish lozimki, daraxt xosil qilinayotganda, otaga nisbatan chap tomondagi o‘g‘il qiymati kichik kalitga, o‘ng tomondagi o‘g‘il esa katta qiymatli kalitga ega bo‘ladi. Masalan, quyidagi elementlardan binar daraxt quramiz: 50, 46, 61, 48, 29, 55, 79. U quyidagi ko‘rinishga ega bo‘ladi:

Natijada, o‘ng va chap qism daraxtlari bir xil bosqichli tartiblangan binar daraxt xosil qildik. Agar daraxtning o‘ng va chap qism daraxtlari bosqichlari farqi birdan kichik bo‘lsa, bunday daraxt ideal muvozanatlangan daraxt deyiladi. YUqorida xosil qilgan binar daraxtimiz ideal muvozanatlangan daraxtga misol bo‘ladi.
Pryufer kodi [1, n] kesmadagi n-2 butun sonlar ketma-ketligi yordamida n uchlari bilan belgilangan daraxtlarni birma-bir kodlash usuli. Ya’ni, Pryufer kodi - bu toʻliq graf va raqamlar ketma-ketligining barcha daraxtlari orasidagi biyeksiyasidir. Daraxtlarni kodlashning ushbu usuli nemis matematiki Xaynts Pryufer tomonidan 1918-yilda taklif qilingan. 𝑛 ta uchlari bilan berilgan daraxt uchun Pryufer kodini qurish algoritmini koʻrib chiqaylik. Kirishda qirralarning roʻyxati berilgan. Eng kichik raqamga ega boʻlgan daraxtning bargi tanlanadi, keyin u daraxtdan olib tashlanadi va bu barg bilan bogʻlangan uchlarning soni Pryufer kodiga qoʻshiladi. Ushbu protsedura n − 2 marta takrorlanadi. Oxir-oqibat, daraxtda faqat 2 ta uch qoladi va algoritm shu yerda tugaydi. Qolgan ikkita uchning raqamlari kodga yozilmaydi. Shunday qilib, ma’lum bir daraxt uchun Pryufer kodi n − 2 ta raqamlar ketma-ketligi boʻlib, bu yerda har bir raqam eng kichik barg bilan bogʻlangan uchning soni - bu segmentdagi raqam [1, n ].

66. Daraxtlarda Pryufer kodini aniqlash bosqichlari. Pryufer kodi orqali daraxtni tiklash

Pryufer kodini aniqlash.

Kodni olish algoritmi quyidagicha. Daraxt tugunlari 1 dan n gacha boʻlgan raqamlar bilan belgilangan (raqamlangan) boʻlsin. Biz eng kichik sonli 1-darajali uchni topamiz va kodga unga qoʻshni boʻlgan uchning sonini kiritamiz, shundan soʻng topilgan uchni (qirrasi bilan birga) oʻchirib tashlaymiz. Olingan graf osti bilan biz xuddi shu amalni bajaramiz, uni faqat bitta qirra qolguncha takrorlaymiz. Kodni yaratish jarayoni 34-rasmda keltirilgan. Keyingi bosqichda oʻchirilgan uchning soni ramkaga kiritilgan. Berilgan grafda (34-rasm, a) birinchi darajali uchlar orasida minimal son 2-uchda joylashgan. U 1-uchga qoʻshni. Shuning uchun Pryufer kodining birinchi raqami 1. 2-uchni olib tashlash natijasida biz b-rasmda koʻrsatilgan grafni olamiz. Ushbu grafda darajasi birga teng boʻlgan uchlar orasidagi minimal son 3 ga teng, shuning uchun kodning ikkinchi raqami 4. Shaklda koʻrsatilgan graflarga mos keladigan yana uchta takrorlashni bajargandan soʻng, c, d, e-rasmlardagi bitta qirradan iborat daraxtni olamiz {7; 6}. Jarayon tugallandi.
67. Tartiblashgan va muvozanatlashgan daraxtlar (AVL daraxti, uchlarni muvozanatlash, muvozanatlashgan daraxtlar haqidagi teorema)
AVL daraxti (ixtirochilar nomi bilan atalgan Adelson-Velskiy va Landis) bu o'z-o'zini muvozanatlashtiradigan ikkilik qidiruv daraxti. Bu birinchisi edi ma'lumotlar tuzilishi ixtiro qilinmoq. AVL daraxtida balandliklar ikkitadan bola har qanday tugunning pastki daraxtlari eng ko'pi bilan farq qiladi; agar har qanday vaqtda ular bir nechta farq qilsa, bu xususiyatni tiklash uchun muvozanatlash amalga oshiriladi. Qidiruv, qo'shish va o'chirish uchun hamma narsa kerak O(log n) o'rtacha va yomon holatlarda ham vaqt, qaerda - bu operatsiyadan oldin daraxtdagi tugunlarning soni. Qo'shish va o'chirish daraxtni bir yoki bir nechtasi bilan muvozanatlashni talab qilishi mumkin daraxtlarning aylanishi.
AVL daraxti ikkitasining nomi bilan atalgan Sovet ixtirochilar, Georgi Adelson-Velskiy va Evgenii Landis, kim uni o'zlarining 1962 yilgi "Axborotni tashkil etish algoritmi" maqolasida chop etgan.
AVL daraxtlari ko'pincha taqqoslanadi qizil-qora daraxtlar chunki ikkalasi ham bir xil operatsiyalar to'plamini qo'llab-quvvatlaydi va qabul qiladi asosiy operatsiyalar uchun vaqt. Qidiruv intensiv dasturlar uchun AVL daraxtlari qizil-qora daraxtlarga qaraganda tezroq, chunki ular yanada mutanosibroq.[4] Qizil-qora daraxtlarga o'xshash AVL daraxtlari balandligi bo'yicha muvozanatlashgan. Ikkalasi ham umuman emas vazn muvozanatli na - har qanday kishi uchun muvozanatli ;[5] ya'ni birodarlik tugunlari juda ko'p turli xil avlodlarga ega bo'lishi mumkin.

68. AVL daraxtlarining samaradorligini tahlil qilish (AVL daraxtlarining samaradorligini tahlil qilish, AVL daraxtidan barcha tugunlarni olib tashlash funksiyasi, Tugundan kalit boʻyicha izlash funksiyasi, Tugun hosil qilish funksiyasi)

Daraxtni muvozanatlash algoritmi
Binar daraxt muvozanatlangan yoki AVL-muvozanatlangan bo’lishi mumkin. DaraxtAVL-muvozanatlangan (1962 yil sovet olimlariAdelson, Velsk
Georgiy Maksimovich va Landis Yevgeniya Mihaylovichlar tomonidan taklif qilingan) deyiladi, agar daraxtdagi har bir tugunning chap va o’ng qismdaraxtlari balandliklari farqi 1 tadan ko’p bo’lmasa.
Berilgan butun sonlar – kalitlar ketma-ketligidan binar daraxt yaratib olamiz va uni muvozanatlaymiz. Daraxtni muvozanatlashdan maqsad, bunday daraxtga yangi element kiritish va daraxtdan element izlash algoritmi samaradorligini oshirishdan iborat, ya’ni bu amallarni bajarishdagi solishtirishlar soni kamayadi. Binar daraxtni muvozanatlash algoritmi quyidagicha bo’ladi.
69. B daraxtlar (B daraxt ta’rifi, B daraxtda amallar)
Knutning ta'rifiga ko'ra, tartibning B daraxti m quyidagi xususiyatlarni qondiradigan daraxt:

1. 
   Har bir tugun maksimal darajada bo'ladi m bolalar.
   
2. 
   Barg bo'lmagan har bir tugun (ildizdan tashqari) kamida ⌈ ga egam/ 2⌉ bolalar tugunlari.
   
3. 
   Ildizning barg tuguni bo'lmasa kamida ikkita bolasi bor.
   
4. 
   Yaproq bo'lmagan tugun k bolalar o'z ichiga oladi k - 1 tugma.
   
5. 
   Barcha barglar bir xil darajada ko'rinadi va hech qanday ma'lumotga ega emas. Har bir ichki tugunning kalitlari uning pastki daraxtlarini ajratadigan ajratish qiymatlari vazifasini bajaradi. Masalan, ichki tugunda 3 ta tugun (yoki kichik daraxt) bo'lsa, unda u 2 ta tugmachaga ega bo'lishi kerak: a₁ va a₂. Eng chap pastki daraxtdagi barcha qiymatlar kamroq bo'ladi a₁, o'rta kichik daraxtdagi barcha qiymatlar orasida bo'ladi a₁ va a₂va eng o'ng pastki daraxtdagi barcha qiymatlar quyidagidan kattaroq bo'ladi a₂. B daraxtlarida ichki (bargsiz) tugunlari ba'zi oldindan belgilangan oraliqda o'zgaruvchan bolalar tugunlariga ega bo'lishi mumkin. Ma'lumotlarni qo'shish yoki tugundan olib tashlashda uning tugunlari soni o'zgaradi. Oldindan belgilangan diapazonni saqlab qolish uchun ichki tugunlar birlashtirilishi yoki bo'linishi mumkin. Bir qator bolalar tugunlariga ruxsat berilganligi sababli, B daraxtlari boshqa muvozanatlashtiruvchi qidiruv daraxtlari singari qayta muvozanatlashishga hojat yo'q, lekin bo'sh joyni yo'qotishi mumkin, chunki tugunlar to'liq emas. Bola tugunlari sonining pastki va yuqori chegaralari odatda ma'lum bir dastur uchun belgilanadi.
   

70. Ustivor navbatlar (Binar uyum (kucha) - piramida (binary heap)