Algoritmlarning xossalari Algoritmning asosiy xossalari. Algoritmning 5-ta asosiy xossasi bor: Diskretlilik Cheklilik

Ta'rif: cheklangan to'plam Tbir yoki bir nechta tugunlardan iborat bo'lib, ular quyidagilar:
a) Ushbu daraxtning ildizi deb nomlangan bitta maxsus tugun mavjud.
b) tugunlarning qolgan qismi (ildizdan tashqari) juftlik bilan ajratilgan kichik to'plamlarda joylashgan bo'lib, ularning har biri o'z navbatida daraxtdir. Daraxtlar deyiladi kichik daraxtlar bu daraxt
Ushbu ta'rif rekursivdir. Qisqacha aytganda, daraxt - bu ildiz va unga bog'langan subtreelardan iborat bo'lgan to'plam, ular ham daraxtlardir. Daraxt o'zi orqali aniqlanadi. Biroq, bu ta'rif mantiqan to'g'ri keladi, chunki rekursiya cheklangan. Har bir kichik daraxt tarkibidagi daraxtga qaraganda kamroq tugunlarni o'z ichiga oladi. Oxir-oqibat, biz faqat bitta tugunni o'z ichiga olgan subtree-larga kelamiz va bu nima ekanligi allaqachon aniq.


Shakl: 3. Yog'och.
Shakl. 3-da etti tugunli daraxt ko'rsatilgan. Oddiy daraxtlar pastdan tepaga o'ssa-da, ularni teskari yo'naltirish odat tusiga kiradi. Diagrammani qo'l bilan chizishda bu usul shubhasiz qulayroq. Ushbu nomuvofiqlik tufayli, ba'zida tugunlardan biri ikkinchisining ustida yoki pastida deyilganida chalkashliklar paydo bo'ladi. Shu sababli, oilaviy daraxtlarni tavsiflashda, tugunlarni ildiz ajdodlariga va uzoqroq avlodlarga yaqinroq chaqirishda ishlatiladigan terminologiyadan foydalanish qulayroq.
Daraxtni boshqa usullar bilan grafik tasvirlash mumkin. Ulardan ba'zilari shakl. 4. Ta'rifga ko'ra, daraxt - bu o'rnatilgan to'plamlar tizimi, bu erda bu to'plamlar kesishmaydi yoki to'liq bir-birining ichiga kiradi. Bunday to'plamlarni tekislikdagi maydonlar sifatida tasvirlash mumkin (4a-rasm). Shakl. 4b, ichki o'rnatilgan to'plamlar tekislikda joylashgan emas, balki bitta qatorga kengaytirilgan. Shakl: 4b-ni ichki qavslarni o'z ichiga olgan ba'zi algebraik formulaning diagrammasi sifatida ham ko'rib chiqish mumkin. Shakl: 4c daraxt tuzilishini peshayvon sifatida tasvirlashning yana bir mashhur usulini taqdim etadi.

Shakl: 4. Daraxt tuzilmalarini tasvirlashning boshqa usullari: (a) ichki to'plamlar; b) ichki qavslar; (c) imtiyozlar ro'yxati.

Uyg'un ro'yxat dastur kodini formatlash bilan aniq o'xshashliklarga ega. Darhaqiqat, tuzilgan dasturlash paradigmasi doirasida yozilgan dastur ichki konstruktsiyalardan iborat daraxt sifatida ifodalanishi mumkin.
Shuningdek, yorliqlar ro'yxati va kitoblardagi tarkib jadvallari ko'rinishi o'rtasida o'xshashlik hosil qilishingiz mumkin, bu erda bo'limlarda kichik bo'limlar, o'z navbatida bo'limlarda va boshqalar mavjud. Bunday bo'limlarni raqamlashning an'anaviy usuli (1-bo'lim, 1.1 va 1.2-bo'limlar, 1.1.2-kichik bo'lim va boshqalar) Deyvi o'nlik tizimi deb ataladi. Shakldagi daraxtga qo'llaniladi. 3 va 4 ushbu tizim quyidagilarni beradi:
1. A; 1,1 B; 1,2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;
5.2. O'tayotgan daraxtlar
Daraxt tuzilmalari bilan bog'liq barcha algoritmlar doimo bir xil g'oyani, ya'ni g'oyani o'z ichiga oladi o'tish yoki daraxtlarni kesib o'tish... Bu daraxt tugunlariga tashrif buyurishning bir usuli bo'lib, unda har bir tugun aynan bir marta bosib o'tiladi. Bu daraxt tugunlarining chiziqli joylashishiga olib keladi. Xususan, uchta usul mavjud: siz tugunlarni oldinga, teskari va oxirgi tartibda o'tishingiz mumkin.