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

İkili Arama Ağacı Nedir?

İkili Arama Ağacı (BST), ağaç yapısında modellenen düğümü, sol ve sağ dallarını analiz etmek ve değeri döndürmek için kullanılan gelişmiş bir algoritmadır. BST, temel bir ikili arama algoritmasının mimarisi üzerine kurulmuştur; bu nedenle, düğümlerin daha hızlı aranmasını, eklenmesini ve kaldırılmasını sağlar. Bu da programı gerçekten hızlı ve doğru hale getirir.

İ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şkisi şeklinde 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, sağ alt ağaçta bulunan düğümlerin anahtarları, üst düğümlerinin anahtarlarından daha büyüktür.

1. Burada ana düğüm veya üst düzey 11 bulunur. Bunun altında, kendi anahtar değerlerine sahip sol ve sağ düğümler/dallar yer alır.
2. Sağdaki alt ağacın anahtar değerleri, üst düğümün anahtar değerlerinden daha büyüktür.
3. Sol alt ağacın anahtar değerleri, üst düğümün anahtar değerlerinden daha küçüktür.

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

• İkili arama ağacını herhangi bir gerçek dünya problemine en uygun çözüm haline getiren iki temel 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 üst düğümden büyük veya küçükse, düğüm hangi ağaç tarafında arama yapacağını bilir. Bunun nedeni, sol alt ağacın her zaman üst düğümden küçük olması ve sağ alt ağacın değerlerinin her zaman üst düğüme eşit veya ondan büyük 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çtaki tüm seviyeler dolu, son seviyede olası bir istisna dışında. Benzer şekilde, tüm düğümler dolu ve en sola doğru yöneliyorlar.
• Tam ikili ağaç: Yaprak düğüm hariç tüm düğümlerin 2 alt düğümü vardır.
• Dengeli veya Mükemmel ikili ağaç: Ağaç yapısında, tüm düğümlerin iki çocuğu vardır. Ayrıca, her alt düğüm aynı seviyededir.

Hakkında daha fazla bilgi edinin 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.

Eklenecek, aranacak veya silinecek öğeye bağlı olarak, karşılaştırmadan sonra algoritma kök düğümün sol veya sağ alt ağacını kolayca silebilir.

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

• Arama: İkili ağaçtan elemanı arar.
• Yerleştirin: İkili ağaca bir eleman ekler.
• Sil: İkili ağaçtan öğeyi siler.

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 daha sonra, bulunacak elemanın 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'dur.
2. Elemanı kök düğüm 12 ile karşılaştırın, 10 < 12, bu nedenle sol alt ağaca geçin. Sağ alt ağacı analiz etmenize gerek yok.
3. Şimdi 10'u 7 numaralı düğümle karşılaştırın, 10 > 7, bu yüzden sağ alt ağaca geçin.
4. Ardından 10'u bir sonraki düğüm olan 9 ile karşılaştırın, 10 > 9 ise sağ alt ağaçtaki çocuğa bakın.
5. 10, düğümdeki değerle eşleşir, 10 = 10, kullanıcıya değeri döndürür.

Sözde Code BST'de arama için

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 oldukça basit bir işlemdir. Öncelikle 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üçükse sol alt ağaca eklenir.

1. İkili arama ağacına soldan sağa doğru sırayla eklenmesi gereken 6 elemanlık bir liste var.
2. Kök düğüm olarak 12'yi ekleyin ve sırasıyla sağ ve sol alt ağaçlara eklemek için sonraki değerler olan 7 ve 9'u karşılaştırın.
3. Kalan değerler olan 19, 5 ve 10'u kök düğüm 12 ile karşılaştırın ve buna göre yerleştirin. 19 > 12 ise, 12'nin sağ çocuğu olarak yerleştirin; 5 < 12 ve 5 < 7 ise, 7'nin sol çocuğu olarak yerleştirin. Şimdi 10'u karşılaştırın, 10 < 12 ve 10 > 7 ve 10 > 9 ise, 10'u 9'un sağ alt ağacına yerleştirin.

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

İkili arama ağacından bir düğümü silmek için bazı durumlar söz konusudur; örneğin, kök düğümü veya yaprak düğümü silmek. Ayrıca, bir kök düğümü sildikten sonra, kök düğümü de 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 – Hiç çocuğu olmayan düğüm: Bu en kolay durum, sağında veya solunda başka çocuğu olmayan düğümü silmeniz yeterli.
• Durum 2 – Tek çocuklu düğüm: Düğümü sildikten sonra, silinen değerin alt düğümünü üst düğümüne bağlamanız yeterlidir.
• 3. Durum – İki çocuğu olan düğüm: Bu en zor durum ve şu iki kurala göre işliyor:
  • 3a – Sıralı Önceki İşlem: İki alt düğümü olan düğümü silmeniz ve silinen düğümün sol alt ağacındaki en büyük değerle değiştirmeniz gerekiyor.
  • 3b – Sıralı Halef: İki alt düğümü olan düğümü silmeniz ve silinen düğümün sağ alt ağacındaki en küçük değerle değiştirmeniz gerekiyor.

1. Bu, çocuk düğümü olmayan bir düğümü sildiğiniz ilk silme işlemidir. Şemada da görebileceğiniz gibi, 19, 10 ve 5'in çocuk düğümü yoktur. Ancak 19'u sileceğiz.
2. 19 değerini silin ve bağlantıyı düğümden kaldırın.
3. 19. basamak olmadan BST'nin yeni yapısını inceleyin.

1. Bu, bir alt öğesi olan bir düğümü sildiğiniz ikinci silme işlemidir. Şemada da görebileceğiniz gibi, 9'un bir alt öğesi vardır.
2. 9 numaralı düğümü silin ve yerine alt düğümü olan 10 numaralı düğümü ekleyin, ayrıca 7'den 10'a bir bağlantı ekleyin.
3. 9. basamak olmadan BST'nin yeni yapısını inceleyin.

1. Burada iki alt düğümü olan 12 numaralı düğümü sileceksiniz.
2. Düğümün silinmesi, sıralı öncül kuralına göre gerçekleşecektir; bu da 12'nin sol alt ağacındaki en büyük elemanın onun yerini alacağı anlamına gelir.
3. 12 numaralı düğümü silin ve yerine 10 numaralı düğümü koyun, çünkü bu sol alt ağaçtaki en büyük değerdir.
4. 12. elemanı sildikten sonra ikili arama ağacının yeni yapısını inceleyin.

1. İki çocuğu olan 12 numaralı düğümü silin.
2. Düğümün silinmesi, Sıralı Ardıl kuralına göre gerçekleşecektir; bu da 12'nin sağ alt ağacındaki en küçük elemanın onun yerini alacağı anlamına gelir.
3. 12 numaralı düğümü silin ve yerine 19 numaralı düğümü koyun, çünkü bu sağ alt ağaçtaki en küçük değerdir.
4. 12. elemanı sildikten sonra ikili arama ağacının yeni yapısını inceleyin.

Sözde Code Bir düğümü silmek için

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, delete the successor
        free(newNode)
    else
        free(y)

Önemli Terimler

• Yerleştirin: Bir ağaca öğe ekler / bir ağaç oluşturur.
• Arama: Ağaç yapısında bir öğeyi arar.
• Ön Sıralı Gezinti: Bir ağacı öncelikli bir sırayla dolaşır.
• Sıra Geçişi: Bir ağaç yapısını sırayla dolaşır.
• Sipariş Sonrası Geçiş: Bir ağacı, sonradan sıralanmış bir şekilde dolaşır.

SSS