Veri Yapısında B AĞACI: Ara, Ekleme, Silme İşlemi Örneği

İçindekiler:

Anonim

B Ağacı nedir?

B Ağacı , verileri daha hızlı ve bellek açısından verimli bir şekilde aramak, eklemek ve silmek için belirli bir kurallar kümesine dayanan kendi kendini dengeleyen bir veri yapısıdır. Bunu başarmak için aşağıdaki kurallara uyulur ve bir B Ağacı oluşturulur.

B-Ağacı, veri yapısındaki özel bir ağaç türüdür. 1972'de, bu yöntem ilk olarak McCreight tarafından tanıtıldı ve Bayer, ona Yükseklik Dengeli m-yollu Arama Ağacı adını verdi. Sıralanan verileri korumanıza yardımcı olur ve daha kısa sürede Ekleme, arama ve silme gibi çeşitli işlemlere izin verir.

Bu B-Ağacı eğitiminde şunları öğreneceksiniz:

  • B Ağacı nedir?
  • Neden B-Ağacı kullanmalısınız?
  • B Ağacının Tarihçesi
  • Arama İşlemi
  • İşlem Ekle
  • İşlemi Sil

B-Tree Kuralları

İşte, B_Tree oluşturmak için önemli kurallar

  • Tüm yapraklar aynı seviyede oluşturulacaktır.
  • B-Ağacı, aynı zamanda "sıra" olarak da adlandırılan (bir programcı gibi harici bir aktör tarafından belirtilir) bir derece derecesiyle belirlenir ve şu şekilde anılır: 
    m
    ileriye. Değeri 
    m
    verinin esas olarak bulunduğu diskteki blok boyutuna bağlıdır.
  • Düğümün sol alt ağacı, alt ağacın sağ tarafına göre daha düşük değerlere sahip olacaktır. Bu, düğümlerin de soldan sağa artan sırada sıralandığı anlamına gelir.
  • Bir kök düğüm ve alt düğümlerinin içerebileceği maksimum alt düğüm sayısı şu formülle hesaplanır: 
    m - 1
    Örneğin: 
    m = 4max keys: 4 - 1 = 3

  • Kök dışındaki her düğüm, minimum anahtarları içermelidir: 
    [m/2]-1
    Örneğin: 
    m = 4min keys: 4/2-1 = 1
  • Bir düğümün sahip olabileceği maksimum alt düğüm sayısı, derecesine eşittir; 
    m
  • Bir düğümün sahip olabileceği minimum çocuk sayısı, m / 2 olan sıranın yarısıdır (tavan değeri alınır).
  • Bir düğümdeki tüm anahtarlar artan sırada sıralanır.

Neden B-Ağacı kullanmalısınız?

İşte, B-Tree kullanmanın nedenleri

  • Diskte yapılan okuma sayısını azaltır
  • B Ağaçlar, disk boyutuna göre boyutunu (yani alt düğümlerin sayısı) ayarlamak için kolayca optimize edilebilir
  • Büyük miktarda veriyi işlemek için özel olarak tasarlanmış bir tekniktir.
  • Veritabanları ve dosya sistemleri için kullanışlı bir algoritmadır.
  • Büyük veri bloklarını okumak ve yazmak söz konusu olduğunda tercih etmek için iyi bir seçim

B Ağacının Tarihçesi

  • Veriler diskte bloklar halinde saklanır, bu verilere ana belleğe (veya RAM) getirildiğinde veri yapısı denir.
  • Çok büyük veri olması durumunda, diskteki bir kaydın aranması tüm diskin okunmasını gerektirir; bu, yüksek disk erişim frekansı ve veri boyutu nedeniyle zamanı ve ana bellek tüketimini artırır.
  • Bunun üstesinden gelmek için, kayıtların kayıt referansını bulundukları bloklara göre kaydeden dizin tabloları oluşturulur. Bu, zaman ve bellek tüketimini büyük ölçüde azaltır.
  • Çok büyük veriye sahip olduğumuz için çok seviyeli indeks tabloları oluşturabiliyoruz.
  • Çok seviyeli dizin, verileri kendi kendini dengeleyen bir şekilde sıralamak için B Ağacı kullanılarak tasarlanabilir.

Arama İşlemi

Arama işlemi, B Ağacı üzerindeki en basit işlemdir.

Aşağıdaki algoritma uygulanır:

  • Anahtarın (değerin) "k" ile aranmasına izin verin.
  • Aramaya kökten başlayın ve yinelemeli olarak aşağı kaydırın.
  • K, kök değerinden küçükse, sol alt ağaçta arama yapın, k kök değerinden büyükse, sağ alt ağaçta arama yapın.
  • Düğüm bulunan k'ye sahipse, düğümü döndürmeniz yeterlidir.
  • Eğer k düğümde bulunmazsa, daha büyük bir anahtarla alt çocuğa doğru ilerleyin.
  • Ağaçta k bulunmazsa NULL döndürürüz.

İşlem Ekle

B Ağacı kendi kendini dengeleyen bir ağaç olduğundan, herhangi bir düğüme bir anahtar eklemeye zorlayamazsınız.

Aşağıdaki algoritma geçerlidir:

  • Arama işlemini çalıştırın ve uygun yerleştirme yerini bulun.
  • Yeni anahtarı uygun konuma yerleştirin, ancak düğümde zaten maksimum sayıda anahtar varsa:
  • Düğüm, yeni eklenen bir anahtarla birlikte orta öğeden ayrılacaktır.
  • Ortadaki eleman, diğer iki alt düğüm için ebeveyn olacaktır.
  • Düğümler, anahtarları artan sırada yeniden düzenlemelidir.

İPUCU

Ekleme algoritması hakkında aşağıdakiler doğru değildir:

Düğüm dolu olduğundan, bu nedenle bölünecek ve ardından yeni bir değer girilecektir.

Yukarıdaki örnekte:

  • Anahtar için düğümde uygun konumu arayın
  • Anahtarı hedef düğüme ekleyin ve kuralları kontrol edin
  • Eklemeden sonra, düğüm 1 olan minimum anahtar sayısına eşitten fazla mı? Bu durumda evet öyle. Sonraki kuralı kontrol edin.
  • Eklemeden sonra, düğümde maksimum 3'ten fazla anahtar var mı? Bu durumda hayır, olmaz. Bu, B Ağacı'nın herhangi bir kuralı ihlal etmediği ve ekleme işleminin tamamlandığı anlamına gelir.

Yukarıdaki örnekte:

  • Düğüm, maksimum anahtar sayısına ulaştı
  • Düğüm bölünecek ve orta anahtar, geri kalan iki düğümün kök düğümü haline gelecektir.
  • Çift sayıda anahtar olması durumunda, orta düğüm sol önyargı veya sağ eğilim ile seçilecektir.

Yukarıdaki örnekte:

  • Düğümde maksimum anahtar sayısı az
  • 3'ün yanına 1 eklenir, ancak artan sıra kuralı ihlal edilir
  • Bunu düzeltmek için anahtarlar sıralanır

Benzer şekilde, 13 ve 2, düğümler için maksimum anahtar kuralından daha azını yerine getirdiklerinden düğüme kolayca eklenebilir.

Yukarıdaki örnekte:

  • Düğüm, maksimum anahtara eşit anahtarlara sahiptir.
  • Anahtar, hedef düğüme eklenir, ancak maksimum anahtar kuralını ihlal eder.
  • Hedef düğüm bölünmüştür ve sol önyargı ile orta anahtar artık yeni alt düğümlerin ebeveynidir.
  • Yeni düğümler artan sırada düzenlenmiştir.

Benzer şekilde, yukarıdaki kurallara ve durumlara dayalı olarak, değerlerin geri kalanı B Ağacına kolayca eklenebilir.

İşlemi Sil

Silme işlemi, ekleme ve arama işlemlerinden daha fazla kurala sahiptir.

Aşağıdaki algoritma geçerlidir:

  • Arama işlemini çalıştırın ve düğümlerde hedef anahtarı bulun
  • Aşağıdaki bölümlerde açıklandığı gibi, hedef anahtarın konumuna göre uygulanan üç koşul

Hedef anahtar yaprak düğümde ise

  • Hedef yaprak düğümde, minimum anahtardan fazla.
    • Bunu silmek B Ağacı'nın özelliğini ihlal etmeyecektir.
  • Hedef yaprak düğümde, minimum anahtar düğümleri var
    • Bunu silmek, B Ağacı'nın özelliğini ihlal eder.
    • Hedef düğüm, anahtarı hemen sol düğümden veya hemen sağ düğümden (kardeş) ödünç alabilir
    • Kardeş, minimum anahtar sayısından fazla anahtar varsa evet diyecektir .
    • Anahtar ebeveyn düğümden ödünç alınacak, maksimum değer bir ebeveyne aktarılacak, ebeveyn düğümün maksimum değeri hedef düğüme aktarılacak ve hedef değer kaldırılacak
  • Hedef yaprak düğümde, ancak hiçbir kardeşin minimum sayıda anahtarı yok
    • Anahtar ara
    • Kardeşlerle ve minimum üst düğümlerle birleştirme
    • Toplam anahtarlar şimdi dakikadan fazla olacak
    • Hedef anahtar, en az bir üst düğüm ile değiştirilecektir.

