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 - 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.
Do'stlaringiz bilan baham: |
