Daraxt asoslari
Kompyuteringizda papkalar qanday joylashganini tasavvur qiling. Bir papka ichida boshqa papkalar, ularning ichida yana papkalar va fayllar bor. Eng yuqoridagi papka barchaning ota-onasi; quyi papkalar uning bolalari. Bu tuzilma — daraxt.
Daraxt (tree) — tugunlar (node) va ularni bog'lovchi qirralar (edge) dan iborat ierarxik ma'lumotlar tuzilmasi. Har bir tugun bitta ota-ona (parent) tugunga va bir yoki bir nechta bola (child) tugunga ega bo'lishi mumkin. Bitta maxsus tugun — ildiz (root) — ota-onasiz turadi va butun daraxtning boshlanish nuqtasi hisoblanadi.
Bu tuzilma linked list yoki arraydan tubdan farq qiladi: u chiziqli emas, ierarxik. Bu farq ko'plab muammoni samarali yechishga imkon beradi.
Nima uchun daraxt kerak?
Ro'yxatda bir million elementdan biror narsani qidirish eng yomon holatda million qadam oladi. Tartibli daraxtda esa har qadamda elementlarning yarmini yo'q qilish mumkin — bu O(log n) bosqich.
Bundan tashqari, ba'zi ma'lumotlar tabiatan ierarxik: fayl tizimi, tashkilot sxemasi, HTML/XML hujjat, til sintaksisi, toifa daraxtlari. Ularni ro'yxat yoki arrayda saqlash sun'iy va noqulay bo'ladi.
Asosiy terminlar
Tugun (node)
Daraxtdagi har bir element — tugun. Tugun qiymat va bir yoki bir nechta bola tugunga murojaat saqlaydi.
Qirra (edge)
Ota-tugun va bola-tugunni bog'lovchi mantiqiy ulanish. n tugunli daraxtda aynan n - 1 ta qirra bo'ladi.
Ildiz (root)
Ota-onasiz yolg'iz tugun. Butun daraxt shu tugundan boshlanadi. Ildiz yo'q bo'lsa — daraxt bo'sh.
Bola (child) va ota (parent)
Tugunning to'g'ridan-to'g'ri bog'langan quyi tugunlari — bolalari; unga to'g'ridan-to'g'ri bog'langan yuqori tugun — otasi.
Aka-uka (sibling)
Bir ota-onaga ega bo'lgan tugunlar. Yuqoridagi rasmda B va C — aka-uka.
Barg (leaf)
Hech qanday bolasi yo'q tugun. Daraxtning eng quyi uchidagi tugunlar.
Chuqurlik (depth)
Tugundan ildigacha bo'lgan qirralar soni. Ildizning chuqurligi 0.
Balandlik (height)
Tugundan eng pastdagi bargigacha bo'lgan qirralar soni. Barg tugunning balandligi 0. Daraxtning balandligi ildizning balandligi.
Qavat (level)
Ildizdan bir xil masofadagi tugunlar bir qavatda turadi. Ildiz 0-qavatda (ba'zi manbalarda 1-qavatda). d chuqurlikdagi tugunlar d-qavatda.
Daraxt vs chiziqli tuzilmalar
Daraxtda har tugunning faqat bitta ota-onasi va cheksiz (yoki cheklangan) bolalari bo'lishi mumkin. Linked listda ham tugunlar reference orqali bog'lanadi, lekin u chiziqli — har tugunning ko'pi bilan bittasi "keyingi" uchun. Grafda esa tsikl va birgalikdagi ota-onalar mumkin; daraxtda ular taqiqlangan.
Daraxt xotirada qanday ifodalanadi?
Node-reference modeli
Eng keng tarqalgan usul: har bir tugun alohida obyekt sifatida xotirada turadi. Tugun qiymat va bola tugunlarga murojaatlar (reference) saqlaydi.
Binar daraxt node:
+----------+
| qiymat |
| left → ─┼──► [chap bola]
| right → ─┼──► [o'ng bola]
+----------+
Umumiy n-ary daraxtda bola murojaatlari ro'yxat sifatida saqlanadi. Bolalar soni turli tugunlarda har xil bo'lishi mumkin.
Node'lar xotirada tarqoq joylashadi: biri yerda, bolasi boshqa joyda. Bu linked list'ga o'xshash — ketma-ket joylashuv kafolatlanmaydi.
Massiv asosidagi ifodalash
Binar daraxt uchun maxsus holat: agar daraxt to'liq (complete) bo'lsa, ya'ni barcha qavatlari to'la va oxirgi qavat elementlari chapdan joylashgan bo'lsa, massivda saqlash mumkin.
[A]
/ \
[B] [C]
/ \ /
[D] [E][F]
Massiv: [A, B, C, D, E, F]
Index: 0 1 2 3 4 5
i-indeksdagi tugun uchun:
chap bola: 2*i + 1
o'ng bola: 2*i + 2
ota-ona: (i - 1) / 2
Bu usul heap uchun muhim — heap doim to'liq binar daraxt sifatida massivda saqlanadi. Lekin tarqoq daraxtda bo'sh kataklar ko'p bo'lib, xotira isrof bo'lishi mumkin.
Daraxt turlari
Umumiy daraxt (general tree)
Har bir tugunning ixtiyoriy sondagi bolasi bo'lishi mumkin. Fayl tizimi yoki tashkilot sxemasi shu ko'rinishda.
Binar daraxt (binary tree)
Har tugunning ko'pi bilan ikkita bolasi bo'ladi: chap (left) va o'ng (right). Bu cheklov daraxtni ko'p amallarda samaraliroq qiladi.
To'liq binar daraxt (full binary tree)
Har tugunning nol yoki aynan ikkita bolasi bor. Bitta bolali tugun yo'q.
Mukammal binar daraxt (complete binary tree)
Barcha qavatlari to'la, faqat oxirgi qavat chap tomonga joylashgan bo'lishi mumkin.
Massivda ixcham saqlash mumkin — bo'sh joy yo'q.
Mukammal to'liq binar daraxt (perfect binary tree)
Barcha ichki tugunlar ikkita bolaga ega va barcha barglar bir xil chuqurlikda.
h balandlikdagi perfect binary tree'da 2^(h+1) - 1 ta tugun bor.
Muvozanatlangan daraxt (balanced tree)
Har tugunning chap va o'ng kenja daraxtlari (subtree) balandligi bir-biridan ko'pi bilan ma'lum miqdor (odatda 1) farq qiladi. AVL daraxt va qizil-qora daraxt (red-black tree) shu kategoriyaga kiradi.
Muvozanat daraxtni O(log n) balandlikda ushlab turadi — bu BST, heap va boshqa daraxt operatsiyalarining O(log n) murakkabligini kafolatlaydi.
Binar qidiruv daraxti (BST)
Chap kenja daraxtidagi barcha qiymatlar ildizdan kichik, o'ng kenja daraxtidagi barcha qiymatlar ildizdan katta bo'lgan binar daraxt. Keyingi mavzuda batafsil ko'ramiz.
Daraxt xususiyatlari
Tsikl yo'q. Daraxtda hech qanday node zanjiri o'ziga qaytib kelolmaydi. Bu uni grafdan ajratib turuvchi asosiy xususiyat.
Ildizdan har tugunga bitta yo'l. Har tugunga ildizdan aynan bitta yo'l bor.
n tugun, n-1 qirra. Bu zarur va yetarli shart.
Bog'liqlik. Daraxt bog'liq — har qanday ikkita tugun o'rtasida yo'l mavjud.
Asosiy amallar
Traversal (aylanib chiqish)
Daraxtdagi har tugunni bir marta ko'rish. Ro'yxatdan farqli o'laroq, daraxtda bir nechta traversal tartibi mavjud:
- DFS (Depth-First Search): chuqurlik bo'yicha — bir shoxga to imkon qadar chuqur kirib, keyin orqaga qaytish.
- BFS (Breadth-First Search): kenglik bo'yicha — qavatma-qavat o'qish.
Bu traversallar keyingi mavzuda batafsil ko'riladi.
Qidirish
Maqsad qiymatni topish. Umumiy daraxtda O(n) (barcha tugunlar ko'rilishi mumkin). BST'da tartib tufayli O(h) — h balandlik.
Qo'shish va o'chirish
Tugun qo'shish: maqsad o'rni topiladi, yangi tugun ulanadi. O'chirish: tugun topiladi, bolalari boshqa tugunga ulanadi. Murakkablik va detallar daraxt turiga qarab farq qiladi.
Vaqt murakkabligi
| Amal | Umumiy daraxt | Balanced BST | Unbalanced BST |
|---|---|---|---|
| Qidirish | O(n) |
O(log n) |
O(n) |
| Qo'shish | O(n) |
O(log n) |
O(n) |
| O'chirish | O(n) |
O(log n) |
O(n) |
| Traversal | O(n) |
O(n) |
O(n) |
| Min/Max | O(n) |
O(log n) |
O(n) |
Muvozanatlangan daraxtda balandlik O(log n), shuning uchun balandlikka bog'liq amallar O(log n).
Real qo'llanishlar
Fayl tizimi
Operatsion tizim kataloglarini n-ary daraxt sifatida saqlaydi. Ildiz — asosiy katalog. Har katalog papkalar (ichki tugunlar) va fayllardan (barglar) iborat. find buyrug'i DFS bilan ishlaydi.
HTML va XML hujjat
Brauzer HTML'ni DOM (Document Object Model) daraxt sifatida saqlaydi. <html> ildiz, <head> va <body> uning bolalari. CSS selektorlar va JavaScript DOM manipulyatsiyasi daraxt traversali bilan bajariladi.
Dasturiy kod sintaksisi
Kompilyator va interpretator kodni abstract syntax tree (AST) ga aylantiradi. a + b * c ifodasi + ildizli, a chap bola, * o'ng bola bo'lgan daraxtga aylanadi. Bu daraxt asosida kod tekshiriladi va optimallashtiriladi.
Qaror daraxti
Machine learningdagi decision tree klasifikatsiya uchun: har ichki tugun bir shart, barglar — bashorat. "Harorat > 30? Yuqori qon bosimi bormi?" kabi savollar tugun sifatida joylashadi.
Ma'lumotlar bazasi indeksi
B-tree va B+ tree — disk asosida ishlash uchun optimallashtirilgan muvozanatlangan daraxtlar. Ko'p ma'lumotlar bazalari indeks uchun shu tuzilmani ishlatadi.
Keng tarqalgan xatolar va nozik holatlar
Bo'sh daraxt. Ildiz NULL bo'lsa, daraxt bo'sh. Har bir rekursiv funksiya bu holatni avval tekshirishi kerak. Tushirib qoldirilsa, null-reference xatosi keladi.
Bitta tugunli daraxt. Ildiz ham barg. Chuqurlik = 0, balandlik = 0. Ko'p algoritm bu holatda to'g'ri ishlashini alohida tekshirib ko'rish kerak.
Balandlik va chuqurlikni aralashtirish. Balandlik bargdan yuqoriga hisoblanadi, chuqurlik ildizdan pastga. Ildizning chuqurligi 0, bargning balandligi 0.
Qisqa yo'l bilan to'liq daraxt deb taxmin qilish. Ko'p algoritm daraxt muvozanatlangan deb taxmin qilsa ham, amalda muvozanatsiz bo'lishi mumkin. Eng yomon holat — zanjir ko'rinishidagi daraxt — balandligi O(n).
Chap va o'ng bolalarni aralashtirish. BST'da tartib muhim: chap < ildiz < o'ng. Bolalar joyini teskari yozish daraxt xususiyatini buzadi.
Qachon daraxt ishlatish kerak?
- Ma'lumotlar tabiatan ierarxik bo'lganda (fayl tizimi, tashkilot, toifa).
- Saralangan tartibda tez qidirish, qo'shish va o'chirish kerak bo'lganda (BST).
- Ko'plab elementlar orasida eng katta yoki eng kichikni tez topish kerak bo'lganda (heap).
- Matn qidirish va prefix muammolari uchun (trie).
- Qaror mezonlari ierarxiyasi kerak bo'lganda (decision tree).
Qachon daraxt ishlatmaslik kerak?
- Tartibli ro'yxat kerak bo'lsa — tartiblangan array yoki linked list soddaroq.
- Ixtiyoriy indexga tez kirish kerak bo'lsa — array
O(1)indeks bilan tezroq. - Ierarxiya yo'q bo'lsa — chiziqli tuzilma samaraliroq.
- Tsikl yoki ko'p ota-ona bo'lsa — bu endi daraxt emas, graf.
- Disk asosidagi katta ma'lumot bo'lsa — oddiy xotira daraxti o'rniga B-tree talab qilinishi mumkin.
Eng muhim xulosa
Daraxt ierarxik ma'lumotlarni ifodalovchi va ko'plab algoritmik muammolarni samarali yechadigan asosiy tuzilma. Asosiy atamalar — ildiz, ota-ona, bola, barg, chuqurlik, balandlik, qavat — daraxt haqidagi har qanday muloqotda ishlatiladi.
Daraxt turlari muammo tabiatiga qarab tanlanadi: umumiy daraxt ierarxiya uchun, binar daraxt va BST tartibli qidirish uchun, heap ustuvorlik uchun, trie prefix qidirish uchun, muvozanatlangan daraxtlar esa eng yomon holat kafolatini ta'minlash uchun.
Daraxtni o'rganishda keyingi tabiiy qadamlar — binar qidiruv daraxti operatsiyalari va daraxtni aylanib chiqish algoritmlari.