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.