15-mavzu: Muvozanatlangan ikkilik daraxtlar. Muvozanatlash algoritmlari: muvozanatlashning umumiy va hususiy algoritmlari. Avl daraxti

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.

Tugunlarni daraxtga kiritish

• Agar ma'lumotlar tuzilishiga yangi ma'lumotlar qo'shilishi kerak bo'lsa, bu ma'lum bir algoritmga muvofiq amalga oshirilishi kerak. Bu barcha ikkilik qidiruv daraxtlarida shundaydir, ammo AVL daraxtida algoritm biroz to'ldiriladi: kiritishdan keyin majburiy muvozanat keladi.

Kiritish. Tugunni daraxtga kiritish uchun har bir qadamda yangi tugunning qiymatini joriy tugun bilan taqqoslab, boshidan pastga o'tish kerak. Algoritm har qanday pastki daraxtning oxiriga etib boradi va yangi tugunni qiymatiga qarab uning o'ng yoki chap avlodiga aylantiradi. Shunday qilib, ikkilik qidiruv daraxtining asosiy qoidasi saqlanib qoladi-elementlarning qiymat bo'yicha joylashishini talab qilish.

• Kiritish. Tugunni daraxtga kiritish uchun har bir qadamda yangi tugunning qiymatini joriy tugun bilan taqqoslab, boshidan pastga o'tish kerak. Algoritm har qanday pastki daraxtning oxiriga etib boradi va yangi tugunni qiymatiga qarab uning o'ng yoki chap avlodiga aylantiradi. Shunday qilib, ikkilik qidiruv daraxtining asosiy qoidasi saqlanib qoladi-elementlarning qiymat bo'yicha joylashishini talab qilish.