Anasayfa » Arşiv

Veri Yapıları Kategorisindeki Yazılar

Algoritmalar, Veri Yapıları »

[30 Ara 2011 | 2 Yorum | 27.902 kez okundu]
1 Star2 Stars3 Stars4 Stars5 Stars (2 oy,5 üzerinden : 4,00 )
Loading...
Breadth First Search ve Depth First Search Algoritmaları

Breadth first search ve depth first search algoritmaları graph larda gezinme ve arama algoritmalarıdır.
Bu graphlarda ilişkiler iki şekilde tutulabilir. İki boyutlu array ve linked listler ile
Breadth First Search  (Sığ Öncelikli Arama)
BFS (breadth first search) algoritmasının çalışma mantığı şu şekildedir. Verilen bir node dan başlayarak ilgili node un tüm komşuları gezilir. Daha sonra gezilen komşuların komşuları gezilerek verilen graph gezilmiş olur.
Algoritma

Fonksiyona gönderilen node kuyruğa atılır.
Kuyruk boşalıncaya kadar döngü sürdürülür.
Sıradaki node kuyruktan çıkarılır.
Çıkarılan node daha önce gezilmemiş ise, gezildi işareti konur ve gezilmemiş komşuları kuyruğa konur.

Pseudo kodunu şöyle yazabiliriz.

Alttaki şekil de verilen …

Devamını oku...

Algoritmalar, Veri Yapıları »

[2 Ara 2011 | 7 Yorum | 15.127 kez okundu]
1 Star2 Stars3 Stars4 Stars5 Stars (1 oy,5 üzerinden : 5,00 )
Loading...
Kırmızı – Siyah Ağaç Yapıları ( Red – Black Trees)

Bu yazımda sizlere red black tree lerden yani kırmızı siyah diye adlandırılan ağaç yapılarından bahsedeceğim. Red Black Tree ler aslında binary search tree yapısıdır. Binary search treelerden tek farkı, extradan her nodun rengini tutan yapının olmasıdır. Bu renkler isimden de anlaşılacağı gibi kırmızı veya siyahtır.
Red black tree ler dengeli ağaçlardır. Bu yüzden en kötü zamanda bile n elemanlı bir ağaca ekleme, silme arama gibi işlemler O(logn) zamanda yapılabilir.
Her nodun bildiğimiz gibi değeri, sağ çocuğu, sol çocuğu, ebeveyni (parent) ve rengi vardır. Ayrıca red black treelerde yapraklar nill dir.
Red Black Tree lerin …

Devamını oku...

Dosya Organizasyonu, Veri Yapıları »

[4 Haz 2011 | 11 Yorum | 21.176 kez okundu]
1 Star2 Stars3 Stars4 Stars5 Stars (6 oy,5 üzerinden : 3,17 )
Loading...
B Tree (B Ağacı) Insertion Deletion Searching

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;

 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.)
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ç …

Devamını oku...