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

Tugun balandligi

11

Tugunning muvozanatganliklik koeffitsienti

Бу қисмдарахт баландиги =1
11

Tugunning muvozanatganliklik koeffitsienti

Бу АВЛ дарахт эмас
Бу қисмдарахт баландиги =1
11

Muvozanatlash algoritmlari

• Daraxtga yangi element qo‘shilgach, tugunlarning muvozanat koeffitsientlarini yangilab chiqish kerak bo‘ladi. Agar bironta tugunning bu parametri 2 yoki -2 ga teng bo‘lsa, u xolda bu qism daraxtni burish usuli bilan muvozanatlash kerak. Burib muvozanatlash algoritmining bir nechta usullari mavjud.
• R – bir marta o‘ngga burish ;
• L – bir marta chapga burish ;
• LR – chapga va o‘ngga burish;
• RL – o‘ngga va chapga burish.
•  

R – bir marta o`nga burish

• CHap qismdaraxtga 1 qo‘shildi
• Daraxt muvozanatlanmagan
• H(Left)=1 > H(Right)=-1
• O‘ng qismdaraxt balandligini oshirish kerak.
•  

R – bir marta o`nga burish

Ildiz va chap tugunni bog‘lovchi yoyni o‘ngga buramiz. Daraxt muvozanatlandi..

R – bir marta o`nga burish

• CHap qism daraxtga yangi X element qo‘shildi.
• Daraxt muvozanatlanmagan
• H(Left) > H(Right)
•  

R – bir marta o`nga burish

L – bir marta chapga burish

• O‘ng qismdaraxtga 3 qo‘shildi. Ildiz va o‘ng tugunni bog‘lovchi yoyni chapga buramiz.
•  

L – bir marta chapga burish

O‘ng qismdaraxtga yangi element X qo‘shildi.
Ildiz va o‘ng tugunni birlashtiruvchi yoyni chapga buramiz.

LR – ikki marta chapga o`nga burish

• Ushbu algoritm ildiz chap tugunining o‘ng qismdaraxtiga yangi element kiritilganda qo‘llaniladi.
• 1. R ning chap qismini chapga L burish
•  

LR – ikki marta chapga o`nga burish

• 2. yangi darxtningР tugunini R burish