Aşağıdaki eğitimde B Ağacı veri yapısını öğreneceğiz ve onu görselleştirmeyi ele alacağız.
Öyleyse başlayalım.
B Ağacı Nedir?
B Ağacı bir özel türde çok yollu arama ağacı , yaygın olarak bilinen M yolu Kendini dengeleyen ağaç. Dengeli yapıları nedeniyle bu ağaçlar, geniş veritabanlarını çalıştırmak ve yönetmek ve aramaları basitleştirmek için yaygın olarak kullanılır. Bir B Ağacında her düğüm en fazla n alt düğüme sahip olabilir. B Ağacı, Veritabanı Yönetim Sistemindeki (DBMS) Çok Düzeyli Dizin Oluşturmanın bir örneğidir. Yaprak ve Dahili düğümlerin her ikisinin de kayıt referansları olacaktır. B Ağacı, Dengeli Saklanmış Ağaç olarak bilinir çünkü tüm yaprak düğümleri aynı seviyededir.
Aşağıdaki diyagram bir B Ağacı örneğidir:
Şekil 1. 3. sıradaki A B Ağacı
B Ağacının Kurallarını Anlamak
Bir B Ağacının önemli özellikleri şunlardır:
- Tüm yaprak düğümleri aynı seviyededir.
- B Ağacı veri yapısı minimum derece 'd' terimiyle tanımlanır. 'D' değeri disk bloğunun boyutuna bağlıdır.
- Kök hariç her düğüm en az d-1 anahtarından oluşmalıdır. Kök düğüm en az 1 anahtardan oluşabilir.
- Tüm düğümler (kök düğüm dahil) en fazla aşağıdakilerden oluşabilir: (2g-1) anahtarlar.
- Bir düğümün çocuk sayısı eşittir içinde bulunan anahtarların sayısının eklenmesi ve .
- Bir düğümün tüm anahtarları artan düzende sıralanır. K1 ve k2 anahtarları arasındaki çocuk sırasıyla k1 ve k2 arasındaki tüm anahtarlardan oluşur.
- İkili Arama Ağacından farklı olarak B Ağacı veri yapısı kökten itibaren büyür ve daralır. Oysa İkili Arama Ağacı aşağı doğru büyür ve aşağı doğru küçülür.
- Diğer Kendinden Dengeli İkili Arama Ağaçlarına benzer şekilde, B Ağacı veri yapısının arama, ekleme ve silme gibi işlemler için Zaman karmaşıklığı şu şekildedir: O(log?n) .
- B Ağacına Bir Düğümün Eklenmesi yalnızca Yaprak Düğümünde gerçekleşir.
Minimum mertebesi 5 olan bir B Ağacının aşağıdaki örneğini ele alalım.
Şekil 2. A B Sıralama Ağacı 5
Not: Pratik bir B Ağacında minimum sıranın değeri 5'ten çok daha fazladır.
Yukarıdaki şemada tüm yaprak düğümlerin aynı seviyede olduğunu, yaprak olmayan tüm düğümlerin boş alt ağacının olmadığını ve çocuk sayısından bir eksik anahtardan oluştuğunu görebiliriz.
B Ağacı kurallarının belirlenmiş formülasyonu:
Her B Ağacı, olarak bilinen pozitif bir sabit tamsayıya bağlıdır. MİNİMUM Tek bir düğümde tutulabilecek veri öğelerinin sayısını belirlemek için kullanılır.
Kural 1: Kök, yalnızca bir tane kadar az veri öğesine sahip olabilir (veya alt öğesi de yoksa hiçbir veri öğesine sahip olmayabilir); diğer her düğümde en azından MİNİMUM veri elemanları.
Kural 2: Bir düğümde depolanan maksimum veri öğesi sayısı, değerinin iki katıdır. MİNİMUM .
Kural 3: B Ağacının her bir düğümünün veri öğeleri, en küçük veri öğesinden (indekste) sıralanmış, kısmen doldurulmuş bir dizide depolanır. 0 ) en büyük veri öğesine (dizinin son kullanılan konumunda).
xd xd anlamı
Kural 4: Yaprak olmayan bir düğümün altındaki alt ağaçların toplam sayısı her zaman o düğümdeki veri öğelerinin sayısından bir fazladır.
- alt ağaç 0, alt ağaç 1,...
Kural 5: Yaprak olmayan herhangi bir düğüme ilişkin olarak:
- Dizindeki bir veri öğesi, alt ağaç numarasındaki tüm veri öğelerinden daha büyüktür Ben düğümün ve
- Dizindeki bir veri öğesi, alt ağaç numarasındaki tüm veri öğelerinden daha azdır ben+1 düğümün.
Kural 6: B Ağacındaki her yaprak aynı derinliğe sahiptir. Böylece B Ağacının dengesiz ağaç sorununu önlemesini sağlar.
B Ağacı veri yapısındaki işlemler
İşlemler sırasında B Ağacı veri yapısının hiçbir özelliğinin ihlal edilmediğinden emin olmak için B Ağacı bölünebilir veya birleştirilebilir. B Ağacı üzerinde gerçekleştirebileceğimiz bazı işlemler şunlardır:
- B Ağacında bir veri öğesini arama
- B Ağacına veri öğesinin eklenmesi
- B Ağacındaki bir veri öğesinin silinmesi
B Ağacında Arama Operasyonu
B Ağacında bir öğeyi aramak, İkili Arama Ağacındakine benzer. Ancak İkili Arama Ağacı gibi iki yönlü (Sol veya Sağ) bir karar vermek yerine, B Ağacı, m'nin düğümün alt öğelerinin sayısı olduğu her düğümde m yönlü bir karar verir.
B Ağacında bir veri öğesini arama adımları:
Aşama 1: Arama kök düğümden başlar. Arama elemanını (k) kök ile karşılaştırın.
Adım 1.1: Kök düğüm k elemanından oluşuyorsa arama tamamlanacaktır.
Adım 1.2: Eğer k elemanı kökteki ilk değerden küçükse en soldaki çocuğa ilerleyip çocuğu yinelemeli olarak arayacağız.
Adım 1.3.1: Kökün yalnızca iki çocuğu varsa, en sağdaki çocuğa geçeceğiz ve alt düğümleri yinelemeli olarak arayacağız.
Adım 1.3.2: Kökün ikiden fazla anahtarı varsa geri kalanını arayacağız.
Adım 2: Ağacın tamamını geçtikten sonra k öğesi bulunamazsa, arama öğesi B Ağacında mevcut değildir.
Yukarıdaki adımları bir örnek yardımıyla görselleştirelim. Aşağıdaki B Ağacında k=34 anahtarını aramak istediğimizi varsayalım:
Alisa Manyonok
Şekil 3.1. Belirli bir B Ağacı
- Öncelikle anahtarın olup olmadığını kontrol edeceğiz. k = 34 kök düğümdedir. Anahtar kökte olmadığı için alt düğümlerine geçeceğiz. Ayrıca kök düğümün iki çocuğu olduğunu da gözlemleyebiliriz; bu nedenle iki anahtar arasındaki gerekli değeri karşılaştıracağız.
Şekil 3.2. K anahtarı kökte mevcut değil - Artık k anahtarının kök düğümden (30) büyük olduğunu fark ettiğimize göre, kökün sağ çocuğuyla ilerleyeceğiz.
Şekil 3.3. Anahtar k > 30, sağ çocuğa git - Şimdi k anahtarını düğümde mevcut olan değerlerle (sırasıyla 40 ve 50) karşılaştıracağız. K anahtarı sol anahtardan (40) küçük olduğundan, düğümün sol çocuğuna geçeceğiz.
Şekil 3.4. anahtar k<40, move to left child< li> - 40'ın sol çocuğundaki değer gerekli değer olan 34 olduğundan anahtarın bulunduğu ve arama işleminin tamamlandığı sonucuna varabiliriz.
Şekil 3.4. Anahtar k = 34, 40'ın sol çocuğu
Yukarıdaki örnekte anahtarı bulana kadar dört farklı değerle karşılaştırdık. Böylece, bir B Ağacındaki arama işlemi için gereken zaman karmaşıklığı şu şekildedir: O(log?n) .
B Ağacına İşlem Ekleme
B Ağacına bir veri elemanı eklerken öncelikle o elemanın ağaçta mevcut olup olmadığını kontrol etmeliyiz. Veri öğesi B Ağacı içinde bulunursa ekleme işlemi gerçekleşmez. Ancak durum böyle değilse ekleme işlemine devam edeceğiz. Yaprak düğüme bir öğe eklenirken dikkate alınması gereken iki senaryo vardır:
B Ağacına veri öğesi ekleme adımları:
Aşama 1: B Ağacının sırasına göre düğümdeki maksimum anahtar sayısını hesaplayarak başlayacağız.
Adım 2: Ağaç boşsa bir kök düğüm tahsis edilir ve kök düğüm görevi gören anahtarı yerleştiririz.
Aşama 3: Şimdi ekleme için uygun düğümü arayacağız.
Adım 4: Düğüm doluysa:
Adım 4.1: Veri elemanlarını artan sırada ekleyeceğiz.
Adım 4.2: Veri elemanları maksimum anahtar sayısından büyükse, tam düğümü medyandan böleceğiz.
Adım 4.3: Medyan tuşunu yukarı doğru itip sol ve sağ tuşları sol ve sağ çocuk olarak böleceğiz.
Adım 5: Düğüm dolu değilse düğümü artan sırada ekleyeceğiz.
Yukarıdaki adımları bir örnek yardımıyla görselleştirelim. 4. dereceden bir B Ağacı oluşturmamız gerektiğini varsayalım. B Ağacına eklenmesi gereken veri öğeleri şunlardır: 5,3,21,11,1,16,8,13,4 ve 9 .
- m 3'e eşit olduğundan, bir düğüm için maksimum anahtar sayısı = m-1 = 3-1 = 2 .
- Ekleyerek başlayacağız 5 boş ağaçta.
Şekil 4.1. 5 ekleme - Şimdi ağaca 3 ekleyeceğiz. 3, 5'ten küçük olduğundan, aynı düğüme 3'ü 5'in soluna ekleyeceğiz.
Şekil 4.2. 3 ekleniyor - Şimdi ağaca 21 ekleyeceğiz ve 21, 5'ten büyük olduğu için aynı düğümde 5'in sağına eklenecek. Ancak düğümdeki maksimum anahtar sayısının 2 olduğunu bildiğimiz için bu anahtarlardan biri, onu bölmek üzere yukarıdaki düğüme taşınacaktır. Böylece ortadaki veri elemanı olan 5 yukarı hareket edecek ve sırasıyla 3 ve 21 onun sol ve sağ düğümleri haline gelecektir.
Şekil 4.3. 21 ekleme - Şimdi sıra 5'ten büyük ancak 21'den küçük olan bir sonraki veri elemanını yani 11'i eklemenin zamanı geldi. Bu nedenle anahtar olarak 21'den oluşan düğümün soluna 11 anahtar olarak eklenecektir.
Şekil 4.4. 11 ekleme - Benzer şekilde bir sonraki veri elemanı 1'i ağaca ekleyeceğiz ve gözlemleyebileceğimiz gibi 1, 3'ten küçük; bu nedenle anahtar olarak 3'ten oluşan düğümün soluna anahtar olarak eklenecektir.
Şekil 4.5. 1 ekleniyor - Şimdi ağaca 11'den büyük ancak 21'den küçük olan 16 numaralı veri elemanını ekleyeceğiz. Ancak o düğümdeki anahtar sayısı maksimum anahtar sayısını aşıyor. Bu nedenle, düğüm orta anahtarı köke taşıyarak bölünecektir. Bu nedenle, 11 ve 21'i iki ayrı düğüme bölerek 5'in sağına 16 eklenecektir.
Şekil 4.6. 16 ekleme - Veri öğesi 8, 11'in soluna anahtar olarak eklenecektir.
Şekil 4.7. 8 ekleme - Ağaca 16'dan küçük ve 11'den büyük olan 13'ü ekleyeceğiz. Bu nedenle 8 ve 11'den oluşan düğümün sağına 13 numaralı veri elemanını yerleştirmeliyiz. Ancak ağaçta maksimum sayıda anahtar bulunabileceği için yalnızca 2 olması durumunda, ortadaki veri elemanı 11'in yukarıdaki düğüme ve 8 ve 13'ün iki ayrı düğüme taşınmasıyla bir bölünme meydana gelecektir. Şimdi yukarıdaki düğüm 5, 11 ve 16'dan oluşacak ve bu yine maksimum anahtar sayısını aşacaktır. Bu nedenle, veri öğesi 11'i, 5 ve 16'nın çocukları olacak şekilde kök düğüm haline getiren başka bir bölünme olacaktır.
Şekil 4.8. 13 ekleme - 4 numaralı veri elemanı 5'ten küçük ancak 3'ten büyük olduğundan 1 ve 3'ten oluşan düğümün sağına eklenecektir, bu da yine bir düğümdeki maksimum anahtar sayısını aşacaktır. Bu nedenle 3'ü 5'in yanındaki üst düğüme taşıyarak yeniden bir dökülme meydana gelecektir.
Şekil 4.9. 4 ekleniyor - Son olarak 8'den büyük ancak 11'den küçük olan veri elemanı 9, anahtar olarak 8'den oluşan düğümün sağına eklenecektir.
Şekil 4.10. 9 ekleniyor
Yukarıdaki örnekte farklı karşılaştırmalar yaptık. İlk değer doğrudan ağaca eklendi; bundan sonra her değerin o ağaçta bulunan düğümlerle karşılaştırılması gerekiyordu. Bir B Ağacına Ekleme İşleminin zaman karmaşıklığı düğüm sayısına ve .
kat timpf yüksekliği
B Ağacındaki İşlemi Silme
B Ağacındaki bir veri öğesinin silinmesi üç ana olayı içerir:
- Silinecek anahtarın bulunduğu düğümün aranması,
- Anahtarın silinmesi ve
- Gerekirse ağacı dengelemek.
Ağaçtan bir öğe silinirken, Yetersiz Akış olarak bilinen bir durum ortaya çıkabilir. Bir düğüm minimum anahtar sayısından daha az sayıda oluştuğunda yetersiz akış meydana gelir; tutması gerekir.
Silme/kaldırma işlemini görselleştirmeden önce anlaşılması gereken bazı terimler şunlardır:
Aşağıda bir B Ağacındaki silme işleminin öne çıkan üç durumu verilmiştir:
Durum 1: Anahtarın Silinmesi/Kaldırılması Yaprak düğümünde yer alır - Bu dava ayrıca iki farklı davaya ayrılmıştır:
1. Anahtarın silinmesi/kaldırılması, bir düğümün tutması gereken minimum anahtar sayısı özelliğini ihlal etmez.
Bu durumu aşağıdaki B Ağacından 32 anahtarını sileceğimiz bir örnek kullanarak görselleştirelim.
Şekil 4.1: B Ağacından bir yaprak düğüm anahtarının (32) silinmesi
Gördüğümüz gibi bu ağaçtan 32'nin silinmesi yukarıdaki özelliği ihlal etmiyor.
2. Anahtarın silinmesi/kaldırılması, bir düğümün tutması gereken minimum anahtar sayısı özelliğini ihlal eder. Bu durumda, en yakın kardeş düğümünden Soldan Sağa sırayla bir anahtar ödünç almamız gerekir.
Öncelikle en yakın Sol kardeşi ziyaret edeceğiz. Sol kardeş düğümün minimum anahtar sayısından daha fazlasına sahip olması durumunda, bu düğümden bir anahtar ödünç alacaktır.
java referans türleri
Aksi takdirde, yakın Sağ kardeş düğümden ödünç almayı kontrol edeceğiz.
Şimdi yukarıdaki B Ağacından 31’i sileceğimiz bir örnek yardımıyla bu durumu görselleştirelim. Bu durumda sol kardeş düğümden bir anahtar ödünç alacağız.
Şekil 4.2: B Ağacından bir yaprak düğüm anahtarının (31) silinmesi
Her iki yakın kardeş düğüm de zaten minimum sayıda anahtardan oluşuyorsa, o zaman düğümü ya sol kardeş düğümle ya da sağdakiyle birleştireceğiz. Bu birleştirme işlemi ana düğüm aracılığıyla yapılır.
Yukarıdaki B Ağacından 30 anahtarını silerek tekrar görselleştirelim.
Şekil 4.3: B Ağacından bir yaprak düğüm anahtarının (30) silinmesi
Durum 2: Anahtarın Silinmesi/Kaldırılması Yaprak olmayan düğümde yer alır - Bu dava ayrıca farklı vakalara bölünmüştür:
1. Kaldırılan Yaprak olmayan/Dahili düğüm, Sol alt düğümün minimum anahtar sayısından daha fazlasına sahip olması durumunda sıralı bir öncül ile değiştirilir.
Bu durumu B Ağacından 33 anahtarını sileceğimiz bir örnek kullanarak görselleştirelim.
Şekil 4.4: B Ağacından bir yaprak düğüm anahtarının (33) silinmesi
2. Sağ alt düğümün minimum anahtar sayısından daha fazlasına sahip olması durumunda, kaldırılan Yaprak olmayan/Dahili düğüm, sıralı bir halef ile değiştirilir.
Eğer her iki çocuktan birinin minimum sayıda anahtarı varsa, o zaman Sol ve Sağ alt düğümleri birleştireceğiz.
robot bileşenleri
Bu durumu B Ağacından 30 anahtarını silerek görselleştirelim.
Şekil 4.5: B Ağacından bir yaprak düğüm anahtarının (30) silinmesi
Birleştirmeden sonra, eğer ana düğüm minimum sayıdan daha az anahtara sahipse, aşağıdaki gibi kardeşler aranabilir: Dava 1 .
Durum 3: Aşağıdaki durumda ağacın boyu kısalır. Hedef anahtar bir Dahili düğümde bulunuyorsa ve anahtarın kaldırılması düğümde daha az sayıda anahtara yol açıyorsa (bu, gerekli olan minimum sayıdan daha az), o zaman sıralı öncül ve sıralı ardılı arayın. Her iki çocuğun da minimum sayıda anahtarı varsa ödünç alma işlemi yapılamaz. Bu şuna yol açar: Durum 2(3) yani alt düğümlerin birleştirilmesi.
Anahtarı ödünç almak için yine kardeşimizi arayacağız. Ancak kardeş de minimum sayıda anahtardan oluşuyorsa, o zaman düğümü ana düğümle birlikte kardeşle birleştireceğiz ve alt düğümleri gereksinimlere göre (artan düzende) ayarlayacağız.
Verilen B Ağacından 10 numaralı veri elemanını sileceğimiz bir örnek yardımıyla bu durumu görselleştirelim.
Şekil 4.6: B Ağacından bir yaprak düğüm anahtarının (10) silinmesi
Yukarıdaki örneklerdeki zaman karmaşıklığı, anahtarın silinmesi gereken konuma göre değişir. Dolayısıyla, bir B Ağacındaki Silme İşleminin zaman karmaşıklığı şu şekildedir: O(log?n) .
Sonuç
Bu dersimizde B Ağacını öğrendik ve farklı işlemlerini farklı örneklerle görselleştirdik. Ayrıca B Ağacının bazı temel özelliklerini ve kurallarını da anladık.