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


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



Yorumlar

Kullanıcı girişi yaparak ya da zorunlu olan * alanlarını doldurarak yorum yapabilirsiniz.

İsminiz *

Email adresiniz *

Web siteniz

Mesajınızı buraya yazabilirsiniz:

Toplam 4 yorum var.

  1. Ağaçlar (tree) : bilgisayar.kavramlari.com | 07 May 2008, 05:36

    [...] İkili arama ağaçları (Binary Search Tree) [...]

  2. Trie (Metin Ağacı) : bilgisayar.kavramlari.com | 14 May 2008, 12:17

    [...] ağaçlarının (trie), ikili arama ağaçlarına göre en önemli avantajları bir metni aramanın, metin boyutu kadar işlem gerektirmesidir. [...]

  3. AVL Ağacı (AVL Tree) : bilgisayar.kavramlari.com | 15 May 2008, 08:47

    [...] Ağaçları sürekli olarak dengeli olan ikili arama ağaçlarındandır.  G.M. Adelson-Velsky ve E.M. Landis tarafından geliştirilmiş olan bu ağaç algoritmasının [...]

  4. Fibonacci Arama Algoritması (Fibonacci Search Algorithm) : bilgisayar.kavramlari.com | 05 Aug 2008, 10:49

    [...] bir parçala fethet (divide and conquere) yaklaşımıdır. Benzer bir arama yöntemi olan ikili arama (binary search) ile aynı algoritma karmaşıklığına sahiptir O(log n) ancak yapılan matematiksel [...]

Bu Yazı Hakkında

Bilgisayar Kavramları ü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 3176 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.


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
Yapılan Son Yorumlar
Yakın Yazılar
Bağlantılar