Bu uning har bir tuguni nol yoki bir- necha bolaga ega bo‘lgan iyerarxik tuzilmadir


Ikkilik daraxtlarning xususiyatlari


Download 130.12 Kb.
bet2/8
Sana29.01.2023
Hajmi130.12 Kb.
#1137878
1   2   3   4   5   6   7   8
Bog'liq
Daraxt

Ikkilik daraxtlarning xususiyatlari


  • Tugunlarning soni  to'liq ikkilik daraxtda, hech bo'lmaganda  va ko'pi bilan  , qayerda  bo'ladi balandlik daraxtning. Faqatgina ildiz tugunidan iborat daraxtning balandligi 0 ga teng.

  • Barg tugunlari soni  mukammal ikkilik daraxtda, bo'ladi  chunki bargsiz (ichki a) tugunlarning soni  .

  • Bu degani, to'liq binar daraxt bilan  barglari bor  tugunlar.

  • muvozanatli to'liq ikkilik daraxt,  (qarang ship funktsiyasi ).[iqtibos kerak ]

  • mukammal to'liq ikkilik daraxt,  shunday qilib  .

  • Ning ikkilik daraxtidagi bo'sh havolalar soni (ya'ni tugunlarning yo'q bolalari) n tugunlari (n+1).

  • A-dagi ichki tugunlarning soni to'liq binar daraxt n tugunlar  .

  • Bilan har qanday bo'sh bo'lmagan ikkilik daraxt uchun n0 barg tugunlari va n2 2-darajali tugunlar, n0 = n2 + 1.[25]

Kombinatorika


Yilda kombinatorika biri berilgan o'lchamdagi to'liq binar daraxtlar sonini hisoblash masalasini ko'rib chiqadi. Bu erda daraxtlarning tugunlariga biriktirilgan qiymatlari yo'q (bu mumkin bo'lgan daraxtlar sonini osonlikcha aniqlanadigan omilga ko'paytiradi) va daraxtlar faqat tuzilishi bilan ajralib turadi; ammo, har qanday tugunning chap va o'ng bolasi farqlanadi (agar ular turli xil daraxtlar bo'lsa, ularni almashtirish birinchisidan farq qiladigan daraxt hosil qiladi). Daraxtning kattaligi raqam sifatida qabul qilinadi n ichki tugunlar (ikki bolali); boshqa tugunlar barg tugunlari va ular mavjud n + 1 ulardan. Bunday ikkilik daraxtlarning soni n qatorini to'liq qavsga olish usullari soniga teng n + 1 bilan ajratilgan belgilar (barglarni ifodalovchi) n ikkilik operatorlar (ichki tugunlarni ifodalovchi), har bir operatorning subekspression argumentlarini aniqlash. Masalan uchun n = 3 shunga o'xshash qatorni qavsga qo'shish kerak  , bu besh usulda mumkin:

Ikkilik daraxtlarga yozishmalar aniq bo'lishi kerak va ortiqcha qavslar qo'shilishi (allaqachon qavslangan ifoda atrofida yoki to'liq ifoda atrofida) taqiqlangan (yoki hech bo'lmaganda yangi imkoniyatni keltirib chiqarmaydi).
0 o'lchamdagi (bitta bargdan iborat) noyob ikkilik daraxt mavjud va boshqa har qanday ikkilik daraxt uning chap va o'ng farzandlari juftligi bilan tavsiflanadi; agar ularning o'lchamlari bo'lsa men va j navbati bilan, to'liq daraxt o'lchamiga ega men + j + 1. Shuning uchun, raqam  Ikkilik daraxtlarning n quyidagi rekursiv tavsifga ega  va  har qanday musbat son uchun n. Bundan kelib chiqadiki  bo'ladi Kataloniya raqami indeks n.
Yuqoridagi qavs ichiga olingan satrlarni 2 uzunlikdagi so'zlar to'plami bilan adashtirmaslik kerakn ichida Dyk tili, ular faqat muvozanatli bo'ladigan tarzda faqat qavslardan iborat. Bunday satrlarning soni bir xil rekursiv tavsifni qondiradi (har bir Dyck so'zining uzunligi 2 ga teng)n uzunlik 2 (yopilgan) qavsdan keyin qolgan Dyck pastki so'zi bilan boshlang'ich '(' va uning mosligi ')' bilan qo'shib qo'yilgan Dyck pastki so'zi bilan belgilanadi.men va 2j qondirmoq men + j + 1 = n); shuning uchun bu raqam kataloniya raqamidir  . Shunday qilib, Dykning uzunligi 6 bo'lgan beshta so'zi bor:
.
Ushbu Dyck so'zlari xuddi shu tarzda ikkilik daraxtlarga mos kelmaydi. Buning o'rniga ular quyidagi rekursiv aniqlangan biektsiya bilan bog'liq: bo'sh satrga teng bo'lgan Dyck so'zi faqat bitta bargli 0 o'lchamdagi ikkilik daraxtga to'g'ri keladi. Dyckning boshqa har qanday so'zini () deb yozish mumkin ) , qayerda  , o'zlari (ehtimol bo'sh) Dyck so'zlari va bu erda ikkita yozilgan qavslar mos keladi. So'ngra bijection so'zlarni qo'yib belgilanadi  va  ildizning chap va o'ng bolalari bo'lgan ikkilik daraxtlarga mos keladi.
Bifektiv yozishmalarni quyidagicha aniqlash mumkin: Dyck so'zini qo'shimcha qavs ichiga yozing, natijada natijani quyidagicha izohlash mumkin Lisp ro'yxat ifodasi (bo'sh ro'yxat bilan () faqat paydo bo'ladigan atom); keyin nuqta-juft bu tegishli ro'yxat uchun mos keladigan ikkilik daraxtni tavsiflovchi to'liq parantezli ifoda (belgi sifatida NIL va operator sifatida '.' bilan) (bu to'g'ri ro'yxatning ichki vakili).
Ikkilik daraxtlarni ramzlar va qavslar qatori sifatida ko'rsatish qobiliyati shundan iboratki, ikkilik daraxtlar a elementlarini aks ettirishi mumkin bepul magma singleton to'plamida.

Download 130.12 Kb.

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




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