Muvozanatlashgan daraxtlar haqidagi teorema

121 
 
 
 
 
 
 
 
 
 
 
36-rasm. AVL ikkilik daraxtiga koʻra muvozanatlash 
 
• hl=hR. Yoqilgandan soʻng, L va R har xil balandliklarga aylanadi, 
ammo muvozanat mezonlari buzilmaydi; 
• hLmuvozanat mezonlari yanada yaxshilanadi; 
• hL>hR. Yoqilgandan soʻng muvozanat mezonlari buziladi va 
daraxtni qayta qurish kerak. 
Shunday qilib, biz AVL daraxtiga yangi tugunni kiritish uchun 
umumiy algoritmni tuzamiz: 
1. Kiritilgan daraxtning ichida emasligiga ishonch hosil qilish uchun 
daraxtni aylanib oʻtish; 
2. Yangi uchni kiritish va natijada balans koʻrsatkichini aniqlash; 
3. Qidiruv yoʻli boʻylab "orqaga chekinish" va har bir uchda balans 
koʻrsatkichini tekshirish. Agar kerak boʻlsa, muvozanatni saqlash. 
Amalda AVL balansini tiklashning 4 algoritmi qoʻllaniladi: 
muvozanat koʻrsatkichlari qiymatiga qarab tanlangan kichik va katta 
chap burilish, kichik va katta oʻng burilish (37-40-rasmlar) 
 

122 
37-rasm. Kichik chap burilish algoritmi 

Download 4,61 Mb.