C ++ 'da B Ağacı ve B + Ağacı Veri Yapısı

b tree b tree data structure c

Bu C ++ Öğreticisi B Ağacı ve B + Ağacı Veri Yapılarını Açıklar. Tüm Veriler Ana Bellekte Saklanamadığında Verileri Disklerde Saklamak İçin Kullanılırlar:

B-ağacı, kendi kendini dengeleyen bir ağaçtır ve ayrıca disk erişimi için kullanılan özel bir m-yollu ağaçtır.

Saklanacak veri miktarı çok yüksek olduğunda tüm veriyi ana bellekte saklayamayız. Bu nedenle verileri diskte saklıyoruz. Diskten veri erişimi, ana bellek erişimine kıyasla daha fazla zaman alır.

Disklerde depolanan verilerin anahtar sayısı çok fazla olduğunda, verilere genellikle bloklar halinde erişilir. Bu bloklara erişme süresi, ağacın yüksekliği ile doğru orantılıdır.

=> Absolute C ++ Eğitim Serisi İçin Tıklayınız.

Ne öğreneceksin:

• C ++ 'da B-Ağacı
  • B-Tree'nin Temel İşlemleri
    • # 1) Arama
    • # 2) Ekleme
    • # 3) Silme
  • B Ağaçlarının Uygulamaları
• C ++ 'da B + Ağacı
  • B + Ağaçlarının Avantajları
• B-Ağacı ve B + Ağacı Arasındaki Fark
• Sonuç
  • Önerilen Kaynaklar

C ++ 'da B-Ağacı

B-Ağacı düz bir ağaçtır, yani B ağacının yüksekliği minimumda tutulur. Bunun yerine, B ağacının her bir düğümüne çok sayıda anahtar yerleştirilir. B-ağacının yüksekliğini minimumda tutarak, AVL ağaçları gibi diğer dengeli ağaçlara kıyasla erişim daha hızlıdır.

Tipik bir B ağacı aşağıda gösterilmiştir:

ikili ağaç uygulaması c ++

Genel olarak, B ağacındaki düğüm boyutu blok boyutuyla aynı tutulur.

Aşağıda B-Tree'nin bazı özellikleri listelenmiştir.

• B-ağacının tüm yaprakları aynı seviyededir.
• M düzenindeki bir B ağacında en fazla m-1 anahtarı ve m çocuğu olabilir.
• B-ağacındaki her düğümün en fazla m çocuğu vardır.
• Kök düğüm en az iki düğüme sahip olmalıdır.
• Kök düğüm ve yaprak düğüm hariç her düğüm, m / 2 çocuk içerir.

Daha sonra, B-ağacının bazı temel işlemlerini tartışacağız.

B-Tree'nin Temel İşlemleri

Aşağıda B-Tree'nin temel işlemlerinden bazıları verilmiştir.

# 1) Arama

B ağacında arama, BST'dekine benzer. Yukarıdaki ağaçta 3. maddeyi aramak istersek, o zaman aşağıdaki gibi ilerleyeceğiz:

• 3'ü kök öğelerle karşılaştırın. Burada, 3<6 and 3 <15. So we proceed to the left subtree.
• Soldaki alt ağaçta 3 ile 4'ü karşılaştırın. 3 olarak<4, we proceed to the left subtree of node 4.
• Sonraki düğümün iki anahtarı vardır, 2 ve 3. 3> 2 iken 3 = 3. Yani anahtarı bu düğümde bulduk. Bulunan konuma geri dönün.

B ağacında arama, ağacın yüksekliğine bağlıdır. Belirli bir öğeyi aramak genellikle O (log n) kadar zaman alır.

# 2) Ekleme

B ağacına yeni bir öğenin eklenmesi, yaprak düğümleri düzeyinde yapılır.

Aşağıda, B ağacına yeni bir öğe eklemek için adımlar (algoritma) dizisi verilmiştir.

