Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti nurafshon filiali

6. Bir burilish bilan balanslarni tartibga solish
Belgilang:

"Joriy" - balansi -2 yoki 2 bo'lgan tugun: ya'ni aylantirilishi kerak bo'lgan tugun (diagrammada - element a)

"Pivot" - timsolning o'qi. +2: oqimning chap bolasi, −2: oqimning o‘ng bolasi (diagrammadagi b elementi)

Agar element o'rnatilganda aylanish amalga oshirilsa, Pivot balansi 1 yoki -1 bo'ladi. Boshqa holatda, qarama-qarshi tomonlarning muvozanat satrini aylantirgandan so'ng 0.

O'chirishda hamma narsa boshqacha bo'ladi: Pivot balansi mavjud bo'lishi mumkin 0 (buni shubha qilish oson).

Yakuniy balansning aylanish yo'nalishiga va Pivot boshlang'ich muvozanat tuguniga bog'liqligining umumiy diagrammasi berilgan:

Aylanish yo'nalishi Old Pivot.Balance New Current.Balance New Pivot.Balance

Chap yoki O'ng -1 yoki +1 0 0
O'ngga 0 -1 +1
Chapga 0 +1 -1


7. Ikki burilish bilan balanslarni tartibga solish
Pivot va Current bir xil, lekin navbatning uchinchi a'zosi ishlab chiqariladi. Keling, uni "pastki" deb belgilaymiz: u (ikki marta aylanish o'ngida) Rotaryning chap o'g'li va qo'sh chap bilan - Rotaryning o'ng o'g'li.

Burilish paytida - Past natijada har doim 0 ga etadi, ammo Pivot va Current uchun balanslarning joylashishi dastlabki balansga bog'liq.

Yakuniy balanslarning aylanish yo‘nalishi va boshlang‘ich balans tuguniga bog‘liqligining yig‘ma diagrammasi quyida keltirilgan.

Yo'nalish Old Bottom.Balance New Current.Balance New Pivot.Balance

Chap yoki o'ng 0 0 0
O'ngga +1 0 -1
O'ngga -1 +1 0
Chapga +1 -1 0
Chapga -1 0 +1
8. Ish faoliyatini baholash
G.M.Adelson-Velskiy va E.M.Landis o‘sish sur’atini isbotladilar, unga ko‘ra N ta ichki uchli AVL daraxtining balandligi log2(N+1) va 1,4404*log2(N+2)-0,328 nisbatiga to‘g‘ri keladi, ya’ni. , AVL daraxtining balandligi hech qachon mukammal muvozanatli daraxt balandligidan 45% dan oshmaydi. Katta N uchun u 1,04*log2(N) ga teng. Shunday qilib, 1 - 3 asosiy operatsiyalarni bajarish log 2 (N) taqqoslash tartibini talab qiladi. Eksperimental ravishda bitta muvozanatlash ikkita qo'shimchani va istisnolarni istisno qilishni talab qilishi aniqlandi.


Adabiyot
Wirth N. Algoritmlar va ma'lumotlar tuzilmalari M.: Mir, 1989. 4.5-bob (272-286-betlar)
G. M. Adelson-Velskiy, E. M. Landis. Axborotni tashkil qilish uchun bitta algoritm // Doklady AN SSSR. 1962. V. 146, No 2. S. 263–266.