Örnekle İkili Arama Ağacı (BST)

İkili Arama Ağacının Nitelikleri

Bir BST, birden fazla düğümden oluşur ve aşağıdaki niteliklerden oluşur:

• Ağacın düğümleri ebeveyn-çocuk ilişkisiyle temsil edilir
• Her ana düğüm sıfır alt düğüme veya sol ve sağ tarafta en fazla iki alt düğüme veya alt ağaca sahip olabilir.
• İkili arama ağacı olarak da bilinen her alt ağacın sağında ve solunda alt dalları vardır.
• Tüm düğümler anahtar/değer çiftleriyle bağlantılıdır.
• Sol alt ağaçta bulunan düğümlerin anahtarları, üst düğümlerinin anahtarlarından daha küçüktür
• Benzer şekilde, sol alt ağaç düğümlerinin anahtarları, üst düğümlerinin anahtarlarından daha düşük değerlere sahiptir.

1. Ana düğüm veya üst seviye 11 vardır. Onun altında, kendi anahtar değerlerine sahip sol ve sağ düğümler/dallar vardır.
2. Sağ alt ağaç, üst düğümden daha büyük anahtar değerlere sahiptir
3. Sol alt ağaçta üst düğümden değerler var

Neden İkili Arama Ağacına ihtiyacımız var?

• İkili arama ağacını gerçek dünya sorunlarına optimum çözüm haline getiren iki ana faktör Hız ve Doğruluktur.
• İkili aramanın ebeveyn-çocuk ilişkileriyle dal benzeri bir formatta olması nedeniyle algoritma, elemanların ağacın hangi konumunda aranması gerektiğini bilir. Bu, programın istenen öğeyi bulmak için yapması gereken anahtar/değer karşılaştırmalarının sayısını azaltır.
• Ayrıca aranacak elemanın ana düğümden büyük veya küçük olması durumunda düğüm ağacın hangi tarafında aranacağını bilir. Bunun nedeni, sol alt ağacın her zaman üst düğümden daha küçük olması ve sağ alt ağacın her zaman üst düğüme eşit veya ondan daha büyük değerlere sahip olmasıdır.
• BST, karmaşık aramaları, sağlam oyun mantığını, otomatik tamamlama aktivitelerini ve grafikleri uygulamak için yaygın olarak kullanılır.
• Algoritma, arama, ekleme ve silme gibi işlemleri verimli bir şekilde destekler.

İkili Ağaç Türleri

Üç tür ikili ağaç şunlardır:

• Tam ikili ağaç: Ağaçlardaki tüm seviyeler, son seviyenin olası istisnalarıyla doludur. Benzer şekilde, tüm düğümler dolu ve en sola yöneliyor.
• Tam ikili ağaç: Yaprak dışındaki tüm düğümlerin 2 alt düğümü vardır.
• Dengeli veya Mükemmel ikili ağaç: Ağaçtaki tüm düğümlerin iki çocuğu vardır. Ayrıca her alt düğümün aynı seviyesi vardır.

Hakkında daha fazla bilgi alın Veri Yapısında İkili Ağaç Eğer ilgini çektiyse.

İkili Arama Ağacı Nasıl Çalışır?

Ağacın her zaman bir kök düğümü ve ister solda ister sağda olsun başka alt düğümleri vardır. Algoritma, tüm işlemleri buna göre sol veya sağ alt ağaçtaki kök ve onun alt düğümleriyle karşılaştırarak gerçekleştirir.

Karşılaştırmanın ardından eklenecek, aranacak veya silinecek öğeye bağlı olarak algoritma, kök düğümün sol veya sağ alt ağacını kolaylıkla bırakabilir.

BST, temel olarak kullanımınıza aşağıdaki üç tipte işlem sunmaktadır:

• Arama: öğeyi ikili ağaçtan arar
• Ekle: ikili ağaca bir öğe ekler
• Sil: öğeyi ikili ağaçtan silin

Her işlemin kendine özgü yapısı ve yürütme/analiz yöntemi vardır, ancak bunların en karmaşığı Silme işlemidir.

Ara Operayon

Ağacı analiz etmeye her zaman kök düğümden başlayın ve ardından yerleştirilecek öğenin kökten küçük veya büyük olmasına bağlı olarak kök düğümün sağ veya sol alt ağacına doğru ilerleyin.

1. Aranacak eleman 10
2. Öğeyi 12, 10 < 12 kök düğümüyle karşılaştırın, böylece sol alt ağaca gidersiniz. Sağ alt ağacı analiz etmeye gerek yok
3. Şimdi 10'u 7. düğümle karşılaştırın, 10 > 7, dolayısıyla sağ alt ağaca geçin
4. Daha sonra 10'u bir sonraki düğüm olan 9, 10 > 9 ile karşılaştırın, sağ alt ağaç çocuğuna bakın
5. 10, düğümdeki değerle eşleşir, 10 = 10, kullanıcıya değeri döndürür.

BST'de Arama İçin Sahte Kod

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

Ekle Operayon

Bu çok doğrudan bir operasyondur. İlk önce kök düğüm eklenir, ardından bir sonraki değer kök düğümle karşılaştırılır. Değer kökten büyükse sağ alt ağaca, kökten küçükse sol alt ağaca eklenir.

1. Soldan sağa doğru bir BST'ye eklenmesi gereken 6 öğenin listesi vardır.
2. Kök düğüm olarak 12'yi ekleyin ve sağ ve sol alt ağaca uygun şekilde yerleştirmek için sonraki 7 ve 9 değerlerini karşılaştırın
3. Geriye kalan 19, 5 ve 10 değerlerini kök düğüm 12 ile karşılaştırın ve buna göre yerleştirin. 19 > 12, bunu 12'nin sağ çocuğu olarak yerleştirin, 5 < 12 & 5 < 7, dolayısıyla 7'nin sol çocuğu olarak yerleştirin. Şimdi 10'u karşılaştırın, 10 < 12 ve 10 > 7 ve 10 > 9, 10'a yerleştirin 9'un sağ alt ağacı olarak.

BST'ye Düğüm Eklemek için Sahte Kod

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Sil Operaleri

Bir BST'den bir düğümün silinmesi için bazı durumlar vardır; örneğin bir kökün silinmesi veya bir yaprak düğümün silinmesi. Ayrıca bir kökü sildikten sonra kök düğümü düşünmemiz gerekir.

Diyelim ki bir yaprak düğümü silmek istiyoruz, onu silebiliriz, ancak bir kökü silmek istiyorsak, kökün değerini başka bir düğümle değiştirmemiz gerekir. Aşağıdaki örneği ele alalım:

• Durum 1- Sıfır çocuğu olan düğüm: Bu en kolay durumdur, sadece sağda veya solda başka çocuğu olmayan düğümü silmeniz yeterlidir.
• Durum 2 – Tek çocuklu düğüm: Düğümü sildiğinizde, alt düğümünü silinen değerin üst düğümüne bağlamanız yeterlidir.
• Durum 3 İki çocuğu olan düğüm: Bu en zor durumdur ve aşağıdaki iki kurala göre çalışır
• 3a – Sırayla Öncül: iki çocuklu düğümü silmeniz ve onu, silinen düğümün sol alt ağacındaki en büyük değerle değiştirmeniz gerekir.
• 3b – Sırayla Ardıl: iki çocuklu düğümü silmeniz ve onu, silinen düğümün sağ alt ağacındaki en büyük değerle değiştirmeniz gerekir.

1. Bu, alt öğesi olmayan bir düğümü sildiğiniz ilk silme durumudur. Diyagramda gördüğünüz gibi 19, 10 ve 5'in çocuğu yok. Ama 19'unu sileceğiz.
2. 19 değerini silin ve bağlantıyı düğümden kaldırın.
3. BST'nin 19'suz yeni yapısını görüntüleyin

1. Bu, şemada 1'un bir çocuğu olduğunu görebileceğiniz gibi, 9 çocuğu olan bir düğümü sildiğiniz ikinci silme durumudur.
2. 9 nolu düğümü silin ve onu 10 nolu çocuğuyla değiştirin ve 7'den 10'a bir bağlantı ekleyin
3. BST'nin 9'suz yeni yapısını görüntüleyin

1. Burada iki çocuğu olan 12. düğümü sileceksiniz.
2. Düğümün silinmesi, sırasıyla öncül kuralına göre gerçekleşecektir; bu, 12'nin sol alt ağacındaki en büyük öğenin onun yerini alacağı anlamına gelir.
3. 12 numaralı düğümü silin ve sol alt ağaçtaki en büyük değer olduğundan 10 ile değiştirin
4. 12'yi sildikten sonra BST'nin yeni yapısını görüntüleyin

1. 1 İki çocuğu olan 12 numaralı düğümü silin
2. 2 Düğümün silinmesi Sıralı Ardıl kuralına göre gerçekleşecektir; bu, 12'nin sağ alt ağacındaki en büyük öğenin onun yerini alacağı anlamına gelir.
3. 3 12 numaralı düğümü silin ve sağ alt ağaçtaki en büyük değer olduğundan 19 ile değiştirin
4. 4 12'yi sildikten sonra BST'nin yeni yapısını görüntüleyin

Bir Düğümü Silmek için Sahte Kod

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Önemli Terimler

• Ekle: Ağaca bir öğe ekler/ağaç oluşturur.
• Ara: Ağaçtaki bir öğeyi arar.
• Ön Sipariş Geçişi: Bir ağacı ön sipariş tarzında geçer.
• Sırasız Geçiş: Bir ağacın sıralı bir şekilde geçmesini sağlar.
• Sipariş Sonrası Geçiş: Sipariş sonrası bir şekilde bir ağacın üzerinden geçer.

ÖZET

• BST, düğüm değerlerinin kök düğüm ile karşılaştırılmasına dayalı olarak çeşitli işlemleri gerçekleştiren ileri düzey bir algoritmadır.
• Ebeveyn-çocuk hiyerarşisindeki noktalardan herhangi biri düğümü temsil eder. En az bir ebeveyn veya kök düğüm her zaman mevcut kalır.
• Sol alt ağaç ve sağ alt ağaç vardır. Sol alt ağaç kök düğümden daha küçük değerleri içerir. Ancak sağ alt ağaç, kök düğümden daha büyük bir değer içerir.
• Her düğümün sıfır, bir veya iki çocuğu olabilir.
• İkili arama ağacı, arama, ekleme ve silme gibi birincil işlemleri kolaylaştırır.
• Silme işlemi en karmaşık olduğundan birden fazla duruma sahiptir, örneğin, çocuğu olmayan bir düğüm, bir çocuğu olan bir düğüm ve iki çocuğu olan bir düğüm.
• Algoritma; oyunlar, otomatik tamamlama verileri ve grafikler gibi gerçek dünya çözümlerinde kullanılır.