Ağaçlarda Dengeleme (Rotation, Balancing)

Yazan : Şadi Evren ŞEKER

En çok karşılaşılan durum, ikili arama ağaçlarında bir düğüm için çocuklarının derinliklerinin 2 olması durumudu. Bu durum aşağıdaki örnekte gösterilmiştir:

Yukarıdaki tasvirde ayrıca bu ağacın dengelenmiş hale nasıl dönüştürüldüğü de gösterilmiştir. Buna göre ağaç sağa dengelenmiş ve ikili arama ağacı özelliği bozulmamıştır. Yani dengelendikten sonra da ağacın sağ kolundaki değerler, sol kolundaki değerlerden büyüktür.

Yukarıdaki şekilde de gösterildiği üzere ağacın kolları arasındaki derinlik farkı 2 olduğunda dengeleme yapılabilir. Bu durum iki türlü olabilir ya sağ kolu daha uzun ya da sol kolu daha uzun olacaktır. Her iki durum içinde yapılan işlemler sola dengele veya sağa dengele olarak sınıflandırılabilir.

Örneğin yukarıda, bir ağacın kolları arasındaki derinlik farkı 2′yi geçmiş ve bu dengesizlikde derin olan taraf sol kolu olmuştur. Buna göre ağacın dengelenmiş halinde, ilk halinde kökte bulunan düğüm sağ kola yerleştirilir.

Benzer bir durumda ağacın sağ kolunun daha derin olamsı halidir. Bu durum da da ağacın kökünde bulunan düğüm sol kola yerleştirilir.

Ağaçlarda dengesiz olan bütün durumlar yukarıda anlatılan örnekte olduğu gibi dengelenebilir. Basitçe şayet ağacımız dengeli yapılmak isteniyorsa ve her ekleme veya silme işleminden sonra bu dengeleme kontrolü çalışıyorsa ağaç dengeli bir halde kalacaktır. Ayrıca ikili ağaçların iki kolu bulunduğu için yukarıdaki durumlar dışında bir durum ile karşılaşılamaz.

Aşağıda ise sadece silme işleminden sonra karşılaşılabilecek bir durum verilmiştir:

Yukarıdaki bu durum ekleme işlemleri sırasında karşılaşılamaz çünkü eklenen her adımdan sonra ağaç dengeli hale getirileceği için C eklenmesi durumunda D, D eklenmesi durumunda ise C dengeli bir ağaca eklenecektir. Ancak silme durumlarında yukarıdaki şekilde dengeleme işlemi yapılabilir. Ağacın sola dengelenmesi gerektiği durum ise yukarıda tasvir edilen halin simetriğidir.

« AVL Ağacı (AVL Tree) | Özetleme Fonksiyonları (Hash Function) »

Yorumlar

Toplam 2 yorum var.

AVL Ağacı (AVL Tree) : bilgisayar.kavramlari.com | 15 May 2008, 10:54
[...] dengelemesi için ağaçlarda dengeleme konusuna [...]
cansu | 10 Jan 2010, 11:30
Bu avl agacına c de yazılmış bi örnek kod verebilir misiniz?

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Ağaçlarda Dengeleme (Rotation, Balancing)' isimli yazı 15 May 2008 tarihinde, saat: 10:53 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1330 defa okunmuştur.

Benzer yazıları Automata (otomatlar, özdevinirler), algoritma analizi (teory of algorithms), 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