Kendini dengeleyen ikili arama ağacı veri yapısıdır. Orijinal yapı 1972 yılında Rudolf Bayer tarafından “Simetrik ikili B-Ağaçları” olarak oluşturuldu. Fakat 1978 yılında Leonidas J. Guibas ve Robert Sedgewick tarafından yayımlanan makalede bugünkü adını almıştır. Red-black ağaçlar yapı bakımından biraz karmaşıktır. Arama, ekleme ve silme işlemlerini           O(log n) zamanda gerçekleştirirler (ağaçtaki eleman sayısı n). Bazı kuralları vardır: Her düğüm siyah veya kırmızıdır. Kök her zaman siyahtır. Tüm yapraklar siyahtır. Kırmızı düğümün çocukları siyah olmak zorundadır. Seçilen herhangi bir düğümden, altındaki tüm yapraklara olan yolda aynı sayıda siyah düğüm olmak sorundadır.   Diğer tüm kurallar, ikili arama ağacındaki gibidir.     Ekleme ve çıkartma işlemlerinde siyah düğüm sayısına dikkat edilmelidir. Tags: , , , | Categories: Algoritma

Ocak 1007

B Ağacı (B Tree)

Bilgisayar bilimlerinde bir B ağacı, veri sıralaması tutar ve logaritmik azalan zamanda ağaç yapısında ekleme, çıkartma ve arama işlemlerine izin verir. B ağaçları ikili sıralama ağaçlarının daha genel halidir. Özelikleri: Her B ağacının m değerinde bir faktör değeri vardır (m>1 koşulu sağlanmalıdır). Her düğümde en fazla m adet çocuk bulunmalıdır. m sayısından daha fazla çocuk olması durumunda düğüm parçalanır. Kök ve yaprak düğümleri haricinde en az m/2 adet eleman bulunmalıdır. Aksi takdirde diğer düğümlerle birleştirme işlemi uygulanır. Ağacın derinliği her yaprak için aynı olmalıdır. Her bir düğümde k çocuk bulunuyorsa k-1 sayıda elemanı gösteren anahtar (key) bulunmalıdır.   Örnek B ağacı aşağıdaki şekildeki gibidir:   B ağacı üzerindeki işlemler: B-Tree-Search(x, k) i <- 1while i <= n[x] and k > keyi[x]     do i <- i + 1if i <= n[x] and k = keyi[x]     then return (x, i)if leaf[x]     then return NIL     else Disk-Read(ci[x])          return B-Tree-Search(ci[x], k) B ağacındaki arama ikili araçtaki arama ile benzerdir. Arama sırasında sağ - sol taraf seçenekleri yerine n tane farklı taraf vardır. Düğüm içerisinde lineer bir arama yapılarak doğru çocuk düğüme yönlenebilir. İstenilen değere küçük eşit değer bulunduktan sonra, bulunan key değerinin sol tarafındaki çocuk düğüme gidilir. Eğer Düğümdeki tüm keylerin değerleri aranan değerden küçükse en sağdaki çocuk düğüme dallanılır. Aranan değer bulununca arama işlemi sonlanır. Arama sırasındaki geçen zaman ağacın derinliğine bağlı O(logt n) olarak hesaplanır. B-Tree-Create(T) x <- Allocate-Node()leaf[x] <- TRUEn[x] <- 0Disk-Write(x)root[T] <- x Boş B ağacı yaratma işlemidir. Çocuk düğümü olmayan kök düğümü yaratır. B-Tree-Create işlemi O(1) zamanda koşulur. B-Tree-Insert(T, k) r <- root[T]if n[r] = 2t – 1     then s <- Allocate-Node()          root[T] <- s          leaf[s] <- FALSE          n[s] <- 0          c1 <- r          B-Tree-Split-Child(s, 1, r)          B-Tree-Insert-Nonfull(s, k)     else B-Tree-Insert-Nonfull(r, k) B-Tree-Split-Child(x, i, y) z <- Allocate-Node()leaf[z] <- leaf[y]n[z] <- t – 1for j <- 1 to t – 1     do keyj[z] <- keyj+t[y]if not leaf[y]     then for j <- 1 to t          do cj[z] <- cj+t[y]n[y] <- t – 1for j <- n[x] + 1 downto i + 1     do cj+1[x] <- cj[x]ci+1 <- zfor j <- n[x] downto i     do keyj+1[x] <- keyj[x]keyi[x] <- keyt[y]n[x] <- n[x] + 1Disk-Write(y)Disk-Write(z)Disk-Write(x) Eğer düğümdeki eleman sayısı faktör değerine ulaşmışsa ayırma işlemi uygulanması gerekir. Ayırma işlemi, tümüyle dolu bir düğümü 2t-1 key), 2 adet düğüme (t-1 key) dönüştürür. Unutulmamalıdır ki, ayırma işlemi ile bir tane key ebeveyn düğüme kayar. Ayırma işlemi O(t) kadar zamanda gerçekleşir. B-Tree-Delete(x) B ağaçları için silme işlemi mümkündür. Fakat diğer işlemlere nazaran daha çok dikkat gerektiren bir işlemdir. Çünkü çıkartma işlemi sonrasında eğer key sayısı koşulumuzu sağlamıyorsa düğümlerde birleştirme işlemi yapılmalıdır. Fakat bu durumda da ağacın dengeli olmasına (derinliğinin her yaprak için aynı olmasına) dikkat edilmelidir.   Bu kadar yazı okudunuz. Ancak B Tree nin B’sinin neyin kısaltması olduğundan hiç biryerde bahsetmedim. Bahsedememem de zaten. Bu algoritmayı yazandan başka kimse bilmiyor bunu. Sadece varsayımlardan behsediliyor. Yazımın sonunda bu konu hakkında ufak bir alıntı yapmak istiyorum: The origin of "B-tree" has never been explained by the authors. ... "balanced," "broad," or "bushy" might apply. Others suggest that the "B" stands for Boeing. [Bayer and McCreight were at Boeing Scientific Research Labs in 1972.] Because of his contributions, however, it seems appropriate to think of B-trees as "Bayer"-trees.     -   Douglas Comer, The Ubiquitous B-Tree, Computing Surveys, 11(2):123, June 1979. Tags: | Categories: Algoritma