DSA daraxtlar
Daraxtlar
Daraxt ma’lumotlar tuzilmasi bog‘langan ro‘yxatlarga o‘xshaydi: har bir tugun ma’lumot saqlaydi va boshqa tugunlarga bog‘lanishi mumkin.
Biz avvalroq massivlar, bog‘langan ro‘yxatlar, steklar va navbatlar kabi ma’lumotlar tuzilmalarini ko‘rib chiqdik. Ularning barchasi chiziqli tuzilmalar, ya’ni har bir element ketma-ketlikda boshqasidan keyin darhol keladi. Daraxtlar esa boshqacha. Daraxtda bitta element bir nechta 'keyingi' elementga ega bo‘lishi mumkin, bu esa ma’lumotlar tuzilmasining turli yo‘nalishlarda shoxlanishiga imkon beradi.
Bu ma’lumotlar tuzilmasi "daraxt" deb ataladi, chunki u xuddi quyidagi rasmdagi kabi daraxtga o‘xshaydi, faqat teskari holatda.
Daraxt ma’lumotlar tuzilmasi ko‘p hollarda foydali bo‘lishi mumkin:
- Iyerarxik ma’lumotlar: fayl tizimlari, tashkiliy modellar va h.k.
- Ma’lumotlar bazalari: ma’lumotlarni tez olish uchun ishlatiladi.
- Marshrutlash jadvallari: tarmoq algoritmlarida ma’lumotlarni marshrutlash uchun ishlatiladi.
- Saralash/qidirish: ma’lumotlarni saralash va qidirish uchun ishlatiladi.
- Ustuvor navbatlar: ustuvor navbat (priority queue) ma’lumotlar tuzilmalari odatda ikkilik uyumlar (binary heap) kabi daraxtlar yordamida amalga oshiriladi.
Daraxt terminologiyasi va qoidalari
Quyidagi interaktiv daraxt vizualizatsiyasidan foydalanib, daraxt ma’lumotlar tuzilmasini tasvirlashda ishlatiladigan so‘zlarni o‘rganing.
Daraxtdagi birinchi tugun ildiz tugun deb ataladi.
Bir tugunni boshqasiga bog‘laydigan bog‘lanish qirra (edge) deb ataladi.
Ota tugun o‘zining bola tugunlariga bog‘lanishlarga ega. Ota tugunning boshqa nomi — ichki tugun.
Tugunning bola tugunlari bo‘lmasligi, bitta yoki ko‘p bo‘lishi mumkin.
Tugunning faqat bitta ota tuguni bo‘lishi mumkin.
Boshqa bola tugunlarga bog‘lanishi bo‘lmagan tugunlar barglar yoki barg tugunlar deb ataladi.
Daraxt balandligi — ildiz tugundan barg tugungacha bo‘lgan qirralarning maksimal soni. Yuqoridagi daraxtning balandligi 2 ga teng.
Tugun balandligi — tugun va barg tugun orasidagi qirralarning maksimal soni.
Daraxt o‘lchami — daraxtdagi tugunlar soni.
Daraxt turlari
Daraxtlar informatikadagi fundamental ma’lumotlar tuzilmasi bo‘lib, iyerarxik munosabatlarni ifodalash uchun ishlatiladi. Ushbu darslikda daraxtlarning bir nechta asosiy turlari ko‘rib chiqiladi.
Ikkilik daraxtlar: Har bir tugun ko‘pi bilan ikkita bolaga — chap bola tugun va o‘ng bola tugunga ega. Bu tuzilma ikkilik qidiruv daraxtlari va AVL daraxtlari kabi murakkabroq daraxt turlari uchun asos hisoblanadi.
Ikkilik qidiruv daraxtlari (BST): Ikkilik daraxtning shunday turiki, unda har bir tugun uchun chap bola tugun kichikroq qiymatga, o‘ng bola tugun esa kattaroq qiymatga ega.
AVL daraxtlari: O‘zini o‘zi muvozanatlaydigan ikkilik qidiruv daraxti turi bo‘lib, unda har bir tugun uchun chap va o‘ng qism daraxtlar balandliklari orasidagi farq ko‘pi bilan bittaga teng. Bu muvozanat tugunlar qo‘shilganda yoki o‘chirilganda aylantirishlar (rotation) orqali saqlab turiladi.
Bu ma’lumotlar tuzilmalarining har biri keyingi sahifalarda animatsiyalar va ularni qanday amalga oshirish bilan birga batafsil tasvirlangan.
DSA mashqlari
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!