Home / Algoritmalar / AVL Ağacı Döndürme İşlemleri

AVL Ağacı Döndürme İşlemleri

AVL Ağaçları, İkili Arama ağaçları üzerinde dengelemeyi hedefler. Dengeleme işleminin temel amacı da algoritma karmaşıklığını azaltmaya yönelik bir eylemdir. İkili arama ağacına istediğiniz kadar eleman ekleyin, akıllı bir dengeleme mantığı yoktur. Ve doğal olarak da ağaç dengesiz olabilir. (mesela küçükten büyüğe doğru sayılar ekleyin, ağacın sağa doğru dengesizleştiğini göreceksiniz)

AVL Ağaçları dengeli ikili arama ağaçlarıdır. Bu ağaçların dengeli olabilmesi için AVL ağacı döndürme işlemleri gerçekleşir. Tabii ki öncelikli olarak ağaç dengesizliği nedir buna bir göz atalım.

Bir ağacın sol ya da sağ alt ağaçları arasındaki yükseklik 1’den fazlaysa, yani en az 2  ise dengesizlik bulunur. Dengesizliği gidermek için döndürme işlemleri gerçekleştirilir.

AVL Ağacı Dengesizlik Durumları

AVL Ağacında 4 temel dengesizlik durumu vardır. İsimlerini dengesizliğin bulunduğunu konuma göre almışlardır.

  • Sol Sol Dengesizliği (Left Left case)
  • Sağ Sağ Dengesizliği (Right right case)
  • Sol Sağ dengesizliği (Left Right Case)
  • Sağ Sol Dengesizliği (Right left case)

Sol Sol Dengesizliği

Dengesizlik ağacın sol tarafındadır ve dallanma sola doğru gerçekleşmiştir.

Yukarıdaki resme dikkat edin en tepedeki z düğümünün sağda sadece 1 adet çocuğu var (T4). Solda ise tam 3 tane. 3 – 1 = 2, yani aradaki fark 1’den büyük. (not yükseklik farkı hesap edilirken genelde kök düğümde sayılır bu durumda 4 – 2 = 2 olur, değişen bir şey olmaz).. Dengesizlik solun soluna doğru olduğu için sol – sol dengesizliği bulunmaktadır.

Sağ Sağ Dengesizliği

sağ sağ dengesizliğinde, ikili arama ağacında dengesizlik sağa doğrudur ve sağa doğru dallanmıştır.

Yukarıdaki resimde de gördüğünüz üzere z düğümünün soluna ve sağına baktığımızda dengesizliği göreceksiniz. Soldaki yükseklik 2 iken (z dahil), sağdaki yükseklik ise 4’tür (z dahil) bu durumda 2 fark oluşmaktadır. Bu da dengesizliği doğurur.

Sol Sağ Durumu

bu tip durumlar kafanızı karıştırabilir, karıştırmasın. Dengesizlik sola doğrudur, ancak dallanma sağa doğrudur. Aşağıda örneğimiz mevcut.

Resimde dikkat ettiyseniz ağaçta sol taraf daha derin, ancak y düğümünün sağa doğru derinleştiğini görüyoruz. Yani kök düğüme (z) göre sol taraf derin, ancak en derin düğüm (T3 ve T4) sağa doğru dallanmış. Bu yüzden Sol – Sağ dengesizliği adı veriyoruz. Eğer kafanız karıştıysa sol sol dengesizliğine tekrar bakın. Aradaki fark dallanmanın olduğu taraftır.

 

Sağ Sol Dengesizliği

Sağ sol dengesizliğinde dengesizlik sağa doğrudur, ancak sola doğru dallanma gerçekleşmiştir.

Artık anladığınızı umuyorum, z düğümünün sağ tarafının derinliği sol tarafından 2 daha fazladır. Bu yüzden dengesizlik sağa doğrudur. Ancak sağdaki dengesizlikte sola doğru dallanma gerçekleşmiştir. Bu yüzden sağ sol dengesizliği diyoruz.

 

Peki bu konu bu kadar mı? Daha durun yahu, biz sadece dengesizlik durumlarını tespit ettik 🙂 daha dengeleyeceğiz. Ama dengelemede iki temel işlem var. Bu işlemleri doğru noktalarda uygulayarak sonuca gideceğiz.

AVL Ağacı Döndürme İşlemleri

AVL ağacı dengesizlik durumlarını döndürme işlemleri ile yaparız. Döndürmedeki temel hedefimiz dengesizliği çözmektir, esasında ise o ağacın yüksekliğini azaltmaktır. Birazdan vereceğimiz örneklerde daha net göreceksiniz.

  • Sağa Döndürme İşlemi
  • Sola Döndürme İşlemi

Tüm dengesizlik durumlarını yukarıdaki iki işlemle rahatlıkla çözebiliriz. Şimdi AVL Ağacındaki dengesizlik durumlarını döndürme işlemleriyle nasıl çözüyoruz buna bakalım.

 

AVL Ağacı Dengeleme İşlemleri

AVL Ağacında 4 temel dengesizlik durumu vardı. (Az önce okumuştunuz ya hani 🙂 ) bu 4 temel durumu yukarıdaki iki döndürme işlemini kullanarak dengeleyeceğiz. Şimdi sıra ile bu işlemleri gerçekleştirelim.

AVL Ağacı Sol Sol Dengesizliği Çözümü – AVL Ağacı Sağa Döndürme

