Horspool Algoritması

Algoritmanın gayesi, bir metin İÇERİSİNDE Verilen Bir  dizginin (string)  aranmasıdır. Literatürde arama Yapılan metin Click T (ingilizcedeki Metin (metin) kelimesinden gelmektedir) aranan kelime Click P (ingilizcedeki Desen (örüntü) kelimesinden gelmektedir) kullanılmaktadır ettik.

Klasik bir arama, yukarıdaki resimde gösterilmiştir Temsili.

Algoritmanın Diğer metin arama algoritmalarından En Büyük farkı, aranan dizgi (pattern) Yerine aranılan metin (text) Üzerinden Işlem yapmasıdır.

Yukarıdaki sekilde gösterildiği gibi, uzerinde arama isleminin Yapıldığı Metinde Bulunan HERHANGİ Bir X harfi İçin, aranılan metin Üzerindeki (pattern) en solda Olan harf bulunmaya çalışılır.

Arama işlemine başlanan α değerinin Ardından gelen harfler eşleştiği Sürece, aranan kelimenin (pattern) Sonuna Kadar eşleştikçe arama İşlemi devam eder. Şayet bu aşama uyuşmayan bir harf olursa, zaten aranan kelimenin olmadigi sonucuna varılabilir.

Ardından uyuşma OLUP olmadığına bakılmaksızın aranan kelimeyi ß değerine denk gelecek sekılde kaydırma İşlemi Yapılır. Bu kaydırmanın Olması Click kelimenin (pattern) kalan kısmında ikinci Bir değerinin bulunmaması Gerekir.

Örnek

Algoritmanın CALISMASINI Bir örnek Üzerinden göstermeye çalışalım.

Yukarıdaki sekilde görüldüğü Üzere, aranan kelime Click (P) sağdan sola doğru Bir numaralandırma yapılmakta bu numaralandırma Üzerinden aşağıda gösterilen HpBc dizisi çıkarılır ve. Bu dizi Üzerinden metin uzerinde arama Yapılır.

Sırasıyla, bir kez harfi aranır. Ardından C G harfleri aranır ettik. Dikkat edilirse, kelimede üç kere Geçen A harfi, dizide bir kere kullanılmaktadır.

Uyuşma oldukca aranan kelime kaydırılmaktadır.

Müsvette Kod (Pseudo Code)

Algoritmanın müsvette kodu aşağıdaki sekılde yazılabilir:

Horspool (p = p 1 p 2 ... p m , T = t 1 t 2 t ... n )  

Önişleme Aşaması

Için c Î Σ Do d [ c ] ← m     

Için j Î 1 ... m -1 Do d [ p j ] ← m - j     

Arama Aşaması

Poz ← 0

Iken pos ≤ nm Do    

j  ← m

Iken j > 0 Ve t pos + j = p j     Do j ← j- 1        

Eğer j : = 0 Bulundu pos +1   

pos  ← pos + d [ t pos + m ]  

Süre sonu

Yukarıdaki algoritmada Geçen değerlerin, örnek Üzerindeki gösterimlerini adım adım anlatmaya çalışalım:

Yukarıdaki ilk Adımda aranan ilk harf Olan C harfi için öncelikle kümede OLUP olmadigi KONTROLÜ Yapılır. Eklendi bunun anlamı aranan kelimenin harflerinden birisi Olmaması durumunda vakit kaybedilmemesidir.

İkinci Adımda ISE Daha Önce çıkardığımız HpBc [a] dizisine Göre onu Harfin Değerleri atanır.

Arama isleminin devamı aşağıdaki şekildedir:

GCATCGC bir GAGAGTATACAGTACG

GCAGAGA G

     Poz  ← 0 + d [t 0 + 7 ], pos ← 0 + d [ A ], pos ← 1        

Yukarıda görüldüğü Üzere, kelimenin ilk KONTROLÜ Bir Değeri aranmıştır Bulunan 1. pozisyonda Click. Ardından arama İşlemi Sonraki harf Olan G Click aşağıdaki sekılde devam eder:

GCATCG CAG AGAGTATACAGTACG

GCAGA GAG

pos  ← 1 + d [t 1 + 7 ], pos ← 1   + d [ G ], pos ← 3.  

G harfi ile Cı harfinin tutuşmamasından Dolayı aranan kelime (P) kaydırılmıştır.

GCATCG CAGAG AGTATACAGTACG

GKRY GAGAG

pos  ← 3 + d [t 3 + 7 ], pos ← 3 + d [ G ], pos ← 5      

Benzer sekilde Cı G ziyaretinde uyuşmamasından Dolayı bir kere Daha kaydırıyoruz.

GCATC GCAGAGAG TATACAGTACG

GCAGAGAG

Iken j > 0 Ve t pos + j = p j Do j ← j-1        

Eğer j = 0 pos + 1'de Bulundu   

pos  ← 5 + d [t 5 + 7 ], pos ← 5   + d [ G ], pos ← 7  

Görüldüğü Üzere aranan kelime ile uyuşma oldu. Algoritmamızın Ilgili satırlarını çalıştırıyor bulunduğunu rapor Ediyoruz ettik.

GCATCGCAGAGAGT bir TACAGTACG

GCAGAGA G

pos  ← 7 + d [t 7 + 7 ], pos ← 7   + d [ A ], pos ← 8  

İkinci kere A harfini arıyoruz.

GCATCGCAGAGAGTA T ACAGTACG

GCAGAGA G

pos  ← 8 + d [t 8 + 7 ], pos ← 8   + d [ T ], pos ← 16  

Bir harfi G harfi ile uyuşmadığı Click atlıyoruz Bulunan:

GCATCGCAGAGAGTATACAGTAC G

GCAGAGA G

pos  ← 16 + d [t 16 + 7 ], pos ← 16   + d [ G ], pos 18 ←  

pos> nm // pos> 23-7

döngüsünden cik iken.

Oğlu Olarak kelimenin Sonuna gelindiği halde aranan yazı bulunmadığı Click algoritma sonlanıyor.

Algoritmanın Karmaşıklığı

Algoritmanın zaman karmaşıklığı aranan kelimenin boyu n ziyaretinde aranılan kelimenin boyu m olmak Üzere O (mn) 'dir denilebilir. Çünkü en kötü DURUMDA onu aranılan kelime harfi Click uzerinde arama Yaptığımız onu harfi karşılaştırmamız gerekebilir. Bu da onu n harf Click m adet karşılaştırmaya eşittir.

 Brute-Force'a Benzer sekilde pattern'in oğlu harfinden başlanarak soldan saga ve yukagbıdan doğru desen ziyaretinde text'te karşılıklı denk gelen harfler karşılaştırılır. Eger pattern'deki Tüm karakterlerin eşleşmesi sağlanırsa alt dize bulunmuş demektir. Bu DURUMDA arama durdurulabilir VEYA Başka eşleşme var mı diye Aramaya devam Edilebilir.

Eşleşme olmazsa pattern'i Sağa kaydırmamız Gerekir. Bu DURUMDA HERHANGİ Bir eşleşmeyi kaçırma olasılığını riske atmadan yapabileceğimiz En Büyük olasi kaydırmayı yapmak isteriz. Horspool algoritması burada son karakterine karsilik gelen (c) 'pattern'in karakterine bakarak kaydırma yapar. Burada dört Olasılık söz konusudur. Bu durumlardan ilerideki sayfalarda bahsedilecek.

BERBER pattern'ini Bir text'te aradığımızı düşünelim.

Pattern'in oğlu elemanı Olan R ile başlayarak sağdan sola doğru hareket ediyoruz ziyaretinde metin ile pattern'de karsilik gelen Karakterleri karşılaştırıyoruz. Eger pattern'deki karakterlerin tümü eşleşirse alt dize bulunmuş demektir.

Eşleşme olmazsa pattern'i Sağa kaydırmamız Gerekir. Bu DURUMDA HERHANGİ Bir eşleşmeyi kaçırma olasılığını riske atmadan yapabileceğimiz En Büyük olasi kaydırmayı yapmak isteriz. Horspool algoritması burada son karakterine karsilik gelen (c) 'pattern'in karakterine bakarak kaydırma yapar.

Burada dört durum söz konusudur.

Durum 1 : c harfi pattern'de yoksa Örn. örnekteki S harfi. . Bu DURUMDA pattern'i BOYUTU Kadar Sağa kaydırabiliriz (Bu boyuttan Küçük Bir karşılastırma gerçekleştirirsek pattern'i karşılaştırdığımız KONUMDA pattern'de olmayan Bir c harfi ile denk getirmiş oluruz):

Durum 2 : Patternde c harfi Varsa o oğul karakter değilse orn ettik. örnekteki B harfi. Kaydırma Cı harfinin patternde görüldüğü en Sağ Noktaya denk gelecek sekilde gerçekleştirilmelidir, bu sekilde patterndeki Cı harfi ile text'teki Cı harfi eşleşmiş olur ziyaretinde Diğer karakteler de Eşit mi diye bakılır.

Durum 3:  c karakteri patterndeki oğlu karakterse göster Fakat pattern'in Diğer m - 1 karakterinde bu c karakteri yoksa Örn. örnekteki R harfi. Bu DURUMDA, makarnalık 1'e Benzer sekilde desen BOYUTU Kadar kaydırma Yapılır.

Durum 4 : c karakteri patterndeki oğlu karakterse pattern'in Diğer m A.Ş. - 1 karakterinde bu karakter tekrar ediyorsa Örn. örnekteki R harfi. Bu DURUMDA, Durum 2'ye Benzer sekilde patternde c'nin bulundugu tr Sağ Konuma Göre kaydırma Yapılır. Bu sayede text'teki c karakteri ile pattern'deki Cardio karakter hizalanmış olur. 

Bu örnek sağdan sola şeklinde gerçekleştirilen karakter karşılaştırmalarının kaba kuvvet algoritmasındaki gibi her Adımda Bir kaydırmadan öteye gidebileceğini Bize açıkça göstermektedir. Her turda patterndeki Tüm karakterlerin Kontrol Edilmesi bu algoritmanın üstünlüğünü Ortadan kaldırırdı. Neyse ki girdi Geliştirme fikri tekrar eden karşılaştırmaları gereksiz hale daha zor hale getiriyor. Kaydırma boyutlarını Önceden hesaplayıp Bir tabloya atabiliriz. Tablo text'te karşımıza çıkabilecek Tüm want Karakterleri içerecektir; doğal dil text'leri Click boşluk, noktalama işaretleri ziyaretinde Diğer Özel karakterler gibi. Tablo, folmül ile Bulunan kaydırma boyutunu gösterecektir.

Örneğin ERKEK pattern'i İçin, E, B, R3 4 OLACAKTIR ziyaretinde bir Karakterleri sırasıyla 1, 2, ve,. Diğer Tüm tablo Girdileri 6'ya Eşit OLACAKTIR.

Aşağıda kaydırma tablosunun hesaplanması Click Basit bir algoritma verilmiştir. Tablodaki Tüm Girdileri pattern'in BOYUTU Olan m Değeri Başlangıç ​​Değeri Olarak yüklenir desen ziyaretinde soldan Sağa doğru devamındaki aşamayı m - 1 kere tekrar EDECEK sekilde taranır; patterndeki j. karakter Click (0 <= j <= m - 2) ONUN tablodaki girdisini m - 1 - j ile Change Language. Bu da karakterin pattern'in oğul karakterine Olan uzaklığıdır. Algoritma pattern'i soldan saga ve yukagbıdan taradığı oğlu Click için üstüne yazma tr sağdaki karakterde gerçekleşecektir.

ALGORİTMA  ShiftTable (P  [0 ..M  -  1] )

// Horspool en ve Boyer-Moore algoritması tarafından kullanılan kaydırma tablosunu doldurur

// Girdi: Pattern  P [0 ..M  -  1] olası karakterleri ve bir alfabe

// Çıktı:  Tablo [0 ..size  -  1] alfabe karakterleri ve endeksli

// Formülle hesaplanan vardiya boyutları ile dolu

için  i  ← 0  için  boyut  -  1  do  Masa [ i ] ← m

için  j  ← 0  için  m  -  2  do  Tablo [ P [ j  ]] ← m  -  1 -  j

Dönüş  Tablosu

Algoritmayı şu sekılde özetleyebiliriz:

