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

LR – ikki marta chapga o`nga burish

• Bu usul o‘ng qismdaraxtning chap qismiga yangi element kiritilganda qo‘llaniladi
•  

AVL daraxtlarining xususiyatlari

• АВЛ daraxti oddiy ikkilik qidiruv daraxtidan bir nechta xususiyatlari bilan farq qiladi:
• u balandlikda muvozanatli. Har bir tugunning chap va o'ng avlodlari tomonidan hosil bo'lgan pastki daraxtlar uzunligi bir darajadan oshmasligi kerak;

birinchi xususiyatdan yana biri kelib chiqadi — daraxtning umumiy uzunligi va shunga mos ravishda u bilan ishlash tezligi logaritmik va kafolatlangan tugunlar soniga bog'liq;

• birinchi xususiyatdan yana biri kelib chiqadi — daraxtning umumiy uzunligi va shunga mos ravishda u bilan ishlash tezligi logaritmik va kafolatlangan tugunlar soniga bog'liq;
• kuchli muvozanatsiz AVL daraxtini olish ehtimoli juda kichik va uning buzilish xavfi deyarli yo'q.

Binar qidiruv daraxti

• Binar qidiruv daraxti
• AVL – daraxti

Bunday daraxtning muvozanati , ehtimollik bilan muvozanatlangan randomizatsiyalangan daraxtlardan farqli o'laroq kafolatlanadi — ya'ni ozgina ehtimollik bilan tuzilma yana paydo bo'lishi mumkin.

• Bunday daraxtning muvozanati , ehtimollik bilan muvozanatlangan randomizatsiyalangan daraxtlardan farqli o'laroq kafolatlanadi — ya'ni ozgina ehtimollik bilan tuzilma yana paydo bo'lishi mumkin.

Muvozanatlash nima?

• Balanslash-bu daraxtni yanada muvozanatli qiladigan operatsiya. AVL daraxtlari holatida, agar strukturaning asosiy qoidasi buzilgan bo'lsa, u ishlatiladi: daraxtlar ostida-bitta tugunning avlodlari bir darajadan ko'proq farq qila boshlaydi. Agar darajalar sonidagi farq 2 yoki -2 ga teng bo'lsa, muvozanat boshlanadi: ajdodlar va avlodlar o'rtasidagi aloqalar to'g'ri tuzilmani saqlab qolish uchun o'zgartiriladi va tiklanadi.

Odatda, buning uchun tugunlarning har biri chapga yoki o'ngga "aylanadi", ya'ni uning joylashishini o'zgartiradi. Joylashuv faqat bitta tugunni o'zgartirganda yoki katta bo'lsa, burilish oddiy bo'lishi mumkin: u bilan ikkita tugun turli yo'nalishlarda aylanadi. Katta burilish normal ishlamaydigan joyda samarali bo'ladi.

• Odatda, buning uchun tugunlarning har biri chapga yoki o'ngga "aylanadi", ya'ni uning joylashishini o'zgartiradi. Joylashuv faqat bitta tugunni o'zgartirganda yoki katta bo'lsa, burilish oddiy bo'lishi mumkin: u bilan ikkita tugun turli yo'nalishlarda aylanadi. Katta burilish normal ishlamaydigan joyda samarali bo'ladi.