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

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

Ö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 ){

  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

 }

}