Adım 1  Verilen m boyutlu model ziyaretinde text'te Kullanılan alfabe Click kaydırma Tablosunu yukarda anlatıldığı gibi oluştur desen ziyaretinde

Adım 2  Pattern'i text'in Başına Hizala

Adım 3  Bunu Eşleşen Bir alt dize bulana Kadar ya da text'in Sonuna Kadar gelene tekrarla. Tüm m karakteri eşleşene Kadar ya da eşleşme bozulana Kadar pattern'deki oğlu karakterden başlayarak, ziyaretinde pattern'de text'de denk gelen Karakterleri karşılaştır. Eşleşme bozulursa Cı karakteri Click kaydırma tablosunda denk gelen sayıyı ark ziyaretinde pattern'i bu sayı Kadar Sağa kaydır.

ALGORİTMA  HorspoolMatching (P  [0 ..M  -  1] , T  [0 ..N  -  1] )

// Girdi: Pattern  P [0 ..M  -  1] ve metin  T  [0 ..N  -  1]

// Çıktı: ilk eşleşen alt dizenin sol ucunda indeksi

// Veya  - 1 eşleşme varsa

ShiftTable (P  [0 ..M  -  1] )           oluşturmak //  Tablo  kaymaların

i  ← m  -  desenin sağ ucunun 1 // pozisyonu

ise  i  ≤  n  -  1  do

k ← eşleşen karakter 0 // sayısı

ise  k  ≤  m  -  1  ve  P [ m  -  1 -  k ] =  T  [ i  -  k ]  do

k ← k  +  1

eğer  k  =  m  dönüş  i  -  m  +  1

Başka  i  ← i  +  Masa [ T  [ i ]]

dönmek  - 1

ÖRNEK  Horspool algoritmasının tam uygulamasına örnek vermek gerekirse; İngilizce harflerden Boşluktan ziyaretinde (alt çizgi ile gösterilen) OLUŞAN Bir text'te ERKEK kelimesini arayacak olalım. Öncelikle kaydırma Tablosunu Önceden belirttiğimiz formül ile aşağıdaki gibi doldururuz.

Arama İşlemi imkb aşağıdaki gibi gerçekleşir.

Horspool algoritmasının kötü anahtar etkinligi O (nm) 'dir. Fakat BBC muhabirine rastgele textler Click met karmaşıklık  Θ (n) 'dir kaba kuvvet ziyaretinde sınıfı ile Cardio etkinliğe Sahip olsa da Horspool algoritması açıkça görülmektedir ki ona göre Daha hızlıdır. Hatta bu algoritma kendinin Daha Karmaşık hali Olan Boyer-Moore algoritması Kadar etkin'ait sayılır.

C # dili ile uygulanmış hali:

///  <summary>

///  Horspool algoritması Click vardiya Tablosunu oluşturur

///  </ summary>

///  <param name = "text"> Kontrol edilecek, metin </ param>

///  <param name = "desen"> Text'te Arancak kelime </ param>

///  <döner> Shift tablosuna Uygun'un Verileri atar </ döner>

Özel  static  void  ShiftMyTable ( dize  deseni,  dize  metni)

{

   bool  baskaVar =  false ;

           

   ShiftTable =  new  Hashtable ();  // Tablo edilir başlatılamadı

   için  ( int  i = 0; i <text.Length; i ++)

   {

       eğer  (! ShiftTable.ContainsKey (metin [i]))  // Text'teki Değişken tabloya Daha Önceden eklenmemişse

       {

           eğer  (! pattern.Contains (metin [i] .ToString ()))  // Text'teki harf patternde yoksa

               ShiftTable.Add (metin [i] pattern.Length);  // O harf Click pattern'in lenght'ini tabloya yaz

           başka

           { // Text'teki harf patternde Varsa

               için ( int  J = pattern.Length - 2, J> = 0; j--)

               {

                  eğer  (pattern [j] == metin [i])

                  {

                      baskaVar =  true ;

                      ShiftTable.Add (metin [i], pattern.Length - j - 1);  // Sondan başlayarak O Harfin patterndeki konumuna Göre tabloya Değeri atar

                      kırmak ;

                  }

               }

               eğer  (baskaVar ==  false )

                  ShiftTable.Add (metin [i], pattern.Length);

               başka

                  baskaVar =  false ;}}}}

