“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Natijada quyidagicha muvozanatlangan binar daraxt hosil bo‘ladi. Oldingi ko‘rinishida daraxt balandligi 4 ga teng edi. Endi esa 3 ga teng. Lekin bu algoritmning bir muncha noqulayligi bor.

• Natijada quyidagicha muvozanatlangan binar daraxt hosil bo‘ladi. Oldingi ko‘rinishida daraxt balandligi 4 ga teng edi. Endi esa 3 ga teng. Lekin bu algoritmning bir muncha noqulayligi bor.
• - Oldin daraxtni chapdan o‘ngga skanerlab elementlardan massiv hosil qilish kerak.
• Bu esa xotiradan joy talab etadi.
• Bu usulda daraxtni boshqatdan qurish kerak

bo‘ladi. Keyinchalik muvozanatlashning

boshqa algoritmlari ishlab chiqilgan.

19
30
23
15
3
12
29
44
16

Binar daraxtlar bilan ishlaganda unga element qo‘shish yoki o‘chirishda uning muvozanatlanganligi buzilishi mumkin. Bunday xollarda uni muvozanatlab turish kerak. Muvozanatlangan daraxt ko‘rinishlari:

• Binar daraxtlar bilan ishlaganda unga element qo‘shish yoki o‘chirishda uning muvozanatlanganligi buzilishi mumkin. Bunday xollarda uni muvozanatlab turish kerak. Muvozanatlangan daraxt ko‘rinishlari:
• AVL daraxt
• Qora-qizil daraxt
• B-daraxt va x.k.
•  

AVL-daraxt

• AVL-daraxtining nomi uning mualliflari ismlari bosh xarflaridan olingan bo‘lib, ular – sovet matematiklari Georgiy Maksimovich Adelson-Velskiy va Evgeniy Mixaylovich Landis, 1962 yil ushbu muvozanatlangan AVL daraxtni taklif etishgan.
• AVL daraxt bu muvozanatlangan binar daraxt bo‘lib, unda xar bir tugunning o‘ng va chap qism daraxtlari balandliklari orasidagi farq 1 dan katta emas.
• AVL daraxtda xar bir tugunning muvozanatlanganlik darajasi xaqidagi ma’lumotni saqlash uchun xar bir tugunga qo‘shimcha maydon kiritiladi.
•  

AVL-daraxti

• Asosiy g‘oya: agar element ko‘shish, o‘chirish amallarida muvozanat buzilsa, u xolda daraxt muvozanatlanadi
• Tugunning muvozanatlanganlik koeffitsienti (balance factor) bu tugunning chap va o‘ng qism daraxtlari balandligi farqi
• AVL daraxtda xar bir tugunning muvozanatlanganlik koeffitsienti (-1, 0, 1) to‘plamdan qiymat qabul qiladi
• Tugun balandligi (height) bu undan eng uzoq joylashgan barg tugungacha bo‘lgan balandlik xisoblanadi.
• Barg tugunnning balandligi 0 ga teng.
• Bo‘sh qism daraxtning balandligi -1 ga teng.