 |
| Büyük bir Ağaç Yapısı |
AVL Ağacıyla ilgili her türlü konuya sitemizden ulaşabilirsiniz. Avl Ağacı Nedir diye merak ediyorsanız linke tıklayabilirsiniz. AVL Ağacı algoritması konusunun kritik noktası Rotation yani döndürme işlemleridir. Rotation İşlemleri AVL'ye has bir konu değildir. İkili Arama Ağacı konusuna dahildir. Dengesiz ağaçlar Rotation işlemiyle dengeli hale getirilirler.
Ağaçlarda Döndürme İşlemleri Nelerdir?
Sola Döndürme (Left Rotation)
Sağa Döndürme (Right Rotation)
Bu iki döndürme işlemleriyle ağaçlar dengeli hale getirilir. AVL ağaçlarında döndürme işlemleriyle dengesiz ağaçlar dengeli hale getirilirler.
Ağaçlar Neden Dengesiz Hale Gelir?
Ağaçlara yeni düğüm eklerken ya da silerken yükseklik farkları 1'den büyük hale gelebilir. Bu yüzden dengeleme işlemine tabii tutulmalıdır.
AVL Sola Döndürme Nasıl Yapılır? - (AVL Left Rotation Nasıl Yapılır?)
Eğer bir ağacın sağ tarafı daha derinse sola döndürme işlemi gerçekleştirebiliriz.
Muhteşem çizimimden de gördüğümüz üzere sola döndürme işleminde L düğümü root haline gelmiş, K ise alta kaymıştır. Yalnız Dikkat edin T1, T2 ve T3 düğümlerinin çocukları yoktur. Bunlar ağaç veri yapısı terminolojisinde Leaf olarak adlandırılırlar. Leaf olan düğümler leaf olmak zorundadır.
AVL Sağa Döndürme Nasıl Yapılır? - (AVL Right Rotation Nasıl Yapılır?)
Bir ağacın sol tarafı daha derinse sağa döndürme işlemi yapılır.
Gördüğünüz üzere K düğümü L'nin yerine gelmiş, L düğümüde aşağıya kaymıştır. T2 Leaf düğümü ize L'nin Child Düğümü olmuştur.
Buraya kadar her şey güzel, AVL Tree Rotation işlemlerini anladık. Fakat hangi durumlarda bunları uygulayacağız?
AVL Ağacı Dengesizlik Durumları
4 Ana Durum vardır.
Sol Sol Durumu - (Left Left Case)
Sağ Sağ Durumu - (Right Right Case)
Sol Sağ Durumu - (Left Right Case)
Sağ Sol Durumu - (Right Left Case)
Peki bunlar bizim ne işimize yarayacak? Hiçbir durum tespiti ve döndürme işlemi bize durup dururken Ağaç Dengesi sağlamaz. Bize dengesizliğin var olup olmadığını söyleyecek bir Balance Factor lazım. Balans faktörünü, Ağaçlara düğüm eklendiğinde ya da silindiğinde devreye girer. Eğer solDerinlik - sagDerinlik > 1 sonucunu veriyorsa dengesizlik durumuna göre döndürme işlemleri uygulanır.
AVL Ağacı Sol Sol Durumu - (Left Left Case)
Yukarıdaki ağaç yapısında Sol tarafın derinliği 3 birim iken, sağ tarafın derinliği 1 birimdir. Yani 2 birimlik bir fark durumu söz konusudur. Bu da Balans Faktörünün 1'den büyük olduğu manasına gelir. Derinliğin sürekli solun soluna doğru olması sol sol durumunu oluşturur.
Sol Sol durumu yani AVL Left Left Case durumunda Sağa Dönüş (right rotation) uygulanır. Yani mantık çok basit, ağaç yapımız direkt sola doğru yardırmış, dengelemek için sağa döndürüyoruz. Peki Nasıl Yapacağız?
AVL Ağacı Sol Sol Durumu Dengeleme İşlemi
AVL Ağacı Sağ Sağ Durumu - (AVL Tree Right Right Case)
(bu sefer ağacı çaldım, kendim çizince hem kötü oluyor, hem de çok uzun sürüyor :) ) Yukarıda gördüğünüz ağaçta olan durum sağ sağ durumudur. Farkettiyseniz derinlikler arasındaki fark 1'den büyüktür. Bu durumda AVL Sola Döndürme işlemi yapılmalıdır.
AVL Ağacı Right Right Case Dengesizliği Çözümü
Görüldüğü üzere 3 düğümü 1 düğümünün yerine getirilmiştir. 3 Düğümünün Leaf'i olan 2 düğümü 1 düğümüne bağlanmıştır. Leaf hep leaf olmalıdır. (Burada Right Rotation yani sağa Döndürme Uygulanmıştır.
AVL Ağacı Left Righ Case
Yukarıdaki ağaç Left Right yani Sol-Sağ durumuna örnektir. Mantık şu, hangi taraf daha derin? Sol, Peki soldan sonra ne tarafa derinleşmiş? Sağ. İşte bu yüzden bu duruma Sol-Sağ durumu deniliyor.
Çözüm için ilk olarak Sola döndürme, daha sonra sağa döndürme yapılır, ağaç dengelenir.
AVL Ağacı Left Right Case Çözümü
Gördüğünüz üzere iki döndürme işlemi yaptık. Çünkü mantık aslında basit, ilk adımda sola döndürme yapınca Left-left case elde ettik. Onu da çözmeyi zaten biliyoruz, sağa döndürme işlemi yapıyoruz. Böylece ağaç dengeleniyor.
AVL Ağacı Sağ-Sol Durumu (AVL Right Left Case)
Yukarıdaki ağaç yapısından da gördüğünüz üzere ağacın derin tarafı Sağ taraf, ama sağ tarafta sola doğru derinleşmiş. Çözümü ise çok basit. ilk olarak sola döndürüyoruz, daha sonra sağa.
AVL Ağacı Sağ-Sol Durumu Dengeleme İşlemi
Şekinden de gördüğünüz üzere ilk solarak sağa döndürdük ve right rigt case elde ettik. Daha sonra sola döndürerek ağacı dengeledik.
AVL Ağacı Dengeleme İşlemleri
AVL ağacı algoritmasının esas noktası balans faktörüdür. Ağaca ekleme yaparken ya da silerken balans faktörü ile kontrol yapılır. Eğer derinlik farkı 1'den büyükse dengeleme işlemi gerekir.
Sola doğru derinlik fazlaysa sağa doğru döndürme işlemi yapılır.
Sağa doğru derinlik fazlaysa sola doğru döndürme işlemi yapılır.
Sola doğru derinlik fazlaysa ve sol taraf üzerinden sağa doğru derinleşme varsa ilk olarak sola daha sonra sağa döndürme işlemi yapılır. (sol-sağ durumu)
sağa doğru derinlik fazlaysa ve sağ taraf üzerinden sola doğru derinleşme varsa ilk olarak sağ daha sonra sola döndürme işlemi yapılır. (sağ-sol durumu)
Mutlaka Bakın! AVL Ağacı Hazır C KoduEtiketler: AVL Ağacı algoritması, avl sağ sağ durumu, avl sağ sol durumu, avl sağa döndürme, avl sol sağ durumu, avl sol sol durumu, avl sola döndürme
