Ağacların balanslaşdırılması: AVL-ağaclar

4.1 Balanssız ağacların problemləri

Adi (balanssız) ağaclarda elementlərin əlavə olunması zamanı xoşagəlməz təsirlər müşahidə edilə bilər.

1. Ağacın hündürlüyünün artması:

Balanssız ağaclarda hündürlük n-ə (burada n — düyünlərin sayı) çata bilər ki, bu da performansın pisləşməsinə səbəb olur.

Əsas əməliyyatların (axtarış, əlavə, silmə) icra müddəti ən pis halda O(n) olur.

2. Düyünlərin qeyri-bərabər paylanışı:

Balanssız ağaclarda bəzi alt ağaclar digərlərinə nisbətən daha çox düyünlərə malik ola bilər ki, bu da yaddaşın səmərəsiz istifadəsinə və emal müddətinin artmasına səbəb olur.

3. Əməliyyatların icra müddətinin pisləşməsi:

Balanssız ağaclarda axtarış, əlavə və silmə əməliyyatları ağacın hündürlüyünün artması səbəbindən daha çox vaxt tələb edir.

Balanssız ağacın nümunəsi:

Bu nümunədə ağac faktiki olaraq əlaqəli siyahıya çevrilir və əməliyyatların icra müddəti xətti olur.

4.2 AVL-ağacın tərifi və xüsusiyyətləri

AVL-ağac (öz ixtiraçıları Adelson-Velskiy və Landisin şərəfinə adlandırılmışdır) - balanslaşdırılmış binar axtarış ağacının növüdür, burada hər hansı bir node üçün sol və sağ subtree-lərin hündürlükləri arasındakı fərq 1-i keçmir.

AVL-ağacın xüsusiyyətləri:

1. Balanslaşdırılmışlıq:

Hər hansı bir node üçün sol və sağ subtree-lərin hündürlükləri arasındakı fərq 1-i keçmir.

Bu, ağacın hündürlüyünü O(log n) edir, burada n - node-ların sayıdır. Bu, axtarış, əlavə etmə və silmə əməliyyatlarının effektiv yerinə yetirilməsini təmin edir.

2. Binar axtarış ağacı:

AVL-ağac binar axtarış ağacının bütün xüsusiyyətlərinə malikdir: hər hansı bir node üçün sol subtree-dəki bütün açarlar node-un açarından kiçikdir, sağ subtree-dəki bütün açarlar isə node-un açarından böyüklər.

3. Avtomatik balanslaşdırma:

Hər yeni əlavə və ya silmə əməliyyatından sonra ağac balanslaşdırılır ki, onun xüsusiyyətləri saxlanılsın.

4.3 Ağacların balanslaşdırılması nümunələri

Döndürmələr — bu, AVL-ağacında balansı bərpa etmək üçün düyünlərin daxil edilməsi və ya silinməsi sonrası icra edilən əməliyyatlardır. Dörd növ döndürmə mövcuddur: sol, sağ, sol-sağ və sağ-sol döndürmə.

1. Sol döndürmə (Left Rotation):

Sol döndürmədə düyün x yuxarı qalxır, onun sağ övlad düyünü y isə onun valideyni olur. y-nin sol alt ağacı x-in sağ alt ağacı olur.

2. Sağ döndürmə (Right Rotation):

Sağ döndürmədə düyün x yuxarı qalxır, onun sol övlad düyünü y isə onun valideyni olur. y-nin sağ alt ağacı x-in sol alt ağacı olur.

3. Sol-sağ döndürmə (Left-Right Rotation):

Əvvəlcə sol övlad düyünündə sol döndürmə, sonra isə əsas düyündə sağ döndürmə edilir.

4. Sağ-sol döndürmə (Right-Left Rotation):

Əvvəlcə sağ övlad düyünündə sağ döndürmə, sonra isə əsas düyündə sol döndürmə edilir.

4.4 AVL-ağaclarında əsas əməliyyatlar

AVL-ağaclarında əsas əməliyyatlara daxil etmə, silmə və axtarış daxildir.

Daxil etmə (Insertion)

Yeni bir node-u AVL-ağacına daxil etmək və lazım olduğu halda rəvanlaşdırmaq lazımdır.

Addımlar:

1. Node-un daxil edilməsi:
   • Ağacın kökündən başlayırıq və cari node-larla müqayisə edərək yeni node-un düzgün yerini rekursiv olaraq tapırıq.
   • Yeni node-u tapılan yerə adi binary search ağacında olduğu kimi əlavə edirik.
2. Hündürlüklərin yenilənməsi:
   • Daxil etmədən sonra yeni node-dan kökə qədər bütün node-ların hündürlüklərini yeniləyirik.
3. Ağacın balanslaşdırılması:
   • Yeni node-dan kökə qədər olan hər bir node-un balansını yoxlayırıq.
   • Əgər hər hansı bir node-un balansı pozulubsa (sol və sağ subağacların hündürlükləri arasındakı fərq 1-dən böyükdürsə), balansı bərpa etmək üçün uyğun rotation yerinə yetiririk.

Nümunə:

2. Silmə (Deletion)

AVL-ağacından node silmək və lazım olduğu halda rəvanlaşdırmaq lazımdır.

Addımlar:

1. Node-un tapılması və silinməsi:

• Ağacın kökündən başlayırıq və silinməli olan node-u rekursiv olaraq tapırıq.
• Node-u adi binary search ağacında olduğu kimi silirik:
• Əgər node leaf-dirsə, sadəcə onu silirik.
• Əgər node-un bir övladı varsa, node-u onun övladı ilə əvəz edirik.
• Əgər node-un iki övladı varsa, sağ subağacda ən kiçik node-u (və ya sol subağacda ən böyük node-u) tapırıq, onun dəyərini silinməsi tələb olunan node-a köçürürük və rekursiv olaraq sağ subağacda ən kiçik node-u silirik.

2. Hündürlüklərin yenilənməsi:

• Silinmədən sonra silinmiş node-dan kökə qədər bütün node-ların hündürlüklərini yeniləyirik.

3. Ağacın balanslaşdırılması:

• Silinmiş node-dan kökə qədər olan hər bir node-un balansını yoxlayırıq.
• Əgər hər hansı bir node-un balansı pozulubsa, balansı bərpa etmək üçün uyğun rotation yerinə yetiririk.

Nümunə:

3. Axtarış (Search)

AVL-ağacında verilmiş dəyərlə node tapmaq lazımdır.

Addımlar:

1. Rekursiv axtarış:

• Ağacın kökündən başlayırıq və axtarılan dəyəri cari node-larla rekursiv olaraq müqayisə edirik.
• Əgər dəyər cari node-dan kiçikdirsə, sol subağaca keçirik.
• Əgər dəyər cari node-dan böyükdürsə, sağ subağaca keçirik.
• Əgər dəyər cari node ilə eynidirsə, həmin node-u qaytarırıq.

Nümunə: