Daraxt (ma'lumotlar tarkibi) - Tree (data structure)

Umumiy va shunga o'xshash ikkilik bo'lmagan, saralanmagan, ba'zi yorliqlar takrorlangan, daraxtning o'zboshimchalik diagrammasi. Ushbu diagrammada 7 deb nomlangan tugunda 2, 10 va 6 deb nomlangan uchta bola bor, va bitta ota-ona, 2 deb belgilangan. Ildiz tugunining yuqori qismida ota-ona yo'q.

Yilda Kompyuter fanlari, a daraxt keng tarqalgan mavhum ma'lumotlar turi bu ierarxikani taqlid qiladi daraxt tuzilishi, a bilan qiymati bo'lgan bolalarning pastki daraxtlari va pastki daraxtlari bilan ota tugun, bog'langan to'plam sifatida ifodalanadi tugunlar.

Daraxt ma'lumotlari tuzilishini aniqlash mumkin rekursiv tugunlar to'plami sifatida (ildiz tugunidan boshlab), bu erda har bir tugun qiymatdan iborat ma'lumotlar tuzilmasi va tugunlarga havolalar ro'yxati ("bolalar") bilan birga, hech qanday ma'lumot takrorlanmaydigan cheklovlar bilan va hech kim ildizga ishora qilmaydi.

Shu bilan bir qatorda, daraxtni mavhum ravishda (butun dunyo bo'ylab) an sifatida belgilash mumkin buyurtma qilingan daraxt, har bir tugunga berilgan qiymat bilan. Ushbu ikkala nuqtai nazar ham foydalidir: daraxtni matematik jihatdan bir butun sifatida tahlil qilish mumkin bo'lsa-da, aslida ma'lumotlar strukturasi sifatida ifodalanganida, u odatda tugunlar bilan ajralib turadi (tugunlar to'plami va o'rniga emas) qo'shni ro'yxat tugunlar orasidagi qirralarning, chunki u digraf, masalan; misol uchun). Masalan, daraxtga umuman nazar tashlab, berilgan tugunning "ota tuguni" haqida gapirish mumkin, lekin umuman olganda ma'lumotlar tuzilishi sifatida berilgan tugun faqat o'z farzandlarining ro'yxatini o'z ichiga oladi, ammo havolani o'z ichiga olmaydi uning ota-onasi (agar mavjud bo'lsa).

Umumiy foydalanish

• Vakil ierarxik kabi ma'lumotlar:
  • Abstrakt sintaksis daraxtlari kompyuter tillari uchun
  • Daraxtlarni tahlil qilish inson tillari uchun
  • Hujjat ob'ekti modellari ning XML va HTML hujjatlar
  • JSON va YAML ishlov berilayotgan hujjatlar
• Daraxtlarni qidirish ma'lumotlarni samaradorligini oshiradigan tarzda saqlang qidirish algoritmi orqali mumkin daraxtlarni kesib o'tish
  • A ikkilik qidiruv daraxti ning bir turi ikkilik daraxt
• Vakil saralangan ro'yxatlar ma'lumotlar
• Uchun ish oqimi sifatida kompozitsion uchun raqamli rasmlar vizual effektlar^{[iqtibos kerak ]}
• Saqlash Barns-Hut galaktikalarni simulyatsiya qilish uchun ishlatiladigan daraxtlar

Terminologiya

A tugun qiymat yoki shartni o'z ichiga oladigan yoki alohida ma'lumotlar tuzilishini ifodalaydigan (bu o'z daraxti bo'lishi mumkin) strukturadir. Daraxtdagi har bir tugun nolga yoki undan ko'pga ega bolalar tugunlaridaraxtdan pastda joylashgan (odat bo'yicha daraxtlar pastga qarab o'sadi). Farzandga ega bo'lgan tugun bola deb ataladi ota tugun (yoki ustun ). Tugun eng ko'p bitta ota-onaga ega, lekin ehtimol ko'p ajdod tugunlari, masalan, ota-onaning ota-onasi. Xuddi shu ota-onaga ega bo'lgan bolalar tugunlari aka-uka tugunlari.

An ichki tugun (shuningdek, ichki tugun, inode qisqasi yoki filial tuguni) - bu tugunlarga ega bo'lgan daraxtning har qanday tugunidir. Xuddi shunday, bir tashqi tugun (shuningdek, tashqi tugun, barg tuguni, yoki terminal tuguni) bola tugunlari bo'lmagan har qanday tugun.

Daraxtning eng yuqori tugunchasi deyiladi ildiz tuguni. Ta'rifga qarab, daraxtdan ildiz tuguni bo'lishi talab qilinishi mumkin (bu holda barcha daraxtlar bo'sh emas) yoki bo'sh bo'lishiga ruxsat berilishi mumkin, bu holda uning ildiz tuguni bo'lishi shart emas. Eng yuqori tugun bo'lib, ildiz tugunida ota-ona bo'lmaydi. Bu daraxtda algoritmlar boshlanadigan tugun, chunki ma'lumotlar tuzilishi sifatida faqat ota-onadan bolalarga o'tish mumkin. E'tibor bering, ba'zi algoritmlar (masalan, buyurtma bo'yicha chuqurlik-birinchi izlash) ildizdan boshlanadi, lekin avval barg tugunlariga tashrif buyuring (barg tugunlari qiymatiga kiring), faqat ildizga oxirgi marta tashrif buyuring (ya'ni, ular avval ildiz bolalariga kirishadi) , lekin faqat ildizning qiymatiga so'nggi kiring). Boshqa barcha tugunlarga quyidagi orqali erishish mumkin qirralar yoki havolalar. (Rasmiy ta'rifda har bir bunday yo'l ham o'ziga xosdir.) Diagrammalarda ildiz tuguni an'anaviy ravishda yuqori qismida chizilgan. Kabi ba'zi daraxtlarda uyumlar, ildiz tuguni maxsus xususiyatlarga ega. Daraxtdagi har bir tugunni shu tugunda joylashgan subtree ildiz tuguni sifatida ko'rish mumkin.

The balandlik tugunning uzunligi - bu tugundan bargga boradigan eng uzun pastga tushadigan yo'lning uzunligi. Ildizning balandligi daraxtning balandligi. The chuqurlik tugunning bu uning ildiziga (ya'ni, uning) yo'lining uzunligi ildiz yo'li). Bu odatda o'z-o'zini muvozanatlashtiradigan turli xil daraxtlarni manipulyatsiya qilishda kerak bo'ladi, AVL daraxtlari jumladan. Ildiz tugunining chuqurligi nolga, barg tugunlarining balandligi nolga, faqat bitta tugunli daraxt (shu sababli ham ildiz, ham barg) daraxtning chuqurligi va balandligi nolga teng. An'anaviy ravishda bo'sh daraxt (agar shunday ruxsat berilsa, tugunlari bo'lmagan daraxt) balandligi −1 ga teng.

A kichik daraxt daraxt T tugunidan tashkil topgan daraxtdir T va uning barcha avlodlari T.^[a][1] Shunday qilib tugunlar pastki daraxtlarga to'g'ri keladi (har bir tugun o'zi va uning barcha avlodlari subtreega mos keladi) - ildiz tuguniga mos keladigan daraxt butun daraxt bo'lib, har bir tugun o'zi belgilagan kichik daraxtning ildiz tugunidir; har qanday boshqa tugunga mos keladigan subtree a deb nomlanadi tegishli daraxt (a o'xshashligi bilan to'g'ri to'plam ).

Daraxtlar bilan ishlatiladigan boshqa atamalar:

Qo'shni

Ota-ona yoki bola.

Ajdod

Farzanddan ota-onaga takroriy o'tish orqali erishish mumkin bo'lgan tugun.

Avlod

Ota-onadan bolaga takroriy takrorlash orqali erishish mumkin bo'lgan tugun. Shuningdek, nomi bilan tanilgan kichik bola.

Filial tuguni

Ichki tugun

Hech bo'lmaganda bitta bolali tugun.

Darajasi

Berilgan tugun uchun uning bolalar soni. Barg, albatta, nol darajaga teng. Daraxtning darajasi uning ildiz darajasidir.

Daraxt darajasi

Ildiz darajasi.

Masofa

Ikki tugun orasidagi eng qisqa yo'l bo'ylab qirralarning soni.

Daraja

1 + tugun va ildiz orasidagi qirralarning soni, ya'ni (chuqurlik + 1)^{[shubhali – muhokama qilish]}

Kengligi

Darajadagi tugunlar soni.

Kenglik

Barglarning soni.

O'rmon

To'plam n ≥ 0 ta daraxt.

Buyurtma qilingan daraxt

Har bir tepalikning bolalari uchun buyurtma ko'rsatiladigan ildiz otgan daraxt.

Daraxtning kattaligi

Daraxtdagi tugunlar soni.

Dastlabki ta'rif

Daraxt emas: ikkita bo'lmaganulangan qismlar, A → B va C → D → E. Bir nechta ildiz bor.

Daraxt emas: yo'naltirilmagan tsikl 1-2-4-3. 4-da bir nechta ota-ona bor (kirish chekkasi).

Daraxt emas: B → C → E → D → B tsikli. B bir nechta ota-onaga ega (kiruvchi chekka).

Daraxt emas: tsikl A → A. A ildiz, lekin uning ota-onasi ham bor.

Har bir chiziqli ro'yxat ahamiyatsiz daraxt

Daraxt - bu chiziqli ma'lumotlar tuzilmasi bo'lgan massivlar, bog'langan ro'yxatlar, to'plamlar va navbatlarga nisbatan chiziqli ma'lumotlar tuzilishi. Daraxt hech qanday tugunsiz bo'sh bo'lishi mumkin yoki daraxt - bu ildiz va nol yoki bitta yoki bir nechta pastki daraxt deb nomlangan bitta tugundan iborat tuzilish.

Daraxtlarni chizish

Daraxtlar ko'pincha samolyotda chiziladi. Buyurtma qilingan daraxtlar samolyotda asosan noyob tarzda ifodalanishi mumkin va shuning uchun ular shunday nomlanadi chinorlar, quyidagicha: agar kimdir odatdagi tartibni (masalan, soat sohasi farqli o'laroq) tuzatsa va bola tugunlarini shu tartibda joylashtirsa (birinchi kiruvchi ota-ona chekkasi, keyin birinchi bola qirrasi va boshqalar), bu daraxtning tekislikda joylashishini keltirib chiqaradi. qadar atrof-muhit izotopiyasi. Aksincha, bunday joylashish bola tugunlarining tartibini belgilaydi.

