11-Labaratoriya ishi. Mavzu: Daraxtlarning minimal balandligi

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.