İkili Arama Ağacı (Binary Search Tree)


Yazan : Şadi Evren ŞEKER

İkili ağaçların (Binary Tree) özel bir hali olan ikili arama ağaçlarında, düğümlerde duran bilgilerin birbirine göre küçüklük büyüklük ilişkisi bulunmalıdır. Örneğin tam sayılardan(integer) oluşan veriler tutulacaksa bu verilerin aralarında küçük-büyük ilişkisi bulunmaktadır.

İkili arama ağacı, her düğümün solundaki koldan ulaşılabilecek bütün verilerin düğümün değerinden küçük, sağ kolundan ulaşılabilecek verilerin değerinin o düğümün değerinden büyük olmasını şart koşar.

iaa.JPG

Örneğin yukarıda bir ikili arama ağacı tasvir edilmiştir. Bu ağaçta dikkat edilecek olursa kökün solunda bulunan bütün sayılar kökten küçük ve sağında bulunan bütün sayılar kökten büyüktür.

İkili arama ağacına bu kurala uygun olarak ekleme çıkarma veya silme işlemleri yapılabilir. Ancak yapılan her işlemden sonra ikili arama ağacının yapısı bozulmamış olmalıdır.

İkili arama ağacında arama işlemi:

Yukarıda da anlatıldığı üzere ağacın üzerinde duran verilerin özel bir şekilde sıralı bulunması gerekir. Buna göre herhangi bir değeri arayan kişi ağacın kök değerine bakarak aşağıdaki 3 eylemden birisini yapar:

  1. Aranan sayı kökteki değere eşittir -> Aranan değer bulunmuştur
  2. Aranan sayı kökteki değerden küçüktür -> Kökün sol kolu takip edilir
  3. Aranan sayı kökteki deüerden büyüktür -> Kökün sağ kolu takip edilir

İkili arama ağaçlarının önemli bir özelliği ise öz çağıran(recursive) oluşudur. Buna göre bir ağacın sol kolu veya sağ kolu da birer ağaçtır. Bu özellikten faydalanarak örneğin C dilinde aşağıdaki şekilde bir arama fonksiyonu yazılabilir:

dugum * ara(dugum *kok, int deger){
     if(deger == kok->veri){
        return kok;
    }
    else if(deger > kok->veri ){
        return ara(kok->sag, deger);
    }
    else{
        return ara(kok->sol,deger);
   }
}

Yukarıdaki bu örnekte daha önce ikili ağaçlar konusunda tanımlanmış bir düğüm struct’ı kullanılmıştır. Koda dikkat edilecek olursa özçağıran bir yapı görülebilir. Yani fonksiyonun içerisinde kendisi çağrılmış ve yeni kök değeri olarak mevcut kökün sol veya sağ değeri verilmiştir. Arana değer her durumda değişmediği için alt düğümlere kadar aynı olarak indirilmiştir.

Yukarıdaki koddaki önemli bir eksiklik ise kodun ağaç üzerinde bir sayıyı bulamaması durumunun tasarlanmamış olmasıdır. Bu durumda basitçe NULL değer kontrolü ile aşılabilir. Buna göre sol veya sağa gitmeden önce sol veya sağda bir değer olduğuna bakılmalı şayet değer varsa gidilmelidir. Şayet değer yoksa ağaçta bu sayının bulunma ihtimali yoktur ve bu sayının olmadığını belirten bir ifade (örneğin NULL) döndürülmelidir. Kodun bu şekilde tashih edilmiş hali aşağıda verilmiştir:

dugum * ara(dugum *kok, int deger){
     if(deger == kok->veri){
        return kok;
    }
    else if(deger > kok->veri ){
	if(kok->sag != NULL)
	        return ara(kok->sag, deger);
	else
		return NULL;
    }
    else{
	if(kok->sag != NULL)
	        return ara(kok->sol,deger);
	else
		return NULL
   }
}

Bu Yazıyı Paylaşın


« İkili Ağaç (Binary Tree)   |   TML (Time Markup Language, Zaman İşaretleme Dili, ZİD) »



Yorumlar

Giriş yaparak yorum yazabilirsiniz.

Bu Yazı Hakkında

bilgisayar.kavramlari.com üzerinde şu anda okumakta olduğunuz 'İkili Arama Ağacı (Binary Search Tree)' isimli yazı 07 May 2008 tarihinde, saat: 05:35 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 235 defa okunmuştur.

Benzer yazıları Bilgisayar Kavramları, 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.


Eklenen Son Yazılar
Yapılan Son Yorumlar
Bağlantılar
Kapat
E-posta ile paylaş