• Öğeyi eklemek için yaprak düğümlerde bir konum bulmak için B ağacını çaprazlayın.
• Yaprak düğüm anahtarlar içeriyorsa
• Yaprak düğüm anahtarları = m-1 ise, o zaman:
  • Artan sayıda öğeye yeni bir öğe ekleyin.
  • Düğümlerin medyanını alın ve düğümü iki düğüme bölün.
  • Medyanı üst düğümüne itin.
  • Üst düğüm anahtarı = m-1 ise, üst düğüm için de yukarıdaki adımları tekrarlayın. Bu, uygun yaprak düğümünü bulana kadar yapılır.
• Son olarak, öğeyi ekleyin.

B ağacına eklemeyi aşağıdaki gibi gösterdik.

70 numaralı öğeyi aşağıda gösterilen ağaca ekleyelim.

c ++ ne için kullanılır

Verilen ağaç minimum derece ‘m’ = 3'tür. Dolayısıyla, her bir düğüm içinde 2 * m -1 = 5 anahtar barındırabilir.

Şimdi öğe 70'i ekliyoruz. Bir düğümde 5 anahtara sahip olabileceğimiz için, öğe 70'i kök öğe 30 ile karşılaştırıyoruz. 70> 30'dan beri, öğe 70'i sağ alt ağaca ekleyeceğiz.

Sağ alt ağaçta, 40, 50, 60 anahtarları olan bir düğümümüz var. Her düğümün içinde 5 anahtar olabileceğinden, öğe 70'i bu düğümün kendisine ekleyeceğiz.

Eklendikten sonra, B-Ağacı aşağıdaki gibi görünür.

# 3) Silme

Tıpkı yerleştirme gibi, anahtarın silinmesi de yaprak düğümler düzeyinde gerçekleştirilir. Ancak yerleştirmenin aksine, silme işlemi daha karmaşıktır. Silinecek anahtar, bir yaprak düğüm veya bir dahili düğüm olabilir.

Bir anahtarı silmek için aşağıdaki adım sırasını (algoritma) takip ederiz.

1. Yaprak düğümünü bulun.

iki. Bir düğümdeki anahtar sayısının> m / 2 olması durumunda, verilen anahtarı düğümden silin.

3. Yaprak düğümün m / 2 anahtarlarına sahip olmaması durumunda, B ağacını korumak için sağ veya sol alt ağaçlardan anahtarlar alarak anahtarları tamamlamamız gerekir.

Şu adımları takip ediyoruz:

• Soldaki alt ağaç m / 2 öğeleri içeriyorsa, en büyük öğesini ana düğüme iteriz ve ardından araya giren öğeyi anahtarın silindiği yere taşırız.
• Sağ alt ağaç m / 2 öğeleri içeriyorsa, en küçük öğesini ana düğüme iteriz ve ardından araya giren öğeyi anahtarın silindiği yere taşırız.

Dört. Hiçbir düğümde m / 2 düğüm yoksa, yukarıdaki adımlar gerçekleştirilemez, bu nedenle iki yaprak düğümü ve ana düğümün araya giren elemanını birleştirerek yeni bir yaprak düğüm oluştururuz.

5. Bir ebeveyn m / 2 düğümsüz ise, söz konusu ebeveyn düğüm için yukarıdaki adımları tekrar ederiz. Dengeli bir B ağacı elde edene kadar bu adımlar tekrarlanır.

Aşağıda, B ağacından bir düğümü silmek için bir örnek verilmiştir.

Aşağıdaki B ağacını bir kez daha düşünün.

60 anahtarını B ağacından silmek istediğimizi varsayalım. B ağacını kontrol edersek, silinecek anahtarın yaprak düğümünde mevcut olduğunu görebiliriz. 60 anahtarını bu yaprak düğümünden siliyoruz.

Şimdi ağaç aşağıda gösterildiği gibi görünecek:

60 anahtarını sildikten sonra, B ağaç yaprağı düğümünün gerekli özellikleri sağladığını ve B ağacında daha fazla değişiklik yapmamıza gerek olmadığını fark edebiliriz.

Ancak, 20 anahtarını silmemiz gerekse, sol yaprak düğümde yalnızca 10 anahtarı kalmış olacaktı. Bu durumda, kök 30'u yaprak düğümüne kaydırmalı ve anahtar 40'ı köke taşımalıyız.

Bu nedenle B ağacından bir anahtar silinirken dikkatli olunmalı ve B ağacının özellikleri ihlal edilmemelidir.

