Veri Yapıları: İkili Arama Ağacı (Binary Search Tree)

İkili Ağaç Yapısı

Ağaçlar kenarlar ile birbirine bağlanmış düğümlerden oluşur.

Birçok çeşidi vardır fakat bu yazıda ikili ağaç ve ikili arama ağacı ile ilgileneceğiz.

İkili ağaç yapısı her düğümün en fazla iki çoçuk düğüme sahip olduğu özel bir durumdur.

Arama işlemi sıralı dizilerdeki kadar hızlı, ekleme ve silme işlemleri ise bağlı listeler kadar hızlıdır.

Örnek olarak ikili ağaç yapısını şu şekilde modelleyebiliriz;

İkili Ağaç Yapısı

Şekilden anlaşılacağı gibi bu yapıda da bazı terimler mevcut.

Bunları basitçe şu şekilde listeleyebiliriz;

  • Düğüm önceki yapılarda olduğu gibi elemanımızı temsil eder.
  • Kök ağacı oluşturan yani en tepedeki elemandır ve ağaç başına bir tanedir.
  • Ebeveyn düğüm ise kardeş düğümlerin bağlı olduğu düğüm olarak ifade edilebilir.
  • Çocuk düğüm aynı ebeveyn düğüme bağlı olan düğümlerin her biridir.
  • Kardeş düğümler aynı ebeveyn düğüme bağlı olan düğümlerdir.
  • Yaprak düğüm çocuk düğüme sahip olmayan düğümleri ifade etmek için kullanılır.
  • Seviye düğüm jenerasyonlarını belirtmekte kullanılır. Kökün seviyesi 0 olarak kabul edilir ve aşağıya inildikçe artar.
  • Alt ağaç düğümlerin alt jenerasyonundan oluşan yeni ağaçlara denir.

Kod kısmında ise bir düğüm kendi verisini içermenin yanı sıra sağ ve sol çocuklarına işaret eder.

C++ düğüm kodu örneği;

1
2
3
4
5
6
struct dugum
{
int veri;
struct dugum *sol;
struct dugum *sag;
};

Ağaç Üzerinde Dolaşım

Ağaçta dolaşmak için 3 yöntem vardır. Bunlar;

  • Kökten başlayan (Preorder)
  • Kökün ortada olduğu (Inorder)
  • Kökte sonlanan (Postorder)

dolaşım yöntemleridir.

Kökten Başlayan Dolaşım Yöntemi (Preorder)

Bu yöntemde dolaşmaya kökten başlanır sonrasında önce sol alt ağaca ve takiben sağ alt ağaca geçilir.

Örnek bir ağaç modelinde şu şekilde gösterebiliriz;

İkili Ağaç Yapısında Kökten Başlayan Dolaşım

Düğüm sırası: A, (B, Ç, D), (C, E, F)

Kökün Ortada Olduğu Dolaşım Yöntemi (Inorder)

Bu yöntemde dolaşmaya sol alt ağaçtan başlanır ve kökten sağ alt ağaca geçilir.

Örnek bir ağaç modelinde şu şekilde gösterebiliriz;

İkili Ağaç Yapısında Kökün Ortada Olduğu Dolaşım

Düğüm sırası: (Ç, B, D), A, (E, C, F)

Kökte Sonlanan Dolaşım Yöntemi (Postorder)

Bu yöntemde ise dolaşmaya sol alt ağaçtan başlanır sonrasında sağ alt ağaçta dolaşım tamamlanır ve en son köke geçilir.

Örnek bir ağaç modelinde şu şekilde gösterebiliriz;

İkili Ağaç Yapısında Kökte Sonlanan Dolaşım

Düğüm sırası: (Ç, D, B), (E, F, C), A

Yukarıdaki üç sıralama yönteminin de kendi içinde örüntü oluşturduğunu görmüşsünüzdür.
Yapımızı kodlarken bu örüntüyü kolayca özyinelemeye çevirebileceğiz.

İkili Arama Ağacı

İkili arama ağacında temel kural verilerin köke göre bölümlenmesidir.

Yani eğer bir veri kökten küçük ise onun sol alt ağacında büyükse sağ alt ağacında yer alması gerekir ve bu tüm alt ağaçlarda geçerlidir (yani özyinelemelidir).

Bu yazıda ikili arama ağacı yapısında aşağıdaki temel işlemleri adım adım gerçekleştireceğiz;

  • Ekleme
  • Dolaşma
  • En küçük ve en büyük değerleri bulma
  • Silme

İşe temelimiz olan düğüm yapısını oluşturarak başlayalım;

1
2
3
4
5
6
7
8
9
// elemanımız için kullanacağımız düğüm yapımız
struct dugum
{
int veri;
dugum * sol;
dugum * sag;
};

typedef dugum eleman;

Sıra geldi ekleme işlemine. Fonksiyonumuz şu şekilde;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
eleman* ekle(eleman* agac, int eklenecekDeger)
{
// ağacımız tamamen boş ise
if (agac == NULL)
{
// kökümüzü oluşturuyoruz
eleman* kok = (eleman*)malloc(sizeof(eleman));

// kökümüzün sağı ve solunu boş olacakları için NULL yapıyoruz
kok->sag = NULL;
kok->sol = NULL;

// eklenecek değerimizi ekliyoruz
kok->veri = eklenecekDeger;

// ve yeni kök değerimizi geriye döndürüyoruz
return kok;
}

// eklenecek değer kökten büyükse sağ alt ağaca geçip
// fonksiyonumuzu orada tekrar işliyoruz (özyineleme)
if (agac->veri < eklenecekDeger)
{
agac->sag = ekle(agac->sag, eklenecekDeger);
}
else // değer kökten küçükse sol alt ağaca geçiyoruz
{
agac->sol = ekle(agac->sol, eklenecekDeger);
}

// ağacımızın son halini geriye döndürüyoruz
return agac;
}

Bu aşamadan sonra yaptığımız değişiklikleri görebilmemiz için dolaşma işlemlerini gerçekleştirelim.

soldanSagaDolas (inorder) fonksiyonumuz;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void soldanSagaDolas(eleman* agac)
{
// dolaşacak değer kalmadığında geriye dönüyoruz
if (agac == NULL)
{
return;
}

// önce sol alt ağacımıza uğruyoruz
soldanSagaDolas(agac->sol);

// sol alt ağaçtaki yaprak düğümümüzü yazdırıyoruz
cout << agac->veri << " ";

// sonra sağ alt ağaca geçiyoruz
soldanSagaDolas(agac->sag);
}

koktenSagaDolas (preorder) fonksiyonumuz;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void koktenSagaDolas(eleman* agac)
{
// dolaşacak değer kalmadığında geriye dönüyoruz
if (agac == NULL)
{
return;
}

// önce kökümüzü yazdırıyoruz
cout << agac->veri << " ";

// sonra sol alt ağacımıza uğruyoruz
koktenSagaDolas(agac->sol);

// en son sağ alt ağaca geçiyoruz
koktenSagaDolas(agac->sag);
}

soldanKokeDolas (postorder) fonksiyonumuz;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void soldanKokeDolas(eleman* agac)
{
// dolaşacak değer kalmadığında geriye dönüyoruz
if (agac == NULL)
{
return;
}

// önce sol alt ağacımıza uğruyoruz
soldanKokeDolas(agac->sol);

// sonra sağ alt ağaca geçiyoruz
soldanKokeDolas(agac->sag);

// en son kökümüzü yazdırıyoruz
cout << agac->veri << " ";

}

Şimdi diğer işlemlere göre nispeten daha kolay olan en küçük ve en büyük veriye sahip olan düğümleri bulma işlemlerimize geçelim.

İkili arama ağacında en küçük değere sahip düğüm sol alt ağacın en alttaki sol elemanıdır.

Öyleyse fonksiyonumuz şu şekilde olmalıdır;

1
2
3
4
5
6
7
8
9
10
11
12
int enKucukDegeriBul(eleman* agac)
{
eleman* arayici = agac;

// düğüm solunda çocuk barındırdığı sürece
// soluna doğru gitmeye devam ediyoruz
while(arayici->sol != NULL)
arayici = arayici->sol;

// bulduğumuz düğümün değerini geri döndürüyoruz
return arayici->veri;
}

