Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti
Bajardi:Nuriddinov Boburbek
Takshirdi: Akbarova Marg’uba
Mavzu: AVL daraxti
Reja:
1.Mavzu bo’yicha ma’lumotlar
2.Amaliy ish
3.Ish natijasi
4.Xulosa
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.
|
