Tree – chiziqli bo’lmagan ma’lumot tuzilmasi (data structure) bo’lib u ma’lumotlarni ierarxik ko’rinishda tashkil qiladi. Masalan, oila shajarasini tasavvur qiladigan bo’lsak, u ham tree ma’lumot tuzilmasi hisoblanadi.
Tree aslida node‘lar to’plami. Node’lar bir biriga tomonlari (edges) orqali bog’langan. Demak har bir node o’zida qiymat (value) hamda child node’larga pointer bo’ladi. Har bir tree’da birinchi node root deb ataladi.
Agar node bir yoki birnecha node’larga ulangan bo’lsa u node – parent, unga ulangan node’lar children deyiladi. Bolasi yo’q node’lar barglar (leaves) yoki tashqi (external) node, aks holda ichki (internal) node deb nomlanadi. Bitta parent’ga tutashgan node’lar siblings deyiladi.
Yuqoridagi misolda:
- A – B va C ga parent
- B – A uchun child
- B va C – siblings
- E, F, H, I va J – leaves
Node’ning chuqurligi (depth) – node’ning root’gacha bo’lgan yo’lining uzunligi hisoblanadi. Yuqoridagi misolimizda I node’ning chuqurligi 3 ga teng (I -> G -> C -> D).
Node’ning uzunligi (height) sifatida esa node’dan eng pastki node’gacha bo’lgan yo’li uzunligi olinadi. Masalan, B ning uzunligi – 2 ga teng (B -> D -> E).
Binary Tree
Tree node’lari bo’lmasligi yoki bitta va undan ko’p bo’lishi mumkin. Binary Tree‘da node’lar ikkitadan ko’p bo’lmaydi. Har bir node’da chap va o’ng node bo’lishi mumkin.
Binary tree node’lari asosan 3 turdagi ma’lumotlarni o’zida saqlaydi:
- Node’ning qiymati (value)
- Chap child’ga ko’rsatkich (pointer)
- O’ng child’ga ko’rsatkich (pointer)
Binary tree turlari
Dasturlashda asosan binary tree ko’p ishlatiladi. Uning bir necha turlari bor:
Full binary tree. Har bir node 0 yoki 2 children node’ga ega bo’lgan binary tree.
Image credit: https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254
Complete binary tree. Binary tree’ning ohirgi darajasidan tashqari qolgan har bir darajasi tugallangan bo’lsa, u complete binary tree deyiladi.
Image credit: https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254
Perfect binary tree. Agar barcha internal node’larda ikkitadan child bo’lsa va barcha external childlar bir darajada bo’lsa, demak u perfect binary tree bo’ladi.
Image credit: https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254
Balanced binary tree. Agar binary tree’ning uzunligi (height) O(log n) bo’lsa, balanced binary tree deyiladi. Bunda n – tree’dagi node’lar soni.
Image credit: https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254
Degenerate binary tree. Agar har bir parent node’ning faqat bitta child node’i bo’lsa, u degenerate binary tree hisoblanadi.
Image credit: https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254
Xulosa
Ushbu maqola tree ma’lumot tuzilmasi bilan bog’liq barcha ma’lumotlarni o’z ichiga olmagan. Ayniqsa tree’ni kodda ifodalashni qo’shishni lozim topmadim. Sababi, tree’ni kodga ko’chirishdan avval uni ishlatish maqsadini ham aniqlab olish kerak bo’ladi. Masalan binary heap yoki binary search‘ni implementatsiyasi (kodda ifodalash) turlicha bo’ladi.
* * *
Foydalanilgan manbalar: