Mavzu: 14 “Dag‘al kuch” usuli bilan tartiblashtirish. Algoritmlarni loyihalash Algorithm Design

Markerlangan (belgilangan) daraxtlar
Belgilangan daraxt - bu vertikallarga 1 dan n gacha noyob raqamlar berilgan daraxt. Umumiy formulani taklif qilish uchun biz bunday daraxtlarni n ning kichik qiymatlari uchun qo'l bilan hisoblashimiz mumkin. n tugunli belgilangan daraxtlar soni nn−2 ga teng. Ikkita belgilangan daraxtlar izomorfik (bir xil), agar ularning grafikalari izomorf bo'lsa va ikkita daraxtning tegishli nuqtalari bir xil belgilarga ega bo'lsa.
Misol
Misol.
Rasmda (a + b) * (a + c) arifmetik ifodasini ifodalaydigan belgili daraxtni keltirilgan, bu yerda n1, ..., n7 tugunlarning nomlari (rasmdagi belgilar tegishli tugunlar yoniga qo'yilgan). Daraxt belgilarini elementlariga moslashtirish qoidalari quyidagicha.

• Har bir bargning belgisi operandga mos keladi va uning qiymatini o'z ichiga oladi, masalan n4 tugun a operandni ifodalaydi.
• Har bir ichki (ota-ona) tugunning belgisi operatorga mos keladi. Faraz qilaylik, n tuguni θ ikkilik operatori bilan belgilanadi (masalan, + yoki *) va bu tugunning chap o'g'li E1 ifodaga, o'ng tomoni - E2 ifodasiga to'g'ri keladi. U holda n tugun va uning o'g'illari (E1) θ (E2) ifodasini ifodalaydi. Agar kerak bo'lsa, siz ota-onalarni olib tashlashingiz mumkin.

Belgisiz daraxtlar
Belgisiz daraxt - uning tugunlariga raqamlar berilmagan daraxt. n tugunlar soniga ega belgilangan daraxtlar soni $ \ frac {(2n)!} {(N + 1)! N! } $ (n- е kataloniya raqami)
Kombinatorik matematikada Katalon raqami har xil hisoblash masalalarida uchraydigan, ko'pincha rekursiv aniqlangan obyektlarni o'z ichiga olgan tabiiy sonlar ketma-ketligini hosil qiladi. Ular belgiyalik matematik Evgeniy Charlz Katalan (1814-1894) sharafiga nomlangan.
Misol
Ildizli daraxt
Ildizlangan daraxt G - bu daraxtning ildizi deb nomlangan maxsus tugunga ega bo'lgan bog'langan asiklik grafik va har bir chekka to'g'ridan-to'g'ri yoki bilvosita ildizdan kelib chiqadi.Tartiblangan ildizli daraxt - bu har bir ichki tepalikning bolalari buyurtma qilingan ildiz otgan daraxt. Agar ildiz otgan daraxtning har bir ichki tepasida ko'pi bilan m bola bo'lsa, u m-daraxt daraxti deb ataladi. Agar ildiz otgan daraxtning har bir ichki tepasida aynan m bola bo'lsa, u to'liq m-daraxt daraxti deb ataladi. Agar m = 2 bo'lsa, ildiz otilgan daraxt binar daraxt deb ataladi.