Hedef anahtar dahili bir düğümde ise

  • Sırayla öncülü veya sıralı halefi seçin
  • Sıralı öncül olması durumunda, sol alt ağacından maksimum anahtar seçilecektir.
  • Sıralı halef olması durumunda, sağ alt ağacından minimum anahtar seçilecektir.
  • Hedef anahtarın sıralı öncülü min. Anahtarlardan daha fazlasına sahipse, ancak o zaman hedef anahtarı sıralı öncülün maks. İle değiştirebilir.
  • Hedef anahtarın sıralı öncülü minimum anahtara sahip değilse, sıralı halefin minimum anahtarını arayın.
  • Hedef anahtarın sıralı selefi ve ardılının her ikisi de minimum anahtara sahipse, selefi ve halefi birleştirin.

Hedef anahtar bir kök düğümdeyse

  • Sıralı öncül alt ağacın maksimum öğesi ile değiştirin
  • Silme işleminden sonra hedefin minimum anahtarı varsa, hedef düğüm, kardeşinin ebeveyni aracılığıyla kardeşinden maksimum değeri ödünç alır.
  • Ebeveynin maksimum değeri bir hedef tarafından, ancak kardeşin maksimum değerinin düğümleriyle alınacaktır.

Şimdi silme işlemini bir örnekle anlayalım.

Yukarıdaki diyagram, bir B-Ağacında farklı silme işlemi durumlarını gösterir. Bu B-Ağacı 5. sıradadır, yani herhangi bir düğümün sahip olabileceği minimum alt düğüm sayısı 3 ve herhangi bir düğümün sahip olabileceği maksimum alt düğüm sayısı 5'tir. Oysa herhangi bir düğümün minimum ve maksimum anahtar sayısı sırasıyla 2 ve 4 olabilir.

Yukarıdaki örnekte:

  • Hedef düğümün silinecek hedef anahtarı var
  • Hedef düğümde minimum anahtardan daha fazla anahtar var
  • Sadece anahtarı silin

Yukarıdaki örnekte:

  • Hedef düğüm, minimum anahtarlara eşit anahtarlara sahiptir, bu nedenle koşulları ihlal edeceği için doğrudan silemez.

Şimdi, aşağıdaki şema bu anahtarın nasıl silineceğini açıklamaktadır:

  • Hedef düğüm, herhangi bir sıralı halefine (sağ kardeş) sahip olmadığı için, bu durumda sıralı selefinden (sol kardeş) bir anahtar ödünç alır.
  • Inorder öncülünün maksimum değeri üst öğeye aktarılır ve üst öğe, maksimum değeri hedef düğüme aktarır (aşağıdaki şemaya bakın)

Aşağıdaki örnek, sıralı halefinden bir değer gerektiren bir anahtarın nasıl silineceğini gösterir.

  • Hedef düğüm, ilk kardeşten bir anahtar ödünç alır, bu durumda sıralı halef (sağ kardeş) çünkü sıralı selefi (sol kardeş) minimum anahtarlara eşit anahtarlara sahiptir.
  • Sıralı halefin minimum değeri üst öğeye aktarılır ve üst öğe, maksimum değeri hedef düğüme aktarır.

Aşağıdaki örnekte, hedef düğümün anahtarını hedef düğüme verebilecek herhangi bir kardeşi yoktur. Bu nedenle, birleştirme gereklidir.

Böyle bir anahtarı silme prosedürüne bakın:

  • Hedef düğümü, ana anahtarla birlikte yakın kardeşlerinden herhangi biriyle birleştirin
    • Ana düğümdeki anahtar, iki birleşen düğüm arasındaki kardeşlerin
  • Hedef anahtarı birleştirilmiş düğümden silin

Operasyon Sözde Kodunu Sil

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Çıktı :

En büyük eleman B-Ağacından silinir.

Özet:

  • B Ağaç, diskteki verilerin daha iyi aranması, eklenmesi ve silinmesi için kendi kendini dengeleyen bir veri yapısıdır.
  • B Ağaç, belirtilen dereceye göre düzenlenir
  • B Ağaç anahtarları ve düğümler artan sırada düzenlenmiştir.
  • B Ağacının arama işlemi en basit olanıdır, her zaman kökten başlar ve hedef anahtarın düğüm değerinden büyük veya küçük olup olmadığını kontrol etmeye başlar.
  • Önce hedef anahtar için uygun bir yerleştirme konumu bulan, onu yerleştiren, farklı durumlara karşı B Ağacı'nın geçerliliğini değerlendiren ve ardından B Ağacı düğümlerini buna göre yeniden yapılandıran B Ağacı ekleme işlemi oldukça ayrıntılıdır.
  • B Ağacı silme işlemi önce silinecek hedef anahtarı arar, siler, hedef düğümün, kardeşlerin ve üst öğenin minimum ve maksimum anahtarları gibi birkaç duruma göre geçerliliği değerlendirir.