daraxt ko’rinishidagi ma’lumotlar tuzilmasi

DOC 18 стр. 274,0 КБ Бесплатная загрузка

18 стр.

FaylHub.uz

Скачать через Telegram

Размер 274,0 КБ

Тип файла DOC

Страницы 18

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 18

o‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi __universiteti ro’yxatga olindi №__________ ro’yxatga olindi №__________ “_____” ____________20 y. “_____” ____________20 y. “___________________________ “ kafedrasi “_____________________________ “ fanidan kurs ishi mavzu:________________ bajardi:_________________________________ tekshirdi:_______________________________ ______________ - 20___ muvozanatlangan daraxtlar va muvozanatlash algoritmlar. reja: 1. daraxt ko’rinishidagi ma’lumotlar tuzilmasi. 2. daraxtni muvozanatlash algoritmi. 3. binar daraxtni muvozanatlanganmi yoki yo’qligini tekshirish. 4.xulosa. 5.foydalanilgan adabiyotlar. daraxt ko’rinishidagi ma’lumotlar tuzilmasi. uzellar (elementlar) va ularning munosabatlaridan iborat elementlar to‟plamining ierarxik tuzilmasiga daraxtsimon ma‟lumotlar tuzilmasi deyiladi. daraxt – bu shunday chiziqsiz bog‟langan ma‟lumotlar tuzilmasiki, u quyidagi belgilari bilan tavsiflanadi: - daraxtda shunday bitta element borki, unga boshqa elementlardan murojaat yo‟q. bu element daraxt ildizi deyiladi; - daraxtda ixtiyoriy element chekli sondagi ko‟rsatkichlar yordamida boshqa tugunlarga murojaat qilishi mumkin; - daraxtning har bir elementi faqatgina o‟zidan oldingi kelgan bitta element bilan bog‟langan. binar daraxtlarni qurish. binar daraxtda har bir tugun-elementdan ko‟pi bilan 2 ta shox chiqadi. daraxtlarni xotirada tasvirlashda …

2 / 18

valambor daraxt ildizi bilan solishtiriladi. agar element ildiz kalit qiymatidan kichik bo‟lsa, uning chap shoxiga, aks holda o‟ng shoxiga o‟tiladi. agar o‟tib ketilgan shoxda tugun mavjud bo‟lsa, ushbu tugun bilan ham solishtirish amalga oshiriladi, aks holda, ya‟ni u shoxda tugun mavjud bo‟lmasa, bu element shu tugunga joylashtiriladi. masalan, daraxt tugunlari quyidagi qiymatlarga ega 6, 21, 48, 49, 52, 86, 101. u holda binar daraxt ko‟rinishi quyidagi 1-rasmdagidek bo‟ladi: 1-rasm natijada, o‟ng va chap qism daraxtlari bir xil bosqichli tartiblangan binar daraxt hosil qildik. agar daraxtning o‟ng va chap qism daraxtlari bosqichlarining farqi birdan kichik bo‟lsa, bunday daraxt ideal muvozanatlangan daraxt deyiladi. yuqorida hosil qilgan binar daraxtimiz ideal muvozanatlangan daraxtga misol bo‟ladi. daraxtni muvozanatlash algoritmini sal keyinroq ko‟rib chiqamiz. undan oldin binar daraxtni yaratish algoritmini o‟rganamiz. binar daraxt yaratish funksiyasi. binar daraxtni hosil qilish uchun kompyuter xotirasida elementlar quyidagi 2-rasmdagidek toifada bo‟lishi lozim. p v 2-rasm. binar daraxt elementining tuzilishi. p …

3 / 18

uning farzand tugunlari mavjud emas. qolgan elementlar ham shu kabi hosil 66 qilinib, kerakli joyga joylashtiriladi. ya‟ni kalit qiymati ildiz kalit qiymatidan kichik bo‟lgan elementlar chap shoxga, katta elementlar o‟ng tomonga joylashtiriladi. bunda agar yangi element birorta elementning u yoki bu tomoniga joylashishi kerak bo‟lsa, mos ravishda left yoki right maydonlarga yangi element adresi yozib qo‟yiladi. binar daraxtni hosil qilishda har bir element yuqorida ko‟rsatilgan toifada bo‟lishi kerak. lekin hozir biz o‟zlashtirish osonroq va tushunarli bo‟lishi uchun key va rec maydonlarni bitta qilib info maydon deb ishlatamiz. 3-rasm. binar daraxt elementining tuzilishi ushbu toifada element hosil qilish uchun oldin bu toifani yaratib olishimiz kerak. uni turli usullar bilan amalga oshirish mumkin. masalan, node nomli yangi toifa yaratamiz: class node{ public: int info; node *left; node *right; }; endi yuqoridagi belgilashlarda keltirilgan ko‟rsatkichlarni shu toifada yaratib olamiz. node *tree=null; node *next=null; int n, key; cout >n; nechta element (n) kiritilishini aniqlab …

