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

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.

Muvozanatlash(Balanslash). Bu erda AVL daraxtlarining o'ziga xos xususiyati shundaki, kiritilgandan so'ng, pastki daraxtlar uzunligining nisbatlarini tekshirish kerak va agar kerak bo'lsa, muvozanatni saqlash kerak. Bundan tashqari, daraxtning bir necha darajalari uchun muvozanatni saqlash kerak bo'lishi mumkin — bu normal holat.

• Muvozanatlash(Balanslash). Bu erda AVL daraxtlarining o'ziga xos xususiyati shundaki, kiritilgandan so'ng, pastki daraxtlar uzunligining nisbatlarini tekshirish kerak va agar kerak bo'lsa, muvozanatni saqlash kerak. Bundan tashqari, daraxtning bir necha darajalari uchun muvozanatni saqlash kerak bo'lishi mumkin — bu normal holat.

Muvozanatlash algoritmi boshlang'ich tugundan pastga tushishi yoki yangi qo'shilganidan yuqoriga ko'tarilishi mumkin, yo'l davomida balandlik farqini qayta hisoblab chiqadi va agar biron bir joyda ikki darajadagi farq aniqlansa, burilishlar qiladi. Balanslash barcha balandlik qiymatlari qayta hisoblab chiqilguncha va muvozanat bartaraf etilgunga qadar davom etadi.

• Muvozanatlash algoritmi boshlang'ich tugundan pastga tushishi yoki yangi qo'shilganidan yuqoriga ko'tarilishi mumkin, yo'l davomida balandlik farqini qayta hisoblab chiqadi va agar biron bir joyda ikki darajadagi farq aniqlansa, burilishlar qiladi. Balanslash barcha balandlik qiymatlari qayta hisoblab chiqilguncha va muvozanat bartaraf etilgunga qadar davom etadi.