|
Muvozanatlashgan daraxtlar haqidagi teoremaBog'liq ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARIMuvozanatlashgan daraxtlar haqidagi teorema.
Adelson-Velskiy
va Landis quyidagi teoremani isbotladilar:
Teorema
. n ichki tugunli muvozanatli daraxt balandligi
va
qiymatlar bilan chegaralangan.
Shunday qilib, biz AVL-muvozanatlangan daraxtdagi qidirish yoʻli
mukammal muvozanatlangan daraxtdagi qidirish yoʻlidan 45% dan
oshmaydi degan xulosaga kelishimiz mumkin.
AVL daraxtiga yangi tugun kiritilganda paydo boʻladigan
variantlarni koʻrib chiqaylik:
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
|
| |
