Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti nurafshon filiali

О‘ZBEKISTON RESPUBLIKASI OLIY VA О‘RTA MAXSUS
TA’LIM VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT
AXBOROT TEXNOLOGIYALARI UNIVERSITETI
NURAFSHON FILIALI


MUSTAQIL ISH
Mavzu: AVL daraxti


Guruh nomi : 410-21
Bajardi: Reymova Zarafshan
Tekshirdi:Tosheva Muhabbat
Tashkent 2022
Mustaqil ish
AVL daraxti
Reja:
Kirish
1 Umumiy xususiyatlar
2 Balanslash
3 Cho'qqi qo'shish algoritmi
4 Cho'qqini o'chirish algoritmi
5 Olib tashlashdan keyin balanslarni tartibga solish
6 ta bir burilish uchun balanslar
7 Ikki marta aylanish balanslari
8 samaradorlikni baholash
Adabiyot


Kirish
AVL daraxti ikkilik qidiruv daraxti ustidagi o'rtacha balandlikdir: har bir cho'qqi uchun uning ikkita pastki daraxtining balandligi kamdan-kam hollarda 1 ga teng.

AVL - yaratuvchilar (sovet olimlari) Adelson-Velskiy, Georgiy Maksimovich va E. M. Landisning birinchi harflari bilan tuzilgan qisqartma.

1. Umumiy xususiyatlar
H balandlikdagi AVL daraxti kamida F h tugunlariga ega, bu erda F h Fibonachchi soni. kirish


-oltin nisbat,
u holda AVL daraxtining balandligida muhim ahamiyatga ega h = O ( l o g ( n )) , bu erda n - tugunlar soni. Shuni esda tutish kerakki, O ( l o g ( n )) katta mutaxassislik bo'lib, faqat baholash uchun ishlatilishi mumkin (Masalan, agar qishloqda faqat ikkita tugun bo'lsa, qishloqda ikkita daraja mavjud, garchi l o g (2) = 1). Yuqori yog'och ball uchun maxsus pastki dasturdan foydalanish kerak.

Funktsiya TreeDepth(Daraxt: TAVLTree): bayt;

boshlanishi
agar Tree <> nol bo'lsa
natija : = 1 + Maks ( Daraxt chuqurligi ( Daraxt ^ . chap ), Daraxt chuqurligi ( Daraxt ^ . o'ng ) )
boshqa
natija:= 0;
yakun ;
Daraxt turini quyidagicha ta'riflash mumkin
TKey = LongInt;
TIinfo = LongInt;
TB balansi = - 1 .. 1;
TAVLTree = ^ TAVLNode;
TAVLNode = rekord
chap, o'ng: TAVLTree;
kalit: TKey;
ma'lumot: TInfo;
{ Cho'qqi balansini baholovchi maydon }
balans: TBbalance;
yakun ;


2. Balanslash
AVL daraxtiga nisbatan cho‘qqini muvozanatlash amal deb ataladi, agar chap va o‘ng pastki daraxtlarning balandlik farqi = 2 bo‘lsa, ushbu cho‘qqining pastki daraxtidagi ota-bola aloqalarini o‘zgartiradi, shunda farq <= 1 ga aylanadi, aks holda. hech narsa o'zgarmaydi. Belgilangan natija bu tepada daraxt ostida tug'iladi.

4 turdagi aylanishlar qo'llaniladi:

1. Kichik chap aylanish



Yo'naltiruvchi qiymat (b-subtree balandligi - L balandligi) = 2 va C balandligi <= R balandligi bo'lganda ishlatiladi.

2. Katta chap aylanish

Bu chaqiruv (b-pastki daraxt balandligi - L balandligi) = 2 va c-kichik daraxt balandligi > R balandligi bo'lganda ishlatiladi.

3. Kichik o'ngga aylanish

Yo'naltiruvchi qiymat (b-subtree balandligi - R balandligi) = 2 va C balandligi <= L balandligi bo'lganda ishlatiladi.
4. Katta o'ngga aylanish

Bu chaqiruv (b-pastki daraxt balandligi - R balandligi) = 2 va c-kichik daraxt balandligi > L balandligi bo'lganda foydalaniladi.

Har bir holatda, ishlab chiqarish operatsiyasi kerakli natijani berishi va ishlab chiqarishning o'sishi eng ko'p 1 bo'lishi va ko'payib bo'lmasligini oddiygina tushuntirish kifoya.

Daraxt balandligini muvozanatlash shartlari tufayli O(lg(N)), bu erda N - uchlari soni, shuning uchun O(lg(N)) operatsiyalari elementini qo'shish talab qilinadi.