ikili ağaç ve binary search tree farkı: Arama Mantığı

ikili ağaç ve binary search tree farkı, düğümlerin çocuk sayısından çok, değerlerin nasıl yerleştirildiğiyle ilgilidir. İkili ağaçta her düğümün en fazla iki çocuğu bulunur; Binary Search Tree’de (BST) ise buna ek olarak sol taraftaki değerlerin küçük, sağ taraftaki değerlerin büyük olması beklenir.

Bu nedenle iki çocuğu olan her düğüm, ağacı kendiliğinden BST yapmaz. BST kuralı yalnızca kökte değil, kökün altındaki tüm alt ağaçlarda da korunmalıdır.

İki Çocuğu Olan Her Ağaç Neden BST Değildir?

İkili ağaç, öncelikle yapısal bir tanımdır. Bir düğümün sıfır, bir veya en fazla iki çocuğu olabilir. Çocukların değerleri arasında küçük-büyük ilişkisi bulunması, ikili ağaç olmanın zorunlu şartı değildir.

Binary Search Tree ise yapısal koşula bir de sıralama kuralı ekler. Bir düğümün sol alt ağacındaki değerler o düğümden küçük, sağ alt ağacındaki değerler ise büyük olmalıdır. Üstelik bu kural yalnızca doğrudan çocuklar için değil, ilgili alt ağaçların tamamı için geçerlidir.

Örneğin kökü 7 olan bir ağaçta 4’ün 7’nin solunda, 9’un ise sağında bulunması ilk bakışta doğru görünür. Ancak 4’ün sol çocuğu 6, sağ çocuğu 2 yapılırsa ağaç hâlâ ikili ağaçtır; çünkü hiçbir düğümün ikiden fazla çocuğu yoktur. Buna karşılık 4’ün solunda 6, sağında 2 bulunduğu için BST kuralı bozulur: küçük olması gereken sol tarafta 6, büyük olması gereken sağ tarafta 2 vardır.

Kısacası “iki çocuğu var” ifadesi yalnızca ağacın biçimini anlatır. BST olup olmadığını belirleyen asıl unsur, her düğüm çevresinde korunan değer düzenidir.

Düğüm, Kök ve Alt Ağaçlar Üzerinden İki Yapıyı Karşılaştırma

Düğüm, ağacın içinde bir değer taşıyan temel birimdir. Ağacın en üstündeki düğüme kök adı verilir. Bir düğümün altında bulunan ve o düğümden başlayarak devam eden bölüme ise alt ağaç denir. Bir düğümün sol tarafında bulunan bölüm sol alt ağaç, sağ tarafında bulunan bölüm sağ alt ağaç olarak adlandırılır.

Aşağıdaki iki düzende aynı değerler kullanılır: 7, 4, 9, 2 ve 6. İlk düzende 7 köktür; 4 ve 9 onun çocuklarıdır. 4’ün çocukları 2 ve 6’dır. İkinci düzende yalnızca 4’ün altındaki çocukların yerleri değiştirilmiştir.

Her iki yapı da ikili ağaçtır; çünkü her düğümün en fazla iki çocuğu vardır. Ancak yalnızca ilk yapı BST’dir. İkinci yapıda 6, 4’ün solunda; 2 ise sağında yer aldığı için BST’nin arama düzeni karşılanmaz. Bu küçük yerleşim farkı, arama sırasında hangi dala gidileceğini doğrudan değiştirir.

Bir Ağacın BST Olup Olmadığını Kontrol Etme Listesi

İkili ağaç ve binary search tree farkı, yalnızca düğümlerin en fazla iki çocuğa sahip olmasıyla açıklanamaz. Bir yapının BST sayılabilmesi için değerlerin, ağacın tamamında belirli bir arama kuralına uyması gerekir. Aşağıdaki kontrol listesi pratik bir başlangıç sağlar:

1. Her düğümün en fazla iki çocuğu var mı?
2. Her düğüm için sol alt ağaçtaki değerler, seçilen BST kuralına göre düğümden küçük; sağ alt ağaçtaki değerler büyük mü?
3. Bu koşul yalnızca doğrudan çocuklarda değil, sol ve sağ alt ağaçların tamamında tekrar tekrar sağlanıyor mu?
4. Eşit değerler varsa uygulamanın kuralı ne? Eşit değerler sola, sağa veya ayrı bir politikaya göre mi yerleştiriliyor?

Örneğin aşağıdaki yapı bir BST düzenidir:

        7
       / 
      4   9
     / 
    2   6

Her düğümün en fazla iki çocuğu vardır. 7'nin solundaki tüm değerler 7'den, sağındaki değer ise 7'den büyüktür. Ayrıca 4'ün solundaki 2, 4'ten küçük; sağındaki 6 ise 4'ten büyüktür. Alt ağaçların içinde de aynı kural sürdüğü için bu yapı BST kontrolünden geçer.

Şimdi benzer görünen şu yapıya bakalım:

        7
       / 
      4   9
     / 
    6   2

Bu ağaçta da her düğümün en fazla iki çocuğu bulunur ve 7 açısından ilk bakışta değerler uygun görünür. Ancak 4 düğümünün solunda 4'ten büyük 6, sağında ise 4'ten küçük 2 vardır. Bu nedenle yapı BST değildir. Yalnızca doğrudan çocukları veya yalnızca kökü kontrol etmek yeterli olmaz; her düğümün alt ağacı bütünüyle incelenmelidir.

BST'de Arama Kökten Başlayarak Nasıl İlerler?

BST'de arama kökten başlar ve her karşılaştırma, aranacak değerin hangi alt ağaçta bulunabileceğini belirler. 7, 4, 9, 2 ve 6 değerlerinden oluşan BST içinde 6 değerini arayalım:

1. 6, kök 7'den küçük olduğu için sol alt ağaca, yani 4 düğümüne ilerlenir.
2. 6, 4'ten büyük olduğu için 4 düğümünün sağ çocuğuna, yani 6'ya ilerlenir.
3. Aranan 6 ile mevcut düğümün değeri eşit olduğu için değer bulunur.

Beklenen sonuç: 6 değeri bulundu ve kökten itibaren 7, 4, 6 düğümleri karşılaştırıldı.

Bu mantık, dil bağımsız bir sözde kodla şöyle gösterilebilir:

ara(kök, hedef):
    mevcut = kök

    mevcut boş değilken:
        eğer hedef == mevcut.değer:
            döndür "bulundu"
        eğer hedef < mevcut.değer:
            mevcut = mevcut.sol
        aksi halde:
            mevcut = mevcut.sağ

    döndür "bulunamadı"

BST'de her karşılaştırma bir alt ağacı elememizi sağlar. Genel ikili ağaçta ise değerlerin sıralı olması garanti edilmediğinden arama, birden fazla dalı dolaşmayı gerektirebilir. Ekleme işleminde de BST, aynı karşılaştırma mantığıyla uygun boş konuma ilerler; genel ikili ağaçta ise değer temelli tek bir evrensel ekleme kuralı yoktur.

Bu ayrımı pekiştirmek ve algoritmik düşünme temellerini yoklamak için algoritmik düşünme ve kodlama bilgi testlerine göz atabilirsin.

BST'de Sıralı Dolaşma Neden Sıralı Sonuç Verir?

Bir ağaçta sıralı dolaşma (in-order traversal), düğümleri şu sırayla ziyaret eder: önce sol alt ağaç, sonra mevcut düğüm, ardından sağ alt ağaç. Bu işlem yalnızca kökte değil, ağacın her alt ağacında aynı şekilde uygulanır.

BST'nin temel kuralına göre bir düğümün sol alt ağacındaki değerler düğümden küçük, sağ alt ağacındaki değerler ise düğümden büyüktür. Bu kural her alt ağaçta tekrarlandığı için sıralı dolaşma önce küçük değerleri, sonra aradaki düğümü, en sonunda büyük değerleri ziyaret eder. Böylece çıktı küçükten büyüğe doğru oluşur.

Örneğin kökü 7 olan ve sol alt ağacında 4, 4'ün çocukları olarak 2 ve 6, sağ alt ağacında da 9 bulunan BST'yi ele alalım. Dolaşma adımları şöyledir:

1. 7'nin sol alt ağacına git.
2. 4'ün solundaki 2'yi ziyaret et.
3. 4'ü ziyaret et.
4. 4'ün sağındaki 6'yı ziyaret et.
5. 7'yi, ardından sağındaki 9'u ziyaret et.

Beklenen sıralı dolaşma çıktısı 2, 4, 6, 7, 9 olur.

Aynı değerleri BST kuralını bozan bir ikili ağaçta yerleştirelim: kök 7, 7'nin solunda 4, sağında 9 bulunsun; 4'ün sol çocuğu 6, sağ çocuğu ise 2 olsun. Bu yapı BST değildir; çünkü 4'ün solundaki 6 daha büyük, sağındaki 2 ise daha küçüktür.

Bu ağaçta yine sol alt ağaç, düğüm, sağ alt ağaç sırası izlenirse çıktı 6, 4, 2, 7, 9 olur. Görüldüğü gibi sonuç sıralı değildir. Dolayısıyla genel bir ikili ağaçta sıralı dolaşmanın küçükten büyüğe çıktı verme garantisi yoktur; bu özellik, BST'nin düzenleme kuralından kaynaklanır.

Dengesiz BST'de Arama Neden O(n) Olabilir?

BST aramasının maliyeti, kökten başlayarak aşağı doğru izlenen yolun uzunluğuna bağlıdır. Her karşılaştırmada sol veya sağ alt ağaçtan biri seçildiği için ağaç uygun biçimde şekillendiğinde gereksiz düğümlerin önemli bir bölümü elenir. Ancak BST olması, ağacın her zaman dengeli veya hızlı olacağı anlamına gelmez.

Örneğin değerler küçükten büyüğe doğru tek tek eklenirse 2, 4, 6, 7, 9 gibi bir sıra, bazı durumlarda her yeni düğümün bir öncekinin sağ çocuğu olduğu zincir benzeri bir yapı oluşturabilir. Böyle bir yapıda 9 değerini aramak için kökten başlayıp düğümlerin büyük bölümünü incelemek gerekebilir. Benzer biçimde, ters yönde ekleme de sola doğru uzayan bir yapı oluşturabilir.

Genel olarak BST araması O(h) maliyetine sahiptir; burada h, ağacın yüksekliğini ifade eder. Ağaç dengeli bir şekle yakınsa kökten hedefe giden yol kısa olabilir. Fakat dengesiz bir ağaçta yükseklik düğüm sayısına yaklaşabilir. Bu nedenle en kötü durumda arama maliyeti O(n) olabilir. Bu, her BST aramasının mutlaka bu sürede çalışacağı anlamına gelmez; sonuç, ağacın şekline ve aranan değerin konumuna göre değişir.

Ağacın yüksekliğini kontrol etmeye yönelik ileri dengeleme yapıları ayrı bir konudur ve burada ayrıntılarına girmiyoruz. Temel ayrım şudur: İkili ağaç yalnızca her düğümün en fazla iki çocuğu olmasını şart koşarken BST, buna ek olarak değerlerin sol ve sağ alt ağaçlara nasıl yerleşeceğini de belirler. Bu düzen, aramayı ve sıralı dolaşmayı mümkün kılar; ancak ağacın dengeli kalacağı kendiliğinden garanti edilmez. Veri yapılarıyla ilgili diğer açıklamalar için bilgi verici veri yapıları yazılarına göz atabilirsin.

Sık Sorulan Sorular

İki çocuğu olan her ikili ağaç BST midir?

Hayır. İkili ağaçta temel koşul, her düğümün en fazla iki çocuğunun olmasıdır. BST'de buna ek olarak sol alt ağaçtaki değerlerin küçük, sağ alt ağaçtaki değerlerin büyük olması gerekir.

Bir ağacın BST olup olmadığını yalnızca kökün çocuklarına bakarak anlayabilir miyim?

Hayır. Kökün doğrudan çocukları doğru yerde olsa bile daha alt seviyelerdeki bir düğüm BST kuralını bozabilir. Kontrol, ağacın tüm alt ağaçlarını kapsamalıdır.

BST'de eşit değerler sol tarafa mı, sağ tarafa mı yerleştirilir?

Tek bir zorunlu yön yoktur. Uygulama, eşit değerleri sürekli sola, sürekli sağa veya ayrı bir sayaçla aynı düğümde tutacak şekilde bir kural belirleyebilir. Önemli olan bu kuralın tutarlı uygulanmasıdır.

BST araması her zaman O(log n) sürede mi çalışır?

Hayır. O(log n) beklentisi ağacın dengeli veya yüksekliğinin sınırlı olduğu durumlarla ilişkilidir. Dengesiz bir BST'de arama en kötü durumda O(n) olabilir.

Genel bir ikili ağaçta arama neden BST aramasından farklıdır?

Genel ikili ağaçta değerlerin konumuyla ilgili sıralama kuralı bulunmayabilir. Bu nedenle aranan değeri bulmak için birden fazla dalı, hatta ağacın tamamını kontrol etmek gerekebilir.

İkili ağaç ile BST arasındaki farkı anlamanın en kısa yolu, çocuk sayısına değil, düğümlerin değer düzenine ve bu düzenin arama davranışına bakmaktır.