LOGO Veri Yapıları

LOGO
Veri Yapıları
Ağaç-2
B+ AĞACI
 Dengeli arama ağacı yapısı kurmanın bir başka yolu da her
düğümde bir değil birden fazla değer saklamaktır.
 Bu tip ağaç yapıları ikili ağaçların genellemeleri olup, literatürde
𝑑 -li ağaç yapıları olarak adlandırılırlar.
B+ AĞACI TANIMI
 B+ ağacı dinamik bir arama ağacı yapısı olup, indeks kısmı ve
verilerin saklandığı kısım olmak üzere iki kısımdan
oluşmaktadır.
 İndeks kısmı 𝑑 -li ağaç yapısında olup, her düğüm 𝑑 ≤ 𝑚 ≤ 2𝑑
değer içermektedir. 𝑑 değeri B+ ağacının parametresi olup, B+
ağacının kapasitesini göstermekte ve ağacın derecesi olarak
ifade edilmektedir.
B+ AĞACI TANIMI
 Kök düğüm bu kuralın tek istisnası olup 1 ≤ 𝑚 ≤ 2𝑑 değer




içerebilmektedir.
Her düğüm kendisine ait 𝑚 + 1 tane çocuk düğümü gösteren
𝑚 + 1 tane işaretçi içerir.
Bu işaretçiler yardımıyla, ağaç yukarıdan aşağı doğru
gezilebilmektedir.
𝑃𝑖 , 𝑖. Çocuk düğümü gösteren işaretçi, 𝐾𝑖 ise aynı düğümde
saklanan 𝑖. Değeri göstermek üzere, 𝑖. Çocuk düğüm ve bu
düğümün tüm soyundaki veriler 𝐾𝑖 ≤ 𝐾 < 𝐾𝑖+1 aralığında değer
alırlar.
Veriler yaprak düğümlerde saklanmakta olup, ağaç tanımı
gereği yaprak düğümlerin çocuk düğümleri olamaz.
B+ AĞACI TANIMI
 Yukarıdaki şekilde 15 veri içeren 𝑑 = 2 dereceli örnek bir B+
ağacı gösterilmiştir.
 𝑑 = 2 olduğundan düğümler en az 2, en fazla 4 değer
içerebilmektedirler. Üst kısımda sadece kök düğüm olup,
toplam 4 değer ve 5 işaretçi içermektedir.
 Alt kısımda ise 𝐾 < 11 aralığında 4 veri, 11 ≤ 𝐾 < 18 aralığında
2 veri, 18 ≤ 𝐾 < 25 aralığında 2 veri, 25 ≤ 𝐾 < 32 aralığında 3
veri ve son olarak 𝐾 ≥ 32 aralığında ise 4 veri bulunmaktadır.
B+ AĞACI TANIMI
 Yukarıdaki şekilde 13 veri içeren 𝑑 = 1 dereceli başka bir B+ ağacı
gösterilmiştir.
 Üst kısımda kök dahil olmak üzere toplam 4 düğüm
bulunmaktadır. 𝑑 = 1 olduğundan düğümler en az 1, en fazla 2
değer içerebilmektedirler. 1. Şekildeki ağaçtan farklı olarak bu
ağaçta tam dolu olmayan bir düğüm bulunmakta, bu sebeple aynı
düğümün diğer düğümlerden farklı olarak 2 çocuğu bulunmaktadır.
B+ AĞACINDA ELEMAN ARAMAK
 B+ ağacında belirli bir elemanı aramak, ikili arama ağacında
belirli bir elemanı aramaya benzer.
 Arama işlemine ikili arama ağacında olduğu gibi yine kök
düğümünden başlanır ve her aşamada ağaçta bir seviye aşağı
inilir.
 İkili arama ağacına göre B+ ağacında eleman arama iki
noktada farklıdır. Birincisi, ikili arama ağacında veriler
düğümlerde veya yapraklarda olabildiği halde, B+ ağacında
veriler sadece yaprak düğümlerde saklanır.
B+ AĞACINDA ELEMAN ARAMAK
 Bu sebeple, ikili arama ağacında arama işlemi ağacın herhangi
bir yerinde bitebilecekken, B+ ağacında arama ancak ve ancak
yaprak düğümlere ulaşıldığında sona erer.
 İkinci olarak, ikili arama ağacında aranan eleman düğümdeki
tek bir değerle karşılaştırılıp sol veya sağ çocukla aramaya
devam edilirken, B+ ağacının düğümlerinde 𝑚 tane değer
olduğundan, bu değerlerin bir kısmı veya hepsiyle karşılaştırma
yapılıp, hangi çocukla aramaya devam edileceğinin
belirlenmesi gerekir.
B+ AĞACINDA ELEMAN ARAMAK
 2. şekildeki B+ ağacında 30’un aranması
B+ AĞACINA ELEMAN EKLEME
 B+ ağacına eleman eklerken AVL ağacında olduğu gibi ağacın




yeniden şekillendirilmesi gerekebileceği gibi sadece ağacın ilgili
yaprağına eklemek de yeterli olabilir.
B+ ağacında veriler yapraklarda saklandığı için eklenecek
elemanın önce hangi yaprağa ekleneceğinin bulunması gerekir.
Bu yaprak bulunduktan sonra, önce eleman yaprağa eklenir,
sonra yapraktaki veri sayısı sınırı aşmışsa yaprak ikiye bölünüp
bir üst düğüme yeni bir eleman eklenir.
Eğer üst düğüme eklenen eleman da üst düğümün sınırı
aşmasına sebep olursa, üst düğüm ikiye bölünür ve iki üst
düğüme yeni bir eleman eklenir.
İşlem bu şekilde herhangi bir üst düğümde sınır aşılmayıncaya
kadar devam eder.
B+ AĞACINA ELEMAN EKLEME
 1. şekildeki B+ ağacına 22’nin eklenmesi aşağıdaki şekilde olur.
B+ AĞACINA ELEMAN EKLEME
 Yukarıdaki ağaca 22’nin eklenmesi şu şekilde olur.
 22’nin ekleneceği yaprakta daha önceden 25 ve 27 olup, ekstra
eleman için yer bulunmamaktadır. Önce bu yaprağa 22
eklenmekte, ardından yaprak ikiye bölünüp bir tanesi 22 ve
diğeri 25 ile 27 içeren iki yaprak meydana gelmektedir. Bu
durum, üst düğüme 25’in eklenmesini gerektirmektedir.
B+ AĞACINA ELEMAN EKLEME
 İlk üst düğümde 20 ve 28 olup, ekstra eleman için yer
bulunmamaktadır. Önce ilk üst düğüme 25 eklenmekte,
ardından düğüm ikiye bölünüp bir tanesi 20 diğeri 28 içeren iki
düğüm meydana gelmekte, bu durum yine bir üst düğüme 25’in
eklenmesini gerektirmektedir.
 İkinci üst düğümde 18 ve 32 olup, ekstra eleman için yer
bulunmamaktadır. Önce ikinci üst düğüme 25 eklenmekte,
ardından düğüm ikiye bölünüp bir tanesi 18 diğeri 32 içeren iki
düğüm meydana gelmekte, bölünen düğüm kök düğümü
olduğundan yeni bir kök düğümü oluşturulup 25 kök düğüme
yerleştirilmektedir.
B+ AĞACINA ELEMAN EKLEME
Örnek:
 9, 11, 7, 13, 10, 5, 6, 8 sayılarının boş bir ikili arama ağacına
eklenmesiyle oluşturulan ağacı gösteriniz. Sonra bu ağaçtan
9’u siliniz. Ortaya çıkan ikili arama ağacında önce, ara ve sonra
algoritmalarıyla gezintilerinin sıralamalarını yazınız.
LOGO