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:

rotate.jpg

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.

soladengele.jpg

Ö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.

sagadengele.jpg

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:

soladengele2.jpg

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.

Yorumlar

  1. mert

    Verilen son grafikteki gibi bir dengeleme asla olamaz,sanırım bir yanlışınız var. Cunku ikili arama ağaçlarında sol taraf root'tan her zaman küçükken sağ taraf her zaman büyüktür. Dengeleme sonunda A node'unun sağına D node'unun eklendiğini görüyoruz. Fakat denegeleme öncesinde D node'u A'nın sol tarafında yer almakta yani A'dan küçük bir key'e sahip. Bu yüzden dengeleme sonunda A'nın sol tarafında olmalıydı tekrar.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


+ sekiz = 14