Orkhan ALIYEV arkadaşıma katkılarından dolayı teşekkür ederim.
- Veri Yapılarına Genel Bakış
- Veri Yapısının Özellikleri
- Veri Yapısı İhtiyacı
- Yürütme Süresi Kutuları
- Temel Terminoloji
- Veri Yapıları Temelleri
- Diziler
- Listeler
- Trees(Ağaçlar)
- Kaynakça
Veri Yapısı, verileri verimli kullanmak için verileri organize etmenin sistematik bir yoludur. Aşağıdaki terimler bir veri yapısının temel terimleridir.
- Arayüz - Her veri yapısının bir arayüzü vardır. Arayüz bir veri yapısının desteklediği işlem kümesini temsil eder. Bir arabirim yalnızca desteklenen işlemlerin listesini, kabul edebilecekleri parametre türlerini ve bu işlemlerin türünü döndürür.
- Uygulama - Uygulama, bir veri yapısının iç temsilini sağlar. Uygulama ayrıca, veri yapısının işlemlerinde kullanılan algoritmaların tanımını sağlar.
- Doğruluk - Veri Yapısı uygulaması, arayüzünü doğru şekilde uygulamalıdır.
- Zaman Karmaşıklığı - Veri yapısı işlemlerinin çalışma süresi veya yürütme süresi mümkün olduğu kadar küçük olmalıdır.
- Karmaşıklığı - Bir veri yapısı işleminde bellek kullanımı mümkün olduğunca az olmalıdır.
Uygulamalar karmaşıklaştıkça ve veri bakımından zenginleştikçe, uygulamaların bugünlerde karşılaştığı üç genel sorun var.
- Veri Arama - Bir mağazanın 1 milyon (10^6) kaleminden oluşan bir envanteri düşünün. Eğer uygulamanın amacı bir öğeyi aramaksa. Aramayı yavaşlatan sebep her seferinde 1 milyon (10^6) maddede arama yapması gerekmesidir. Veriler büyüdükçe arama yavaşlar.
- İşlemci hızı - İşlemci hızı çok yüksek olabilir fakat, veriler milyarca olduğu takdirde bu işlemci hızı bir işe yaramaz.
- Birden çok istek - Binlerce kullanıcı bir web sunucusunda aynı anda veri arayabildiğinden, veri ararken çok hızlı sunucu bile başarısız olur. Veri yapıları yukarıdaki problemleri çözmek için bize yardımcı olur. Veriler, veri yapısında tüm öğelerin aranması gerekmeyebilecek ve gerekli veriler neredeyse anında aranabilecek şekilde düzenlenebilir.
Çeşitli veri yapısının yürütme süresini göreceli bir şekilde karşılaştırmak için kullanılan üç durum vardır.
- En Kötü Durum - Bu, belirli bir veri yapısı işleminin alabileceği maksimum süreyi aldığı senaryodur. Bir işlemin en kötü durum süresi ƒ (n) ise, bu işlem ƒ (n) 'in n işlevini temsil ettiği ƒ (n) zamandan daha uzun sürmez.
- Ortalama Durum - Bu, bir veri yapısının işleminin ortalama yürütme zamanını gösteren senaryodur. Bir işlem yürütme sırasında ƒ (n) zaman alırsa, m işlemleri mƒ (n) zaman alır.
- En İyi Durum - Bu, bir veri yapısının çalışmasının mümkün olan en az yürütme süresini gösteren senaryodur. Bir işlem yürütmede ƒ (n) zaman alırsa, gerçek işlem ƒ (n) kadar maksimum olan rasgele sayı olarak zaman alabilir.
- Veri - Veri değer veya değer kümesidir.
- Veri Öğesi - Veri öğesi, tek bir değer birimini ifade eder.
- Grup Öğeleri - Alt öğelere ayrılan veri öğesine Grup Öğeleri denir.
- Temel Öğeler - Bölünemeyen veri öğesi, Temel Öğeler olarak adlandırılır.
- Nitelik ve Varlık - Varlık, değer atanabilecek belirli nitelikleri veya özellikleri içeren varlıktır.
- Varlık Kümesi - Benzer özellikteki varlıklar, bir varlık kümesini oluşturur.
- Alan - Alan, bir işletmenin bir niteliğini temsil eden tek bir temel bilgi birimidir.
- Kayıt - Kayıt, belirli bir varlığın alan değerlerinin toplamıdır.
- Dosya - Dosya, belirli bir varlık kümesindeki varlıkların kayıtlarının toplamıdır.
Veri Yapısı, verileri verimli kullanılabilecek şekilde organize etmenin bir yoludur. Bu döküman veri yapısı ile ilgili temel terimleri açıklamaktadır.
Veri Tanımı, aşağıdaki özelliklere sahip belirli bir veriyi tanımlar.
- Atomik - Tanım tek bir kavram tanımlamalıdır
- İzlenebilir - Tanım, bazı veri öğelerine eşlenebilmelidir.
- Düzgün - Tanım net olmalıdır.
- Açık ve Özlü - Tanım anlaşılabilir olmalıdır.
Veri Nesnesi, verileri olan bir nesneyi temsil eder.
Veri türü, karşılık gelen veri türüyle kullanılabilecek değerleri, karşılık gelen veri türünde gerçekleştirilebilecek işlem türlerini belirleyen tam sayı, dizge vb. gibi çeşitli veri türlerini sınıflandırma yoludur. İki tip veri türü -
- Dahili Veri Tipi
- Türetilmiş Veri Türü
Bir dilin yerleşik desteğine sahip olduğu veri türleri, Dahili Veri türleri olarak bilinir. Örneğin, dillerin çoğu yerleşik veri türlerini takip etmeyi sağlar.
- Tamsayılar
- Boole (doğru, yanlış)
- Yüzer (Ondalık sayılar)
- Karakter ve Dizeler
Birinden veya başka bir şekilde uygulanabileceğinden uygulamadan bağımsız olan veri tipleri, türetilmiş veri türleri olarak bilinir. Bu veri tipleri normalde birincil veya dahili veri tiplerinin ve bunlarla ilişkili işlemlerin birleşimiyle oluşturulur. Örneğin -
- Liste
- Dizi
- Yığın
- Kuyruk
- Traversing(Çaprazlama ilerleme)
- Searching(Arama)
- Insertion(Ekleme)
- Deletion(Silme)
- Sorting(Sıralama)
- Merging(Birleştirme)
Dizi, sabit sayıda öğeyi tutabilen bir kaptır ve bu öğeler aynı türden olmalıdır. Veri yapısının çoğu, algoritmalarını uygulamak için dizi kullanır. Array kavramlarını anlamak için önemli terimler aşağıdadır.
- Öğe - Dizide depolanan her öğeye öğe adı verilir.
- Dizin - Bir dizideki bir öğenin her konumu, öğeyi tanımlamak için kullanılan sayısal bir dizine sahiptir.
Diziler, farklı dillerde çeşitli şekillerde açıklanabilir. Örnek olarak, C dizi tanımını ele alalım.
Yukarıdaki resmlere göre, dikkate alınması gereken önemli noktalar aşağıdadır.
- Diziler 0 ile başlar.
- Dizi uzunluğu 10'dur, yani 10 öğe saklayabilir.
- Her elemana indeksi üzerinden erişilebilir.
Bir dizi tarafından desteklenen temel işlemler aşağıdadır.
- Traverseing(Çaprazlama ilerleme) - tüm dizi öğelerini tek tek yazdırın.
- Insertion(Ekleme) - Verilen dizine bir öğe ekler.
- Deletion(Silme) - Belirtilen dizindeki bir öğeyi siler.
- Searching(Arama) - Verilen dizini kullanarak veya değeri kullanarak bir öğeyi arar.
- Update(Güncelle) - Verilen dizindeki bir öğeyi günceller.
Ekleme işlemi, bir diziye bir veya daha fazla veri öğesi eklemektir. Gereksinime bağlı olarak, başında, sonunda veya herhangi bir dizi içerisinde yeni bir öğe eklenebilir.
Silme, var olan bir öğeyi diziden kaldırmayı ve dizinin tüm öğelerini yeniden düzenlemeyi ifade eder.
Bir dizi öğesini, değerini veya indisini temel alarak arama yapabilirsiniz.
Güncelleme işlemi, belirli bir indiste varolan bir öğenin güncellenmesi anlamına gelir.
Bağlı bir liste, bağlantılar yoluyla birbirine bağlanmış bir dizi veri yapısıdır.
Bağlı Liste, öğeleri içeren bir bağlantılar dizisidir. Her bağlantı başka bir bağlantıya bağlantı içerir. Bağlı liste, diziden sonraki en çok kullanılan veri yapısıdır. Bağlı Liste kavramını anlamak için önemli terimler aşağıdadır.
- Bağlantı - Bağlı listedeki her bağlantı, öğe olarak adlandırılan verileri saklayabilir.
- Sonraki - Bağlı listedeki her bağlantıda İleri adlı bir sonraki bağlantıya bir bağlantı bulunur.
- LinkedList - Linked List, First adındaki ilk linke bağlantıyı içerir.
Bağlı liste, her düğümün bir sonraki düğüme işaret ettiği bir düğüm zinciri olarak örneklendirilebilir.
Yukarıdaki resme göre, dikkate alınması gereken önemli noktalar aşağıdadır.
- Bağlı Liste, önce adı verilen bir bağlantı elemanı içerir.
- Her bağlantı bir veri alanı ve bir sonraki adı verilen bir bağlantı alanı taşır.
- Her link bir sonraki linkini kullanarak bir sonraki linke bağlanır.
- Son bağlantı, listenin sonunu işaretlemek için boş bir bağlantı taşır.
Çeşitli Bağlı liste türleri aşağıdadır.
- Tek Yönlü Bağlı Liste - Öğe gezinme sadece ileri.
- Çift Yönlü Bağlı Liste - Öğeler ileri ve geri götürebilir.
- Dairesel Bağlı Liste - Son öğe, bir sonraki gibi ilk öğenin bağlantısını içerir ve ilk öğe, önceki gibi bir son öğenin bağlantısını içerir.
Bir liste tarafından desteklenen temel işlemler aşağıdadır.
- Ekleme - Listenin başına bir öğe ekler.
- Silme - Listenin başındaki bir öğeyi siler.
- Görüntüleme - Listenin tamamını görüntüler.
- Arama - Verilen anahtarı kullanarak bir öğeyi arar.
- Silme - Verilen anahtarı kullanarak bir öğeyi siler.
Çift Yönlü Liste, Tek Yönlü Listeye göre kolayca ileri veya geri gezinmenin her iki yönde de mümkün olduğu Yönlü listenin bir çeşididir. İkili Yönlü liste kavramını anlamak için önemli terimler aşağıdadır.
- Bağlantı - Yönlü listedeki her bağlantı, öğe olarak adlandırılan verileri saklayabilir.
- Sonraki - Yönlü listedeki her bağlantıda İleri adlı bir sonraki bağlantıya bir bağlantı bulunur.
- Önceki - Bağlanan listedeki her bağlantı, Önceki adlı önceki bağlantıya ait bir bağlantı içerir.
- LinkedList - Bağlı bir Liste, İlk adı verilen ilk bağlantıya ve Son adı verilen son bağlantıya bağlantı bağlantısını içerir.
- Çift Bağlantılı Liste, ilk ve son olarak adlandırılan bir bağlantı öğesi içerir.
- Her bağlantı bir veri alanı ve sonraki ve prev olarak adlandırılan iki bağlantı alanı taşır.
- Her link bir sonraki linkini kullanarak bir sonraki linke bağlanır.
- Her bağlantı önceki bağlantıyı kullanarak önceki bağlantıyı kullanarak bağlanır.
- Son bağlantı, listenin sonunu işaretlemek için boş bir bağlantı taşır.
- Ekleme - Listenin başına bir öğe ekler.
- Silme - Listenin başındaki bir öğeyi siler.
- Sonuncuyu Ekle - Listenin sonuna bir öğe ekler.
- Sonuncuyu Sil - Bir öğeyi listenin sonundan siler.
- Sonra Ekle - Listedeki bir öğenin arkasına bir öğe ekler.
- Sil - tuşunu kullanarak listeden bir öğe siler.
- İleri göster - Listenin tamamını ileri şekilde görüntüler.
- Geriye doğru göster - Listenin tamamını geriye doğru görüntüler.
Dairesel Bağlı Liste, ilk öğenin son öğeye, son öğenin ilk öğeye işaret ettiği Bağlı listenin bir çeşididir. Hem Tekli Bağlı Liste hem de İkili Bağlı Liste, dairesel bir Bağlı listeye eklenebilir.
Tek başına bağlı listede, son düğümün bir sonraki göstericisi ilk düğüme işaret eder.
- Son bağlantının sonraki listesi, hem tek tek hem de iki kat bağlantılı listedeki ilk listeye işaret eder.
- İkili bağlantı durumunda, ilk bağlantı önceki listenin sonunu gösterir.
- insert - Listenin başına bir öğe ekler.
- delete - Bir öğeyi listenin başından siler.
- display - Listeyi görüntüler.
Ağaçlar; dizilerden, bağlı listelerden, doğrusal veri yapıları olan yığın ve kuyruklardan farklı olarak hiyerarşik veri yapılarıdır. En üstteki düğüme ağacın kökü denir. Bir düğümün altındaki düğümlere o düğümün çocukları denir. Bir düğümün üzerindeki düğüme o düğümün ebeveyni adı verilir. Aşağıdaki örnek için, "A", "F" nin çocuğu ve "F", "A" nın ebeveynidir. Çocuğu olmayan düğümlere ise yaprak adı verilir.
- Ağaçları doğal olarak hiyerarşi oluşturan bilgileri depolamak istediğimiz zaman kullanabiliriz. Örneğin, bir bilgisayarlardaki dosya sistemleri.
- Ağaçlar orta düzeyde erişim veya arama sağlar(Bağlı listelerden daha hızlı, dizilerden daha yavaş).
- Ağaçlar orta düzeyde ekleme veya silme sağlar(Dizilerden daha hızlı, sıralı olmayan bağlı listelerden daha yavaş).
- Bağlı listelerdeki gibi ama dizilerden farklı olarak, ağaçların düğümleri işaretçiler kullanılarak bağlandığı için, düğüm sayısında üst sınır yoktur.
Elemanlarının her birinin en fazla 2 çocuğa sahip olduğu ağaçlara ikili ağaç denir. İkili bir ağaçtaki her düğümün sadece 2 çocuğu olabileceğinden, genellikle bunları sol ve sağ çocuk olarak adlandırırız.
Bir ağaç, ağaçtaki en üst düğüme işaretçi ile temsil edilir. Ağaç boşsa, kök değeri NULL olur. Bir Ağaç düğümü aşağıdaki bölümleri içerir.
- Veri
- Sol çocuk için işaretçi
- Sağ çocuk için işaretçi
-
Bir ikili ağacın 'k' seviyesindeki maksimum düğüm sayısı 2k-1'dir. Burada seviye, kökten düğüme giden yoldaki düğüm sayısıdır (kök ve düğüm dahil). Kök seviyesi 1'dir. Örneğin;
Kök için(k = 1); Düğüm Sayısı = 2k - 1 = 1 olur. -
H yüksekliğindeki bir ikili ağaçtaki maksimum toplam düğüm sayısı 2H - 1'dir. Burada yükseklik, kökten yaprak yoluna kadar olan yüksekliktir. Tek düğümlü bir ağacın yüksekliği 1 olarak kabul edilir. Tüm seviyelerde maksimum düğüm varsa, o ağaçtaki maksimum düğüm sayısına ulaşılmıştır. Bu nedenle, H yüksekliğinde bir ikili ağaçtaki toplam maksimum düğüm sayısı 1 + 2 + 4 + .. + 2H-1'dir.
Bu ise H terimli basit bir geometrik seridir ve bu serinin toplamı 2H - 1'dir. - N düğümlü bir ikili ağaç için mümkün olan minimum yükseklik veya minimum seviye sayısı Log2 (N + 1)dir.
-
L sayıda yaprağı olan ikili ağaç var olabilir mi? Bunun için Log2L + 1 denkleminden faydalanırız.
Bir ikili ağaç, tüm seviyeleri tamamen dolu iken maksimum yaprak sayısına (ve minimum seviye sayısına) sahiptir. Tüm yaprakların L seviyesinde olduğunu düşünerek aşağıdaki eşitliği inceleyelim:
L <= 2L-1
L = Log2L + 1 => eşitliği sağlanıyorsa L minimum seviye sayısıdır. -
Her düğümün 0 veya 2 çocuğunun olduğu bir ikili ağaçta, yaprak düğüm sayısı her zaman iki çocuklu düğümlerin sayısından bir fazladır.
L = Yaprak Düğüm Sayısı
T = İki Çocuklu Düğüm Sayısı
L = T + 1
-
Full Binary Tree - Her düğümünün 0 veya 2 çocuğunun olduğu ağaçlar Full Binary Tree(Tam İkili Ağaç) olarak adlandırılır. Aynı zamanda; yaprakları dışındaki tüm düğümlerinin iki çocuğu olan ağaçlar olarak da tanımlayabiliriz. Full Binary Tree örnekleri;
Tam ikili ağaçlarda yaprak düğüm sayısı iç düğüm sayısından 1 fazladır.
L = Yaprak düğüm sayısı, I = İç düğüm sayısı
L = I + 1 -
Complete Binary Tree - Son seviye hariç tüm seviyelerin tamamen dolu olduğu ve son seviyenin mümkün olduğu kadar düğüme sahip olduğu ağaçlar Complete Binary Tree(tamamlanmış ikili ağaçlar) olarak adlandırılırlar. Örnekler;
-
Perfect Binary Tree - Tüm iç düğümlerin iki çocuğa sahip olduğu ve tüm yaprakların aynı seviyede olduğu ağaçlar Perfect Binary Tree(mükemmel ikili ağaç) olarak adlandırılırlar. H yüksekliğindeki mükemmel ikili ağaç 2H - 1 düğüme sahiptir. Örnekler;
-
Balanced Binary Tree - Her iç düğümün en fazla bir çocuğunun olduğu ağaçlar Balanced Binary Tree(dengeli ikili ağaç) olarak adlandırılırlar. Bu tür ağaçlar performans bakımından bağlı listelerle aynıdır. Bu ağaçlarda kök ile her yaprağın yolu aynıdır.
