|
O‘zbekiston Respublikasi Raqamli texnalogiyalar vazirligi Muhammad Al-Xorazmiy
|
| bet | 2/4 | | Sana | 22.05.2024 | | Hajmi | 0,66 Mb. | | #250518 |
Bog'liq 3-deadline 615-22Amaliy qism:
12-Amaliy mashg‘ulot: Heap tree ko‘rinishidagi binary daraxtlar bilan ishlash algoritmlari.
Ishdan maqsad. Ushbu amaliyot ishida talabalar Heap tree ko‘rinishidagi binary daraxtlar bilan ishlash algoritmlari bilan tanishib chiqishlari kerak
Qo‘yilgan masala. Talabalar topshiriq variantiga mos ravishda Heep tree darxtlar ustida berilgan amallar bilan ishlash ko‘nikmasiga ega bo‘lishlari kerak.
Ish tartibi:
Tajriba ishi nazariy ma’lumotlarini o‘rganish;
Berilgan topshiriqning algoritmini ishlab chiqish;
C++ dasturlash muhitida dasturni yaratish;
Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
Heap tree(bosh daraxt), qulaylik va tezlik bilan ko‘p miqyosli ma’lumotlarni o‘z ichiga olish uchun ishlatiladi. Quyidagi algoritmlar bosh daraxtlar bilan ishlash uchun bazi asosiy operatsiyalardir:
Qo‘shish (Insertion): Yangi elementni bosh daraxtga qo‘shish uchun quyidagi qadamlar bajariladi:
Elementni daraxtning oxiriga qo‘shing.
Agar yangi element bosh daraxt qoidaga zarar yetkazmasa (ya’ni, bosh daraxtning barcha qoidalariga qarshi holda to‘g‘ri o‘tsa), unda bosh daraxtni tiklash uchun qoida alohida boshqaruvchiga o‘tkazing (masalan, “heapify_up” funksiyasiga).
O‘chirish (Deletion): Bosh daraxtning eng yirik elementini (o‘rniga bosh elementni) o‘chirish uchun quyidagi qadamlar bajariladi:
Bosh elementni o‘chirib, daraxtning oxiridagi eng kichik elementni bosh
elementning o‘rniga ko‘chirish.
Agar daraxtning oxiridagi element bosh daraxtning barcha qoidalariga qarshi
holda to‘g‘ri o‘tkazmasa, unda daraxtni tiklash uchun “heapify_down” funksiyasiga qarshi holda barcha qoidalarga to‘g‘ri o‘tsa qadamlar bajariladi.
Bosh daraxtni tiklash (Heapify): Bosh daraxtning tuzilishi qoidalariga mos keladigan holatga keltirish uchun “heapify” funksiyasi ishlatiladi. Buni ikki turdagi funksiyalar amalga oshiradi:
heapify_up: Bu funksiya yangi elementni bosh daraxtga qo‘shishdan so‘ng
uning o‘zi bosh daraxtni tiklash uchun ishlatiladi. Element bosh daraxtni ustiga chiqsa, u o‘rniga yo‘qotiladi va uning o‘zi bilan bir o‘rin pastdagi elementni solishtirib olish uchun qoidalar bilan solishtiriladi.
heapify_dow: Bu funksiya o‘chirilgan elementning o‘rnini to‘g‘ri olish uchun ishlatiladi. O‘chirilgan element bosh daraxtning oxiri bilan solishtirilib, qoidalarga mos kelishi va barcha qoidalar bilan to‘g‘ri o‘tish qoidalariga amal qilish uchun barcha qoidalarga solishtiriladi.
|
| |
