Temel Veri Yapıları
Temel veri yapıları, verileri depolamanın ve erişmenin düzenli yollarıdır — diziler, bağlı listeler, karma tablolar, ağaçlar, yığınlar ve bunların akrabaları — ve üzerlerine inşa edilen işlemlerin verimliliğini belirlemektedir.
Tanım
Bir veri yapısı, verileri, soyut veri tipi tarafından tanımlanan işlemlerin verimli bir şekilde gerçekleştirilebilmesi için düzenleme ve depolama yöntemidir; temel veri yapıları ise diğerlerinin çoğunun üzerine inşa edildiği küçük bir genel amaçlı yapılar kümesidir.
Kapsam
Bu alan, soyut veri tiplerini (listeler, sözlükler, öncelik kuyrukları, kümeler) ve bunları uygulayan somut yapıları, en kötü durum ve amortize edilmiş analiz altında temel işlemlerinin (ekleme, silme, arama, güncelleme) maliyetiyle birlikte kapsamaktadır. Yapı seçiminin algoritma performansını nasıl şekillendirdiğini ve bu yapılara dayanan tasarım paradigmaları ile graf ve dize algoritmalarıyla nasıl bağlantılı olduğunu ele almaktadır. Diğer alt alanlarda ele alınan veritabanı ve dosya sistemi depolama yapılarını içermemektedir.
Alt konular
Temel sorular
- Bir uygulama hangi soyut veri tipine ihtiyaç duyar ve hangi somut yapı onu en iyi şekilde uygular?
- Belirli bir yapı üzerindeki her işlemin en kötü durum ve amortize edilmiş maliyetleri nelerdir?
- Yapılar belleği zamanla, ya da okuma hızını güncelleme hızıyla nasıl takas eder?
- Bir değişmezi (sıralılık, denge, yığın özelliği) sürdürmek işlem maliyetlerini nasıl sınırlar?
- Asimptotik olarak daha hızlı ama daha karmaşık bir yapıya göre basit bir yapı ne zaman tercih edilir?
Anahtar kavramlar
- soyut veri tipi
- diziler ve bağlı listeler
- yığınlar ve kuyruklar
- karma tablolar
- ikili arama ağaçları
- dengeli ağaçlar
- yığınlar ve öncelik kuyrukları
- amortize edilmiş analiz
- zaman-alan takasları
Temel kuramlar
- Soyut veri tipleri ve uygulamaları
- Soyut bir veri tipi, işlemlerini ve semantiğini gösterimden bağımsız olarak belirtir; birden fazla somut veri yapısı, aynı soyut veri tipini farklı performans profilleriyle uygulayabilir, bu da tasarımcıların doğruluk ve maliyet hakkında ayrı ayrı akıl yürütmesine olanak tanır.
- Amortize edilmiş analiz
- Bazı yapılar (dinamik diziler, splay ağaçları) ara sıra pahalı işlemlere sahip olsa da, bir dizi üzerinde ortalama olarak ucuz işlemlere sahiptir; amortize edilmiş analiz (toplu, muhasebe, potansiyel yöntemler) bu ortalama maliyeti titizlikle sınırlamaktadır.
Klinik önem
Temel veri yapıları, esasen tüm yazılımların yapı taşlarıdır: karma tablolar sözlükleri ve veritabanı indekslerini destekler, dengeli ağaçlar ve B-ağaçları dosya sistemlerini ve veritabanlarını düzenler, öncelik kuyrukları zamanlayıcıları ve olay simülasyonlarını yönlendirir ve doğru yapı seçimi genellikle bir sistemin ölçeklenip ölçeklenemeyeceğini belirlemektedir.
Tarihçe
Temel veri yapıları, Knuth'un 1968'de başlayan The Art of Computer Programming adlı eserinde kataloglanmıştır. Kendi kendini dengeleyen ağaçlar (AVL ağaçları, 1962; kırmızı-siyah ağaçlar ve B-ağaçları 1970'lerde) ve Fibonacci yığınları ile splay ağaçları gibi gelişmiş yapılar (1980'ler, büyük ölçüde Tarjan ve işbirlikçileri sayesinde) alanı genişletirken, amortize edilmiş analiz performanslarının titiz bir açıklamasını sağlamıştır.
Öne çıkan isimler
- Donald Knuth
- Robert Sedgewick
- Robert Tarjan
- Rudolf Bayer
İlgili konular
Temel eserler
- knuth1997vol1
- cormen2009
- sedgewick2011
Sıkça sorulan sorular
- Bir karma tablo ile dengeli bir arama ağacı arasında nasıl seçim yaparım?
- Karma tablolar beklenen O(1) arama ve ekleme sağlar ancak sıralama yapmazken, dengeli arama ağaçları O(log n) işlemler sağlar ve anahtarları sıralı tutarak aralık sorgularını ve sıralı geçişi destekler. Sadece anahtar aramaları için karma tabloyu, sıralama veya aralık işlemleri önemli olduğunda ise ağacı seçmek genellikle tercih edilmektedir.
- Bir veri yapısı için amortize edilmiş maliyet ne anlama gelir?
- Amortize edilmiş maliyet, en kötü durumdaki bir işlem dizisi boyunca işlem başına düşen ortalama maliyettir. Örneğin, dinamik bir dizi ara sıra yeniden boyutlandırmak için O(n) maliyet öder, ancak yeniden boyutlandırmalar ucuz eklemelere göre nadir olduğu için ekleme başına ortalama O(1) maliyet düşmektedir.