11-Labaratoriya ishi. Mavzu: Daraxtlarning minimal balandligi



Download 155,56 Kb.
Sana03.04.2021
Hajmi155,56 Kb.
#62575
Bog'liq
Algoritm 11
Shorobiddinov B HFX 4, Tekst boyicha savol tuzish (1), Tekst boyicha savol tuzish (1), Mundarij a Kirish-fayllar.org, Ustlik 230520220455, Action planning in learning auditory, qegwsh, Maykl Faradey, Zamonaviy iqtisodiyot-Sillabus(A.Kadirov) Lotincha, New Doc 2020-06-02 13.51.43, Маъруза матни (5), Маъруза матни (5), Маъруза матни (5), soliqlar va soliqqa tortish



11-Labaratoriya ishi.

Mavzu: Daraxtlarning minimal balandligi

Agar mening avvalgi postlarimdan birida u muvozanatli qidiruv daraxtlarini yaratish uchun zamonaviy zamonaviy yondashuv bo'lgan bo'lsa, unda bu yozuv AVL daraxtlarini yaratishga bag'ishlangan - ehtimol bu 1962 yilda bizning (o'sha paytdagi sovet) olimlarimiz Adelson tomonidan ixtiro qilingan muvozanatli ikkitomonlama qidiruv daraxtlari. -Velskiy va Landis. Tarmoqda AVL daraxtlarining ko'plab sotuvlarini topishingiz mumkin (masalan, bu erda), lekin men ko'rgan hamma narsa juda nekbinlikka ilhom bermaydi, ayniqsa agar siz hamma narsani noldan aniqlamoqchi bo'lsangiz.

Hamma joyda AVL daraxtlari qizil-qora daraxtlarga qaraganda sodda ekanligi ta'kidlanmoqda, ammo unga biriktirilgan kodga qarab, siz ushbu bayonotga shubha qila boshlaysiz. Aslida, barmoqlarda AVL daraxtlari qanday joylashtirilganligini tushuntirish istagi ushbu xabarni yozishga turtki bo'ldi. Taqdimot C ++ kodi bilan tasvirlangan.AVL daraxti, asosan, ikkilik qidiruv daraxti bo'lib, ularning kalitlari standart xususiyatga mos keladi: har qanday daraxt tugunining kaliti ushbu tugunning chap pastki qismidagi kalitlardan kam emas va ushbu tugunning pastki satridagi biron bir kalitdan ko'p emas. Bu AVL daraxtidan kerakli kalitni qidirish uchun standart algoritmdan foydalanishingiz mumkin degan ma'noni anglatadi. Oddiylik uchun, daraxtdagi barcha kalitlar butun bo'lib, takrorlanmaydi deb taxmin qilamiz.

AVL daraxtining o'ziga xos xususiyati shundaki, u quyidagi ma'noda muvozanatlangan: har qanday daraxt tugunlari uchun uning pastki pastki balandligi balandligi chap pastki daraxt balandligidan ko'pi bilan farq qiladi. Ushbu xususiyat daraxtning balandligi logaritmik ravishda tugunlar soniga bog'liq bo'lishi uchun etarli ekanligi isbotlandi: AVL daraxtining h balandligi n tugmachalari log2 (n + 1) dan 1.44 log2 (n + 2) - 0.328 oralig'ida. Ikkilamchi qidirish daraxtlarida (operatsiyalarni bajarish, tugunlarni kiritish va yo'q qilish) asosiy operatsiyalar uning balandligiga chiziqli bog'liq bo'lganligi sababli, biz ushbu algoritmlarning ishlash vaqtining daraxtda saqlanadigan kalitlar soniga kafolatlangan logaritmik bog'liqligini olamiz. Eslatib o'tamiz, tasodifiy qidiruv daraxtlari faqat ehtimollik ma'nosida muvozanatni ta'minlaydi: katta n uchun yuqori muvozanatsiz daraxtni olish ehtimoli, ahamiyatsiz bo'lsa ham, nolga teng emas.

Tugun tuzilishi

Biz AVL daraxtining tugunlarini quyidagi tuzilishga ega bo'lamiz:

struct node // структура для представления узлов дерева

{

int key;

unsigned char height;

node* left; node* right;

node(int k) { key = k; left = right = 0; height = 1; }

};

Kalit maydonchasi tugun tugmachasini saqlaydi, balandlik maydoni - bu tugunning ildizi bilan pastki qismning balandligi, chap va o'ng maydonlar chap va o'ng pastki qismlarga ishora qiladi. Oddiy konstruktor berilgan k tugmachasi bilan yangi tugun (balandlik 1) hosil qiladi.

An'anaga ko'ra, AVL daraxtining tugunlari balandlikni saqlamaydi, lekin o'ng va chap pastki daraxtlarning balandligidagi farq (balans koeffitsienti deb ataladi), ular faqat uchta, 1, 0 va 1 qiymatlarini olishi mumkin. Shunga qaramay, ushbu farq o'zgaruvchida saqlanib qolinadi, uning hajmi kamida bitta baytga teng (agar siz bunday qiymatlarni "samarali" qadoqlashning ba'zi hiyla-nayrang sxemalarini o'ylab topmasangiz). Eslatib o'tamiz, balandligi h <1.44 log2 (n + 2), bu, masalan, n = 109 (bir milliard tugmachasi, tugunlarni saqlash uchun 10 gigabaytdan ortiq xotira) bo'lganda, daraxt balandligi h = 44 qiymatidan oshmaydi, bu muvaffaqiyatli joylashtirilgan. muvozanat koeffitsienti bilan bir xil bayt xotirada. Shunday qilib, balandlikni saqlash bir tomondan daraxt tugunlari uchun ajratilgan xotira hajmini oshirmaydi, ammo boshqa tomondan ba'zi operatsiyalarni bajarishni sezilarli darajada osonlashtiradi.

Biz balandlik bilan bog'liq uchta yordamchi funktsiyani aniqlaymiz. Birinchisi - balandlik maydonchasi uchun o'rash, u nol ko'rsatkichlar bilan (bo'sh daraxtlar bilan) ishlashi mumkin:








node* balance(node* p) // балансировка узла p { fixheight(p); if( bfactor(p)==2 ) { if( bfactor(p->right) < 0 ) p->right = rotateright(p->right); return rotateleft(p); } if( bfactor(p)==-2 ) { if( bfactor(p->left) > 0 ) p->left = rotateleft(p->left); return rotateright(p); } return p; // балансировка не нужна }

Kalitlarni kiritish

Yangi kalit AVL daraxti ichiga, katta-kichiklikda, oddiy izlash daraxtlari singari kiritilgan: biz tugunni joriy tugun va solishtiriladigan kalitni taqqoslash natijasiga qarab harakatning o'ng yoki chap yo'nalishini tanlaymiz. Faqatgina farq shundaki, siz rekursiondan qaytganingizda (ya'ni, o'ng yoki chap pastki qatorga kalit kiritilganidan keyin va bu daraxt muvozanatlangan bo'lsa), hozirgi tugun muvozanatlanadi. Yo'l bo'ylab biron bir tugunga shunday kiritish natijasida kelib chiqadigan nomutanosiblik ikkitadan oshmasligi aniq isbotlangan, bu yuqorida tavsiflangan muvozanat funktsiyasini qo'llash to'g'ri ekanligini anglatadi.

Foydalangan adabiyotlar:

  1. M.Aripov, A.Haydarov,Informatika asoslari Toshkent 2002-yil.

  2. A.A.Abduqodirov , A.G’Hayitov.Axborot texnalogiyalari, Toshkent <> 2003-yil.

  3. Ziyonet.uz , yandex.uz ,google.

Download 155,56 Kb.

Do'stlaringiz bilan baham:




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

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
maxsus ta’lim
zbekiston respublikasi
axborot texnologiyalari
O’zbekiston respublikasi
guruh talabasi
nomidagi toshkent
o’rta maxsus
davlat pedagogika
texnologiyalari universiteti
toshkent axborot
xorazmiy nomidagi
Ўзбекистон республикаси
rivojlantirish vazirligi
pedagogika instituti
таълим вазирлиги
махсус таълим
haqida tushuncha
O'zbekiston respublikasi
tashkil etish
toshkent davlat
vazirligi muhammad
saqlash vazirligi
kommunikatsiyalarini rivojlantirish
respublikasi axborot
vazirligi toshkent
bilan ishlash
Toshkent davlat
uzbekistan coronavirus
sog'liqni saqlash
respublikasi sog'liqni
koronavirus covid
coronavirus covid
vazirligi koronavirus
risida sertifikat
qarshi emlanganlik
sertifikat ministry
covid vaccination
vaccination certificate
Ishdan maqsad
o’rta ta’lim
fanidan tayyorlagan
matematika fakulteti
haqida umumiy
fanidan mustaqil
moliya instituti
fanining predmeti
pedagogika universiteti
fanlar fakulteti
ta’limi vazirligi