DSA ikkilik daraxtlar
Ikkilik daraxtlar
Ikkilik daraxt — daraxt ma’lumotlar tuzilmasining shunday turiki, unda har bir tugun ko‘pi bilan ikkita bola tugunga: chap bola tugun va o‘ng bola tugunga ega bo‘lishi mumkin.
Tugun ko‘pi bilan ikkita bola tugunga ega bo‘lishi mumkinligi haqidagi bu cheklov bizga ko‘plab afzalliklar beradi:
- Aylanib chiqish, qidirish, qo‘shish va o‘chirish kabi algoritmlarni tushunish va amalga oshirish osonlashadi hamda ular tezroq ishlaydi.
- Ma’lumotlarni ikkilik qidiruv daraxtida (BST) saralangan holda saqlash qidiruvni juda samarali qiladi.
- Bola tugunlar soni cheklangan bo‘lsa, daraxtlarni muvozanatlash osonroq, masalan, AVL ikkilik daraxti yordamida.
- Ikkilik daraxtlarni massivlar ko‘rinishida ifodalash mumkin, bu esa daraxtni xotira jihatidan samaraliroq qiladi.
Ikkilik daraxt qanday ko‘rinishini va uni tasvirlash uchun qanday so‘zlardan foydalanishimizni ko‘rish uchun quyidagi animatsiyadan foydalaning.
Ikkilik daraxtdagi ota tugun yoki ichki tugun — bitta yoki ikkita bola tugunga ega bo‘lgan tugun.
Chap bola tugun — chap tomondagi bola tugun.
O‘ng bola tugun — o‘ng tomondagi bola tugun.
Daraxt balandligi — ildiz tugundan barg tugungacha bo‘lgan qirralarning maksimal soni.
Ikkilik daraxtlar hamda massivlar va bog‘langan ro‘yxatlar
Ikkilik daraxtlarning massivlar va bog‘langan ro‘yxatlarga nisbatan afzalliklari:
- Massivlar elementga to‘g‘ridan-to‘g‘ri murojaat qilmoqchi bo‘lganingizda, masalan, 1000 elementli massivdagi 700-elementga murojaat qilganda tez ishlaydi. Biroq elementlarni qo‘shish va o‘chirish yangi elementga joy ochish yoki o‘chirilgan element o‘rnini egallash uchun boshqa elementlarning xotirada siljishini talab qiladi va bu ko‘p vaqt oladi.
- Bog‘langan ro‘yxatlar tugunlarni qo‘shish yoki o‘chirishda tez ishlaydi, xotirada siljitish kerak emas, ammo ro‘yxat ichidagi elementga murojaat qilish uchun ro‘yxatni aylanib chiqish kerak va bu vaqt oladi.
- Ikkilik qidiruv daraxtlari va AVL daraxtlari kabi ikkilik daraxtlar massivlar va bog‘langan ro‘yxatlarga qaraganda juda yaxshi, chunki ular tugunga murojaat qilishda HAM tez, tugunni o‘chirish yoki qo‘shishda HAM tez, bunda xotirada hech qanday siljitish talab qilinmaydi.
Ikkilik qidiruv daraxtlari (BST) va AVL daraxtlari qanday ishlashini keyingi ikki sahifada batafsilroq ko‘rib chiqamiz, lekin avval ikkilik daraxtni qanday amalga oshirish va uni qanday aylanib chiqish mumkinligini ko‘rib chiqaylik.
Ikkilik daraxt turlari
Ikkilik daraxtlar qanday tuzilishi mumkinligini yaxshiroq tushunish uchun ikkilik daraxtlarning muhokama qilishga arziydigan turli variantlari yoki turlari mavjud.
Ikkilik daraxtlarning turli xillarini hozir aytib o‘tish ham foydali, chunki bu so‘z va tushunchalar keyinroq darslikda ishlatiladi.
Quyida ikkilik daraxt tuzilmalarining turli turlari qisqacha tushuntirilgan, tushuntirishlar ostida esa imkon qadar oson tushunish uchun bunday tuzilmalarning chizmalari berilgan.
Muvozanatlangan (balanced) ikkilik daraxtda daraxtdagi har bir tugun uchun chap va o‘ng qism daraxtlar balandliklari orasidagi farq ko‘pi bilan 1 ga teng.
To‘liq (complete) ikkilik daraxtda oxirgi darajadan tashqari barcha darajalar tugunlar bilan to‘la bo‘ladi, oxirgi daraja esa to‘la bo‘lishi yoki chapdan o‘ngga to‘ldirilgan bo‘lishi mumkin. To‘liq ikkilik daraxtning xususiyatlari uning muvozanatlangan ham ekanini bildiradi.
To‘la (full) ikkilik daraxt — har bir tugunda 0 ta yoki 2 ta bola tugun bo‘ladigan daraxt turi.
Mukammal (perfect) ikkilik daraxtda barcha barg tugunlar bir xil darajada bo‘ladi, ya’ni barcha darajalar tugunlar bilan to‘la va barcha ichki tugunlar ikkitadan bola tugunga ega. Mukammal ikkilik daraxtning xususiyatlari uning to‘la, muvozanatlangan va to‘liq ham ekanini bildiradi.
Ikkilik daraxtni amalga oshirish
Keling, ushbu ikkilik daraxtni amalga oshiraylik:
Yuqoridagi ikkilik daraxtni biz bir tomonlama bog‘langan ro‘yxatni amalga oshirganimizga juda o‘xshash tarzda amalga oshirish mumkin, faqat har bir tugunni bitta keyingi tugunga bog‘lash o‘rniga har bir tugun o‘zining chap va o‘ng bola tugunlariga bog‘lanishi mumkin bo‘lgan tuzilma yaratamiz.
Ikkilik daraxtni quyidagicha amalga oshirish mumkin:
Misol
Python:
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')
root.left = nodeA
root.right = nodeB
nodeA.left = nodeC
nodeA.right = nodeD
nodeB.left = nodeE
nodeB.right = nodeF
nodeF.left = nodeG
# Test
print("root.right.left.data:", root.right.left.data)Ikkilik daraxtni aylanib chiqish
Daraxtning har bir tuguniga birma-bir tashrif buyurib chiqish aylanib chiqish (traversal) deb ataladi.
Massivlar va bog‘langan ro‘yxatlar chiziqli ma’lumotlar tuzilmalari bo‘lgani uchun ularni aylanib chiqishning faqat bitta aniq usuli bor: birinchi element yoki tugundan boshlang va hammasiga tashrif buyurmaguningizcha keyingisiga o‘tishda davom eting.
Ammo daraxt turli yo‘nalishlarda shoxlanishi (chiziqli bo‘lmasligi) mumkinligi sababli daraxtlarni aylanib chiqishning turli usullari mavjud.
Daraxtni aylanib chiqish usullarining ikkita asosiy toifasi mavjud:
Kenglik bo‘yicha qidiruv (BFS) — daraxtdagi keyingi darajaga o‘tishdan oldin bir xil darajadagi tugunlarga tashrif buyuriladigan usul. Bu daraxt ko‘proq yon tomonga qarab o‘rganilishini anglatadi.
Chuqurlik bo‘yicha qidiruv (DFS) — aylanib chiqish daraxt bo‘ylab barg tugunlargacha pastga tushib boradigan, daraxtni shoxma-shox pastga yo‘nalishda o‘rganadigan usul.
DFS aylanib chiqishning uch xil turi mavjud:
Chuqurlik bo‘yicha qidiruvga asoslangan ushbu uchta aylanib chiqish usuli keyingi sahifalarda batafsil tasvirlangan.
DSA mashqlari
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!