4 / 18

ili mavjud. ularni berilgan daraxt misolida ko‟rib chiqaylik: 1) yuqoridan pastga ko‟rik (daraxt ildizini qism daraxtlarga nisbatan oldinroq ko‟rikdan o‟tkaziladi): a, b, c ; 2) chapdan o‟ngga: b, a, c ; 3) quyidan yuqoriga (ildiz qism daraxtlardan keyin ko‟riladi): b, c, a . daraxt ko‟rigi ko‟pincha ikkinchi usul bilan, ya‟ni tugunlarga kirish ularning kalit qiymatlarini o‟sish tartibida amalga oshiriladi. daraxtni muvozanatlash algoritmi. binar daraxt muvozanatlangan yoki avl-muvozanatlangan bo‟lishi mumkin. daraxt avl-muvozanatlangan (1962 yil sovet olimlari аdelson, velsk 76 georgiy maksimovich va landis yevgeniya mihaylovichlar tomonidan taklif qilingan) deyiladi, agar daraxtdagi har bir tugunning chap va o‟ng qismdaraxtlari balandliklari farqi 1 tadan ko‟p bo‟lmasa. berilgan butun sonlar – kalitlar ketma-ketligidan binar daraxt yaratib olamiz va uni muvozanatlaymiz. daraxtni muvozanatlashdan maqsad, bunday daraxtga yangi element kiritish va daraxtdan element izlash algoritmi samaradorligini oshirishdan iborat, ya‟ni bu amallarni bajarishdagi solishtirishlar soni kamayadi. binar daraxtni muvozanatlash algoritmi quyidagicha bo‟ladi. algoritm 1. binar daraxtni yaratib …

5 / 18

$g qismdaraxtini hosil qilish uchun massivning ko‟rilayotgan oralig‟ining 2-yarmini olamiz, ya‟ni start=mid+1 va end=end (oldingi qadamdagi end). 3-5 qadamlarni takrorlaymiz. datur kodi : node *new_tree(int *arr, int start, int end) { if(start>end) return null; else { int mid=(start+end)/2; node *tree=new node; tree->info=arr[mid]; tree->left=new_tree(arr,start,mid-1); tree->right=new_tree(arr,mid+1,end); return tree; } } binar daraxt balandligi. binar daraxtning balandligi deb daraxt bosqichlari soniga aytiladi. binar daraxt balandligini aniqlash uchun uning har bir tuguni chap va o‟ng qismdaraxtlari balandliklari solishtiriladi va maksimal qiymat balandlik deb olinadi. daraxt balandligini aniqlash dastur kodini keltiramiz. int height(node *tree){ int h1,h2; if (tree==null) return (-1); else { h1 = height(tree->left); h2 = height(tree->right); if (h1>h2) return (1 + h1); else return (1 + h2); } } binar daraxtni muvozanatlanganmi yoki yo’qligini tekshirish. daraxtning balandligini aniqlashni o‟rganganimizdan keyin uning muvozanatlanganligini tekshirish mumkin. binar daraxtning muvozanatlanganligini tekshirish uchun uning har bir tugunini har ikkala qismdaraxti balandliklarini hisoblab, farqlarini tekshirib ko‟rish kerak. agar …$

Хотите читать дальше?

Скачайте все 18 страниц бесплатно через Telegram.

Скачать полный файл

О "daraxt ko’rinishidagi ma’lumotlar tuzilmasi"

o‘zbekiston respublikasi oliy ta’lim, fan va innovatsiyalar vazirligi __universiteti ro’yxatga olindi №__________ ro’yxatga olindi №__________ “_____” ____________20 y. “_____” ____________20 y. “___________________________ “ kafedrasi “_____________________________ “ fanidan kurs ishi mavzu:________________ bajardi:_________________________________ tekshirdi:_______________________________ ______________ - 20___ muvozanatlangan daraxtlar va muvozanatlash algoritmlar. reja: 1. daraxt ko’rinishidagi ma’lumotlar tuzilmasi. 2. daraxtni muvozanatlash algoritmi. 3. binar daraxtni muvozanatlanganmi yoki yo’qligini tekshirish. 4.xulosa. 5.foydalanilgan adabiyotlar. daraxt ko’rinishidagi ma’lumotlar tuzilmasi. uzellar (elementlar) va ularning munosabatlaridan iborat elementlar to‟plamining ierarxi...

Этот файл содержит 18 стр. в формате DOC (274,0 КБ). Чтобы скачать "daraxt ko’rinishidagi ma’lumotlar tuzilmasi", нажмите кнопку Telegram слева.

Теги: daraxt ko’rinishidagi ma’lumotl… DOC 18 стр. Бесплатная загрузка Telegram