11-Labaratoriya ishi. Mavzu: Daraxtlarning minimal balandligi



Download 155,56 Kb.
Sana03.04.2021
Hajmi155,56 Kb.
#62575
Bog'liq
Algoritm 11




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 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