Yukarıdaki algoritma Horspool algoritması Click Kullanılan kaydırma Tablosunu olusturan algoritmanın C # 'Edilmiş halidir uygulamak ta. Bu yöntem Parametre Olarak desen metin değişkenlerini almaktadır ettik.

için  ( int  i = 0; i <text.Length; i ++)

Text'teki Tüm karakterler Click kaydırma Değeri belirleniyor.

eğer  (! ShiftTable.ContainsKey (metin [i]))

Text'teki karakter Daha Önceden tabloya eklenmişse tekrar eklenmesi gerekmemesi Click Kullanılan koşul.

eğer  (! pattern.Contains (metin [i] .ToString ()))

Eger text'teki karakter patternde yoksa o karakter Click tabloda m Değeri yani pattern'in BOYUTU atanmaktadır. Karakter patternde Varsa karakterin konumunu sağdan başlayarak hesaplıyoruz ziyaretinde bulduğumuz Değer karakterin kaydırma tablosundaki Değer oluyor.

///  <summary>

///  Horspool algoritmasını kullanarak Verilen text'te desen eşleşmesi OLUP olmadığını bulur ziyaretinde eşleşme Varsa eşleşmenin konumunu Dondurur

///  </ summary>

///  <param name = "text"> Kontrol edilecek, metin </ param>

///  <param name = "desen"> Text'te Arancak kelime </ param>

///  <döner> Pattern eşleşmesinin konumunu Dondurur </ döner>

Özel  static  int  HorspoolMatching ( dize  deseni,  dize  metni)

{

      ShiftMyTable (desen, metin);  // Shift tablosunun hesaplanması Click yöntemi çağrılıyor

      int  i = pattern.Length - 1;

      ise  (i <= text.Length - 1)  // göstergesi lenght'ten Kısa ISE döngüye giriliyor

         {

            int  k = 0;

            ise  (- 1 && desen [pattern.Length - 1 - - k] == metin [i k] k <= pattern.Length)  ; // Anahtar karşılaştırma karşılaştırılan harfler eşitse Girilir

            {

                k ++;

            }

            Eğer  (k == pattern.Length)  // Desen bulunduysa

            {

               geri  i - pattern.Length + 1;  // Eşleşmenin Hakkinda Konumu döndürülüyor

            }

            başka

            {

               i = i +  dönüştürme , .ToInt32 (. ShiftTable [metin [i]] ToString ())  // Eşleşme tablosuna Göre endeksi vardiya çıkacağı kayması olmadıysa

            }}

      geri  -1;  // desen eşleşmesi yoksa -1 döndürülüyor

}

Algoritma Parametre Olarak desen text'i alıyor, ve. DAHA SONRA kaydırma tablosu oluşturuluyor. Eşleşme sağlanırsa k değişkeninin Değeri artıyor. k değişkeni m değerine ulaşırsa bu pattern'i textte bulduğumuz anlamına geliyor. Farkı bir durum olursa desen kaydırma tablosuna Göre Sağa kaydırılıyor ziyaretinde karşılaştırmaya devam ediliyor.

2-3-4 Ağaçları (2 3 4 trees)

2-3-4 ağacı, B-ağaçlarının (B-Trees) özel bir halidir. Bu ağacın özelliği, düğüm boyutunun (node size) 3 ile sınırlı olmasıdır. Ağaç ayrıca sürekli olarak dengeli bir ağaç garantisi verir (balanced tree). 2-3-4 ağaçları, kırmızı siyah ağaçlarının (red-black trees) , eş şekillisi (isomorphic) olarak da düşünülebilir.

2-3-4 ağacının ismi, ağaçtaki düğümlerin değişik durumlarda değişik numaralar almasından kaynaklanmaktadır. Yani bir düğüm 2,3 veya 4 durumunda olabilir. Bu durumlara göre farklı uygulamalar söz konusudur.

2 düğümü: 2 adet çocuk düğümü gösteren gösterici (pointer) ve bir veriden oluşur

3 düğümü: 3 adet çocuk düğümü gösteren gösterici (pointer) ve iki veriden oluşur

