Mavzu: 13 Dinamik dasturlash. Kriptoalgoritmlari. Algoritmlarni loyihalash Algorithm Design


Bu mukammal muvozanatlangan daraxt, ya'ni chap va o'ng pastki qism daraxtlar bir-biridan bittadan ko'p bo'lmagan darajada farq qiladigan daraxtdir


Download 1.24 Mb.
bet4/16
Sana15.06.2023
Hajmi1.24 Mb.
#1482872
1   2   3   4   5   6   7   8   9   ...   16
Bog'liq
13 mavzu Dinamik dasturlash. Kriptoalgoritmlarii

Bu mukammal muvozanatlangan daraxt, ya'ni chap va o'ng pastki qism daraxtlar bir-biridan bittadan ko'p bo'lmagan darajada farq qiladigan daraxtdir.


Binar daraxtning har bir tuguni to'rt turdagi maydonlardan iborat tuzilmadir. Ushbu maydonlarning tarkibi quyidagicha bo'ladi:
axborot maydoni (tugun kaliti);
xizmat ko'rsatish maydoni (bir nechta bo'lishi yoki bo’lmasligi ham mumkin);
chap qism daraxtga ko'rsatkich;
o'ng qism daraxtga ko'rsatkich.
Tugunlar darajasiga ko'ra, binar daraxtlar quyidagilarga bo'linadi:
qat'iy - daraxt tugunlari nol darajaga (barglar uchun) yoki ikkita (tugunlar uchun) ega;
qat'iy bo'lmagan - daraxt tugunlari nol darajaga ega (barglar uchun), bitta yoki ikkita (tugunlar uchun).
Binar daraxt faqat to'liq to'ldirilgan darajalarni o'z ichiga olgan bo'lsa to'liq deb nomlanadi. Aks holda, u to'liq emas.
Binar daraxt bo'sh to'plam bo'lishi mumkin. Binar daraxt ro'yxatga aylanishi mumkin.

m-daraxtni binar daraxtga aylantirish

m-daraxtni binar daraxtga aylantirish

    • Daraxtning har qanday tugunida barcha shoxlar kesishadi, faqat chetki chap katta o'g'illarga to'g'ri keladiganlaridan tashqari.
    • Bir ota-onaning barcha o'g'illari gorizontal chiziqlar bilan bog'lanadi.
    • Hosil qilingan strukturaning har qanday tugunidagi katta o'g'il ushbu tugun ostidagi tugun bo'ladi (agar mavjud bo'lsa).

Algoritm harakatlarining ketma-ketligi rasmda ko'rsatilgan
m-daraxtni binar daraxtga aylantirish
Daraxt markazlari va bi-markazlar
Daraxtning markazi - eng kam ekssentriklikka ega tugun. G daraxtidagi X tugunning ekssentrisitetligi - bu X tugun va daraxtdagi har qanday boshqa tugun orasidagi maksimal masofa. Maksimal ekssentrisitet - bu daraxtning diametri. Agar daraxtda faqat bitta markaz bo'lsa, u "Markaziy daraxt" deb nomlanadi va agar u faqat bir nechta markazga ega bo'lsa, u "Bi-markazli" daraxti deb nomlanadi. Har bir daraxt markaziy yoki ikki markazli bo'ladi.


Download 1.24 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   16




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling