Maxmasoatova faridaning algoritmlarni loyihalash fanidan tayyorlagan

Daraxtlarni aks ettirish usullari

Hozirgacha biz mantiqiy tuzilma sifatida mavhum holda daraxtlar haqida gaplashdik. Keling, gunohkor erga tushib, uni jismoniy joylashtirish variantlarini muhokama qilaylik. Massivlar, ro'yxatlar, ko'rsatgichlar massivi daraxtning jismoniy tasvirining tarkibiy qismlari bo'lishi mumkin. Eng oddiyidan boshlaylik.
Daraxtning ajdodlar indekslari bilan massiv sifatida tasvirlanishi. Har bir bolaning bitta ajdodlari bo'lganligi sababli, tepaliklarni massivga joylashtirish orqali siz ularning har biriga ajdodlar indeksini qo'yishingiz mumkin.



Anjir. 8 1. 1 . Ajdodlar indekslari bo'lgan massivdagi daraxt

Algoritmlarning daraxtlar bilan ishlash samaradorligi

"Daraxtlar - rekursiv algoritmlar" va "makon-vaqt" juftligi o'rtasida o'xshashliklarni yaratish mumkin. Rekursiv dastur ishlayotganda funktsiya chaqiruv daraxti o'z vaqtida kengaytiriladi va daraxt ma'lumotlar tuzilishi sifatida rekursiv algoritm bajarilishining xotirada xaritalangan natijasiga o'xshaydi. Shuning uchun rekursiv algoritmlarning samaradorligi to'g'risidagi xulosalar daraxtlarga taalluqlidir:
- daraxtning to'liq rekursiv o'tishi chiziqli;
- samarali ochko'zlik algoritmlari. Daraxtga nisbatan ochko'zlik har bir tepada bitta bolani tanlashdan iborat. Rekursiv chaqiruv davri o'rniga, barcha avlodlar uchun bitta qo'ng'iroq bo'lishi kerak. Siz har bir qadamda tanlangan bolaga borib, rekursiv algoritmni dumaloq algoritm bilan almashtirishingiz mumkin. Aniq uchun asosochko'z tanlov - daraxtga ortiqcha narsalarni kiritish (tepalikdagi qo'shimcha ma'lumotlar) yoki undagi ma'lumotlarni buyurtma qilish.
Daraxtlarning to'liq rekursiv o'tishiga asoslangan algoritmlar. Dastlab, daraxtda ma'lumotlar qanday tashkil qilinganligidan qat'i nazar, eng oddiy algoritmlarni ko'rib chiqamiz. Daraxtning to'liq rekursiv o'tishi daraxtning barcha tepalarini bosib o'tishni va butun daraxt tuzilishining umumiy xususiyatlarini olishdan iborat. Siz darhol bypass natijasini shakllantirishning texnologik usullari haqida to'xtalishingiz kerak:
- rekursiv funktsiyani aniq natijasi rekursiv funktsiyadan tushadigan zanjirning bajarilishi paytida uning to'planishini nazarda tutadi (ya'ni, natijaning to'planishi teskari yo'nalishda - avlodlardan ajdodgacha). Bundan tashqari, har bir tepalik, avlodlardan olingan natijalarni o'ziga xos "malhamda uchib" qiladi, ya'ni. subtrees natijalarini o'zi bilan birlashtiradi;
- rekursiv chaqiriqlar zanjiri bo'ylab uzatiladigan rasmiy parametr - zvenodan foydalanish mumkin. Bunday holda, barcha rekursiv chaqiriqlar natijani to'plash uchun ishlatiladigan global ma'lumotlarning rolini o'ynaydigan umumiy o'zgaruvchiga ishora qiladi.
Ro'yxatlar va massivlar bilan dastlabki taqqoslash. Daraxtdagi ma'lumotlarni tashkil qilish tafsilotlariga kirmasdan ham, biz uchun ma'lum bo'lgan uning vakili shakllariga asoslanib, dastlabki xulosalar chiqarishimiz mumkin. Birinchidan, ichidaAlgoritmik ravishda daraxt taniqli so'zlarni "o'rmonga - ko'proq o'tin" ga amal qiladi. Bu holda "o'tin" bu daraxtning "chuqurligi" o'sishi bilan sonning eksponent o'sishi bo'lgan tepalardir. Agar bir vaqtning o'zida "ortiqcha" daraxtlarni kesishni samarali tashkil etish imkoniyati mavjud bo'lsa, unda elementlarni qiymatlari bo'yicha topish va ularga mantiqiy raqamlar bo'yicha kirishning samarali algoritmlariga umid qilish mumkin. Bu erda ro'yxatlarga nisbatan aniq ustunlik mavjud, bu erda barcha algoritmlar to'liq qidirishga asoslangan (chiziqli qidirish). Ikkinchidan, texnologik jihatdantepaliklarning tartibini yoki daraxtlarga joylashishini o'zgartirish, ro'yxatlarda bo'lgani kabi, alohida tepalardagi bog'lanishlarni (filiallarni) qayta tashkil etish orqali ham amalga oshirilishi mumkin. Bu elementlarning massiv harakatini (siljishini) talab qiladigan massivlarga nisbatan aniq ustunlikka ega. Shunday qilib, samaradorlik nuqtai nazaridan daraxt bu ikkita haddan tashqari: qator va ro'yxat o'rtasidagi kelishuvdir.

