Daraxtlar
Daraxt - bu qirralar bilan bog‘langan tugunlardan tashkil topgan ierarxik ma’lumotlar strukturasi.
Har bir tugun o‘zining kichik tugunlariga qiymat va havolalarni o‘z ichiga oladi.
Daraxtlar
Daraxt ma’lumotlar strukturasi bog‘langan listlarga o‘xshaydi, chunki har bir tugun ma’lumotlarni o‘z ichiga oladi va boshqa tugunlarga bog‘lanishi mumkin.
Biz ilgari massivlar, bog‘langan listlar, steklar va navbatlar kabi ma’lumotlar tuzilmalarini ko‘rib chiqdik. Bularning barchasi chiziqli tuzilmalardir, ya’ni har bir element ketma-ketlikda to‘g‘ridan-to‘g‘ri boshqasidan keyin keladi. Biroq, daraxtlar boshqacha. Daraxtda bitta element bir nechta "keyingi" elementlarga ega bo‘lishi mumkin, bu esa ma’lumotlar strukturasini turli yo‘nalishlarda tarmoqqa ajratish imkonini beradi.
Ma’lumotlar strukturasi "daraxt" deb ataladi, chunki u daraxt tuzilishiga o‘xshaydi.
Daraxt ma’lumotlar strukturasi ko‘p hollarda foydali bo‘lishi mumkin:
- Ierarxik ma’lumotlar: fayl tizimlari, tashkiliy modellar va boshqalar.
- Ma’lumotlar bazalari: Tez ma’lumotlarni olish uchun ishlatiladi.
- Marshrutlash jadvallari: Tarmoq algoritmlarida ma’lumotlarni marshrutlash uchun ishlatiladi.
- Saralash/Qidiruv: Ma’lumotlarni saralash va ma’lumotlarni qidirish uchun ishlatiladi.
- Prioritet navbatlar: Prioritet navbat ma’lumotlar tuzilmalari odatda daraxtlar yordamida amalga oshiriladi, masalan, ikkilik to‘plar.
Daraxt turlari
Daraxtlar ierarxik munosabatlarni ifodalash uchun foydalaniladigan informatika fanidagi asosiy ma’lumotlar strukturasidir. Ushbu qo‘llanma bir nechta asosiy daraxt turlarini o‘z ichiga oladi.
Ikkilik daraxtlar: Har bir tugunning ikkitagacha bolasi bor, chap tugun va o‘ng tugun. Ushbu tuzilma Binay Search Trees va AVL Trees kabi murakkabroq daraxt turlari uchun asosdir.
Ikkilik qidiruv daraxtlari (BSTs): Ikkilik daraxtning bir turi, bunda har bir tugun uchun chap pastki tugun pastroq qiymatga ega va o‘ng pastki tugun yuqoriroq qiymatga ega.
AVL daraxtlari: Har bir tugun uchun chap va o‘ng pastki daraxtlar orasidagi balandlik farqi ko‘pi bilan bitta bo‘lishi uchun o‘z-o‘zini muvozanatlashtiradigan ikkilik qidiruv daraxti turi. Ushbu muvozanat tugunlar kiritilganda yoki o‘chirilganda aylanishlar orqali saqlanadi.
Ushbu ma’lumotlar tuzilmalarining har biri keyingi sahifalarda, jumladan, animatsiyalar va ularni qanday amalga oshirish haqida batafsil tavsiflangan.
Daraxtlar va massivlar va bog‘langan listlar
Daraxtlarning massivlar va bog‘langan listlarga nisbatan afzalliklari:
- Agar siz to‘g‘ridan-to‘g‘ri elementga kirishni xohlasangiz, massivlar tez bo‘ladi, masalan, 1000 elementli massivdagi 700 element raqami. Lekin elementlarni kiritish va o‘chirish yangi elementga joy bo‘shatish yoki o‘chirilgan elementlarni o‘z o‘rnini egallash uchun boshqa elementlarning xotirada siljishini talab qiladi va bu ko‘p vaqt talab etadi.
- Bog‘langan listlar tugunlarni kiritish yoki o‘chirishda tez ishlaydi, xotirani o‘zgartirish shart emas, lekin list ichidagi elementga kirish uchun listni kesib o‘tish kerak va bu vaqt talab etadi.
- Ikkilik daraxtlar, Ikkilik qidiruv daraxtlari va AVL daraxtlari kabi daraxtlar massivlar va bog‘langan ro‘yxatlar bilan solishtirganda juda yaxshi, chunki ular tugunga tez kirishadi va tugunni o‘chirish yoki kiritishda ham tezdir, xotirada hech qanday o‘zgarishlar talab qilinmaydi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!