Bajardi: buronov umid qabul Qildi: Isroilov Sh Samarqand -2022 Heap tree tuzulmasi va ustida amallar bajarish algoritmlari

Tree ma’lumotlar tuzilmasi. Binary Tree
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.
Shajara – tree malumotlar tuzulmasi sifatida

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:

1.A – B va C ga parent
2.B – A uchun child
3.B va C – siblings
4.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:
1.Node’ning qiymati (value)
2.Chap child’ga ko’rsatkich (pointer)
3.O’ng child’ga ko’rsatkich (pointer)

Binary Tree.

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.

Full va full bo’lmagan binary tree.
Binary tree’ning ohirgi darajasidan tashqari qolgan har bir darajasi tugallangan bo’lsa, u complete binary tree deyiladi

Complete va non complete binary tree.