AVL Ağacı (AVL Tree)

Yazan: Şadi Evren ŞEKER

AVL Ağaçları sürekli olarak dengeli olan ikili arama ağaçlarındandır. G.M. Adelson-Velsky ve E.M. Landis tarafından geliştirilmiş olan bu ağaç algoritmasının ismi de bu kişilerin isimlerinin baş harflerinden oluşmaktadır.

Algoritma basitçe, bir düğümün kolları arasındaki derinlik farkı 2 ise bu durumda dengeleme işlemi yapılır. Şayet fark 2′den az ise (yani 1 veya 0) ise bu durumda bir dengeleme işlemine gerek yoktur.

Algoritmanın ağacı dolaşma (traverse) algoritması ikili arama ağaçları ile aynıdır. Ancak ağaca ekleme ve silme işlemleri sırasında ağacın dengesinin bozulması söz konusu olduğu için bu fonksiyonlara ilave olarak derinlik kontrolü eklenmiştir.

Ekleme ve silme işlemlerinde ikili arama ağacının ekleme ve silme işleminin aynısını yaptıktan sonra aşağıdaki dengeleme işlemi yapılır.

Ağaçta ekleme veya silme yapılan her düğüm için:

sol <- Düğümün sol kolunun derinliğini ölç

sağ <- Düğümün sağ kolunun derinliğini ölç

şayet sol - sağ >1

    sola dengele

şayet sağ - sol < -1

    sağa dengele

Ağaç dengelemesi için ağaçlarda dengeleme konusuna bakabilirsiniz.

« Trie (Metin Ağacı) | Ağaçlarda Dengeleme (Rotation, Balancing) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'AVL Ağacı (AVL Tree)' isimli yazı 15 May 2008 tarihinde, saat: 08:47 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 2430 defa okunmuştur.

Benzer yazıları veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar