Anasayfa » Dosya Organizasyonu, Veri Yapıları

B Tree (B Ağacı) Insertion Deletion Searching

4 Haziran 2011 21.177 kez okundu 11 yorum
1 Star2 Stars3 Stars4 Stars5 Stars (6 oy,5 üzerinden : 3,17 )
Loading...

B tree (B ağacı) binary (ikili) sıralama ağaçlarının genel halidir. Genel olarak arama işleminde daha hızlı sonuç vermesine karşın ekleme ve silme işlemlerinde daha yavaştır. Kayıtların sayısı capacity order la orantılıdır. Capacity order ve diğer sınırlamalar belli bir kurala bağlıdır. “Capacity order = d” dersek;

  1.  d<=keys<=2d  (anahtarlar d ile 2d arasında olmak zorundadır.Yanlız root 1 ile 2d arasında olabilir.)d+1<=pointers<=2d+1 (işaretçiler d+1 ile 2d+1 arasındadır. Yanlız rootun pointerları 2 ile 2d+1 arasında olabilir.)
  2. Bütün leafler (yapraklar) aynı seviyededir.

eleman sayısı 2d yi geçtiği anda düğümü parçalamak gerekir. Aynı şekilde root ve leaf ler hariç bütün node larda d’den az eleman bulunursa diğer node lar ile birleştirmek gerekir.

Örnek bir B Tree:

Şimdi adım adım örnek ekleme işlemi yapalım:

Algoritma aslında gayet basit, eklenecek kayıtları binary insertion ile ekliyoruz. Ne zaman eklenecek node da yer kalmadı. Ekleyeceğimiz elemanıda hesaba katarak, ortanca sayıyı bir üstteki noda yolluyoruz ve diğer iki parçayı ayrı ayrı node yapıyoruz. Örneğin 50 60 70 80 ekledik ve sonra 90 geldi. Bu 5 elemanın ortancası hangisi, “70” , bunu şimdi bir üst noda yolluyoruz. ve 50 60 , 70’in sol kolu; 80 90 70’in sağ kolu oluyor. Eğer 70 yukarı çıktığında yukarıdaki node da kapasitesini aşmış ise yine aynı işlemi uyguluyor ve bölüyoruz, ortadakini yine yukarı yolluyoruz.

Şimdi de bir video izleyelim:

Buradan kendiniz deneyebilirsiniz :)

 DELETİON (SİLME)

Şimdi sırasıyla silme işlemini gerçekleştirelim. Amaç elemanı sildikten sonra node da d/2 den az eleman bırakmamaktır. d/2 nin altına düştüğünde ya sağ veya sol kardeş node dan eleman alacağız yada yeterince kayıt yoksa birleştireceğiz.

1)Eğer yaprak node dan sildikten sonra eleman sayısı minimum kapasitenin (d/2) altına düşmediyse herhangi bir işlem yapmıyoruz.

88’i siliyoruz ve yandaki elemanları birer kaydırıyoruz. Node minimum kapasite olan d/2=2 nin altına düşmediği için başka birşey yapmıyoruz.

2) Yaprak dışından bir node dan siliyorsak ve sildiğimizde minimum kapasitenin altına düşmüyorsa yine ekstra bir şey yapmıyoruz.Örneğin 71'i siliyoruz. Silerken 71'in yerine inorder successorunu koyuyoruz(inorder successor altta anlatılmıştır,oraya bakın).

71'i silmek için yerine inorder successoru olan 73 ü koyuyoruz ve 73 ü aldığımız node da minimum kapasitenin altına düşülmediği için başka birşey yapmıyoruz.

3)Eğer yapraktan sildikten sonra minimum kapasitenin altına düştü ise kardeş nodelardan yeterince varsa eleman alıyoruz.

83'ü sildiğimizde nodeun eleman sayısı 1'e düşüyor.Önce sağ sonra sol kardeş noda bakacağız,sağ node da minimumdan fazla eleman olduğu için bir tanesini alabiliriz.89 u yukarı alıyoruz 86nın yerine koyuyoruz.86 yı alıyoruz ve silme işlemini yaptığımız node a koyuyoruz.

4)Eğer silme işlemi sonrasında sağ ve sol kardeşlerinde yeterince alınabilecek kayıt yoksa birleşime gidiyoruz.

73 ü sildiğimizde inorder successoru olan 74 ü yerine yazıyoruz. 74 ün eski nodunda eleman sayısı minimumun altın düştü, sağ ve sol kardeş nodelarında da yeterince fazladan node yok, o zaman birşeştrimeye gideceğiz.86,89,91,96 u birleştirip tek node yapıyoruz.

Şimdi üstten 89 u alınca üstteki node da minimumun altına düştü, yine aynı şekilde 98 yanlız kaldı, sağ ve sol kardeş node larından alınabilecek eleman olmadığından yine birleştirme işlemini yapacağız.

31,50,74,98 i birleştirip tek noda çeviriyoruz.

 

İnorder Successor

Bir nodun inorder successorunu bulmak için o nodun en yakın sağındaki noda gidilir,sonra bu node dan başlanarak yaprak node a gelene kadar hep en soldaki pointer izlenir.Örneğin yukarıda 71 i silerken önce sağa 86 nın olduğu node oradan hep en sol noda gidiyoruz ve 73 e ulaşıyoruz.(eğer bütün elemanları bir diziye sıralarsak inorder successor bir sağındaki elemandır.)

<<< Önceki:

Sonraki: >>>


Facebookta Paylaş

11 yorum »

  • zuhal dedi ki:

    faydalı bir paylaşım oldu. teşekkürler

  • nazan dedi ki:

    çok açıklayıcı bir anlatım olmuş ellerinize sağlık

  • Yusuf dedi ki:

    Çok açıklayıcı olmuş.Emeğinize sağlık.

  • mehmet dedi ki:

    müthiş bir anlatım emeğine sağlık

  • ali dedi ki:

    teşekkürler.

  • ramazan dedi ki:

    çok faydalı oldu..emeğinize sonsuz teşekkürler..

  • kübra dedi ki:

    çok açıklayıcı olmuş emeğinize sağlık. B# tries ile ilgili de bilgi paylaşırsanız sevinirim.

  • eth dedi ki:

    kolay gelsin hocam silmede bi tane resim gözükmüyor.

  • admin dedi ki:

    Geri bildirim için teşekkürler, en kısa zamanda düzelteceğim.

  • ahmet dedi ki:

    Açıklayıcı bir anlatım olmuş.
    Çok teşekkürler.

  • Samet dedi ki:

    Lütfen resimleri yenileme imkanınız veya yeni kısa örnekler üzerinden tekrar anlatabilmeniz mümkünmüdür internette tek türkce bulabildigim yer burası ve resimler yok 😀

Yorum Bırakın!

Yorum yaz, yada kendi sitende trackback (Geri besleme) olarak ekle. Ayrıca RSS ile bu konuya üye olabilirsin. .

Nazik olun. Temiz tutun. Konu dışına çıkmayın. Spam yaratmayın.

Bu tagları kullanabilirsiniz:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Bloğumuz gavatarı desteklemektedir. Kendi gavatarınızı edinmek için lütfen Gravatar a üye olun.