AVL ağaçlarında Sol Sol dengesizliğini sağa döndürerek çözeriz. Gayet akılda kalıcı bir şey, bir şey sola fazla giderse sağa alırız. bu kadar basit. Şimdi aşağıdaki örneği inceleyelim.

Yukarıdaki şekilde iki farklı ağaç var. İlk dengesizlik durumu konumundaki ağacın sol tarafının daha derin olduğunu, sol ve sağ taraf derinlikleri farkının da 1’den büyük olduğunu görüyoruz. (1 farkı tolere ediyoruz) O halde biz de z düğümünü sağa döndürüyoruz. Yani AVL Ağacı sağa döndürme işlemi yapıyoruz. Peki ne oluyor?

Y düğümü Z düğümünün yerine geçiyor. Doğal olarak da Z düğümü artık Y düğümünün çocuğu oluyor. Dikkat ederseniz T4 düğümü aynen Z ile taşınıyor. (döndürme sonrası denge durumu)

Dikkat ederseniz dengesizlik olan taraftaki tüm düğümlerin yüksekliği 1 azalıyor. X düğümü bir üste geliyor. Ancak kafanızı karıştıracak çok ama çok önemli bir ayrıntı var burada. Nedir terseniz Y düğümünün sağ çocuğu olan T3 düğümüne bir bakın. Normalde T3 düğümü Y’nin sağ çocuğu ancak dengele işleminden sonra artık Z düğümünün sol çocuğu olmuş. Peki ama neden?

Çünkü bu bir ikili arama ağacı. T3’ün Y’düğümünün sağında olma sebebi, Z düğümünden küçük, Y düğümünden büyük olması. (küçükler sola, büyükler sağa) Bu durumda T3 düğümü Z’den küçük olduğu için Z düğümünün soluna geliyor. T3 düğümünü ağaca yeniden ekliyormuşsunuz gibi düşünün. Kafa karıştıracak hiçbir durum yok.

 

AVL Ağacı Sağ Sağ Dengesizliği Çözümü – AVL Ağacı Sola Döndürme

AVL Ağaçlarında Sağ Sağ dengesizliği olduğunda AVL Ağacı sola döndürme işlemi yapılır. Böylece ağaç dengeli bir hale gelir.

Yukarıdaki şekilde, soldaki ağaçta dengesizlik mevcut. Biz bu dengesizliği sola döndürerek çözeceğiz. Z düğümü sola döndürülür, y düğümü ise onun yerine geçer. X düğümü ise çocuklarıyla birlikte y düğümüne bağlı olduğundan aynen taşınır. T2 düğümü ise ağaca baştan ekleniyormuş gibi düşünülerek doğru konumuna eklenir.

 

AVL Ağacı Sol Sağ Dengesizliği Çözümü

Bu tip durumlarda iki ayrı döndürme yapılır. Dallanmanın olduğu kök düğüm sola döndürülerek sol – sol dengesizliği durumu elde ederiz. Daha sonra dengesizliğin olduğu ana kök düğüm sağa döndürülerek ağaç dengelenir.

Soldaki dengesiz ağaca dikkatli bakın, sağa doğru dallanma y düğümünden itibaren başlamış, o halde y düğümü sola döndürülür. Neden? Çünkü sol sol dengesizliği elde edersek bunun çözümünün sağa döndürmek olduğunu biliyoruz. y düğümünü sola döndürünce x düğümü y düğümünün yerine geçiyor. Çocuklar aynen taşınıyor. Şimdi ise sağa döndürme gerçekleştireceğiz. Ama bu sefer z düğümünü kök kabul ederek sağa döndüreceğiz.

Burayı tekrar uzun uzun yazmayacağım. Bildiğiniz üzere sol sol dengesizliği bulunan ağacı sağa döndürerek dengeledik.

AVL Ağacı Sağ Sol Dengesizliği Çözümü

Bu durumda da çözüm iki aşamalıdır. Dallanmanın bağladığı kök düğüm sağa döndürülerek sağ – sağ dengesizliği olan bir ağaç elde edilir, daha sonra bu ağaç sola döndürülerek dengeleme gerçekleştirilir.

Yukarıdaki ağacın dengesiz halinde sağa doğru dengesizliğin olduğunu ancak sola doğru dallanmanın y düğümünden itibaren başladığını görebilirsiniz. İşte bu yüzden y düğümü sağa döndürülür. ve sağdaki, sağ – sağ dengesizliği olan ağaç elde edilir.

Sağ sağ dengesizliği olan ağaçlarda sola döndürme yaparak denge elde edildiğini biliyoruz artık. Dikkat edin z düğümünü sola döndürdük. böylece dengeli bir ağaç elde ettik.

 

AVL Ağaçları bu kadar, temel işlemlerle her türlü soruyu çözebilirsiniz. Sizler için tüm durumları inceledik. Ufak bir noktaya değinmek istiyorum, AVL ağacı tüm eleman eklemelerinde ya da silme işlemlerinde devreye girer, böylece denge durumunda 2 fark oluştuğunda hemen döndürme işlemleriyle sıkıntıyı çözer ve dengeli ağaç oluşturur. Yani hiçbir zaman denge farkının 3 olmasına izin vermez, 1 olunca devreye girmez, iki olunca çalışır. Zaten kodları incelerseniz bunu görürsünüz. Hangi kodları mı? Hemen aşağıya bakın.

AVL Ağacı Ekleme İşlemi (Insertion) C Kodu

AVL Ağacı Eleman Silme C Kodu

One comment

  1. Bu kadar iyi anlatilabilirdi, cok teşekkürler emeğinize sağlık.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir