B Ağaçları

B Ağaçları

         Standart BST(Binary Search Tree) ler sadece çalışma zamanı düşünülerek RAM(ramdom access memory) üzerinde veri kullanımı yapılıyormuş gibi hesaplanarak tasarlanmış bir veri yapısıdır.RAM üzerinde verilerin silinmesi işlenmesi çok hızlı gerçekleşir ancak biz daha büyük verilerle uğraşmaya başladığımızda ram ne yazikki yetersiz kalacaktır.Bundan dolayı hem hızı hem de hafızayı dikkate alınan iki arama ağaçlarının versiyonları olan bazı veri yapıları tasarlanmıştır.Bunlardan bir tanesi Kırmızı – Siyah ağaçlarıdır,bir diğeri ise B Ağaçlarıdır.İsmi hala tartışılsada B ağaçları günümüzde birçok alanda kullanılmaktadır telefon kayıt rehberleri gibi.B ağaçlarının en önemli özelliği dengeli bir arama ağacı olmasıdır.Aynen bst de olduğu gibi sağ kol her zaman daha büyük elemana yönlenir.B ağacının karakteristik özelliklerinden bazıları ;

-Her node'da n tane eleman saklanıyorsa ;

-n+1 tane key vardır.Bu keyler alt basamaktaki nodeları gösteren pointerlardır.

-Node ların sahip olabileceği key sayıları vardır.Buna k dersek bu k >= 2 olup minumum derece olarak adlandırılır.Kök haricinde tüm node'lar minumun k-1 maximum 2k-1 tane key içerebilir.Örneğin k = 2 olduğunda biz B ağaçlarının bir özel türü olan 2-3-4 ağaçlarını oluşturmuş oluyoruz.

-Her yaprak(leaves) aynı seviyede olmalıdır.Not : yaprak en alttaki node lar ki buda ağacın seviyesine eşit oluyor.

-Bu B ağaçlarının yüksekliği konusunda ise şöyle bir eşitlik var .Yüksekliğe y dersek ;

y <= logk({n+1}/{2} )  olur.

Ekleme , Silme ,Arama İşlemleri

           Ekleme işlemi için her node da bulunan keyler takip edilir son durağa gelindiğinde yukarıdaki şartlardan biri bozuluyor mu diye kontrol edilir eğer bir sorun yoksa oraya eklenir ancak bir sorun varsa sağa veya sola döndürme işlemleri denilen işlemler yapılarak denge tekrardan kurulur.

Silme işlemi içinde ekleme işlemindeki aynı prosedür işlenir.

           Arama işlemini yaparken standart bst lerdeki gibi işlem yapılır ancak node lardaki tüm elemanlar kontrol edilerek eğer iki node arasında kalınıyorsa aradaki key ile ,tüm elemanlardan büyükse sağdaki key ile küçükse soldaki key ile yola devam edilir.Örneğin K elamanı yukarıdaki ağaçta aranırken kırmızıyla işaretlenen keyler takip edilinir.