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;
Ş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 | struct dugum |
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;
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;
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;
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 | // elemanımız için kullanacağımız düğüm yapımız |
Sıra geldi ekleme işlemine. Fonksiyonumuz şu şekilde;
1 | eleman* ekle(eleman* agac, int eklenecekDeger) |
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 | void soldanSagaDolas(eleman* agac) |
koktenSagaDolas (preorder) fonksiyonumuz;
1 | void koktenSagaDolas(eleman* agac) |
soldanKokeDolas (postorder) fonksiyonumuz;
1 | void soldanKokeDolas(eleman* agac) |
Ş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 | int enKucukDegeriBul(eleman* agac) |
En büyük değeri bulan fonksiyonumuz;
1 | int enBuyukDegeriBul(eleman* agac) |
Ş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 | eleman* sil(eleman* agac, int silinecekDeger) |
Son olarak test kodlarını içeren main fonksiyonumuz;
1 | int main(int argc, char *argv[]) |
Böylece ikili arama ağacı yapımızı da temel olarak incelemiş olduk. Sonraki yazılarda görüşmek üzere.