Mavzu: Dasturlash tilida sinflar. Do’stona funksiyalar. Inkapsulyasiya. Merosxo’rlik. Polimorfizm. Virtual funksiyalar. Ammallar va usullarni qayta ishlash va qayta aniqlash



Download 8,07 Kb.
Sana25.04.2023
Hajmi8,07 Kb.
#931769
Bog'liq
18-mavzu (Daraxtsimon ma\'lumotlar tuzilmalari. Binar va ko\'p tarmoqli daraxtlar. Ta\'riflar va xususiyatlar)

Mavzu: Daraxtsimon ma'lumotlar tuzilmalari. Binar va ko'p tarmoqli daraxtlar. Ta'riflar va xususiyatlar


Binar daraxt to’g’risida tushuncha.
Binar qidiruv daraxti tushunchasi.
Binar daraxtlarni qurish.
Binar daraxtlar ustuda amallar.
Reja:
Ta’rif 1. Ko'pi bilan ikkita tugundan iborat bo'lgan ierarxik ma'lumotlar tuzilmasiga binar (yoki ikkilik) daraxt deb ataladi.
Har bir tugun "chap" ko'rsatkichga, "o'ng" ko'rsatkichga va ma'lumotlar elementlarini o'z ichiga oladi.
"Ildiz" ko'rsatkichi daraxtning eng yuqori tugunini anglatadi.
Ikkilik (binar) daraxt

Ikkilik daraxt — har bir tuguni ikkitadan ko’p tugunga ega bo’lmagan iyerarxik ma’lumotlar tuzilmasidir. Odatda har bir asosiy tugunlar chap va o’ng yoki alohida tugunlardan tashkil topadi va vorislar deb yuritiladi.

  • Ikkilik daraxt — har bir tuguni ikkitadan ko’p tugunga ega bo’lmagan iyerarxik ma’lumotlar tuzilmasidir. Odatda har bir asosiy tugunlar chap va o’ng yoki alohida tugunlardan tashkil topadi va vorislar deb yuritiladi.
  • Binar daraxt— Bu iyerarxik ma’lumotlar tuzilmasi bo’lib, bunda har bir tugun o’z qiymatiga va ikkita (chap va o’ng) ko’rsatgichiga ya’ni vorisga ega bo’ladi.
  • Eng yuqori o’rinda joylashgan tugunga daraxt ildizi (yoki asosi, root) deb yuritiladi.
  • Vorisga ega bo’lmagan tugunlarga daraxt barglari deb yuritiladi.

Binar daraxt

Binar qidiruv daraxti:

Binar qidiruv daraxti:

Binar qidiruv daraxti deb qo’shimcha xususiyatlarga ega bo’lgan daraxtga aytiladi.

Bu xususiyatlar quyidagicha:

  • Chap vorisning qiymati shu “ota” qiymatidan kichik,
  • O’ng vorisning qiymati shu “ota” qiymatidan katta.
  • Aniq qilib aytadigan bo’lsak binar qidiruv daraxt tuzilmasi qatiiy tartiblangan shaklda saqlanadi.


Binar qidiruv daraxti
Muvozanatlangan binar qidiruv daraxti— bu logarifmik balandlikka ega binar qidiruv daraxtiga aytiladi.
Muvozanatlashgan binar qidiruv daraxt navbati bilan qo’shilgan elementlarni tezkor qidirishni amalga oshiradi.
Binar daraxtni tushunish uchun rekursiya, funksiya va ko’rsatkichlarni yaxshi tushunish talab etiladi.
Muvozanatlashgan binarqidiruv daraxt

Binar daraxtni tashkil etish uchun nimalar kerak?


1 ta element va 2 ta ko’rsatkichli maydon
Element – bu tugunga yozish kerak bo’lgan qiymat;
2 ta ko’rsatkich esa har bir tugun ikkitadan voris yaratishini anglatadi.
class Node{
int data;
Node left, right;
Node(int item){
data = item;
left = right = null;
}
}

Ta’riflar

  • Asosiy (ildiz) tugun — daraxtning eng yuqori tuguni (8 - tugun).
  • Ildiz — kuzatuvchining xohishiga qarab uchlardan biri.
  • Barg yoki terminal tugun— voris elementlarga ega bo’lmagan tugunlarga aytiladi (1, 4, 7, 13).
  • Ichki tugun —barg bo’lmagan vorisga ega ixtiyoriy tugunga aytiladi (3, 6, 10, 14).
  • Daraxt ildizga hech qanday tugun kirmasa, yo'naltirilgan deyiladi.
  • To'liq mahkamlangan kalit  — asosiy yozuvlar (guruhlar) misollarining barcha kalitlarini birlashtirish orqali hosil bo'lgan yozuv identifikatori.

Umumiy amallar

  • Ma’lum pozitsiyaga yangi element qo’shish;
  • Qism daraxt qo’shish;
  • Daraxt shoxachalarini kiritish;
  • Ixtiyoriy tugunlar uchun ildiz elementni izlash;
  • Bir xil qism daraxtlarni qidirish;
  • Elementlarni izlash;
  • Daraxt shohalarni o’chirish;
  • Qism daraxtni o’chirish;
  • Elementlarni o’chirish.

Umumiy qo’llanilishi


Ierarxik ma’lumotlarni boshqarish;
Qidiruvni soddalashtirish;
Saralashlarni boshqarish;
Arifmetik amallarni sintaksis to’g’riligini tashki etishda;
Turli vizual effektlar uchun raqamli rasmlarni birlashtirish texnologiyasi sifatida;
Ko'p bosqichli qaror qabul qilish shakli.
Qizil-qora daraxtlar muvozanatli ikkilik qidiruv daraxtlari.

“Qora-qizil” daraxt xususiyati:

1) Har bir tugun (voris) qora-qizil tartibda joylashgan bo’ladi. 2) Ildiz qora bo’ladi. 3) Barglar NULL (NIL) tugunlari qora rangda. 4) Har bir qizil tugunning ikkita qora tuguni bo'lishi kerak. Shuni ta'kidlash kerakki, qora tugunning qora rangli tugunlari bo'lishi mumkin. Qizil tugunlar tugunlarda faqat qora tugunlarga ega bo'lishi mumkin. 5) Tugundan uning barglarigacha bo'lgan yo'llar bir xil miqdordagi qora tugunlarni o'z ichiga olishi kerak.


void doubleTree(Node node){
Node oldleft;
if (node == null)
return;
/* do the subtrees */
doubleTree(node.left);
doubleTree(node.right);
/* duplicate this node to its left */
oldleft = node.left;
node.left = new Node(node.data);
node.left.left = oldleft;
}
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}

Daraxtning qo’llanilishi


Ikkilik qidiruv daraxti - ko’p dasturlash tillari kutubxonalaridagi map va set obyektlari kabi ma'lumotlar doimiy ravishda kiritiladigan/chaplangan ko'plab qidiruv ilovalarida qo'llaniladi.
Ikkilik fazo bo'limi - qaysi obyektlarni ko'rsatishni aniqlash uchun deyarli har bir 3D video o'yinida foydalaniladi.
Binary Tries - Router jadvallarini saqlash uchun deyarli har bir yuqori tarmoqli kengligi router tomonidan qo'llaniladi.
Download 8,07 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish