Muhammad al-Xorazmiy Nomidagi Toshkent Axborot Texnologiyalari Universititeti

Muhammad al-Xorazmiy Nomidagi Toshkent Axborot Texnologiyalari Universititeti
Samarqand filiali

Ma’lumotlar tuzilmasi fanidan

Mustaqil ishi

1. 
   Mavzu: Ikkilik daraxtlar va ularning ustida amallar
   

Bajardi: Abduazizov A.
Guruh: TT2m21-01

Reja
1.Binar daraxtlar haqida nazariy ma’lumot.

2.Ular ustidagi amallar.
3.Misol.
4.Xulosa.

Binar daraxtlar

Kompyuter fanida ikkilik daraxt-har bir tugunning left child va to'g'ri bola deb ataladigan ikkita filialdan ko'p bo'lmagan daraxtga o'xshash ma'lumotlar tuzilishi. Faqat ko'plik nazariyasi tushunchalarini ishlatadigan recursive ta'rifi (bo'sh) ikkilik daraxt (L, S, R),bu erda L va R ikkilik daraxtlar yoki bo'sh joylar va s — ildizni o'z ichiga olgan yagona to'siq. Ba'zi mualliflar, shuningdek, ikkilikning bo'sh joy bo'lishiga imkon beradi.
Grafika nazariyasi nuqtai nazaridan, ikkilik (va k-Ares) daraxtlari bu erda ta'riflanganidek, arboresansdir. Shunday qilib, ikkilik daraxtni arboretansning bo'linishi deb atash mumkin, ba'zi juda eski dasturlash kitoblarida paydo bo'lgan atama kompyuter fanining zamonaviy terminologiyasi ustunlik qilishdan oldin. Bundan tashqari,ikkilik daraxtni yo'nalishsiz emas,balki yo'naltirilgan grafik sifatida talqin qilish mumkin, va bu holda ikkilik daraxt tartibli, ildiz daraxtidir. Ba'zi mualliflar daraxtning ildiz ekanligini ta'kidlash uchun ikkilamchi daraxt o'rniga ildizli ikkilik daraxtdan foydalanadilar, lekin yuqorida aytib o'tilganidek, ikkilik daraxt har doim ildiz otadi. Ikkilik daraxt k-2 bo'lgan buyurtma qilingan k-Arne daraxtining alohida holatidir.

Matematikada ikkilik daraxt deb ataladigan narsa muallifdan muallifga sezilarli darajada farq qilishi mumkin. Ba'zilar, odatda, vinformatika tomonidan ishlatiladigan ta'riflardan foydalanadilar, [7], lekin boshqalar uni ikki farzandli har bir nonstick sifatida belgilaydi va bolalarni (chap / o'ng) tartibga solmaydi.

Hisoblash texnologiyasida ikkilik daraxtlar ikki xil usulda qo'llaniladi:

Birinchidan, har bir tugun bilan bog'liq ba'zi qiymat yoki yorliq asosida tugunlarga kirish vositasi sifatida. Shu tarzda etiketlangan ikkilik daraxtlar ikki tomonlama qidirish va ikkilik qoziqlarni amalga oshirish,shuningdek, samarali qidirish va tartiblash uchun ishlatiladi. Ushbu ilovalarning ayrimlarida, xususan, ikkilik qidiruv daraxtlarida muhim ahamiyatga ega bo'lgan, faqat bitta bola tuguniga ega bo'lsa ham, chap yoki o'ng bola sifatida Node bo'lmagan tugunlarni belgilash. Biroq, daraxtdagi alohida tugunlarning joylashishi kontseptual ma'lumotlarning bir qismi emas.
Umuman olganda, ikkilik daraxtni aniqlash uchun biz faqat bitta bolaning bo'sh bo'lishi mumkinligini hisobga olishimiz kerak. Buning uchun ba'zi darsliklarda kengaytirilgan ikkilik daraxt deb ataladigan artefakt kerak. Shunday qilib, kengaytirilgan ikkilik daraxt rekursiv ravishda quyidagicha ta'riflanadi:

bo'sh to'siq kengaytirilgan ikkilik daraxtdir

Agar T1 va T2 kengaytirilgan ikkilik daraxtlar bo'lsa, T1 • T2 kengaytirilgan ikkilik daraxtni T1ga chap tomonga va T2ga o'ng tomonga bog'langan r ildizini qo'shish orqali hosil qiling ["r" belgisida "T1 • T2"], bu pastki qismlar bo'sh bo'lmaganda qovurg'alarni qo'shib qo'yish kerak.
Ushbu qurilishni tasavvur qilishning yana bir usuli (va terminologiyani tushunish) bo'sh to'plam o'rniga boshqa turdagi tugunni ko'rib chiqishdir-masalan, kvadrat tugunlar, agar ular to'g'ri bo'lsa.