...Yazan : Şadi Evren ŞEKER
İçerik
1. B-Ağacının Tanımı
2. Örnek B-Ağacı
3. B-Ağacında Arama
4. B-Ağacına Ekleme
5. B-Ağacından Silme
İsminin nereden geldiği (B harfinin) tartışmalı olduğu bu ağaç yapısındaki amaç arama zamanını kısaltmaktır. Buna göre ağacın her düğümünde belirli sayıda anahtar veya kayıt tutularak arama işleminin hızlandırılması öngörülmüştür.
Arama hızının artmasına karşılık silme ve ekleme işlemlerinin nispeten yavaşlaması söz konusudur.
Bir B-Ağacı (B-Tree) aşağıdaki özelliklere sahip olmalıdır:
- Her düğümün (node) en fazla m çocuğu bulunmalıdır. (Bu sayının üzerinde eleman bulunursa düğümün çoğaltılması gerekir)
- Kök (root) ve yaprak (leaf) düğümleri haricindeki her düğümün en az m/2 adet elemanı bulunmalıdır. (Bu sayının altında eleman bulunursa düğüm kaldırılır)
- Bütün yapraklar aynı seviyede olmak zorundadır. Bir yaprağın seviyesinin düşmesi durumunda (daha yukarı çıkması veya daha sığ olması durumunda) ağaçta yapısal değişiklik gerekir.
- Herhangi bir düğümde k çocuk bulunuyorsa k-1 elemanı gösteren anahtar (key) bulunmalıdır.
Aşağıda örnek bir b ağacı gösterilmiştir:
Aşağıda b ağacı üzerinde yapılan ekleme, silme ve arama işlemleri açıklanmıştır.
Bağacında (Btree) arama işlemi kökten başlar. Aranan sayı kök düğümde bulunamaması halinde arama işlemi kökte bulunan anahtarların sağında solunda veya arasında şeklinde yönlendirilir. Örneğin yukarıdaki B-ağacında 87 anahtarı aranıyor olsun. Arama işlemi için aşağıdaki adımlar gerekir:
1. kök düğüme bakılır. 87 değeri 65′ten büyüktür. Kök düğümde tek anahtar olduğu için 65′in sağındaki gösterici(pointer) takip edilir.
2. 65. sağındaki düğüme gidilir ve ilk anahtar olan 82 ile aranan anahtar olan 87 karşılaştırılır. 87 değeri 82′den büyüktür. Öyleyse ikinci anahtar olan 97 ile karşılaştırılır. 87 bu değerden küçük olduğu için bu düğümde 82 ile 97 arasında bulunan gösterici izlenir.
3. Son olarak 82 ile 97 arasındaki düğüm izlenerek ulaşılan düğümdeki anahtar ile 87 karşılaştırılır. Bu düğümdeki ilk anahtar 85′tir. 87 bu değerden büyüktür. Düğümdeki bir sonraki anahtar alınır ve 87 değeri bulunur.
B-ağaçlarının bir özelliği ağacın her düğümündeki anahtarların sıralı oluşudur. Bu yüzden bir düğümde istenen anahtar aranırken, düğümde bulunan sayılara teker teker bakılır (linear search, doğrusal arama)
B ağaçlarında veri yaprak düğümlerden gösterilir (pointer). Yani aslında veri ağacın düğümlerinde değil son düğümlerden gösterilen hafıza bölmeleri (RAM veya Dosya) olarak tutulur. Dolayısıyla B ağacında ekleme işlemi sırasında anahtarlar üzerinden arama ve değişiklikler yapılır ve nihayetinde amaç B ağacının son düğümleri olan yaprak düğümlerden veriyi göstermektir.
B ağaçlarında veri eklemek için aşağıdaki adımlar takip edilir:
1. Ağaçta eklenecek doğru yaprak düğümü aranır. (Bu işlem için bir önceki adımda anlatılan arama algoritması kullanılır)
2. Şayet bulunan yaprak düğümde azami anahtar sayısından (maximum key number) daha az eleman varsa (yani anahtar eklemek için boş yer varsa) bu düğüme ekleme işlemi yapılır.
3. Şayet yeterli yer yoksa bu durumda bulunan bu yapra düğüm iki düğüme bölünür ve aşağıdaki adımlar izlenir:
1. Yeni eleman eklendikten sonra düğümde bulunan anahtarlar sıralanır ve ortadaki elemandan bölünür. (median değeri bulunur)
2. Ortanca değerden büyük elemanlar yeni oluşturulan sağ düğüme ve küçük elemanlar da sol düğüme konulur.
3. Ortanca eleman (median) ise bir üst düğüme konulur.
Yukarıdaki ekleme işlemini aşağıdaki örnek ağaç üzerinden görelim.
Örneğin azami anahtar sayısıs 2 olan yukarıdaki örnek ağaçta ekleme işlemi yapalım ve değer olarak 60 ekleyelim:
Yukarıdaki ekleme işlemi, ekleme algoritmamızdaki 2. durumda gerçekleşmektedir. Yani anahtarımızın ekleneceği yaprakta boş yer bulunmaktadır ve buraya yeni anahtarı ekleriz.
Şayet yukarıdaki ağaca 80 değerini ekleyecek olsaydık bu durumda da algoritmamızdaki 3. ihtimal gerçekleşmiş olacaktı.
Görüldüğü üzere 80 anahtarının ekleneceği düğüm dolmuş ve azami 2 anahtar olamsı gerekirken 3 anahtar olmuştur. Ortanca değer (median) 70 olan bu ekleme işleminden sonra ortanca değer bir üst düğüme çıkmış ve iki farklı düğüme ortanca elemanın solundaki ve sağındaki değerler yukarıdaki şekilde dağıtılmıştır.
B ağacı yukarıdaki özellikleri bölümünde anlatılan özelliklerin bozulmaması için silme işlemi sırasında aşağıdaki iki yöntemden birisini izler:
1. çözümde ağaçtan ilgili anahtar bulunup silinir ve bütün ağaç yeniden inşa edilir
2. çözümde ağaçtan ilgili anahtar bulunup silinir ve bulma işlemi sırasında geçilen ağacın kısımları yeniden inşa edilir.
Ayrıca B+ ağacı (B plus tree) ve B# ağacı (B number tree) şeklinde alt çeşitleri de bulunmaktadır.
Ayrıca B ağacının özel birer uygulaması olarak aşağıdaki ağaçlara bakabilirsiniz:
2,292 views
Teşekkürler
Merhabalar hocam, B-Tree’de arama işleminin zaman karmaşıklığı nedir? (nlog2n??)
taman sanırım buldum, O(logn)
evet logn ‘dir ve logaritmanın tabanı, düğüm boyutudur. Yani bir düğümdeki eleman sayısı kadar farklı alternatif her adımda incelendiği için problemi bu kadar alt parçaya böler ve basitleştirir.
Örneğin düğüm boyutumuz 5 olsun. Arama algoritmamız ilk adımda problemi 5 parçaya böler ve bunlardan birisine iner. Dolayısıyla her adımda problemin kalan kısmının %20′si aranmak üzere seçilir.
Diğer bir deyişle ağacın derinliği (kökten yapraklara kadar olan uzaklık) oluşturulurken logn seviye yeterlidir.
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication14 { class Node { public int? veri; public Node leftNode, rightNode; public Node(int? veri, Node leftNode, Node rightNode) { this.veri = veri; this.rightNode = rightNode; this.leftNode = leftNode; } } class uygulama { static void ekle(int veri, Node root) { Node yeniNode = new Node(veri, null, null); //daha önce node yok ise yeniNode root olacak if (root.veri == null) root.veri = veri; else { Node current = root; Node parent; //geçici root (temp gibi) while (true) { parent = current; if (veri = temp.veri) { temp.veri = temp.rightNode.veri; gecici.rightNode = temp.rightNode.rightNode; } } } } static void preorder(Node node) { Console.WriteLine(node.veri); if (node.leftNode != null) preorder(node.leftNode); if (node.rightNode != null) preorder(node.rightNode); } static void inorder(Node node) { Console.WriteLine(node.leftNode); if (node.veri != null) inorder(node.veri); if (node.rightNode != null) inorder(node.rightNode); } static void postorder(Node node) { Console.WriteLine(node.leftNode); if (node.rightNode != null) postorder(node.rightNode); if (node.veri != null) postorder(node.veri); } static void Main(string[] args) { Node root = new Node(null, null, null); //kök node oluşturma ekle(15, root); ekle(10, root); preorder(root); sil(12, root); } } }sil işlemi çalışmıyor kafam çok karıştı hatalarmda yardm edersenz sevinirm.
kodunuzu inceledim ve visual studio ile denedim (CSharp yazdığınızı varsayıyorum). Ancak kodunuzda çok sayıda tanımlanmamış değişken kullanılması söz konusu. Örneğin temp ve gecici gibi.
Mümkünse kodunuzu içeren projeyi bir rar veya zip dosyası haline getirip mail ile bana ulaştırın. Vakit konusunda söz vermemekle birlikte inceleyip size hatanızı ve düzeltilmiş halini ulaştırmaya çalışırım.
başarılar
yukarıdaki bu kod, btree kodu değil bst (binary search tree) kodudur. Sorunuzun çözümünü daha önce bir ders sayfamda yayınlamıştım http://www.sadievrenseker.com/datastr2009/ adresine bakabilirsiniz.
başarılar
Sırası (order) 50 olan bir B+ ağaçta, yaprak olmayan
bir düğümde 95 işaretçi bulunmaktadır.
Buna göre bu düğümde kaç anahtar vardır?
A) 48 B) 49 C) 93 D) 94 E) 95
Her disk bloğuna 10 kaydın sığabildiği, 5 000 000
kaydın tutulduğu R(A,B,C,D,E) dosyası vardır. A özniteliği
anahtar alandır ve bu alandaki veriler 0 ile
4 999 999 arasında değişen değerler alabilmektedir.
R dosyası A değerlerine göre sıralı saklanmaktadır.
Ayrıca bu dosya için A özniteliğine göre, hem bir B+
ağacı hem de karım (hash) dizin vardır.
Buna göre,
I. σA>50 000 (R)
II. σA=50 000 (R)
III. σA>50 000 ∧ A<50 010 (R)
IV. σA≠50 000 (R)
sorgularından hangileri için B+ ağaç dizinini kullanmak
en hızlı ve en ucuz çözüm olur?
(σ : İlişkisel cebirdeki seçme işlemi)
A) Yalnız II B) Yalnız III
C) Yalnız I ve III D) Yalnız I ve IV
E) Yalnız II ve IV
şimdiden teşekkürler..
Öncelikle sorunuzu ilgili olduğu konu olan b-ağacı başlığına taşıdım.
B ağaçlarında, düğümlerde, anahtar sayının bir fazlası kadar işaretçi bulunur. Yukarıdaki yazıdaki şekillerden bunu görebilirsiniz. Örneğin düğümde 2 anahtar bulunduğunda 3 işaretçi bulunmaktadır. Bu durumda 95 işaretçi (gösterici , pointer) bulunan bir düğümde 94 adet anahtar bulunacaktır.
ikinci sorunuz ise veri tabanı konusu ile daha çok ilgili olmakla birlikte, sorudaki indeksleme yapısının iyi anlaşılması gerkir.
Soruda bir özetleme fonksiyonu (karım ,hash ) kullanıldığından bahsedilmiş. Bu durumda eşitlik kontrolünde O(1) zamanına sahip erişim zaten hash ile yapılabiliyor demektir. Benzer şekilde eşit olmama durumu da O(1) zamanında kontrol edilebilir. Dolayısıyla sorudaki II. ve IV. aramaların vakit olarak B+ ağacından daha hızlı zaten yapılabilmesi söz konusudur.
Geriye kalan I ve III şıklarınız cevap olacaktır. Buradaki B ağaçlarının erişim süresinin O(log n) ve hash indekslemenin erişim süresinin O(1) olduğunu hatırlamanız yeterlidir.
Başarılar
Merhabalar. B Tree’lerle ilgili mantığı yazınızı okuyarak çok rahat anlayabildim. Ancak elimde büyük bir text var ve burdan kelime arama işlemini B trees ile yapmaya çalışıyorum. Bu konuyla ilgili örnek teşkil etmesi amacıyla kod koyabilirmisiniz? Şimdiden teşekkür ediyorum.
tunahancankurt.blogspot.com