muvozanat kabi xarakterli daraxtni tanishtiramiz.Balans daraxt shoxlari uzunliklarida tarqalishini xarakterlaydi. Aniqrog'i, biz ildiz shoxidan tepalikka qadar erkin shox bilan masofalar haqida gapiramiz. Maksimal va minimal novdalar uzunligi 1dan ko'p bo'lmagan farq qilsa, daraxt muvozanatli deb ataladi, bunday daraxt novdaning uzunligi bilan daraxtning tepalari soni o'rtasidagi eksponent (yoki teskari, logaritmik) bog'liqlik bilan tavsiflanadi :

N = 1 + m + m ² + m ³ +… + m ^{L <} m ^L , L m N

Eng yomon holatda, har bir tepada bittadan bola bo'lsa, daraxt tanazzulga uchraydi, bu holda novdalar uzunligi 1 ga teng bo'lmagan tepalar soniga teng bo'ladi.
Bundan tashqari, bir martalik o'qqa asoslangan barcha algoritmlar, to'liq rekursiv o'tish , chiziqli murakkablikka ega bo'ladiT = N . Ularning yaxshilanishi faqatgina "botirish chuqurligini" cheklashdan iborat bo'lishi mumkin, agar buning uchun etarli asoslar mavjud bo'lsa. Yana bir narsa shundaki, unga asoslangan algoritmlardallanma. Har bir tepada ular mumkin bo'lgan bolalardan faqat bittasini tanlaydilar. Bunday algoritmlar deyiladiochko'zlik ("8.7. Rekursiv algoritmlarning samaradorligi" ga qarang). Siz darhol ularning murakkabligi ular tanlagan daraxt novdasi uzunligiga teng ekanligini darhol ko'rishingiz mumkin. Balanslangan daraxt uchun qaramlik logaritmik bo'ladi.


T = L m N,


daraxtlar ro'yxatiga kirib borishi uchun u chiziqli. Bu erda ikkita muammo mavjud. Birinchidan, muvozanatli daraxtni saqlash. Buning ikkita echimi mavjud:
- odatdagidan ancha murakkab bo'lgan daraxt muvozanatini saqlaydigan algoritmlardan foydalanish, chunki ular qo'shni daraxtlar vertikallari guruhlarining turli xil topologik transformatsiyalaridan foydalanadilar (bundan tashqari, rekursiv);
- daraxtning davriy hizalanishi (muvozanati), ehtimol qo'shimcha ma'lumotlar tuzilishi yordamida. Ushbu echim daraxt bilan ishlash uchun oddiy algoritmlardan foydalanishga imkon beradi, lekin uning muvozanatini kuzatishni talab qiladi (xuddi shu algoritmlar buni amalga oshirishi mumkinligiga e'tibor bering, masalan, ma'lum bir qiymatni qidirishda filial uzunligini aniqlash). Balanslash protsedurasi ancha vaqt talab qilishi mumkin, ammo bu nisbatan kamdan-kam hollarda deyiladi.
Kundalik darajada ushbu alternativani "ideal tartib yoki davriy umumiy tozalash " sifatida shakllantirish mumkin . Shunga o'xshash holat har qanday dinamik resurslarni taqsimlash va ulardan foydalanish tizimida uchraydi: dinamik xotirani ajratish tizimida (2.6), ikkilik faylni rejalashtirishda (9.2), operatsion tizimning fayllarni boshqarish tizimida, u o'xshash echimlarga ega.
Ikkinchi muammo algoritmda har bir tepada bitta avlodni aniq tanlash uchun asoslar yotadi (badiiy o'xshashlik - "chorrahada ritsar"). Bu erda yana ikkita yondashuv mavjud:
- tepada qo'shimcha (ortiqcha) ma'lumotlarning mavjudligi , bu "bu erda va hozirda" bunday tanlovni amalga oshirishga imkon beradi;
- daraxtda ma'lumotlarni joylashtirishning ma'lum bir tartibining mavjudligi.
Graflarni ifodalash usullari
Yo’naltirilmagan, yo’naltirilgan va o’girlikka ega bo’lgan graflarni kompyuter dasturlash tillari hotirasida ifodalash, ya'ni xotirada tashkil etish uchun statik tuzilmasi matritsadan yoki dinamik tuzilmasi ro’yxatlardan foydalanish mumkin. Har qanday masalalarida har bitta usulining o’zining afzalligi va kamchiliklariga egadir. Yo’naltirilmagan, yo’naltirilgan va o’girlikka ega bo’lgan graflarni ifodalash uchun har usulining o’zining qoida asosida shakllanadi. Shunday to’rtta usullarga to’xtalib o’tamiz:

• Qo'shma matritsa (adjacency matrix);

  
  

• Intsidientlik matritsa (incidence matrix);

  
  

• Qo'shnilik ro'yxati (adjacency list);

  
  

• Qirralar ro'yxati (edges list).

  
  

G grafning qo'shma matritsasi bu n-o'lchamli A kvadrat matritsa bo'lib,