AVL ağacından bir düğümün silinmesi, ikili arama ağacındakine benzer. Silme, AVL ağacının denge faktörünü bozabilir ve bu nedenle AVL'yi korumak için ağacın yeniden dengelenmesi gerekir. Bunun için rotasyon yapmamız gerekiyor. İki dönme türü L dönüşü ve R dönüşüdür. Burada R rotasyonlarını tartışacağız. L dönüşleri bunların ayna görüntüleridir.

Silinecek düğüm kritik düğümün sol alt ağacında mevcutsa, silinecek düğüm kritik düğümün sağ alt ağacında mevcutsa L rotasyonunun uygulanması gerekir. R rotasyonu uygulanacaktır.

A'nın kritik düğüm ve B'nin sol alt ağacının kök düğümü olduğunu düşünelim. A'nın sağ alt ağacında bulunan X düğümü silinecekse üç farklı durum olabilir:

R0 dönüşü (Düğüm B'nin denge faktörü 0'dır)

B düğümünün denge faktörü 0 ise ve X düğümünün silinmesiyle A düğümünün denge faktörü bozulursa, o zaman ağaç, R0 döndürme kullanılarak ağaç döndürülerek yeniden dengelenecektir.

Kritik düğüm A, sağına taşınır ve B düğümü, sol alt ağacı T1 olacak şekilde ağacın kökü olur. T2 ve T3 alt ağaçları, A düğümünün sol ve sağ alt ağaçları haline gelir. R0 rotasyonunda yer alan süreç aşağıdaki resimde gösterilmektedir.

Örnek:

Aşağıdaki resimde gösterilen AVL ağacından 30 numaralı düğümü silin.

Çözüm

Bu durumda B düğümünün denge faktörü 0'dır, bu nedenle ağaç aşağıdaki görüntüde gösterildiği gibi R0 döndürme kullanılarak döndürülecektir. B(10) düğümü kök haline gelirken, A düğümü sağına doğru hareket ettirilir. B düğümünün sağ çocuğu artık A düğümünün sol çocuğu olacaktır.

java dosyayı satır satır oku

R1 Rotasyonu (Düğüm B denge faktörü 1'e sahiptir)

Düğüm B'nin denge faktörü 1 ise R1 Döndürme gerçekleştirilecektir. R1 döndürmede, kritik düğüm A, sırasıyla sol ve sağ çocuğu olarak T2 ve T3 alt ağaçlarına sahip olacak şekilde sağa doğru hareket ettirilir. T1, B düğümünün sol alt ağacı olarak yerleştirilecektir.

R1 rotasyonunda yer alan süreç aşağıdaki resimde gösterilmektedir.

Örnek

Aşağıdaki resimde gösterilen AVL ağacından Düğüm 55'i silin.

Çözüm :

AVL Ağacından 55'in silinmesi, 50 nolu düğümün, yani kritik düğüm haline gelen A düğümünün denge faktörünü bozar. Bu, A düğümünün sağa doğru hareket edeceği R1 rotasyonunun durumudur (aşağıdaki resimde gösterilmektedir). B'nin sağı artık A'nın solu haline geldi (yani 45).

Çözümde yer alan süreç aşağıdaki resimde gösterilmektedir.

javascript

R-1 Rotasyonu (Düğüm B'nin denge faktörü -1'dir)

B düğümünün denge faktörü -1'e sahip olması durumunda R-1 dönüşü gerçekleştirilecektir. Bu durum LR rotasyonuyla aynı şekilde ele alınır. Bu durumda, B düğümünün sağ çocuğu olan C düğümü, sırasıyla B ve A'nın sol ve sağ çocukları olacak şekilde ağacın kök düğümü olur.

T1, T2 alt ağaçları B'nin sol ve sağ alt ağaçları olurken, T3, T4 A'nın sol ve sağ alt ağaçları olur.

R-1 rotasyonunda yer alan süreç aşağıdaki resimde gösterilmektedir.

Örnek

Aşağıdaki resimde gösterilen AVL ağacından 60 nolu düğümü silin.

Çözüm:

bu durumda B düğümü denge faktörü -1'e sahiptir. Düğümün (60) silinmesi, düğümün (50) denge faktörünü bozar, dolayısıyla R-1 döndürülmesi gerekir. C düğümü, yani 45, B(40) ve A(50) düğümünün sol ve sağ çocuğu olduğu ağacın kökü olur.