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

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.