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

İçindekiler:

Anonim

İkili Arama Ağacı nedir?

İkili arama ağacı, bir ağaç yapısında modellenen ve değeri döndüren düğümü, sol ve sağ dallarını analiz etmek için kullanılan gelişmiş bir algoritmadır. BST, temel bir ikili arama algoritmasının mimarisi üzerine tasarlanmıştır; dolayısıyla düğümlerin daha hızlı aranmasını, eklenmesini ve kaldırılmasını sağlar. Bu, programı gerçekten hızlı ve doğru yapar.

Bu Veri Yapısı eğitiminde şunları öğreneceksiniz:

  • İkili Arama Ağacı nedir?
  • İkili Arama Ağacının Nitelikleri
  • Neden bir İkili Arama Ağacına ihtiyacımız var?
  • İkili Ağaç Türleri
  • İkili Arama Ağacı Nasıl Çalışır?
  • Önemli Terimler

İkili Arama Ağacının Nitelikleri

Bir BST, birden çok düğümden oluşur ve aşağıdaki özniteliklerden oluşur:

  • Ağacın düğümleri bir ebeveyn-çocuk ilişkisinde temsil edilir
  • Her bir ana düğüm, sıfır çocuk düğüme veya sol ve sağ taraflarda maksimum iki alt düğüme veya alt ağaçlara 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 az değere sahiptir.

  1. Ana düğüm veya üst düzey 11. Altında, kendi anahtar değerlerine sahip sol ve sağ düğümler / dallar vardır.
  2. Sağdaki alt ağaç, üst düğümden daha büyük anahtar değerlerine sahip
  3. Sol alt ağaç, ana düğümden daha değerlere sahip

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

  • İkili arama ağacını herhangi bir gerçek dünya sorununa en uygun çözüm haline getiren iki ana faktör Hız ve Doğruluktur.
  • İkili aramanın üst-çocuk ilişkileri ile dal benzeri bir formatta olması nedeniyle, algoritma, öğelerin 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.
  • Ek olarak, aranacak elemanın ana düğümden daha büyük veya daha az olması durumunda, düğüm hangi ağaç tarafının aranacağını bilir. Bunun nedeni, sol alt ağacın her zaman ana düğümden daha küçük olması ve sağ alt ağacın her zaman ana düğüme eşit veya ondan daha büyük değerlere sahip olmasıdır.
  • BST, karmaşık aramalar, sağlam oyun mantığı, otomatik tamamlama etkinlikleri 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ç vardır:

  • Komple 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önlendiriyor.
  • Tam ikili ağaç: Yaprak hariç tüm düğümlerin 2 alt düğümü vardır.
  • Dengeli veya Mükemmel ikili ağaç: Ağaçta, tüm düğümlerin iki çocuğu vardır. Ayrıca, her alt düğümün aynı seviyesi vardır.

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

Ağacın her zaman bir kök düğümü ve solda veya sağda başka alt düğümler vardır. Algoritma, değerleri kök ve bunun sol veya sağ alt ağaçtaki diğer alt düğümleriyle uygun şekilde karşılaştırarak tüm işlemleri gerçekleştirir.

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

BST, öncelikle kullanımınız için aşağıdaki üç tür işlemi sunar:

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

Her işlemin kendi yapısı ve yürütme / analiz yöntemi vardır, ancak en karmaşık olanı Silme işlemidir.

Arama İşlemi

Analiz ağacını her zaman kök düğümde başlatın ve ardından yerleştirilecek öğenin kökten daha küçük veya daha 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, 10 <12 ile karşılaştırın, böylece soldaki alt ağaca geçersiniz. Sağ alt ağacı analiz etmeye gerek yok
  3. Şimdi 10'u düğüm 7, 10> 7 ile karşılaştırın, bu yüzden sağ alt ağaca geçin
  4. Sonra 10'u sonraki düğüm olan 9, 10> 9 ile karşılaştırın, sağ alt ağacın alt kısmına bakın
  5. Düğümdeki değerle 10 eşleşme, 10 = 10, değeri kullanıcıya döndür.

İşlem Ekle

Bu çok basit bir işlem. Ö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 sırayla bir BST'ye eklenmesi gereken 6 öğeden oluşan bir liste var
  2. Kök düğüm olarak 12'yi ekleyin ve uygun şekilde sağ ve sol alt ağaca eklemek için sonraki 7 ve 9 değerlerini karşılaştırın
  3. Kalan 19, 5 ve 10 değerlerini kök düğüm 12 ile karşılaştırın ve uygun şekilde yerleştirin. 19> 12 onu 12, 5 <12 ve 5 <7'nin sağ çocuğu olarak yerleştirin, dolayısıyla 7'nin sol çocuğu olarak yerleştirin.
    1. Şimdi 10'u karşılaştırın, 10 eşittir <12 & 10 eşittir> 7 & 10 eşittir> 9, 10. basamak 9'un sağ alt ağacı olarak.

İşlemleri Sil

Silme, diğer tüm işlemler arasında en gelişmiş ve karmaşık olanıdır. BST'de silinmek üzere ele alınan birden fazla vaka vardır.

  • Durum 1- Sıfır çocuklu düğüm: bu en kolay durumdur, sadece sağda veya solda başka çocuğu olmayan düğümü silmeniz gerekir.
  • Durum 2 - Tek çocuklu düğüm: Düğümü sildiğinizde, sadece alt düğümünü silinen değerin üst düğümüne bağlayın.
  • Durum 3 İki çocuklu düğüm: bu en zor durumdur ve aşağıdaki iki kurala göre çalışır
    • 3a - Öncül Sırasında: düğümü iki alt öğe ile silmeniz ve onu silinen düğümün sol alt ağacındaki en büyük değerle değiştirmeniz gerekir
    • 3b - Sıralı Halef: düğümü iki alt öğe ile 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 da görebileceğiniz gibi 19, 10 ve 5'in çocuğu yok. Ancak 19'u sileceğiz.
  2. 19 değerini silin ve bağlantıyı düğümden kaldırın.
  3. 19 olmadan BST'nin yeni yapısını görüntüleyin

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

  1. Burada iki çocuğu olan düğüm 12'yi sileceksiniz.
  2. Düğümün silinmesi, sırayla önceki kurala bağlı olarak meydana gelecektir, bu da, 12'nin sol alt ağacındaki en büyük elemanın onun yerini alacağı anlamına gelir.
  3. 12 nolu düğümü silin ve sol alt ağaçtaki en büyük değer olduğu için 10 ile değiştirin
  4. 12'yi sildikten sonra BST'nin yeni yapısını görüntüleyin

  1. 1 İki alt öğesi olan bir düğümü 12 silin
  2. 2 Düğümün silinmesi Sıralı Ardıl kuralına göre gerçekleşir, bu da 12'nin sağ alt ağacındaki en büyük öğenin onun yerini alacağı anlamına gelir.
  3. 3 12 nolu düğümü silin ve 19 ile değiştirin, çünkü bu sağ alt ağaçtaki en büyük değerdir
  4. 4 Sildikten sonra BST'nin yeni yapısını görüntüleyin 12

Önemli Terimler

  • Ekle - Ağaca bir öğe ekler / bir ağaç oluşturur.
  • Ara - Ağaçtaki bir öğeyi arar.
  • Preorder Traversal - Bir ağacı ön sipariş şeklinde dolaşır.
  • Inorder Traversal - Bir ağacı sırayla dolaşır.
  • Postorder Traversal - Sipariş sonrası bir şekilde bir ağacı gezer.

Özet

  • BST, düğüm değerlerinin kök düğümle karşılaştırılmasına dayalı olarak çeşitli işlemler gerçekleştiren ileri düzey bir algoritmadır.
  • Bir ebeveyn-çocuk hiyerarşisindeki noktalardan herhangi biri düğümü temsil eder. En az bir ana veya kök düğüm her zaman mevcut kalır.
  • Bir sol alt ağaç ve sağ alt ağaç vardır. Soldaki alt ağaç, kök düğümden daha küçük değerler 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.
  • En karmaşık olan Sil, birden çok duruma sahiptir; örneğin, alt öğesi olmayan bir düğüm, tek çocuklu düğüm ve iki çocuklu düğüm.
  • Algoritma; oyunlar, otomatik tamamlama verileri ve grafikler gibi gerçek dünya çözümlerinde kullanılır.