Agar kimdir ildizni tepada joylashtirsa (ota-onalar bolalar kabi, a nasl-nasab shajarasi ) va ildizdan ma'lum masofada joylashgan barcha tugunlarni (qirralarning soni bo'yicha: daraxtning "darajasi") berilgan gorizontal chiziqqa joylashtiradi, biri daraxtning standart rasmini oladi. Ikkilik daraxtni hisobga olgan holda, birinchi bola chapda ("chap tugun"), ikkinchi bola esa o'ngda ("o'ng tugun").

Umumiy operatsiyalar

• Barcha elementlarni sanab o'tish
• Daraxtning bir qismini sanab o'tish
• Element qidirilmoqda
• Daraxtda ma'lum bir joyga yangi element qo'shish
• Element o'chirilmoqda
• Azizillo: Daraxtning butun qismini olib tashlash
• Payvandlash: Daraxtga butun bo'limni qo'shish
• Har qanday tugunning ildizini topish
• Topish eng past umumiy ajdod ikkita tugunning

Traversal va qidirish usullari

Ota-onalar va bolalar o'rtasidagi aloqalar yordamida daraxt buyumlari bo'ylab qadam bosish deyiladi daraxtda yurishva harakat a yurish daraxtning. Ko'pincha, ko'rsatgich ma'lum bir tugunga kelganida operatsiya bajarilishi mumkin. Har bir ota-ona tuguni o'z farzandlaridan oldin o'tadigan yurish a deb ataladi oldindan buyurtma yurish; o'z ota-onalari bosib o'tmasdan oldin bolalar o'tadigan yurish a keyingi buyurtma yurish; tugunning chap pastki daraxti, so'ngra tugunning o'zi va nihoyat uning o'ng pastki daraxtini kesib o'tadigan yurish tartibda; ... uchun o'tish. (Chap subtree va o'ng subtree, aniq ikkita kichik daraxtga ishora qiluvchi ushbu so'nggi senariy, xususan, ikkilik daraxt.) A darajadagi tartib samarali yurish a kenglik bo'yicha birinchi qidiruv butun daraxt bo'ylab; tugunlar darajadan o'tib ketadi, bu erda avval ildiz tuguniga tashrif buyuriladi, so'ngra uning to'g'ridan-to'g'ri farzand tugunlari va ularning aka-ukalari, so'ngra nabirasi tugunlari va ularning aka-ukalari va boshqalar daraxtning barcha tugunlari o'tib ketguncha.

Vakolatxonalar

Daraxtlarni aks ettirishning turli xil usullari mavjud; umumiy vakolatxonalar tugunlarni quyidagicha ifodalaydi dinamik ravishda ajratilgan o'z farzandlariga, ularning ota-onalariga yoki ikkalasiga ko'rsatgichli yozuvlar yoki an qator, ular orasidagi munosabatlar qatordagi pozitsiyalari bilan belgilanadi (masalan, ikkilik uyum ).

