Daraxtlar terminologiyasi yaxshi standartlanmagan va shuning uchun ham adabiyotda turlicha

Ikkilik daraxt turlari

Daraxtlar terminologiyasi yaxshi standartlanmagan va shuning uchun ham adabiyotda turlicha.

A ildiz otgan ikkilik daraxt bor ildiz tuguni va har bir tugunning ko'pi bilan ikkita bolasi bor.

To'liq binar daraxt

An ajdodlar jadvali mukammal chuqurlik-4 ikkilik daraxtiga xaritalar.

A to'liq ikkilik daraxt (ba'zan a deb ham nomlanadi to'g'ri[15] yoki samolyot ikkilik daraxt)[16][17] har bir tugunda 0 yoki 2 boladan iborat bo'lgan daraxt. To'liq ikkilik daraxtni aniqlashning yana bir usuli bu rekursiv ta'rif. To'liq ikkilik daraxt ham:[11]

Bitta tepalik.

Ildiz tugunida ikkita kichik daraxt bo'lgan daraxt, ikkalasi ham to'liq ikkilik daraxtlardir.

A to'liq har darajadagi ikkilik daraxt, ehtimol oxirgisi bundan mustasno, to'liq to'ldirilgan va oxirgi darajadagi barcha tugunlar iloji boricha chaproq. U 1 dan 2 gacha bo'lishi mumkinh oxirgi darajadagi tugunlar h.[18] Muqobil ta'rif - eng to'g'ri barglari (ehtimol barchasi) olib tashlangan mukammal daraxt. Ba'zi mualliflar ushbu atamadan foydalanadilar to'liq Buning o'rniga quyida keltirilgan mukammal ikkilik daraxtga murojaat qilish, bu holda ular ushbu turdagi daraxtlarni (ehtimol oxirgi daraja to'ldirilmagan holda) deyarli to'liq ikkilik daraxt yoki deyarli yakunlandi ikkilik daraxt.[19][20] To'liq ikkilik daraxt massiv yordamida samarali tarzda ifodalanishi mumkin.[18]

To'liq ikkilik daraxt (bu to'liq emas)

A mukammal ikkilik daraxt - bu barcha ichki tugunlarning ikkita farzandi bo'lgan ikkilik daraxt va barcha barglar bir xil chuqurlik yoki bir xil Daraja.[21] Barkamol binar daraxtning misoli (qarindosh bo'lmagan). ajdodlar jadvali insonning ma'lum bir chuqurlikka ega bo'lishi, chunki har bir odamning ikkita biologik ota-onasi (bitta onasi va bitta otasi) bor. Agar ota-bobolar jadvalida onaning va otaning ma'lum bir tugun uchun har doim bir tomonda bo'lishi sharti bilan, ularning jinsi chap va o'ng bolalarning o'xshashligi sifatida qaralishi mumkin, bolalar bu erda algoritmik atama sifatida tushuniladi. Shuning uchun mukammal daraxt har doim to'liq bo'ladi, ammo to'liq daraxt mukammal bo'lishi shart emas.

In cheksiz to'liq ikkitomonlama daraxt, har bir tugunda ikkita bola bor (va shuning uchun darajalar to'plami shunday) nihoyatda cheksiz). Barcha tugunlarning to'plami son-sanoqsiz, ammo ildizdan chiqadigan barcha cheksiz yo'llarning to'plamini hisoblash mumkin emas. doimiylikning kardinalligi. Buning sababi shundaki, bu yo'llar buyurtmani saqlash bilan mos keladi bijection ning nuqtalariga Kantor o'rnatilgan, yoki (a misolidan foydalanib Stern-Brocot daraxti) ijobiy to'plamga mantiqsiz raqamlar.

A muvozanatli ikkilik daraxt - bu har bir tugunning chap va o'ng pastki daraxtlari balandligi bo'yicha 1 dan ko'p bo'lmagan farq qiladigan ikkilik daraxt tuzilishi.[22] Ikkala daraxtni ham ko'rib chiqish mumkin, u erda hech qanday barg bargdan boshqa bargga qaraganda ancha uzoqroq joylashgan. (Turli xil muvozanatlash sxemalari "ancha uzoqroq" ning turli xil ta'riflariga imkon beradi.[23])

A buzilib ketgan (yoki patologik) daraxt - bu har bir ota-ona tugunida faqat bitta bog'langan tugun mavjud.[24] Bu shuni anglatadiki, daraxt o'zini a kabi tutadi bog'langan ro'yxat ma'lumotlar tuzilishi.

Ikkilik daraxtlarning xususiyatlari

Tugunlarning soni n to'liq ikkilik daraxtda, hech bo'lmaganda n=2h+1 va ko'pi bilan {displaystyle n=2^{h+1}-1}, qayerda h bo'ladi balandlik daraxtning. Faqatgina ildiz tugunidan iborat daraxtning balandligi 0 ga teng.

Barg tugunlari soni l mukammal ikkilik daraxtda, bo'ladi l=(n+1)/2 chunki bargsiz (ichki a) tugunlarning soni n-l=sum _{k=0}^{log _{2}(l)-1}2^{k}=2^{log _{2}(l)}-1=l-1.

Bu degani, to'liq binar daraxt bilan l barglari bor n=2l-1 tugunlar.

A muvozanatli to'liq ikkilik daraxt, h=lceil log _{2}(l)ceil +1=lceil log _{2}((n+1)/2)ceil +1=lceil log _{2}(n+1)ceil (qarang ship funktsiyasi).[iqtibos kerak]

A mukammal to'liq ikkilik daraxt, l=2^{h} shunday qilib n=2^{h+1}-1.

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 lfloor n/2floor .

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

Kombinatorika

Ushbu bo'lim emas keltirish har qanday manbalar. Iltimos yordam bering ushbu bo'limni takomillashtiring tomonidan ishonchli manbalarga iqtiboslarni qo'shish. Manbaga ega bo'lmagan materialga qarshi chiqish mumkin va olib tashlandi. (2014 yil iyul) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

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 X*X*X*X, bu besh usulda mumkin:

((X*X)*X)*X,qquad (X*(X*X))*X,qquad (X*X)*(X*X),qquad X*((X*X)*X),qquad X*(X*(X*X)).

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 C_ {n} Ikkilik daraxtlarning n quyidagi rekursiv tavsifga ega C_ {0} = 1va extstyle C_{n}=sum _{i=0}^{n-1}C_{i}C_{n-1-i} har qanday musbat son uchun n. Bundan kelib chiqadiki C_ {n} 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 C_ {n}. Shunday qilib, Dykning uzunligi 6 bo'lgan beshta so'zi bor:

()()(),qquad ()(()),qquad (())(),qquad (()()),qquad ((())).

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 mumkinw_ {1})w_ {2}, qayerda w_ {1},w_ {2} o'zlari (ehtimol bo'sh) Dyck so'zlari va bu erda ikkita yozilgan qavslar mos keladi. So'ngra bijection so'zlarni qo'yib belgilanadi w_ {1} va w_ {2} 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.

Ikkilik daraxtlarni saqlash usullari

Ikkilik daraxtlarni qurish mumkin dasturlash tili ibtidoiy usullar.

Tugunlar va ma'lumotnomalar

Bilan tilda yozuvlar va ma'lumotnomalar, ikkilik daraxtlar odatda daraxt tugunlari tuzilishi bilan qurilgan bo'lib, unda ba'zi ma'lumotlar va chap farzandi va uning o'ng bolasi haqida ma'lumotlar mavjud. Ba'zan unda noyob ota-onasiga havola mavjud. Agar tugunda ikkitadan kam bola bo'lsa, ko'rsatgichlarning ayrimlari maxsus nol qiymatiga yoki maxsus qiymatga o'rnatilishi mumkin qo'riqchi tuguni.

Ikkilik daraxtlarni saqlashning bu usuli xotiraning juda oz qismini behuda sarflaydi, chunki ko'rsatgichlar yarmidan ko'proq vaqt nolga teng bo'ladi (yoki qo'riqchiga yo'naltiriladi); ko'proq konservativ vakillik alternativasi ipli ikkilik daraxt.[26]

Bilan tillarda belgilangan kasaba uyushmalari kabi ML, daraxt tuguni ko'pincha ikki turdagi tugunlarning yorliqli birikmasi bo'lib, ulardan biri ma'lumotlarning 3-katakchasi, chap bola va o'ng bola, ikkinchisi esa ma'lumotlar yo'q va "barg" tugunidir. ko'rsatgichlari bo'lgan tildagi nol qiymatiga o'xshash funktsiyalar. Masalan, quyidagi kod satri OCaml (ML shevasi) har bir tugunda belgini saqlaydigan ikkilik daraxtni belgilaydi.[27]

turi chr_tree = Bo'sh | Tugun ning char * chr_tree * chr_tree

Massivlar

Ikkilik daraxtlarni kenglikda birinchi tartibda saqlash mumkin yashirin ma'lumotlar tuzilishi yilda massivlar, va agar daraxt to'liq ikkilik daraxt bo'lsa, bu usul bo'sh joyni yo'qotmaydi. Ushbu ixcham tartibda, agar tugun indeksga ega bo'lsa men, uning bolalari indekslarda topilgan 2i+1 (chap bola uchun) va 2i+2 (o'ng tomonda), ota-onasi (agar mavjud bo'lsa) indeksda bo'lsa leftlfloor {frac {i-1}{2}}ightfloor (agar ildiz nol ko'rsatkichiga ega bo'lsa). Shu bilan bir qatorda, 1-indekslangan massiv bilan, amalga oshirishni topilgan bolalar bilan soddalashtirish mumkin 2i va 2i+1, va ota-ona topilgan {displaystyle lfloor i/2floor }.[28] Ushbu usul ixchamroq saqlash va undan yaxshi foyda keltiradi ma'lumotlarning joylashuvi, ayniqsa, oldindan buyurtma o'tish paytida. Biroq, uni etishtirish qimmat va bo'shliqni 2 ga mutanosib ravishda sarflaydih - n chuqurlik daraxti uchun h bilan n tugunlar.

Ushbu saqlash usuli ko'pincha ishlatiladi ikkilik uyumlar.

Massivda saqlangan kichik to'liq binar daraxt