4 düğümü: 4 adet çocuk düğümü gösteren gösterici (pointer) ve üç veriden oluşur

Ekleme işlemini bir örnek üzerinden anlamaya çalışalım

50, 27, 97, 52, 19, 11, 111

Bu sırayla verilen değerleri sırasıyla ağaca ekleyelim:

İlk sayı olan 50’nin eklenmesi sonucunda ağaçta tek bir düğüm ve bu düğümde tek bir veri bulunuyor. Bu tip düğüme 2 düğümü ismi verilmektedir ve iki çocuğu da boştur (null).

İkinci eklenen değer 27’dir. Ağacımızda tek düğüm bulunduğundan ve bu düğüm 2 tipinde olduğundan, düğümde yeni değeri alacak yer bulunmaktadır. Bu yere yeni gelen değer yerleştirilir. Elbette düğümlerin içerisinde sıra bulunması gerektiği için, 27 değeri, 50 değerinin soluna yerleştirilmiştir. Bu kural bundan sonraki ekleme işlemlerinde de geçerli olacaktır. Yani düğüm içerisindeki değerler kendi aralarında sıralı olacak ve herhangi bir değerin solundaki çocuklarının değeri, kendi değerinden küçük ve sağındaki değeri kendi değerinden büyük olacaktır.

Ardından gelen ekleme değeri, 97’dir. Bu değer düğüme eklenince, aşağıdaki gibi bir yapı elde edilir:

Yukarıdaki bu yeni yapı, bizim 2-3-4 ağacımızdaki 4 tipindeki yapıdır ve kabul edilebilir bir durumdur. Ancak bir sayı daha eklenince yapı bozulacaktır. Nitekim sıradaki sayımız olan 52’nin eklendiğini düşünelim:

Şimdiye kadar öğrendiklerimize göre, yukarıdaki gibi bir yapı olması beklenir. Ancak yukarıdaki yapı 2-3-4 ağacı tarafından kabul edilemez (2,3 veya 4 tipinde bir düğüm değildir). Dolayısıyla bu yapının kabul edilir bir şekle indirgenmesi gerekir.

Yukarıdaki yeni şekilde, ağaç 50 ve 27 değerlerini taşıyan iki adet 2 tipinde düğüm ve bir adet 52 ve 97 değerlerini taşıyan 3 tipinde düğüme indirgenmiştir. Bu düğümlerin tamamı 2-3-4 ağacı tarafından kabul edilir düğümlerdir.

Ekleme işlemine 19 sayısı ile devam edelim.

Yukarıdaki şekilde görüldüğü üzere, 19 sayısı, 50’den küçük olduğu için kökteki bu değerin solundaki düğüme yerleştirilmiştir.

11 sayısı eklendikten sonra, bu sayı da daha önceden olduğu gibi, 50’nin solundaki düğüme sıralı olarak eklenir.

Benzer şekilde 111 sayısının eklenmesi de kök değerin sağına yapılır:

Son olarak ağacın 3 düğümü olarak taşıyamayacağı bir örneği göstermek için, örneğin 120 sayısını ağaca eklemeye çalışalım:

Normalde 120 sayısının ekleneceği yer, yukarıdaki şekilde gösterildiği gibi ağacın sağ koludur. Ancak bu durum 2-3-4 ağacı tarafından kabul edilemez çünkü herhangi bir düğüm yapısına uygun değildir.

Çözüm olarak daha önceden 52 sayısının eklendiği örnekte olduğu gibi düğümleri indirgiyoruz.

Bu işlemden sonra kök düğümünü güncelleyerek sonuçta çıkacak olan ağacı elde ediyoruz

Ağacımız son halinde 2-3-4 ağacı kurallarına uygun düğümlerden oluşmaktadır.

2-3 Ağacı (2-3 Tree)

Bilgisayar bilimlerinde kullanılan bir veri yapısıdır (data structures). Özel bir ağaç yapısıdır ve amaç ağacı sürekli olarak dengeli (balanced) tutmaktır.

Ağaçtaki düğümlere (nodes) isim olarak 2 veya 3 ismi verilebilir. Her düğüm aldığı isme göre farklı işleme tabi tutulur. Düğümlerin isimlendirilmesi aşağıdaki şekilde yapılır:

