Muhammad al-Xorazmiy Nomidagi Toshkent Axborot Texnologiyalari Universititeti

Grafika nazariyasi tushunchalaridan foydalanish

Ikkilik daraxt ildiz daraxti bo'lib, u ham tartibli daraxtdir (shuningdek, platan deb ataladi), unda har bir tugunning ikki farzandidan ko'p bo'lmagan bolalari bor. Ildizli daraxt tabiiy ravishda darajadagi kontseptsiyani (ildizdan masofa) uzatadi, shuning uchun har bir tugun uchun bolaning elementlari tushunchasi u bilan bog'liq bo'lgan tugunlar sifatida quyidagi darajaga qarab belgilanishi mumkin. Ushbu bolalarni tartibga solish (masalan, ularni tekislikda chizish orqali) chap bolani o'ng boladan ajratishga imkon beradi. Biroq, bu tugunni chap tomonda emas, balki o'ng qo'li bilan tugunni o'ng qo'li bilan emas, balki chap bolasiz farq qilmaydi.

(V, E1 E E2) ildiz daraxti (arboresansga teng) va E1 E E2 bo'sh bo'lgan,shuningdek,barcha j {{1, 2 } uchun har bir tugunda bir nechta Ej qizi mavjud emas.

Ikkilik daraxt turlari

Daraxtning terminologiyasi juda yaxshi standartlanmagan va shuning uchun adabiyotda farq qiladi.

A ildizli ikkilik daraxt ildiz tuguniga ega va har bir tugunda ikkita kichik tugun yo'q.

To'liq ikkilik daraxt

Ideal 4-darajali ikkilik daraxtga mos keladigan nasl-nasab jadvali.
A to'liq ikkilik daraxt(ba'zan o'z nomi bilan atalgan yoki platan-ikkilik daraxt)— har bir tugunning 0 yoki 2 bolalari bo'lgan daraxt. To'liq ikkilik daraxtni aniqlashning yana bir usuli-bu rekursiv ta'rif. Umumiy ikkilik daraxt:
Bir tepalik.
Ildiz tugunining ikkita podderevga ega bo'lgan daraxt, ularning ikkalasi ham to'liq ikkilik daraxtlardir.
Har bir darajadagi to'liq ikkilik daraxtda, ehtimol, oxirgi,to'liq to'ldirilgan va oxirgi darajadagi barcha tugunlar iloji boricha chap tomonda.



Tugunlar va havolalar

Yozuvlar va havolalarga ega bo'lgan tilda ignabargli daraxtlar, odatda, ba'zi ma'lumotlarni o'z ichiga olgan daraxt shaklidagi tugun tuzilishi va uning chap qizi va o'ng qizi qurilmalariga havolalar bilan quriladi. Ba'zan u o'zining noyob ota-onasiga ham murojaat qiladi. Agar tugun ikkita bola tugunidan kam bo'lsa, ba'zi bolalar ko'rsatgichlari uchun maxsus nol qiymat yoki maxsus kuzatuv birligi o'rnatilishi mumkin.

Ikkilik daraxtlarni saqlashning bu usuli xotiraning adolatli qismini sarflaydi, chunki ko'rsatgichlar yarim soatdan ortiq vaqt davomida nol (yoki soat ko'rsatkichiga ishora qiladi); taqdimot uchun ko'proq konservativ muqobil-ikkilik daraxt oqimi.

ML kabi etiketli uyushmalarga ega bo'lgan tillarda, daraxt tugunlari odatda ikkita tugun turi bilan belgilanadi, ulardan biri 3 ta ma'lumot qutisi, chap bola va o'ng bola, ikkinchisi esa "barg" tugunidir, bu ma'lumotlar va funktsiyalarga juda o'xshash tilda nol qiymatdir.