avl ne demek?

AVL Ağacı (Dengeli Arama Ağacı)

AVL ağacı, ikili arama ağacı'nın (Binary Search Tree - BST) özel bir türüdür. Adını mucitleri Adelson-Velsky ve Landis'ten almıştır. Temel amacı, BST'lerin performansı en kötü senaryoda O(n)'ye düşebileceği durumlardan kaçınarak, arama, ekleme ve silme gibi işlemlerde ortalama ve en kötü durum karmaşıklığını O(log n)'de tutmaktır. Bu, ağacın dengesini koruyarak sağlanır.

Temel Özellikler ve Kavramlar

• Denge Faktörü (Balance Factor): Bir düğümün denge faktörü, sol alt ağacının yüksekliği ile sağ alt ağacının yüksekliği arasındaki farktır. AVL ağaçlarında, her düğümün denge faktörü -1, 0 veya +1 olmak zorundadır. Yani, bir düğümün sol ve sağ alt ağaçlarının yükseklikleri arasındaki fark en fazla 1 olabilir.

• Dönüşler (Rotations): Bir AVL ağacına bir düğüm eklendiğinde veya silindiğinde, ağacın dengesi bozulabilir. Bu durumda, ağacı yeniden dengelemek için dönüşler kullanılır. Dört temel dönüş türü vardır:

  • Sağa Dönüş (Right Rotation): Sol alt ağacın yüksekliği sağ alt ağaca göre çok fazla olduğunda kullanılır.
  • Sola Dönüş (Left Rotation): Sağ alt ağacın yüksekliği sol alt ağaca göre çok fazla olduğunda kullanılır.
  • Sağ-Sola Dönüş (Right-Left Rotation): Bir düğümün sağ alt ağacının sol alt ağacının yüksekliği, kendi sağ alt ağacından yüksek olduğunda kullanılır. Bu, önce sağ alt ağaç üzerinde sağa dönüş, ardından orijinal düğüm üzerinde sola dönüş yapılarak gerçekleştirilir.
  • Sol-Sağa Dönüş (Left-Right Rotation): Bir düğümün sol alt ağacının sağ alt ağacının yüksekliği, kendi sol alt ağacından yüksek olduğunda kullanılır. Bu, önce sol alt ağaç üzerinde sola dönüş, ardından orijinal düğüm üzerinde sağa dönüş yapılarak gerçekleştirilir.

Avantajları

• Garantili Logaritmik Performans: Arama, ekleme ve silme gibi temel işlemler için O(log n) karmaşıklığı garanti eder.
• Dengeli Yapı: Ağacın dengeli olması, en kötü durum senaryolarını önler.

Dezavantajları

• Karmaşık Uygulama: Dönüşler ve denge faktörlerinin yönetimi, uygulamayı ikili arama ağacı'na göre daha karmaşık hale getirir.
• Ek Yük: Her düğümde denge faktörünü saklamak, ek bellek kullanımına neden olur.

Kullanım Alanları

• Veri tabanlarında indeksleme
• Bellek yönetimi
• Diğer veri yapılarını uygulamak (örneğin, sözlükler ve kümeler)