2 düğümleri (2 nodes) : 2 adet çocuğu ve bir veri elemanı bulunan düğüm yapısıdır

3 düğümleri (3 nodes) : 3 adet çocuğu ve iki veri elemanı bulunan düğüm yapısıdır.

2-3 Ağacına Ekleme işlemli

Ağaca eklemeyi bir örnek üzerinden adım adım görelim. Ağacımıza ekleyeceğimiz sayılar aşağıdaki şekilde veriliyor olsun:

50, 27, 97, 52, 19, 11, 111

Bu sırayla verilen değerleri sırasıyla ağaca ekleyelim:

İlk sayı olan 50’nin eklenmesi sonucunda ağaçta tek bir düğüm ve bu düğümde tek bir veri bulunuyor. Bu tip düğüme 2 düğümü ismi verilmektedir ve iki çocuğu da boştur (null).

İkinci eklenen değer 27’dir. Ağacımızda tek düğüm bulunduğundan ve bu düğüm 2 tipinde olduğundan, düğümde yeni değeri alacak yer bulunmaktadır. Bu yere yeni gelen değer yerleştirilir. Elbette düğümlerin içerisinde sıra bulunması gerektiği için, 27 değeri, 50 değerinin soluna yerleştirilmiştir. Bu kural bundan sonraki ekleme işlemlerinde de geçerli olacaktır. Yani düğüm içerisindeki değerler kendi aralarında sıralı olacak ve herhangi bir değerin solundaki çocuklarının değeri, kendi değerinden küçük ve sağındaki değeri kendi değerinden büyük olacaktır.

Ardından gelen ekleme değeri, 97’dir. Bu değer düğüme eklenince, aslında aşağıdaki gibi bir yapı elde edilir:

Ancak ne yazık ki 2-3 ağaçlarında, 3 adet değeri tek bir düğümde bulundurma şansımız yoktur. Bu yüzden yukarıdaki bu hayali yapı bölünerek aşağıdaki şekle geçilir ve 3 adet 2 tipinde düğümümüz olur:

Yeni gelen değerimiz 52’dir:

Yukarıdaki yeni şekilde, gelen 52 değeri, kök düğüm olan 50’den başlanarak ağaçta ufak bir dolaşmaya sebep olur. Öncelikle 50’den küçük olduğu için bu düğümün sağına sonra da 97’den küçük olduğu için bu düğümün soluna yerleştirilir.

52 değerinin, 50 değerinin sağına yerleştirilmemesinin sebebi, bu durumda ağaçta iki veri ve iki çocuk bulunan aşağıdaki hayali ağacın oluşmasıdır:

Yukarıdaki bu hayali ağaç ne yazık ki 2-3 ağaçlarında yer almaz. Tekrar hatırlatacak olursak 2-3 ağaçlarında 2 düğümlerinin 2 çocuk ve bir verisi, 3 düğümlerinin ise 3 çocuk ve 2 verisi bulunur. Yukarıdaki kök düğüm ise 2 veri ve 2 çocuk bulundurmaktadır. Bu durum kabul edilemez.

Yeni eklenen değerimiz 19:

Yukarıdaki bu yeni ağaç yapısı, bir önceki adımda açıklandığı gibi, 50’nin yanına yeni bir veri eklenememesinden dolayı, 50’nin solundaki düğüme eklenmesi sonucunda elde edilmiştir.

Sıradaki eklenecek olan veri 11’dir. Eklenmiş halini görmeden önce, hayali olarak ağaçta olması beklenen adımları açıklayalım. Öncelikle verinin eklenmek isteneceği yer, 50 değerindeki kök düğümünün soludur.

Yukarıdaki hayali ağaç, ne yazık ki 2-3 ağaçları tarafından kabul edilemez. Dolayısıyla üç veri içeren bu düğümü tek başına ele aldığımızda (ki aynı durum, örneğimizde 97 eklenirken de yaşanmış ve 3 adet veri yan yana elde edilmesin diye 3 adet 2 tipinde düğüme dönüştürülmüştü) bölünme işlemi gerçekleştirilir:

Yukarıdaki bu alt ağacı, bir önceki ağacımız ile birleştirirsek:

