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

Daraxtning markazlari va bi-markazlarini topish algoritmi
1-qadam - Berilgan daraxtdan 1-darajadagi barcha tepaliklarni olib tashlang va shuningdek ularning tushgan qirralarini ham olib tashlang.
2-qadam - qirra bilan bog'langan bitta yoki ikkita tugun qolguncha 1-bosqichni takrorlang. Agar bitta tugun qolgan bo'lsa, unda bu daraxtning o'rtasidir va agar qirra bilan bog'langan ikkita tugun bo'lsa, unda bu daraxtning bi-markazidir.
1-masala
Quyidagi daraxtning markazi/bi-markazini aniqlang—
Yechimi
Oldiniga biz 1 darajali tugunlarni o’chiramiz, shuningdek ularning qirralarini ham. Quyidagi daraxtga ega bo’lamiz:
Shunga qaramay, biz 1 darajadagi barcha tugunlarni olib tashlaymiz, shuningdek ularning qirralarini olib tashlaymiz va quyidagi daraxtni olamiz:
Nihoyat, biz bitta "c" tugunga ega bo'ldik va algoritmni to'xtatdik. Bitta tugun bo'lgani uchun, bu daraxt bitta "c" markazga ega va daraxt markaziy daraxtdir.
2-masala
Quyidagi daraxtning markazi/bi-markazini aniqlang—
Yechimi
Oldiniga biz 1 darajali tugunlarni o’chiramiz, shuningdek ularning qirralarini ham. Quyidagi daraxtga ega bo’lamiz:
Shunga qaramay, biz 1 darajadagi barcha tugunlarni olib tashlaymiz, shuningdek ularning qirralarini olib tashlaymiz va quyidagi daraxtni olamiz:
Va nihoyat, bizda ikkita "c" va "d" tugunlar qoldi, shuning uchun algoritmni to'xtatamiz. Biz qirra bilan bog'langan ikkita tugunni qoldirganimiz sababli, bu daraxt ikki markazli “cd" ga ega va daraxt bi-markazlidir.
Markerlangan (belgilangan) daraxtlar
Daraxtdagi har bir tugunga yorliq (label) yoki qiymat belgilash ko'pincha foydalidir, huddi oldingi mavzulardagi ro'yhat elementlari uchun aniq qiymatlarni qo’yganimiz kabi. Yorliqlar bilan bog'langan tugunlarga ega bo'lgan daraxtga belgilangan daraxt deyiladi.
Tugun yorlig'i tugunning nomi emas, balki tugunda "saqlanadigan" qiymatdir. Ba'zi dasturlarda biz yorliqning qiymatini o'zgartiramiz, chunki tugun nomi doimiy ravishda saqlanadi. Quyidagi o'xshashlik foydalidir: ro'yxat-daraxtlar, tugun-holat, yorliq-element.