Home / Veri Yapıları / İkili Arama Ağacı (BST) Search (arama) İşlemi

İkili Arama Ağacı (BST) Search (arama) İşlemi

Bir önceki yazımızda İkili Ama Ağacı özelliklerinden bahsetmiştik. Şimdi sıra bir ağaç üzerinde aradığımız düğümü nasıl bulacağımıza. Elbette arama işlemi derken esas kast ettiğimiz mevzu traverse işlemidir. Aramanın Traverse’den farkı aranılan düğüm bulunduğunda durmaktır. Traverse ise tüm düğümleri dolaşmayı hedefler.

Peki Binary Search Tree (İkili arama ağacı) Arama işlemi algoritması nedir? Bu işlem için uygulayacağımız yöntem kökten başlayarak arama işlemini başlatmaktır. Tabii bu süreçte bize BST’nin özellikleri yardımcı olacaktır.

İkili Arama Ağacı Search Algoritması

Algoritma Genel Olarak şu şekildedir

  1. Kökten başla
  2. Aradığın düğüm mevcut düğümden küçükse sol alt ağaca git
  3. Aradığın düğüm mevcut düğümden büyükse sağ alt ağaca git
  4. Düğümü bulduysan düğümü return et

İkili Arama Ağacı Search Kodu

Aşağıdaki fonksiyon recursive yani özyinelemeli bir fonksiyondur. Sürekli olarak kendisini çağırır. Mevcut düğümün değeri aranılan değer olduğunda return node ile sonlanır.


// İkili arama ağacında arama yapan fonksiyon
// root düğümünü ve aranılan değeri parametre olarak almış
struct node* search(struct node* root, int key)
{
 // Eğer hiç düğüm yoksa ya da aradığımız değer kökse return ediyoruz
 if (root == NULL || root->key == key)
 return root;
 
 // Eğer aradığımız değer root'dan büyükse sağ alt ağaca gideriz
 if (root->key < key)
 return search(root->right, key);
 
 // Eğer aranılan değer kökten küçükse sol alt ağaca gideriz
 return search(root->left, key);
}
}

İkili Arama Ağacı Arama (Search) İşlemi Örneği

Şimdi gelin İkili Arama Ağacı arama işlemi örneği verelim ve adım adım işleyişe göz atalım.

ikili arama ağacı örneği

Yukarıdaki örnekte (44) düğümünü arayalım.

1. Adım: 44 sayısı (root) düğüm ile karşılaştırılır. (25) 44 25‘ten büyük olduğu için sağ çocuğa (50) gidilir.

2. Adım: 44 sayısı 50 sayısından küçüktür. O halde sol çocuğa (35) gidilir.

3. Adım: 44 sayısı 35 sayısından büyüktür. Bu yüzden sağ çocuğa (44) gidilir.

4. Adım: Bu adımda 44 düğümünü bulduk, algoritma gereği bu düğümü return eder ve sonlandırırız.

 

Bir cevap yazın

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