AVL Ağaçları
Bu eğitimde, AVL Ağacı’nın ne olduğunu ve Javascript’te nasıl uygulanacağını öğreneceğiz. AVL ağacı, herhangi bir düğümün iki alt ağacının yüksekliklerinin birden fazla farklılık gösteremeyeceği, kendi kendini dengeleyen bir İkili Arama Ağacıdır (BST). Herhangi bir zamanda birden fazla farklılık gösterirlerse, bu özelliği geri yüklemek için yeniden dengeleme yapılır. Mucitleri, Georgy Adelson-Velsky ve Evgenii Landis’in adını taşıyan, sovyet mucitleri Georgy Adelson-Velsky ve Evgenii Landis’in adını ilk kez 1962 tarihli “Bilginin organizasyonu için bir algoritma” başlıklı makalelerinde yayınladılar.
avantaj : BST işlemlerinin çoğu ( arama, maks, min, ekleme, silme, vb.) Eğik ikili ağaç durumunda, bu işlemlerin maliyeti O (n) olabilir. Bu işlemlerin üst sınırının O (Logn) olarak kalmasını sağlamak için, her ekleme ve silme işleminden sonra ağacın yüksekliğinin O (Logn) olarak kaldığından emin olmalıyız. Böylece, ağacın yüksekliğinin her zaman O (Logn) olduğundan emin olmak için AVL ağacı icat edilir, burada n, ağaçtaki düğüm sayısıdır.
dezavantaj : BST kodundan çok daha karmaşıktır ve birçok köşe durumunu ele almamız gerekir. AVL ağaçlarında yüksekliğin korunması gerektiğinden, çok büyük girdiler için ihmal edilebilir bir miktar fazladan alana bile eğilimli olan, ters çevirme imlecin tepesini artıracak olan sık dönüşler yapılır. AVL ağaçlarında çok sayıda işaretçi değişikliği ve rotasyonu içerdiğinden silme işlemlerinin maliyeti yüksektir. Bu nedenle, AVL ağaçları, geleneksel BST’lere kıyasla biraz fazladan alan ve çok daha karmaşık kodlar pahasına uygulanabilir
Dengeleme Nasıl Yapılır : AVL ağacında her bir düğüm, değeri -1, 0 veya +1 olan, denge faktörü adı verilen ekstra bilgileri tutar. Bir AVL ağacındaki bir düğümün denge faktörü, sol alt ağacın yüksekliği ile o düğümün sağ alt ağacının yüksekliği arasındaki farktır.
denge = (this.height(node.left) - this.height(node.right));
Normalde dengeleme işlemi leaf(yaprak)lardan başlayıp root’a doğru hareket eder. Yukardıdaki fotoğrafta 11'in sağ ve solunda dengesezilik olmadığı için 0 dedik. 21'de sola dallanma olduğu için [sol-sağ=1] oluyor.9'da ise sol’a dallanma var [sol-sağ=-1] burda ağacımızda dengezizlik meydana getirmiyor dengesizliğin olması için fark { -2 veya +2 }olması gerekiyor.
Bu sebepten dolayı 4 sorun ve 4 çözüm yolumuz var hadi bunları imceleyelim.
- Left Rotate (sol->sol dengesizlik)
- Left Right Roate (sol -> sağa dengesizlik)
- Right Roate (sag -> sag dengesizlik)
- Right Left Roate (sag -> sol dengesizlik)
create AVL :
get height :
right roate :
left rotate :
insert :
delete :
sort :
Bu içeriklerin devamı gelecek… JavaScript ile mutlu günler.
github :https://www.github.com/ckymn
linkedin :https://www.linkedin.com/in/ckymn/
Benim adım Muhammet,Türkiye’de Full Stack Developer’ım . Daha fazla makale için takip edin.🤓