En büyük değeri bulan fonksiyonumuz;

1
2
3
4
5
6
7
8
9
10
11
12
int enBuyukDegeriBul(eleman* agac)
{
eleman* arayici = agac;

// düğüm sağında çocuk barındırdığı sürece
// sağına doğru gitmeye devam ediyoruz
while(arayici->sag != NULL)
arayici = arayici->sag;

// bulduğumuz düğümün değerini geri döndürüyoruz
return arayici->veri;
}

Şimdi gelelim en zor aşama olan silme işlemimize.
Bu fonksiyonumuzda yukarıda bulduğumuz en küçük/en büyük değerlerden faydalanacağız.

Sil fonksiyonumuz;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
eleman* sil(eleman* agac, int silinecekDeger)
{
// ağacımız tamamen boş ise
if (agac == NULL)
{
return NULL;
}

// silinecek değer kök düğümde ise
if (silinecekDeger == agac->veri)
{
// kökün çocuk düğümü yoksa
if (agac->sol == NULL && agac->sag == NULL)
{
return NULL;
}

// kökün sağında çocuk düğüm var ise
if (agac->sag != NULL)
{
// kökün sağ alt ağacındaki en küçük değeri buluyoruz
// ve yer değiştirme yapıyoruz
agac->veri = enKucukDegeriBul(agac->sag);

// sonrasında o değeri siliyoruz
agac->sag = sil(agac->sag, enKucukDegeriBul(agac->sag));

return agac;
}
// kökün solunda çocuk düğüm var ise
if (agac->sol != NULL)
{
// kökün sol alt ağacındaki en büyük değeri buluyoruz
// ve yer değiştirme yapıyoruz
agac->veri = enBuyukDegeriBul(agac->sol);

// sonrasında o değeri siliyoruz
agac->sol = sil(agac->sol, enBuyukDegeriBul(agac->sol));
return agac;
}
}
// silinecek değer kökten küçük ise sol alt ağaca geçiyoruz
if (silinecekDeger < agac->veri)
{
// silinecek değeri sol alt ağaçtan sil
// ve o ağacı yeni sol alt ağaç yap
agac->sol = sil(agac->sol, silinecekDeger);
return agac;
}

// silinecek değer kökten büyük ise sağ alt ağaca geçiyoruz
// silinecek değeri sağ alt ağaçtan sil
// ve o ağacı yeni sağ alt ağaç yap
agac->sag = sil(agac->sag, silinecekDeger);

// ağacımızın son halini geriye döndürüyoruz
return agac;
}

Son olarak test kodlarını içeren main fonksiyonumuz;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int main(int argc, char *argv[])
{
// ağacımızı oluşturuyoruz
eleman* agac = NULL;

// örnek değerlerimizi giriyoruz
agac = ekle(agac, 15);
agac = ekle(agac, 6);
agac = ekle(agac, 3);
agac = ekle(agac, 2);
agac = ekle(agac, 4);
agac = ekle(agac, 7);
agac = ekle(agac, 13);
agac = ekle(agac, 18);
agac = ekle(agac, 17);
agac = ekle(agac, 20);

// dolaşma işlemleri
soldanSagaDolas(agac);
cout << endl;
koktenSagaDolas(agac);
cout << endl;
soldanKokeDolas(agac);
cout << endl;

// en küçük ve en büyük değer bulma işlemleri
cout << enKucukDegeriBul(agac) << endl;
cout << enBuyukDegeriBul(agac) << endl;

// silme işlemleri
agac = sil(agac, 2);
soldanSagaDolas(agac);
cout << endl;

agac = sil(agac, 20);
soldanSagaDolas(agac);
cout << endl;

agac = sil(agac, 13);
soldanSagaDolas(agac);
cout << endl;

return 0;
}

Böylece ikili arama ağacı yapımızı da temel olarak incelemiş olduk. Sonraki yazılarda görüşmek üzere.