Elde ettiğimiz yeni ağaç, yukarıdaki şekilde iki ağacın birleştirilmiş hali olur.

Son olarak ekleyeceğimiz değer 111 olsun. Bu değer eklendiğinde ağaçta bir zincirleme reaksiyon oluşur ve birden fazla düğümün yukarıya doğru bölünmesi gerekir. Öncelikle 111 değeri 50’den büyük olduğu için, ağaçta 50’nin sağındaki gösterici (pointer) tarafından gösterilen düğüme yönlendirilir ve sanki aşağıdaki hayali ağacın oluşmasına sebep olur:

Elbette yukarıdaki bu 3 veriyi yan yana tutan düğümü kabul edemeyeceğimiz için bu düğümü bölüyoruz:

Bu sefer kök düğümdeki 3 veriyi kabul edemeyeceğimizden dolayı, kök düğümü de bölüyoruz:

Sonuçta, yukarıdaki ağaç 2-3 ağacı olarak bütün değerlerin eklendiği ağaçtır. Buradaki son bölünmeden sonra toplam 7 adet 2 tipinde düğüm elde edilmiştir. Ayrıca yukarıdaki ekleme işlemleri boyunca her adıma bakıldığında ağacın dengeli bir ağaç olduğu (bütün yaprak düğümlerinin (leaf nodes) aynı seviyede olduğu ) görülebilir.

Aslında yukarıdaki isimlendirmeler, B-Ağacının (B-Tree) özel bir şekli olarak düşünülebilir. Yani, düğüm boyutu 2 olan bir b-ağacında, her düğümde ya iki ya da tek eleman bulunacak ve bulunan eleman sayısının bir fazlası kadar çocuk bulunacaktır.

2-3 Ağaçları, AA ağaçlarının (AA-trees), eş şekillisi (isometry) olarak düşünülebilir.

B Ağacı (B-Tree)

İ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.

1. B-Ağacının tanımı

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.

2. Örnek B-Ağacı

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.

3. B Ağacında Arama

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)

4. B Ağacına Ekleme

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.

5. B Ağacından Silme

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.

Trie (Metin Ağacı)

Metin ağaçları, onu düğümün kendisinden sonra gelen harfi İşaret Ettiği  ağaçlardır . Basitçe ağacın Üzerine Bir metin kodlanabilir ziyaretinde bu Metni veren ağacın uzerinde tek Bir Yol Izlenebilir (deterministik). Durum aşağıdaki örnek uzerinde Daha Rahat anlaşılabilir:

Yukarıdaki ağaçta dikkat edilirse kök düğüm onu ​​zaman boş Metni (string) ifade etmektedir. Bu boş metin hangi harf ile devam edilirse Ilgili kolu takip eder ziyaretinde gitmiş Olduğu düğüm o ana Kadar geçmiş Olduğu kollardaki harflerin birleştirilmiş halidir. Bir düğümden bir harf Taşıyan Sadece Bir kol çıkabilir.

Trie ağacının ismi re tray val kelimesininin ortasındaki 4 harften gelmektedir.

Metin ağaçlarının (tray), ikili arama ağaçlarına Göre tr önemli Diğer Avantajları Bir Metni aramanın, metin BOYUTU Kadar Işlem gerektirmesidir. İkili arama ağaçlarında imkb bu Süre log n Kadar varkit almaktadır. Buradaki n, ağaçtaki düğüm sayısıdır dolayısıyla ikili arama ağaçları , ağaçtaki Bilgiye Göre Hızlı VEYA yavaş Çalışırken, metin ağaçları, ağaçta ne kadar Bilgi bulunduğundan Bağımsız Olarak çalışırlar.     

Metin ağaçları hafızayı da Verimli kullanırlar göster çünkü Bir metin ağacının en derin Noktası, ağaç Üzerindeki en uzun metin kadardır. İkili ağaçlar da imkb bu derinlik Eklenen düğüm sayısına Göre en kötü ihtimalle düğüm Sayısı Kadar olabilmektedir.   

AYRICA metin ağaçları en uzun önek eşlemesi (uzun önek eşleştirme) gibi problemlerin çözümünde de Avantaj Sağlar.