21 / 69

Tree Data Structure

Daraxt ma'lumotlar tuzilmasi

Daraxt (Tree) — qirralar (edges) bilan o'zaro bog'langan tugunlardan (nodes) tashkil topgan nochiziqli (non-linear) iyerarxik ma'lumotlar tuzilmasidir.

Daraxt

Daraxt ma'lumotlar tuzilmasi

Nima uchun daraxt ma'lumotlar tuzilmasi kerak?

Massivlar, bog'langan ro'yxat, stek va navbat kabi boshqa ma'lumot tuzilmalari ma'lumotlarni ketma-ket saqlovchi chiziqli (linear) tuzilmalardir. Elementlar soni ortib borgan sari ularda qidirish yoki o'zgartirish amallarining vaqt sarfi oshib boradi.

Turli xil daraxt tuzilmalari esa nochiziqli tuzilma bo'lganligi sababli ma'lumotlarga ancha tez va oson kirish imkonini beradi.

Daraxt terminologiyalari

Tugun

Tugun (Node) — ma'lumot (kalit yoki qiymat) va o'zining bola tugunlariga yo'naltirilgan ko'rsatkichlarni saqlovchi asosiy elementdir.

  • Har bir yo'lning oxirida joylashgan va keyingi tugunlarga havolasi bo'lmagan tugunlar barg tugunlar (leaf nodes) yoki tashqi tugunlar (external nodes) deb ataladi.
  • Kamida bitta bola tugunga ega bo'lgan har qanday tugun ichki tugun (internal node) deb ataladi.

Qirra / Bog'lam

Ixtiyoriy ikkita tugun o'rtasidagi bog'lovchi chiziq qirra (edge) deb ataladi.

Daraxt tugunlari va qirralari

Daraxtning tugunlari va qirralari

Ildiz

Daraxtning eng yuqori qismida joylashgan boshlang'ich tugun ildiz (root) deyiladi. Daraxtda faqat bitta ildiz tugun bo'ladi.

Tugun balandligi

Tugunning balandligi — ushbu tugundan eng chuqur barg tugungacha bo'lgan qirralar soniga (ya'ni, tugundan barggacha bo'lgan eng uzun yo'lga) teng.

Tugun chuqurligi

Tugunning chuqurligi — daraxt ildizidan berilgan tugungacha bo'lgan qirralar soniga teng.

Daraxt balandligi

Daraxtning umumiy balandligi — uning ildiz tugunining balandligiga yoki eng chuqur tugunning chuqurligiga tengdir.

Tugun balandligi va chuqurligi

Daraxtdagi har bir tugunning balandligi va chuqurligi

Tugun darajasi

Tugunning darajasi — ushbu tugundan chiquvchi tarmoqlar (uning bevosita bolalari) umumiy sonidir.

O'rmon

O'zaro bog'lanmagan (ajratilgan) daraxtlar to'plami o'rmon (forest) deb ataladi.

O'rmon

Daraxtdan o'rmon hosil qilish

Ixtiyoriy daraxtning ildizini olib tashlash orqali alohida daraxtlardan iborat o'rmon hosil qilish mumkin.

Daraxt turlari

  1. Binary Tree (Ikkilik daraxt)
  2. Binary Search Tree (Ikkilik qidiruv daraxti)
  3. AVL Tree (AVL daraxti)
  4. B-Tree (B-daraxt)

Daraxtni aylanib chiqish

Daraxt ustida biror amalni bajarish (masalan, elementni qidirish, o'chirish yoki chop etish) uchun muayyan tugunga yetib borish zarur. Daraxtni aylanib chiqish (tree traversal) algoritmi barcha tugunlarga qaysi ketma-ketlikda tashrif buyurishni belgilaydi.

Batafsil ma'lumot olish uchun keyingi Daraxtni aylanib chiqish (Tree Traversal) darsini o'rganing.

Daraxt ma'lumotlar tuzilmasining qo'llanilishi

  • Ikkilik qidiruv daraxtlari (BST): to'plamda biror element mavjud yoki yo'qligini tezkor tekshirishda ishlatiladi.
  • To'p (Heap): to'p usulida saralash (heap sort) va ustuvorlik navbatlarida qo'llaniladi.
  • Prefiks daraxtlari (Tries): zamonaviy tarmoq marshrutizatorlarida (router) marshrutlash ma'lumotlarini saqlashda va lug'at qidiruvlarida keng foydalaniladi.
  • Ma'lumotlar bazalari: ko'plab ommabop MBBTlar (PostgreSQL, MySQL va b.) tezkor indekslash uchun B-Tree va uning modifikatsiyalaridan foydalanadi.
  • Kompilyatorlar: har bir dastur kodi sintaksisini tekshirish va tahlil qilish uchun sintaksis daraxtidan (Abstract Syntax Tree - AST) foydalanadi.