Yakuniy yozma (M. T. A). Ma’lumotlarning tarmoqli tuzilmalari: ta’riflar, asosiy tushunchalar

Dijkstra algoritmini amalga oshirish

Grafik og'irliklarini saqlash uchun kvadrat matritsa ishlatiladi. Qator va ustun sarlavhalarida grafaning uchlari joylashgan. Grafik yoylarining og'irliklari jadvalning ichki kameralariga joylashtirilgan. Grafikda ko'chadan yo'q, shuning uchun matritsaning asosiy diagonali nol qiymatlarni o'z ichiga oladi.

Daraxt tuzilmalari ustida bajariladigan amallarni sanab bering va misollar yordamida tushuntiring.
Aniq pozitsiyadan yangi tugun qo’shish;
Qism daraxt qo’shish;
Daraxtga yangi shox qo’shish (emlash deyiladi);
Ixtiyoriy tugunning ildiz elementini topish;
Ikkita tugunning umumiy eng kichik avlodini topish;
Daraxtning barcha elementlarini ro’yxatga olish;
Daraxt shoxidagi elementlarni ro’yxatga olish;
Elementni qidirish;
Daraxt shoxini o’chirish (qirqish deyiladi);
Qismdaraxtni o’chirish; Elementni o’chirish.
Daraxtni aylanib o’tish (daraxtda o’tish) (bunda, asosan, tugunlarni chop etish tushuniladi);


64 Ko’p o’lchamli daraxtlarni binar ko’rinishga keltirish amalini tushuntirib bering.

64. Binar daraxtga ta’rif bering, misollar keltiring.
Agar daraxtni tashkil etuvchi element(tugun)lardan ko`pi bilan 2ta shox chiqsa, yani har bir tugun tuzilmaning ko`pi bilan 2ta tuguni bilan bog`langan bo`lsa, u holda bunday daraxt binar daraxt deyiladi.

Umumiy holda binary daraxt har bir elementi 4ta maydonga ega yozuv hisoblanadi.

Tarif 2. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari va vazni teng bo`lsa, u holda bunday binar daraxt ideal muvozanatlangan daraxt deyiladi

Tarif 3. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari orasida farq 1 dan katta bo`lmasa, u holda bunday binary daraxt muvozanatlangan daraxt deyiladi:
Ko`p o`lchamli daraxtni binary ko`rinishga keltirishning noformal algoritmi: Daraxtning har bir tugunida katta o`g`liga mos chetki chap shoxidan tashqari barcha shoxlari kesib tashlanadi.
*Bitta otaning barcha o`g`illari gorizontal chiziq bilan ulanadi.
*Hosil qilingan tuzilmada har bir katta o`g`il mazkur tugun pastida turgan tugun hisoblanadi. (agar u mavjud bo`lsa).Amallar ketma-ketligi quyida keltirilgan: