LOGO Veri Yapıları
Transkript
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