Darhaqiqat, ikkilik daraxt ro'yxatlarning ro'yxati (qiymatlar ro'yxat bo'lgan ro'yxat) sifatida amalga oshirilishi mumkin: ro'yxatning boshi (birinchi davrning qiymati) chap bola (kichik daraxt), dumi (ro'yxat) ikkinchi va keyingi atamalar) - to'g'ri bola (kichik daraxt). Buni Lispda bo'lgani kabi qiymatlarga ruxsat berish uchun o'zgartirish mumkin S-iboralar, bu erda bosh (birinchi davrning qiymati) tugunning qiymati, quyruqning boshi (ikkinchi davrning qiymati) chap bola, va quyruqning dumi (uchinchi va keyingi atamalar ro'yxati) o'ng bola.

Umuman olganda, daraxtdagi tugun ota-onalariga ko'rsatgichlarga ega bo'lmaydi, ammo bu ma'lumotlar kiritilishi mumkin (ma'lumotlar tarkibini kengaytirish, shuningdek, ota-onaga ko'rsatgichni kiritish) yoki alohida saqlanishi mumkin. Shu bilan bir qatorda, yuqoriga yo'naltirilgan havolalar, masalan, a kabi bolalar tugunlari ma'lumotlariga kiritilishi mumkin ipli ikkilik daraxt.

Umumlashtirish

Digraflar

Agar chekkalar (bolalar tugunlari uchun) mos yozuvlar deb hisoblansa, u holda daraxt digrafning alohida hodisasidir va daraxt ma'lumotlari tuzilishini ifodalash uchun umumlashtirish mumkin yo'naltirilgan grafikalar tugun ko'pi bilan bitta ota-onaga ega bo'lishi mumkin bo'lgan va hech qanday tsikllarga yo'l qo'yilmasligi mumkin bo'lgan cheklovlarni olib tashlash orqali. Edgelar hali ham mavhum ravishda tugun juftligi sifatida qaraladi, ammo shartlar ota-ona va bola odatda turli xil atamalar bilan almashtiriladi (masalan, manba va nishon). Turli xil amalga oshirish strategiyalari mavjud: "bolalar ro'yxati" havolalar ro'yxati yoki butun dunyo bo'ylab ushbu kabi tuzilmalar tomonidan qabul qilingan bo'lsa, digraf daraxt bilan bir xil mahalliy ma'lumotlar tuzilishi (qiymati va tugmasi bolalar ro'yxati) bilan ifodalanishi mumkin. qo'shni ro'yxatlar.

Yilda grafik nazariyasi, a daraxt bog'langan asiklikdir grafik; agar boshqacha ko'rsatilmagan bo'lsa, grafik nazariyasida daraxtlar va grafikalar yo'naltirilmagan deb hisoblanadi. Ma'lumotlar tarkibi kabi daraxtlar va daraxtlar o'rtasida birma-bir yozishmalar mavjud emas. Biz o'zboshimchalik bilan yo'naltirilmagan daraxtni olishimiz mumkin, o'zboshimchalik bilan ulardan birini tanlashimiz mumkin tepaliklar sifatida ildiz, uning barcha qirralarini ularni ildiz tugunidan uzoqlashtiradigan qilib hosil qiling daraxtzorlik - va barcha tugunlarga buyurtma berish. Natijada daraxt ma'lumotlari tuzilishiga mos keladi. Boshqa ildizni yoki boshqa tartibni tanlash boshqasini hosil qiladi.

Daraxtdagi tugunni hisobga olgan holda, uning bolalari buyurtma qilingan o'rmonni belgilaydilar (barcha bolalar tomonidan berilgan daraxtlarning birlashishi yoki teng ravishda tugunning o'zi bergan daraxtni olib, ildizni yo'q qilish). Subkretlar rekursiya uchun tabiiy bo'lgani kabi (chuqurlikdagi qidiruvda bo'lgani kabi), o'rmonlar uchun ham tabiiydir kelishuv (kenglik bo'yicha birinchi qidiruvda bo'lgani kabi).

Via orqali o'zaro rekursiya, o'rmon daraxtlar ro'yxati sifatida aniqlanishi mumkin (ildiz tugunlari bilan ifodalanadi), bu erda tugun (daraxt) qiymat va o'rmon (uning farzandlari) dan iborat:

f: [n [1], ..., n [k]] n: v f

Ma'lumotlarning tuzilishiga nisbatan ma'lumotlar turi

Ma'lumotlarning mavhum turi va aniq ma'lumot strukturasi sifatida daraxt o'rtasida farq mavjud, masalan, ro'yxat va a bog'langan ro'yxat.

Ma'lumot turi sifatida daraxtning qiymati va bolalari bor, bolalar esa o'zlari daraxt; daraxtning qiymati va bolalari ildiz tuguni va ildiz tuguni bolalarining pastki daraxtlari qiymati sifatida talqin etiladi. Sonli daraxtlarga ruxsat berish uchun bolalar ro'yxati bo'sh bo'lishiga ruxsat berish kerak (bu holda daraxtlar bo'sh bo'lmasligi kerak, "bo'sh daraxt" o'rniga nol daraxtlar o'rmoni ko'rsatilishi kerak) yoki daraxtlarga ruxsat berish kerak. bo'sh bo'ling, bu holda bolalar ro'yxati aniq o'lchamda bo'lishi mumkin (dallanma omili Agar kerak bo'lsa, ayniqsa 2 yoki "ikkilik").

Ma'lumotlar tarkibi sifatida bog'langan daraxt - bu guruh tugunlar, bu erda har bir tugunning qiymati va ro'yxati mavjud ma'lumotnomalar boshqa tugunlarga (uning farzandlariga). Ikkala "pastga" yo'naltirilgan bir xil tugunga ishora qilmaslik talabi ham mavjud. Amalda, daraxtdagi tugunlar odatda boshqa ma'lumotlarni ham o'z ichiga oladi, masalan keyingi / oldingi ma'lumotnomalar, ularning ota tugunlariga havolalar yoki deyarli hamma narsa.

Foydalanish tufayli ma'lumotnomalar bog'langan daraxt ma'lumotlari tarkibidagi daraxtlarga, daraxtlar ko'pincha ularni ildiz tuguniga havolalar bilan ifodalanadi deb taxmin qilish bilan bevosita muhokama qilinadi, chunki ular aslida qanday amalga oshiriladi. Masalan, bo'sh daraxt o'rniga, bitta nol ma'lumot bo'lishi mumkin: daraxt har doim bo'sh bo'lmaydi, lekin daraxtga havola nol bo'lishi mumkin.

Rekursiv

Rekursiv ravishda, ma'lumotlar turi sifatida daraxt qiymat (ba'zi ma'lumotlar turlarining, ehtimol bo'sh), daraxtlar ro'yxati bilan (ehtimol bo'sh ro'yxat), uning farzandlari subtitrlari bilan belgilanadi; ramziy ma'noda:

t: v [t [1], ..., t [k]]

(Daraxt t qiymatdan iborat v va boshqa daraxtlarning ro'yxati.)

Keyinchalik oqlangan, orqali o'zaro rekursiya, bu daraxt eng oddiy misollardan biri bo'lgan daraxtni o'rmon (daraxtlar ro'yxati) bo'yicha aniqlash mumkin, bu erda daraxt qiymat va o'rmondan (uning bolalarining subtree) iborat:

f: [t [1], ..., t [k]]

t: v f

E'tibor bering, ushbu ta'rif qadriyatlar nuqtai nazaridan va ichida mos keladi funktsional tillar (u taxmin qiladi ma'lumotlarning shaffofligi ); turli xil daraxtlar hech qanday aloqaga ega emas, chunki ular shunchaki qadriyatlar ro'yxati.

Ma'lumotlar tarkibi sifatida daraxt boshqa tugunlarga havolalar ro'yxati bilan bir qatorda (ba'zi ma'lumotlar turlarida, ehtimol bo'sh) qiymatdan iborat bo'lgan tugun (ildiz) sifatida tavsiflanadi (ro'yxat bo'sh bo'lishi mumkin, mos yozuvlar ehtimol null) ); ramziy ma'noda:

n: v [& n [1], ..., & n [k]]

(Tugun n qiymatdan iborat v va boshqa tugunlarga havolalar ro'yxati.)

Ushbu ma'lumotlar tuzilishi yo'naltirilgan grafikani belgilaydi,^[b] va u daraxt bo'lishi uchun uning global tuzilishiga (topologiyasiga) shart qo'shish kerak, ya'ni ko'pi bilan bitta ma'lumot har qanday tugunga ishora qilishi mumkin (tugun ko'pi bilan bitta ota-onaga ega) va daraxtda tugun yo'q ildizga ishora qiling. Aslida, har bir tugunda (ildizdan tashqari) to'liq bitta ota-ona bo'lishi kerak, va ildizda ota-ona bo'lmasligi kerak.

Darhaqiqat, tugunlar ro'yxati berilgan va har bir tugun uchun o'z farzandlariga havolalar ro'yxati berilgan bo'lsa, uning tuzilishi daraxtmi yoki yo'qmi, uning global tuzilishini tahlil qilmasdan va aslida quyida ta'riflanganidek, topologik jihatdan daraxt ekanligini bilib bo'lmaydi.

Turlar nazariyasi

Sifatida mavhum ma'lumotlar turi, mavhum daraxt turi T ba'zi bir turdagi qiymatlar bilan E mavhum o'rmon turidan foydalangan holda aniqlanadi F (daraxtlar ro'yxati), funktsiyalari bo'yicha:

qiymati: T → E

bolalar: T → F

nol: () → F

tugun: E × F → T

aksiomalar bilan:

qiymat (tugun (e, f)) = e

bolalar (tugun (e, f)) = f

Xususida tip nazariyasi, daraxt - bu induktiv tip konstruktorlar tomonidan belgilanadi nol (bo'sh o'rmon) va tugun (berilgan qiymatga ega ildiz tugunli daraxt va bolalar).

Matematik terminologiya

Bir butun sifatida ko'rib chiqilgan, daraxt ma'lumotlarining tuzilishi buyurtma qilingan daraxt, odatda har bir tugunga biriktirilgan qiymatlar bilan. Aniq qilib aytganda, u (agar kerak bo'lsa):

• A ildiz otgan daraxt "ildizdan uzoqlashish" yo'nalishi bilan (torroq atama "daraxtzorlik "), ma'nosi:
  • A yo'naltirilgan grafik,
  • kimning asosida yotadi yo'naltirilmagan grafik a daraxt (har qanday ikkita tepalik bitta oddiy yo'l bilan bog'langan),
  • taniqli ildiz bilan (bitta tepalik ildiz sifatida belgilanadi),
  • qirralarning yo'nalishini belgilaydigan (strelkalar ildizdan uzoqlashadi; chekka berilgan bo'lsa, chekka ko'rsatadigan tugun deyiladi ota-ona va chekka ko'rsatadigan tugun deyiladi bola),

bilan birga:

• berilgan tugunning bolalar tugunlariga buyurtma berish va
• har bir tugunda qiymat (ba'zi ma'lumotlar turlarining).

Ko'pincha daraxtlar sobit (aniqroq, chegaralangan) dallanma omili (ustunlik ), ayniqsa har doim ikkita bola tuguniga ega bo'lishi mumkin (ehtimol bo'sh, shuning uchun) ko'pi bilan ikkitasi bo'sh emas bolalar tugunlari), shuning uchun "ikkilik daraxt".

Bo'sh daraxtlarga ruxsat berish ba'zi bir ta'riflarni soddalashtiradi, ba'zilarini esa ancha murakkablashtiradi: ildiz otgan daraxt bo'sh bo'lmasligi kerak, shuning uchun agar bo'sh daraxtlarga ruxsat berilsa, yuqoridagi ta'rif o'rniga "bo'sh daraxt yoki shunday daraxt ..." bo'ladi. Boshqa tomondan, bo'sh daraxtlar sobit dallanish omilini aniqlashni soddalashtiradi: bo'sh daraxtlarga ruxsat berilgan holda, ikkitomonlama daraxt har bir tugunda to'liq ikkita bolaga ega bo'lgan daraxt bo'lib, ularning har biri daraxt (ehtimol bo'sh) bo'lishi mumkin. Daraxtdagi barcha operatsiyalar to'plami vilkalar bilan ishlashni o'z ichiga olishi kerak.

Matematik ta'rif

Ushbu bo'lim faqat ma'lum bir auditoriyani qiziqtirishi mumkin bo'lgan juda ko'p miqdordagi murakkab tafsilotlarni o'z ichiga olishi mumkin. Iltimos, yordam bering aylanmoq yoki boshqa joyga ko'chirish tegishli har qanday ma'lumot va qarshi bo'lishi mumkin bo'lgan ortiqcha tafsilotlarni olib tashlash Vikipediyaning qo'shilish siyosati. (Avgust 2020) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Tartibsiz daraxt

Matematik jihatdan tartibsiz daraxt^[2] (yoki "algebraik daraxt")^[3] sifatida belgilanishi mumkin algebraik tuzilish (X, ota-ona) qayerda X ning bo'sh bo'lmagan tashuvchisi to'plamidir tugunlar va ota-ona funktsiya yoqilgan X har bir tugunni tayinlaydigan x uning "ota-ona" tuguni, ota-ona (x). Tuzilishi har bir bo'sh bo'lmagan shartga bo'ysunadi subalgebra bir xil bo'lishi kerak sobit nuqta. Ya'ni, noyob "ildiz" tuguni bo'lishi kerak r, shu kabi ota-ona (r) = r va har bir tugun uchun x, ba'zi bir takroriy dastur ota-ona (ota-ona (⋯ ota-ona (x)⋯)) teng r.

Bir nechta teng ta'riflar mavjud.

Eng yaqin alternativa sifatida tartibsiz daraxtlarni quyidagicha aniqlash mumkin qisman algebralar (X, ota-ona) Yuqorida tavsiflangan jami algebralardan ruxsat berish orqali olinadi ota-ona (r) aniqlanmagan. Bu ildiz r - bu yagona tugun ota-ona funktsiyasi aniqlanmagan va har bir tugun uchun x, ildiz erishish mumkin dan x ichida yo'naltirilgan grafik (X, ota-ona). Ushbu ta'rif aslida an ta'rifiga to'g'ri keladi daraxtzorlarga qarshi kurash. The TAoCP kitob bu atamani ishlatadi yo'naltirilgan daraxt.^[4]

O'ng tomondagi katakda qisman algebra tasvirlangan (X, ota-ona) kabi munosabat tuzilishi (X, ≺). Agar (1) bilan almashtirilsa

u holda (2) shart ortiqcha bo'ladi.

Ushbu ta'rifdan foydalanib, ro'yxatdagi shartlarning alohida pastki qismlariga mos keladigan tartibsiz daraxtlarni umumlashtirish uchun maxsus terminologiya taqdim etilishi mumkin:

• (1,2,3) – pseudotree yo'naltirilgan,
• (3) – pseudoforest yo'naltirilgan,
• (3,4) - tartibsiz o'rmon (uning tarkibiy qismlari tartibsiz daraxtlar),
• (4) – yo'naltirilgan asiklik grafik, deb taxmin qildi X cheklangan,
• (1 ', 4) - asiklik kirish mumkin bo'lgan grafika (u holda (2) shart bilvosita bajariladi).

Tartibsiz daraxtning yana bir teng ta'rifi a nazariy daraxt bu yakka asosda va balandligi eng ko'p bo'lgan ω ("chekli-ish" daraxti).^[5] Ya'ni, algebraik tuzilmalar (X, ota-ona) ga teng qisman buyurtmalar (X, ≤) bor yuqori element r va uning har bir direktori xafa (aka asosiy filtr ) cheklangan zanjir. Aniqroq qilib aytganda teskari to'siq-nazariy daraxti, chunki to'siq-nazariy ta'rifi odatda qarama-qarshi tartibni qo'llaydi.

Orasidagi yozishmalar (X, ota-ona) va (X, ≤) reflektiv orqali o'rnatiladi o'tish davri yopilishi / kamaytirish, qisqartirish natijasida "qisman" versiyasi ildiz tsiklisiz paydo bo'ladi.

Ning ta'rifi tavsiflovchi to'plam nazariyasidagi daraxtlar (DST) qisman buyurtmalarning vakolatxonasidan foydalanadi (X, ≥) kabi prefiks cheklangan ketma-ketliklar orasidagi buyurtmalar. Bu qadar chiqadi izomorfizm, DST daraxtlari (teskari) va shu paytgacha aniqlangan daraxt tuzilmalari o'rtasida birma-bir yozishma mavjud.

Sifatida to'rtta ekvivalent xarakteristikaga murojaat qilishimiz mumkin algebra sifatida daraxt, qisman algebra sifatida daraxt, qisman buyurtma sifatida daraxtva prefiks tartibida daraxt. Bunda beshinchi teng ta'rif mavjud - a graf-nazariy ildiz otgan daraxt bu faqat bog'langan asiklikdir ildizli grafik.

Daraxtlarning (qisman) algebralar sifatida ifodalanishi (shuningdek, deyiladi) funktsional grafikalar ) (X, ota-ona) yordamida to'g'ridan-to'g'ri daraxt tuzilmalarini amalga oshirishni ta'qib qiladi ota-ko'rsatkichlar. Odatda, qisman versiya ishlatiladi, unda ildiz tugunida ota-ona aniqlanmagan. Biroq, ba'zi dasturlarda yoki modellarda hatto ota-ona (r) = r doiraviylik o'rnatildi. Taniqli misollar:

• Linux VFS bu erda "Ildiz protezida o'ziga ishora qiluvchi d_parent mavjud".^[6].
• An tushunchasi ibrat daraxti^[7][8][9]

dan ob'ektga yo'naltirilgan dasturlash. Bunday holda, ildiz tuguni yuqoridir metaklass - faqat sinf bu o'z-o'zidan to'g'ridan-to'g'ri misol.

Yuqoridagi ta'rif tan olinganligini unutmang cheksiz daraxtlar. Bu orqali ba'zi bir ilovalar tomonidan qo'llab-quvvatlanadigan cheksiz tuzilmalarni tavsiflashga imkon beradi dangasa baho. Ajoyib misol cheksiz regress ning elektron sinflar dan Yoqut ob'ekt modeli.^[10] Ushbu modelda daraxt orqali o'rnatildi superklass terminal bo'lmagan ob'ektlar orasidagi bog'lanishlar cheksiz va cheksiz filialga ega ("spiral" ob'ektlarning bitta cheksiz filiali - qarang diagramma ).

Birodarlar to'plamlari

Har bir tartibsiz daraxtda (X, ota-ona) taniqli bor bo'lim to'plamning X tugunlari birodarlar to'plamlari. Ildiz bo'lmagan ikkita tugun x, y agar bir xil birodarlarga tegishli bo'lsa ota-ona (x) = ota-ona (y). Ildiz tuguni r hosil qiladi singleton birodarlar to'plami {r}.^[c] Daraxt deb aytilgan mahalliy cheklangan yoki nihoyatda dallanadigan agar uning birodarlarining har biri cheklangan bo'lsa.

Har bir alohida birodarlarning juftligi beqiyos yilda ≤. Shuning uchun bu so'z tartibsiz ta'rifida ishlatiladi. Bunday terminologiya barcha birodarlarning to'plamlari singleton bo'lganida, ya'ni to'plam bo'lganda yanglishishi mumkin X barcha tugunlar butunlay buyurtma qilingan (va shunday qilib yaxshi buyurtma qilingan ) tomonidan ≤ Bunday holatda biz a haqida gapirishimiz mumkin yakka tarvaqaylab ketgan daraxt o'rniga.

O'rnatilgan inklyuziya yordamida

Har bir qisman buyurtma qilingan daraxt daraxtlari kabi (X, ≤) bilan ifodalanishi mumkin qo'shilish tartibi - tomonidan o'rnatilgan tizimlar unda ≤ bilan tasodifiy ⊆, induktsiya qilingan qo'shilish buyurtma. Tuzilmani ko'rib chiqing (U, ℱ) shu kabi U bo'sh bo'lmagan to'plam va ℱ ning pastki to'plamlari to'plamidir U shunday qilib, quyidagilar qoniqtiriladi (tomonidan Ichki to'plam to'plami ta'rifi):

1. ∅ ∉ ℱ. (Anavi, (U, ℱ) a gipergraf.)
2. U ∈ ℱ.
3. Har bir kishi uchun X, Y dan ℱ, X ∩ Y ∈ {∅, X, Y}. (Anavi, ℱ a laminar oila.)^[11]
4. Har bir kishi uchun X dan ℱ, juda ko'p sonli odamlar bor Y dan ℱ shu kabi X ⊆ Y.

Keyin tuzilish (ℱ, ⊆) - ildizi teng bo'lgan tartibsiz daraxt U. Aksincha, agar (U, ≤) tartibsiz daraxt va ℱ to'plam {↓x | x ∈ U} hammasidan asosiy ideallar ning (U, ≤) keyin o'rnatilgan tizim (U, ℱ) yuqoridagi xususiyatlarni qondiradi.

Daraxtlar to'plamlarning laminali tizimi sifatida (Nusxa olingan Ichki o'rnatilgan model )

Daraxt tuzilmalarining o'rnatilgan tizim ko'rinishi standart semantik modelni taqdim etadi - eng mashhur holatlarning aksariyatida daraxt ma'lumotlari tuzilmalari vakili qamrab olish ierarxiyasi. Bu shuningdek, buyurtma yo'nalishi uchun yuqoridagi ildiz bilan asoslashni taklif qiladi: Ildiz tuguni a kattaroq boshqa har qanday tugunga qaraganda konteyner. Taniqli misollar:

• Katalog tuzilishi fayl tizimining. Katalog o'zining pastki kataloglarini o'z ichiga oladi.
• DOM daraxti. DOM tugunlariga mos keladigan hujjat qismlari daraxt tartibiga ko'ra subpart aloqada.
• Yagona meros ob'ektga yo'naltirilgan dasturlashda. Sinfning misoli, shuningdek, superklassning misoli.
• Ierarxik taksonomiya kabi Devining o'nlik tasnifi ortib borayotgan o'ziga xoslik bo'limlari bilan.
• BSP daraxtlari, to'rtburchaklar, sekizlar, R-daraxtlar va rekursiv uchun ishlatiladigan boshqa daraxt ma'lumotlari tuzilmalari kosmik qismlarni ajratish.

Daraxtlar asosli

Tartibsiz daraxt (X, ≤) bu asosli agar qat'iy qisman buyurtma bo'lsa < a asosli munosabat. Xususan, har bir cheklangan daraxt asosli. Faraz qilsak qaram tanlov aksiomasi agar u cheksiz shoxsiz bo'lsa va faqat daraxt yaxshi asosga ega.

Yaxshi asoslangan daraxtlar bo'lishi mumkin rekursiv ravishda aniqlanadi - kichik daraxtlarning bo'linmagan birlashmasidan daraxtlar hosil qilish orqali. Aniq ta'rif uchun, deylik X tugunlar to'plamidir. Dan foydalanish refleksivlik qisman buyurtmalar, biz har qanday daraxtni aniqlashimiz mumkin (Y, ≤) ning pastki qismida X uning qisman tartibi bilan (≤) - ning pastki qismi X × X. To'plam ℛ barcha munosabatlarning R ular asosli daraxt hosil qiladi (Y, R) kichik to'plamda Y ning X bosqichlarida aniqlanadi ℛ_men, Shuning uchun; ... uchun; ... natijasida ℛ = ⋃ {ℛ_men | men tartibli}. Har biriga tartib raqami men, ruxsat bering R ga tegishli men- bosqich ℛ_men agar va faqat agar R ga teng

⋃ℱ ∪ ((dom (⋃ℱ) ∪ {x}) × {x})

qayerda ℱ ning pastki qismi ⋃ {ℛ_k | k < men} elementlari shunday ℱ juftlik bilan ajratilgan va x tegishli bo'lmagan tugun dom (⋃ℱ). (Biz foydalanamiz dom (S) ni belgilash domen munosabatlarning S.) Eng past bosqichga e'tibor bering ℛ₀ bitta tugunli daraxtlardan iborat {(x,x) chunki faqat bo'sh ℱ mumkin. Har bir bosqichda, (ehtimol) yangi daraxtlar R o'rmon olib quriladi ⋃ℱ komponentlar bilan ℱ pastki bosqichlardan va yangi ildizni biriktirishdan x tepasida ⋃ℱ.

Daraxtdan farqli o'laroq balandlik ko'pi bilan ω, the daraja daraxtlar cheksizdir,^[12] xususiyatlarini ko'ring "ochilmoqda ".

Rekursiv juftliklardan foydalanish

Hisoblashda asosli daraxtlarni aniqlashning keng tarqalgan usuli - bu rekursiv tartiblangan juftliklar(F, x): daraxt o'rmon F "yangi" tugun bilan birgalikda x.^[13] A o'rmon F o'z navbatida tugunlarning juftlik bilan ajratilgan to'plamlari bo'lgan bo'sh daraxtlar to'plami. Aniq ta'rif uchun, qurilishidagi kabi davom eting ismlar majburlashning nazariy-texnikaviy uslubida qo'llaniladi. Ruxsat bering X tugunlarning to'plami bo'ling. In yuqori qurilish ustida X, to'plamlarni aniqlang T, ℱ navbati bilan daraxtlar va o'rmonlar va xarita tugunlar: T → ℘(X) har bir daraxtni tayinlash t uning asosiy tugunlari to'plami, shunday qilib:

(daraxtlar tugadi X)		t ∈ T	↔	t juftlik (F, x) dan ℱ × X hamma uchun shunday s ∈ F, x Odes tugunlar (s),
(o'rmonlar tugadi X)		F ∈ ℱ	↔	F ning pastki qismi T har bir kishi uchun shunday s,t ∈ F, s ≠ t, tugunlar (s∩ tugunlar (t) = ∅ }},
(daraxtlar tugunlari)		y Odes tugunlar (t)	↔	t = (F, x) ∈ T va yoki y = x yoki y Odes tugunlar (s) kimdir uchun s ∈ F }}.

Yuqoridagi sharoitlarda aylanalarni har birini tabaqalashtirish yo'li bilan yo'q qilish mumkin T, ℱ va tugunlar oldingi qismdagi kabi bosqichlarga. Keyinchalik, "subtree" munosabatini aniqlang ≤ kuni T "darhol subtree" munosabatining refleksli tranzitiv yopilishi sifatida ≺ tomonidan daraxtlar o'rtasida aniqlangan

s ≺ t

↔

s ∈ π1(t)

qayerda π₁(t) bo'ladi proektsiya ning t birinchi koordinataga; ya'ni bu o'rmon F shu kabi t = (F, x) kimdir uchun x ∈ X. Buni kuzatish mumkin (T, ≤) a ko'p daraxtli: har biri uchun t ∈ T, asosiy ideal ↓t tomonidan buyurtma qilingan ≤ qisman buyurtma sifatida asosli daraxtdir. Bundan tashqari, har bir daraxt uchun t ∈ T, uning "tugunlari" - buyurtma tuzilishi (tugunlar (t), ≤_t) tomonidan berilgan x ≤_t y agar va faqat o'rmonlar bo'lsa F, G ∈ ℱ ikkalasi ham shunday (F, x) va (G, y) ning daraxtlari t va (F, x) ≤ (G, y).

O'qlar yordamida

Yana bir rasmiylashtirish va tartibsiz daraxtlarni umumlashtirish orqali olish mumkin reming ota-bola tugunlari juftlari. Har bir shunday tartiblangan juftlikni mavhum shaxs - "o'q" deb hisoblash mumkin. Buning natijasida a multidigraf (X, A, s, t) qayerda X bu tugunlar to'plami, A ning to'plami o'qlarva s va t funktsiyalari A ga X har bir o'qni tayinlash manba va nishonnavbati bilan. Tuzilishi quyidagi shartlarga bo'ysunadi:

1. (A, s ○ t^–1) umumiy algebra kabi tartibsiz daraxtdir.
2. The t xarita a bijection strelkalar va tugunlar o'rtasida.

(1) da symbol kompozitsiya belgisi chapdan o'ngga talqin qilinishi kerak. Shartda o'qlarning teskari boshqarilishi aytilgan^[d] "boladan ota-onaga" umumiy xaritasi. Ushbu asosiy xarita o'qlar orasidagi belgilansin p, ya'ni p = s ○ t⁻¹. Keyin bizda ham bor s = p ○ t, shuning uchun (1,2) qoniqarli multidigraf ham quyidagicha aksiomatizatsiya qilinishi mumkin (X, A, p, t), ota-ona xaritasi bilan p o'rniga s aniqlovchi sifatida. Ildiz o'qi halqa ekanligiga e'tibor bering, ya'ni uning manbai va maqsadi bir-biriga to'g'ri keladi.

Maqsadli xaritaga ruxsat berish orqali yuqoridagi strukturaning muhim umumlashtirilishi o'rnatiladi t ko'p-yakka bo'lish. Bu shuni anglatadiki (2) ga zaiflashgan

(2 ') The t xarita shubhali - har bir tugun ba'zi o'qlarning maqsadidir.

Shuni yodda tutingki, (1) shart faqat bitta o'q nishonga ega bo'lishiga ruxsat berilganligini tasdiqlaydi. Ya'ni cheklash ning t uchun oralig'i ning p hali ham in'ektsion.

(1,2 ') qoniqtiradigan multidigraflarni "o'q daraxtlari" deb atash mumkin - ularning daraxt xususiyatlari tugunlarga emas, balki o'qlarga o'rnatiladi. Ushbu tuzilmalarni Linux VFS-ning eng muhim ajralmas qismi deb hisoblash mumkin, chunki ular fayl tizimlarining qattiq bog'langan tuzilishini aks ettiradi. Tugunlar deyiladi inodlar, o'qlar stomatologiya (yoki qattiq havolalar ). Ota-onalar va maqsadli xaritalar p va t bilan mos ravishda ifodalanadi d_parent va d_inode stomatologiya ma'lumotlari tarkibidagi maydonlar.^[14] Har bir inodega sobit fayl turi beriladi, ulardan katalog turi "mo'ljallangan ota-onalar" ning alohida rolini o'ynaydi:

Ildiz tsiklining birinchi yarmida chiziqli uslubdan foydalanish, ota-ona xaritasiga o'xshash tarzda, a mavjudligini ko'rsatadi qisman manba xaritasi uchun versiya s unda ildiz o'qining manbai aniqlanmagan. Ushbu variant yanada umumlashtirish uchun ishlatilgan, qarang # Multidigrafdagi yo'llardan foydalanish.

Yo'llarni digrafda ishlatish

Tartibsiz daraxtlar tabiiy ravishda "ochilish" natijasida paydo bo'ladi kirish mumkin bo'lgan grafika.^[15]

Ruxsat bering ℛ = (X, R, r) bo'lishi a aniq relyatsion tuzilish, ya'ni shunday X bu tugunlar to'plami, R tugunlar orasidagi munosabatdir (ning kichik to'plami X × X) va r taniqli "ildiz" tugunidir. Buni yana taxmin qiling ℛ bu kirish mumkin, bu shuni anglatadiki X ga teng oldindan tasvirlash ning {r} ning refleksiv o'tish davri yopilishi ostida R, va bunday tuzilmani an kirish mumkin bo'lgan grafika yoki apg Qisqacha. (⁎) Keyin yana bir apg olish mumkin ℛ '= (X', R', r') - the ochilmoqda ning ℛ - quyidagicha:

• X ' teskari yo'naltirilgan to'plamdir yo'llar ga r, ya'ni bo'sh bo'lmagan cheklangan ketma-ketliklar to'plami p tugunlari (elementlari X) shunday (a) ning ketma-ket a'zolari p teskari Rbilan bog'liq va (b) birinchi a'zosi p bu ildiz r,
• R ' dan yo'llar orasidagi bog'liqlik X ' shunday yo'llar p va q bor R '- agar va faqat shunday bo'lsa p = q ⁎ [x] ba'zi tugun uchun x (ya'ni q maksimal darajada to'g'ri keladi prefiks ning p, "ochildi " p) va
• r ' bir elementli ketma-ketlikdir [r].

Ko'rinishidan, tuzilish (X', R') "qisman algebra" versiyasidagi tartibsiz daraxt: R ' ning har bir root bo'lmagan elementi bilan bog'liq bo'lgan qisman xaritadir X' ota-onasiga yo'l ochish orqali. Ildiz elementi aniq r '. Bundan tashqari, quyidagi xususiyatlar qondiriladi:

• ℛ ochilishi uchun izomorfikdir ℛ ' agar va faqat agar ℛ daraxt (⁑). (Xususan, ochilish idempotent, izomorfizmgacha.)
• Yig'ish asoslilikni saqlaydi: Agar R keyin ham asosli R '.
• Qatlamni saqlab qolish darajasi: Agar R saflari asosli hisoblanadi R va R ' mos keladi.

Izohlar:

(⁎) o'rtasida kelishuvni o'rnatish R va ota-ona xarita, taqdim etilgan ta'rifdan foydalaniladi teskari kirish imkoniyati: r har qanday tugundan erishish mumkin. Tomonidan asl ta'rifida P. Aczel^[15], har bir tugunga erishish mumkin r (shunday qilib, "preimage" o'rniga "image" so'zi qo'llaniladi).^[e]

(⁑) Biz tartibsiz daraxtlarning ta'rifini apgs sifatida bilvosita kiritdik: apg ni chaqiring ℛ = (X, R, r) a daraxt agar qisqartirish bo'lsa (X, R) qisman algebra sifatida tartibsiz daraxtdir. Buni quyidagicha tarjima qilish mumkin: Har bir tugunga aynan bitta yo'l orqali kirish mumkin.

Multidigrafdagi yo'llardan foydalanish

Fayl tizimlarining qattiq bog'langan tuzilishi misolida ko'rsatilgandek, hisoblashda ko'plab ma'lumotlar tuzilmalari imkon beradi bir nechta tugunlar orasidagi bog'lanishlar. Shuning uchun, ma'lumotlar tuzilmalari orasida tartibsiz daraxtlarning ko'rinishini to'g'ri namoyish etish uchun kirish mumkin bo'lgan uchburchak grafikalarni umumlashtirish kerak. multidigraf sozlash. Terminologiyani soddalashtirish uchun biz ushbu atamadan foydalanamiz titroq bu "multidigraph" ning o'rnatilgan sinonimi.

Qilsin kirish mumkin uchli titroq yoki apq qisqasi tuzilma sifatida ta'riflanadi

ℳ = (X, A, s, t)

qayerda

X to'plamidir tugunlar,

A to'plamidir o'qlar,

s a qisman funktsiyasi A ga X (the manba xarita), va

t ning umumiy funktsiyasi A ga X (the nishon xarita).

Shunday qilib, ℳ bu "qisman multidigraf".

Tuzilishi quyidagi shartlarga bo'ysunadi:

1. To'liq bitta "ildiz" o'qi bor, a_r, kimning manbasi s(a_r) aniqlanmagan.
2. Har bir tugun x ∈ X ildiz o'qidan boshlangan ketma-ket o'qlarning cheklangan ketma-ketligi orqali erishish mumkin a_r.

ℳ deb aytiladi a daraxt maqsadli xarita bo'lsa t bu o'qlar va tugunlar orasidagi biektsiya ochilmoqda ning ℳ (2) da ko'rsatilgan ketma-ketliklar bilan hosil bo'ladi - ular kirish yo'llari (qarang Yo'l algebra ). Apq sifatida, ochish quyidagicha yozilishi mumkin

ℳ '= (X', A', s', t')

qayerda

X ' bu kirish yo'llari to'plami,

A ' bilan mos keladi X ',

s yo'lning paydo bo'lishiga to'g'ri keladi va

t ' identifikator yoqilgan X '.

Apgsda bo'lgani kabi, ochish ham idempotent va har doim daraxtga olib keladi.

The asosda apg tuzilishi sifatida olinadi

(X, R, t(a_r))

qayerda

R = {(t(a),s(a)) | a ∈ A {a_r‍}‍}‍.

Yuqoridagi diagrammada 1 + 14 o'qli apq-ning namunasi ko'rsatilgan. Yilda JavaScript, Python yoki Yoqut, strukturani quyidagi kod bilan yaratish mumkin (aynan bir xil):

r = {}; r[1] = {}; r[2] = r[1]; r[3] = {}; r[4] = {}; r[1][5]    = {};   r[1][14]    = r[1][5];r[3][7]    = {};   r[3][8]     = r[3][7];  r[3][13] = {};r[4][9]    = r[4]; r[4][10]    = r[4];     r[4][11] = {};r[3][7][6] = r[3]; r[3][7][12] = r[1][5];

Ismlardan foydalanish

Tartibsiz daraxtlar va ularning umumlashtirilishi mohiyatini tashkil etadi nomlash tizimlari. Nomlash tizimlarining ikkita taniqli namunalari mavjud: fayl tizimlari va (ichki) assotsiativ massivlar. Oldingi kichik bo'limlardan olingan multidigrafga asoslangan tuzilmalar noma'lum ikkala holat uchun abstraktlar. Nomlash imkoniyatlarini olish uchun o'qlar bilan jihozlangan bo'lishi kerak ismlar kabi identifikatorlar.Ism mahalliy darajada noyob bo'lishi kerak - har bir birodar o'qlar to'plamida^[f] ma'lum bir nom bilan etiketlenmiş ko'pi bilan bitta o'q bo'lishi mumkin.

Bu struktura sifatida rasmiylashtirilishi mumkin

ℰ = (X, Σ, A, s, σ, t)

qayerda

X to'plamidir tugunlar,

Σ to'plamidir ismlar,

A to'plamidir o'qlar,

s dan qisman funktsiya A ga X,

σ dan qisman funktsiya A ga Σva

t ning umumiy funktsiyasi A ga X.

Ok uchun a, uchlikning tarkibiy qismlari (s(a), σ(a), t(a)) mos ravishda a"s manba, ism va nishon. Tuzilishi quyidagi shartlarga bo'ysunadi:

1. Qisqartirish (X, A, s, t) bu kirish mumkin uchli titroq (apq) oldindan aniqlanganidek.
2. Ism funktsiyasi σ faqat manbasiz ildiz o'qi uchun aniqlanmagan.
3. Ism funktsiyasi σ har bir birodar o'qlar to'plamini cheklashda, ya'ni har qanday ildiz bo'lmagan o'qlar uchun in'ektsion hisoblanadi a, b, agar s(a) = s(b) va σ(a) = σ(b) keyin a = b.

Ushbu tuzilmani a deb atash mumkin ichki lug'at yoki nomlangan apq. Hisoblashda bunday tuzilmalar hamma joyda mavjud. Yuqoridagi jadvalda ko'rsatilishicha, o'qlarni to'plam sifatida "qayta tiklanmagan" deb hisoblash mumkin A' = {(s(a), σ (a), t(a)) | a ∈ A {a_r}} manba-ism-maqsad uch baravar. Bu relyatsion tuzilishga olib keladi (X, Σ, A') deb qarash mumkin relyatsion ma'lumotlar bazasi stol. Belgilab qo'yilgan manba va ism ko'rsatmoq asosiy kalit.

Strukturani deterministik sifatida qayta o'zgartirish mumkin belgilangan o'tish tizimi: X bu "davlatlar" to'plami, Σ "yorliqlar" to'plami, A ' bu "belgilangan o'tish" to'plamidir. (Bundan tashqari, ildiz tuguni r = t(a_r) "boshlang'ich holat" bo'lib, kirish imkoniyati sharti har bir holatga dastlabki holatdan erishish mumkinligini anglatadi.)

O'ngdagi diagrammada ichki lug'at ko'rsatilgan ℰ oldingi pastki qismdagi misol bilan bir xil asosiy multidigrafga ega. Strukturani quyidagi kod orqali yaratish mumkin. Oldingi kabi, xuddi shu kod JavaScript, Python va Ruby uchun amal qiladi.

Birinchidan, a pastki tuzilish, ℰ₀, a ning bitta topshirig'i bilan yaratiladi so'zma-so'z {...} ga r. To'liq chiziqlar bilan tasvirlangan ushbu tuzilma "o'q daraxti "(shuning uchun bu a yoyilgan daraxt ). O'z navbatida tom ma'noda a JSON ketma-ketligi ℰ₀.

Keyinchalik, qolgan o'qlar allaqachon mavjud tugunlarning tayinlanishi bilan yaratiladi. Tsikllarni keltirib chiqaradigan o'qlar ko'k rangda ko'rsatiladi.

r = {"a":{"a":5,"b":5},"c":{"a":{"w":5},"c":{}},"d":{"w":1.3}}r["b"]           = r["a"]; r["c"]["b"] = r["c"]["a"]r["c"]["a"]["p"] = r["c"]; r["d"]["e"] = r["d"]["o'zim"] = r["d"]

Linux VFS-da nom funktsiyasi σ bilan ifodalanadi d_name stomatologiya ma'lumotlari tarkibidagi maydon.^[14] The ℰ₀ yuqoridagi tuzilma JSON tomonidan namoyish etiladigan tuzilmalar va fayl tizimlarining qattiq bog'langan tuzilmalari o'rtasidagi yozishmalarni namoyish etadi. Ikkala holatda ham "tugunlar" ning o'rnatilgan turlarining to'plami mavjud bo'lib, ularning bir turi konteyner turi hisoblanadi, faqat JSON-da aslida ikkitasi mavjud turlari - Ob'ekt va massiv. Agar ikkinchisiga e'tibor berilmasa (shuningdek, individual ibtidoiy ma'lumotlar turlari orasidagi farq), unda fayl tizimlari va JSON ma'lumotlarining taqdim qilingan abstraktsiyalari bir xil - ikkalasi ham nomlash bilan jihozlangan o'q daraxtlari σ va konteyner tugunlarining farqlanishi.

Ismlar

Nomlash funktsiyasi σ ichki lug'at ℰ tabiiy ravishda o'qlardan o'q yo'llariga qadar cho'ziladi. Har bir ketma-ketlik p = [a₁, ..., a_n] ketma-ket o'qlar bilvosita belgilanadi yo'l nomi (qarang Ism ) - ketma-ketlik σ(p) = [σ(a₁), ..., σ(a_n)] o'q nomlari.^[g]Mahalliy o'ziga xoslik o'q yo'llariga o'tadi: birodarlarning turli yo'llari turli xil nomlarga ega. Xususan, ildizdan kelib chiqqan o'q yo'llari ularning yo'l nomlari bilan bittadan yozishmalarda. Ushbu yozishmalar "ramziy" ko'rinishni taqdim etadi ℰ yo'l nomlari orqali - tugunlar ℰ dunyo bo'ylab yo'l nomlari daraxti orqali aniqlanadi.

Buyurtma qilingan daraxt

The structures introduced in the previous subsection form just the core "hierarchical" part of tree data structures that appear in computing. In most cases, there is also an additional "horizontal" ordering between siblings. Yilda daraxtlarni qidirish the order is commonly established by the "key" or value associated with each sibling, but in many trees that is not the case. For example, XML documents, lists within JSON files, and many other structures have order that does not depend on the values in the nodes, but is itself data — sorting the paragraphs of a novel alphabetically would lose information.^{[shubhali – muhokama qilish]}

Muxbir kengayish of the previously described tree structures (X, ≤) can be defined by endowing each sibling set with a linear order as follows.^[17][18]

An alternative definition according to Kuboyama^[2] is presented in the next subsection.

An buyurtma qilingan daraxt bu struktura (X, ≤_V, ≤_S) qayerda X is a non-empty set of nodes and ≤_V va ≤_S are relations on X deb nomlangan vertical (or also ierarxik^[2]) order and sibling order, respectively. The structure is subject to the following conditions:

1. (X, ≤_V) is a partial order that is an unordered tree as defined in the previous subsection.
2. (X, ≤_S) is a partial order.
3. Distinct nodes are comparable in <_S if and only if they are siblings:

   (<_S) ∪ (>_S) = ((≺_V) ○ (≻_V)) ∖ id_X.

4. Every node has only finitely many preceding siblings, i.e. every principal ideal of (X, ≤_S) cheklangan. (This condition can be omitted in the case of finite trees.)

Conditions (2) and (3) say that (X, ≤_S) is a component-wise linear order, each component being a sibling set. Condition (4) asserts that if a sibling set S is infinite then (S, ≤_S) izomorfik (ℕ, ≤), the usual ordering of natural numbers.

Given this, there are three (another) distinguished partial orders which are uniquely given by the following prescriptions:

(<H)	=	(≤V) ○ (<S) ○ (≥V)	(the horizontal order),
(<L⁻)	=	(>V) ∪ (<H)	(the "discordant" linear order),
(<L⁺)	=	(<V) ∪ (<H)	(the "concordant" linear order).

This amounts to a "V-S-H-L^±" system of five partial orders ≤_V, ≤_S, ≤_H, ≤_L⁺, ≤_L⁻ on the same set X of nodes, in which, except for the pair { ≤_S, ≤_H}, any two relations uniquely determine the other three, see the determinacy table.

Notes about notational conventions:

• The munosabat tarkibi symbol ○ used in this subsection is to be interpreted left-to-right (as ${displaystyle circ _{l}}$).
• Belgilar < va ≤ express the qattiq va qat'iy emas versions of a partial order.
• Belgilar > va ≥ express the converse relations.
• The ≺ symbol is used for the qamrab oluvchi munosabat ning ≤ qaysi darhol version of a partial order.

This yields six versions ≺, <, ≤, ≻, >, ≥ for a single partial order relation. Dan tashqari ≺ va ≻, each version uniquely determines the others. Passing from ≺ ga <requires that < be transitively reducible. This is always satisfied for all of <_V, <_S va <_H but might not hold for <_L⁺ yoki <_L⁻ agar X cheksizdir.

The partial orders ≤_V va ≤_Hare complementary:

(<_V) ⊎ (>_V) ⊎ (<_H) ⊎ (>_H) = X × X ∖ id_X.

As a consequence, the "concordant" linear order <_L⁺ a chiziqli kengaytma ning <_V. Xuddi shunday, <_L⁻ is a linear extension of >_V.

The covering relations ≺_L⁻ va ≺_L⁺ mos keladi oldindan buyurtma berish va buyurtmadan keyingi o'tish navbati bilan. Agar x ≺_L⁻ y then, according to whether y has a previous sibling or not, the x node is either the "rightmost" non-strict descendant of the previous sibling of y or, in the latter case, x is the first child of y. Juftliklar ${displaystyle (x, y)}$ of the latter case form the relation (≺_L⁻) ∖ (<_H) which is a partial map that assigns each non-leaf node its birinchi bola node. Xuddi shunday, (≻_L⁺) ∖ (>_H) assigns each non-leaf node with finitely many children its oxirgi child node.

Definition using horizontal order

The Kuboyama's definition of "rooted ordered trees"^[2] makes use of the horizontal order ≤_H as a definitory relation.^[h] (See also Suppes.^[19])

Using the notation and terminology introduced so far, the definition can be expressed as follows.

An buyurtma qilingan daraxt bu struktura (X, ≤_V, ≤_H) such that conditions (1–5) are satisfied:

1. (X, ≤_V) is a partial order that is an unordered tree. (The vertical order.)
2. (X, ≤_H) is a partial order. (The horizontal order.)
3. The partial orders ≤_V va ≤_H are complementary: (<_V) ⊎ (>_V) ⊎ (<_H) ⊎ (>_H) = X × X ∖ id_X.

   (That is, pairs of nodes that are beqiyos yilda (<_V) are comparable in (<_H) and vice versa.)

4. The partial orders ≤_V va ≤_H are "consistent": (<_H) = (≤_V) ○ (<_H) ○ (≥_V).

   (That is, for every nodes x, y shu kabi x <_H y, all descendants of x must precede all the descendants of y.)

5. Every node has only finitely many preceding siblings. (That is, for every infinite sibling set S, (S, ≤_H) bor buyurtma turi of the natural numbers.) (Like before, this condition can be omitted in the case of finite trees.)

The sibling order (≤_S) tomonidan olinadi (<_S) = (<_H) ∩ ((≺_V) ○ (≻_V)), i.e. two distinct nodes are in sibling order if and only if they are in horizontal order and are siblings.

Determinacy table

The following table shows the determinacy of the "V-S-H-L^±" system. Relational expressions in the table's body are equal to one of <_V, <_S, <_H, <_L⁻, yoki <_L⁺ according to the column. It follows that except for the pair { ≤_S, ≤_H}, an ordered tree (X, ...) is uniquely determined by any two of the five relations.

In the last two rows, inf_L⁻(Y) belgisini bildiradi cheksiz ning Y yilda (X, ≤_L⁻)va sup_L⁺(Y) belgisini bildiradi supremum ning Y yilda (X, ≤_L⁺). In both rows, (≤_S) resp. (≥_S) can be equivalently replaced by the sibling ekvivalentlik (≤_S)○(≥_S). In particular, the partition into sibling sets together with either of ≤_L⁻ yoki ≤_L⁺ is also sufficient to determine the ordered tree. The first prescription for ≺_V can be read as: the parent of a non-root node x equals the infimum of the set of all immediate predecessors of siblings of x, where the words "infimum" and "predecessors" are meant with regard to ≤_L⁻. Similarly with the second prescription, just use "supremum", "successors" and ≤_L⁺.

Aloqalar ≤_S va ≤_H obviously cannot form a definitory pair. For the simplest example, consider an ordered tree with exactly two nodes – then one cannot tell which of them is the root.

XPath axes

The table on the right shows a correspondence of introduced relations to XPath axes ichida ishlatiladigan structured document systems to access nodes that bear particular ordering relationships to a starting "context" node. For a context node^[20] x, uning o'qi named by the specifier in the left column is the set of nodes that equals the rasm ning {x} under the correspondent relation. Sifatida XPath 2.0, the nodes are "returned" in document order, which is the "discordant" linear order ≤_L⁻. A "concordance" would be achieved, if the vertical order ≤_V was defined oppositely, with the bottom-up direction outwards the root like in set theory in accordance to natural daraxtlar.^[men]

Traversal maps

Quyida ro'yxati keltirilgan partial maps that are typically used for ordered tree traversal.^[21] Each map is a distinguished funktsional subrelation of ≤_L⁻ or of its opposite.

• ≺_V ... the parent-node partial map,
• ≻_S ... the previous-sibling partial map,
• ≺_S ... the next-sibling partial map,
• (≺_L⁻) ∖ (<_H) ... the birinchi bola partial map,
• (≻_L⁺) ∖ (>_H) ... the oxirgi bola partial map,
• ≻_L⁻ ... the previous-node partial map,
• ≺_L⁻ ... the next-node partial map.

Generating structure

The traversal maps constitute a partial unary algebra^[22] (X, parent, previousSibling, ..., nextNode) that forms a basis for representing trees as bog'langan ma'lumotlar tuzilmalari. At least conceptually,there are parent links, sibling adjacency links, and first / last child links. This also applies to unordered trees in general, which can be observed on the dentry data structure in the Linux VFS.^[23]

Similarly to the "V-S-H-L^±" system of partial orders, there are pairs of traversal maps that uniquely determine the whole ordered tree structure. Naturally, one such generating structure is (X, _V, _S) which can be transcribed as (X, parent, nextSibling) – the structure of parent and next-sibling links. Another important generating structure is (X, firstChild, nextSibling) sifatida tanilgan chap bolada o'ng aka-uka ikkilik daraxt. This partial algebra establishes a one-to-one correspondence between ikkilik daraxtlar and ordered trees.

Definition using binary trees

The correspondence to binary trees provides a concise definition of ordered trees as partial algebras.

An buyurtma qilingan daraxt bu struktura ${displaystyle (X,lc,rs)}$ qayerda X is a non-empty set of nodes, and lc, rs are partial maps on X deb nomlangan left-vhild va right-siblingnavbati bilan. The structure is subject to the following conditions:

1. The partial maps lc va rs are disjoint, i.e. (lc) ∩ (rs) = ∅ .
2. Ning teskari tomoni (lc) ∪ (rs) is a partial map p such that the partial algebra (X, p) is an unordered tree.

The partial order structure (X, ≤_V, ≤_S) quyidagicha olinadi:

(≺S)	=	(rs),
(≻V)	=	(lc) ○ (≤S).

Encoding by sequences

Ordered trees can be naturally encoded by finite sequences of natural numbers.^[24][j] Denote ω^⁎ the set of all finite sequences of natural numbers. Then any non-empty subset V ω^⁎ that is closed under taking prefikslar gives rise to an ordered tree: take the prefix order for ≥_V va leksikografik tartib uchun ≤_L⁻. Conversely, for an ordered tree T = (X, _V, ≤_L⁻) assign each node x ketma-ketlik ${displaystyle w(x)}$ of sibling indices, i.e. the root is assigned the empty sequence and for every non-root node x, ruxsat bering w(x) = w(parent(x)) ⁎ [men] qayerda men is the number of preceding siblings of x va ⁎ bo'ladi birlashtirish operator. Qo'y V = {w(x) | x ∈ X}. Keyin V, equipped with the induced orders ≤_V (the inverse of prefix order) and ≤_L⁻ (the lexicographical order), is isomorphic to T.

Per-level ordering

Dashed line indicates the <_B⁻ ordering)

As a possible expansion of the "V-S-H-L^±" system, another distinguished relations between nodes can be defined, based on the tree's level structure. First, let us denote by ∼_E the equivalence relation defined by x ∼_E y agar va faqat agar x va y have the same number of ancestors. This yields a partition of the set of nodes into darajalar L₀, L₁, ... (, L_n) - a coarsement of the partition into sibling sets. Then define relations <_E, <_B⁻ va <_B⁺ tomonidan

${displaystyle { egin{aligned}left(<_{mathrm {E} }ight)&=left(<_{mathrm {H} }ight)cap left(sim _{mathrm {E} }ight)&{ ext{((per) level order),}}left(<_{mathrm {B} ^{-}}ight)&=left(<_{mathrm {E} }ight)cup left(left(sim _{mathrm {E} }ight)circ left(>_{mathrm {V} }ight)ight)&{ ext{(breadth-first order, BFS ordering),}}left(<_{mathrm {B} ^{+}}ight)&=left(<_{mathrm {E} }ight)cup left(left({<}_{mathrm {V} }ight)circ left(sim _{mathrm {E} }ight)ight)&{ ext{(breadth-first post-order).}}end{aligned}}}$

It can be observed that <_E is a strict partial order and <_B⁻ va <_B⁺ are strict total orders. Moreover, there is a similarity between the "V-S-L^±" and "V-E-B^±" systems: <_E is component-wise linear and orthogonal to <_V, <_B⁻ is linear extension of <_E va of >_Vva <_B⁺ is a linear extension of <_E va of <_V.

Shuningdek qarang

• Daraxt tuzilishi
• Daraxt (grafik nazariyasi)
• Tree (set theory)
• Kardinal daraxt va Oddiy daraxt
• Ierarxiya (matematika)
• Muloqot daraxti
• Yagona meros
• Generativ grammatika
• Ierarxik klasterlash
• Binary space partition tree
• Rekursiya
• Fenvik daraxti

Boshqa daraxtlar

• Trie
• Day-Stout-Warren algoritmi
• Enfilade
• Left child-right sibling binary tree
• Ierarxik vaqtinchalik xotira

Izohlar

Adabiyotlar

Qo'shimcha o'qish

• Donald Knuth. Kompyuter dasturlash san'ati: Fundamental Algorithms, Uchinchi nashr. Addison-Uesli, 1997 yil. ISBN  0-201-89683-4 . Section 2.3: Trees, pp. 308–423.
• Tomas X. Kormen, Charlz E. Leyzerson, Ronald L. Rivest va Klifford Shteyn. Algoritmlarga kirish, Ikkinchi nashr. MIT Press va McGraw-Hill, 2001 yil. ISBN  0-262-03293-7 . Section 10.4: Representing rooted trees, pp. 214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253–320.

Tashqi havolalar

• Data Trees as a Means of Presenting Complex Data Analysis by Sally Knipe on August 8, 2013
• Tavsif dan Algoritmlar va ma'lumotlar tuzilmalari lug'ati
• CRAN - Package data.tree implementation of a tree data structure in the R programming language
• WormWeb.org: Interactive Visualization of the C. elegans Cell Tree – Visualize the entire cell lineage tree of the nematode C. elegans (javascript)
• Binary Trees by L. Allison