şükela:  tümü | bugün soru sor
  • ismini, bulanlarından alır: adelson-velskii ve landis
  • her elemaninin balance factoru, yani sol kolun derinligi ile sag kolun derinligi arasindaki farki -1 ile 1 arasinda olan, dolaysiyla derinligi her daim o(logn) olan binary tree.
  • balanceı insertion ve removal operasyonlarından sonra bir takım rotationlar yaparak koruyan data tipi.
  • daha kolay anlaşılması için:
    http://www.site.uottawa.ca/…514/applets/avl/bt.html

    edit: link
  • bst ağaçlarında ağacın yüksekliği(veya derinliği) arttıkça işlem karmaşıklığı artar. avl ağaçları bu karmaşıklığı azaltmak için geliştirilmiş bir veri yapısıdır. avl'yi bst'den ayıran tek şey ağaca eleman eklerken döndürme işlemleri yapılarak, ağacın sağ alt ve sol alt yüksekliklerinin arasında en fazla 1 fark olacak şekilde ağacın sürekli dengede tutulması dolayısıyla işlem karmaşıklığının o(logn) olarak sabit kalmasıdır .

    dengeyi sağlamak için dengesizlik durumları tespit etmek gerekir. eğer sağ alt ve sol alt ağaçların yükseklikleri arasındaki farkın mutlak değeri 1'den büyükse dengesizlik var demektir.

    temelde 4 tane dengesizlik durumu ve bu 4 dengesizliği çözecek olan iki tane döndürme yöntemi vardır.

    dengesizlik durumları;
    1) right - right case ( sağ - sağ durumu)
    2) left - left case (sol - sol durumu)
    3) right - left case ( sağ - sol durumu)
    4) left - right case ( sol - sağ durumu)

    döndürme işlemleri
    1) sola döndürme (right rotation)
    2 sağa döndürme (left rotation)

    1. durumda sağa doğru dengesizliği olan ağacı dengelemek için ters tarafa yani sola doğru döndürme yapılır.

    2. durumda 1. durumun tam tersi, yani sağa doğru döndürme yapılır.

    3. durumda dengesizlik sağ tarafa doğrudur ancak sağ alt ağaçın belli bir kısmında ekstra sola doğru da bir dallanmayla sola doğru bir dengesizlik vardır. bu tür bir ağacı dengelemek için önce sağa doğru döndürme yapılır ve ağaç sağ sağ dengesizliğine getirilir, sonra 2. durumdaki çözüm yapılır.

    4. durum 3. durumun tam tersidir.

    ve son olarak çok gereksiz ve yetersiz bir ismi olan bir veri yapısıdır.