11
Tugunning muvozanatganliklik koeffitsienti
Бу қисмдарахт баландиги =1
11
Tugunning muvozanatganliklik koeffitsienti
Бу АВЛ дарахт эмас
Бу қисмдарахт баландиги =1
11
- 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 - 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 LR – ikki marta chapga o`nga burish - 2. yangi darxtningР tugunini R burish
Daraxt muvozanatlandi LR – ikki marta chapga o`nga burish LR – ikki marta chapga o`nga burish - Bu usul o‘ng qismdaraxtning chap qismiga yangi element kiritilganda qo‘llaniladi
-
Do'stlaringiz bilan baham: |