B Ağacında Geçiş

B ağacındaki geçiş de BST'deki sıralı geçişe benzer. Özyinelemeli olarak soldan başlıyoruz, sonra köke geliyoruz ve soldaki alt ağaca doğru ilerliyoruz.

şelale modeli sistem geliştirme yaşam döngüsü

B Ağaçlarının Uygulamaları

• Disklerdeki büyük veritabanlarında depolanan verilere erişim çok zaman aldığından, özellikle büyük veritabanlarında verileri indekslemek için B ağaçları kullanılır.
• Daha büyük sıralanmamış veri kümelerindeki verilerin aranması çok zaman alır, ancak bu, B ağacı kullanılarak indeksleme ile önemli ölçüde iyileştirilebilir.

C ++ 'da B + Ağacı

B + ağacı, B ağacının bir uzantısıdır. B + ağacı ve B ağacındaki fark, B ağacında anahtarların ve kayıtların hem dahili hem de yaprak düğümler olarak saklanabilmesidir, oysa B + ağaçlarında kayıtlar yaprak düğümler olarak depolanır ve anahtarlar yalnızca dahili düğümlerde depolanır.

Kayıtlar, bağlantılı liste tarzında birbirine bağlıdır. Bu düzenleme, B + ağaçlarının aranmasını daha hızlı ve verimli hale getirir. B + ağacının iç düğümlerine dizin düğümleri denir.

B + ağaçlarının iki sırası vardır, yani biri iç düğümler, diğeri yaprak veya dış düğümler içindir.

B + Ağacı Örneği aşağıda gösterilmiştir.

B + ağacı, B-ağacının bir uzantısı olduğundan, B-ağacı başlığı altında tartıştığımız temel işlemler hala geçerlidir.

Eklerken ve silerken, B + Ağaçlarının temel özelliklerini bozulmadan korumalıyız. Bununla birlikte, B + ağacındaki silme işlemi, veriler yalnızca yaprak düğümlerde depolandığından ve her zaman yaprak düğümlerden silineceğinden nispeten daha kolaydır.

B + Ağaçlarının Avantajları

• Kayıtları eşit sayıda disk erişimiyle getirebiliriz.
• B ağacına kıyasla, B + ağacının yüksekliği daha azdır ve dengeli kalır.
• İndeksleme için anahtarlar kullanıyoruz.
• Yaprak düğümleri bağlantılı bir listede düzenlendiği için B + ağacındaki verilere sırayla veya doğrudan erişilebilir.
• Veriler yalnızca yaprak düğümlerde ve bağlantılı liste olarak depolandığından arama daha hızlıdır.

B-Ağacı ve B + Ağacı Arasındaki Fark

Sonuç

Bu eğitimde, B-ağacı ve B + ağacını ayrıntılı olarak tartıştık. Bu iki veri yapısı, çok yüksek miktarda veri olduğunda ve verilerin tamamı ana bellekte saklanamadığında kullanılır. Bu nedenle verileri disklerde saklamak için B-ağacı ve B + ağacını kullanırız.

B-ağacı araması, veriler hem iç düğümlerde hem de yaprak düğümlerde saklandığından biraz daha yavaştır. B + ağacı, B ağacının bir uzantısıdır ve buradaki veriler yalnızca yaprak düğümlerde saklanır. Bu faktör nedeniyle, bir B + ağacında arama daha hızlı ve etkilidir.

=> Tam C ++ Öğreticiler listesi için Burayı Ziyaret Edin.

Önerilen Kaynaklar

• C ++ 'da AVL Ağacı ve Yığın Veri Yapısı
• Resimli C ++ 'da Bağlantılı Liste Veri Yapısı
• Çizim ile C ++ 'da Kuyruk Veri Yapısı
• Çizimle C ++ 'da Yığın Veri Yapısı
• Çizim ile C ++ 'da Dairesel Bağlantılı Liste Veri Yapısı
• C ++ 'da Veri Yapılarına Giriş
• Çizim ile C ++ 'da Öncelik Sırası Veri Yapısı
• Çizimle C ++ 'da Çift Bağlantılı Liste Veri Yapısı