AVL Ağacı Aynı Eleman Ekleme
AVL ağacı, adını mucidi Adelson-Velsky ve Landis’ten alan, dengeli bir ikili arama ağacıdır. AVL ağaçları, arama, ekleme ve silme işlemlerinin O(log n) zaman karmaşıklığına sahip olması nedeniyle verimli bir veri yapısıdır.
AVL ağaçları, her düğümün denge faktörünün -1, 0 veya 1 olması koşuluyla dengelidir. Denge faktörü, bir düğümün sol alt ağacının yüksekliği ile sağ alt ağacının yüksekliği arasındaki farktır.
Aynı eleman bir AVL ağacına eklendiğinde, ağacın dengesi bozulabilir. Bu durumda, ağacın dengesi yeniden sağlamak için yeniden dengelenmesi gerekir. Yeniden dengeleme işlemi, ağacın yapısını değiştirerek yapılır.
AVL ağacına aynı eleman eklemek için aşağıdaki adımlar izlenir:
- Eleman ağaca eklenir.
- Elemanın eklendiği düğümün denge faktörü hesaplanır.
- Denge faktörü -2 veya 2 ise, ağacın dengesi bozulmuştur.
- Ağacın dengesi yeniden sağlamak için yeniden dengelenmesi gerekir.
Yeniden dengeleme işlemi, aşağıdaki dört durumdan birine göre yapılır:
- Sol-sol durumu: Eleman ağacın sol alt ağacına eklenmiş ve sol alt ağacının yüksekliği sağ alt ağacının yüksekliğinden 2 fazla olmuştur.
- Sol-sağ durumu: Eleman ağacın sol alt ağacına eklenmiş ve sol alt ağacının yüksekliği sağ alt ağacının yüksekliğinden 1 fazla olmuştur ve sol alt ağacının sağ alt ağacının yüksekliği sol alt ağacının sol alt ağacının yüksekliğinden 1 fazla olmuştur.
- Sağ-sağ durumu: Eleman ağacın sağ alt ağacına eklenmiş ve sağ alt ağacının yüksekliği sol alt ağacının yüksekliğinden 2 fazla olmuştur.
- Sağ-sol durumu: Eleman ağacın sağ alt ağacına eklenmiş ve sağ alt ağacının yüksekliği sol alt ağacının yüksekliğinden 1 fazla olmuştur ve sağ alt ağacının sol alt ağacının yüksekliği sağ alt ağacının sağ alt ağacının yüksekliğinden 1 fazla olmuştur.
Her durum için yeniden dengeleme işlemi farklıdır. Yeniden dengeleme işlemlerinin ayrıntıları için aşağıdaki kaynaklara bakabilirsiniz: