Örtük veri yapısı - Implicit data structure

Gelen bilgisayar bilimleri , bir örtülü veri yapısı veya uzay verimli veri yapısı bir olan veri yapısı ana veya gerekli verilerin dışındaki depolar çok az bilgi: düşük gerektiren bir veri yapısı yükü . "Örtülü" olarak adlandırılırlar çünkü öğelerin konumu, öğeler arasında anlam ve ilişki taşır; bu, öğeler arasında açık bir ilişki vermek için işaretçilerin kullanımıyla çelişir . "Düşük ek yük" tanımları değişir, ancak genellikle sabit ek yük anlamına gelir; içinde büyük O gösterimde , O (1) üst. Daha az kısıtlayıcı bir tanım, daha fazla ek yüke izin veren kısa ve öz bir veri yapısıdır .

Tanım

Bir örtük veri yapısı, sabit O (1) uzay yüküne sahip bir yapıdır ( bilgi-teorik alt sınırın üzerinde).

Tarihsel olarak, Munro & Suwanda (1980) örtük bir veri yapısını (ve bir tanesine göre hareket eden algoritmaları) "yapısal bilginin işaretçilerde açıktan ziyade verilerin depolanma biçiminde örtük olduğu" bir yapı olarak tanımladılar. Tanımda biraz belirsizdirler, onu en katı şekilde, yalnızca boyutu korunan (tek bir ek yük sayısı) tek bir dizi olarak veya daha gevşek bir şekilde sabit ek yükü olan bir veri yapısı olarak tanımlarlar ( O (1) ). Bu son tanım bugün daha standarttır ve sabit olmayan fakat küçük o (n) ek yükü olan bir veri yapısının hala daha gevşek olan kavramı, Jacobson (1988) tarafından tanımlandığı gibi, bugün kısa ve öz veri yapısı olarak bilinmektedir ; Munro & Suwanda (1980) tarafından yarı örtük olarak ifade edilmiştir .

Temel bir ayrım, statik veri yapıları (salt okunur) ve dinamik veri yapıları (değiştirilebilir) arasındadır. Sıralanmış bir listeyi bir dizi olarak temsil etmek gibi basit örtük veri yapıları, statik bir veri yapısı olarak çok verimli olabilir, ancak değişiklik işlemleri (sıralı bir liste durumunda ekleme gibi) nedeniyle dinamik bir veri yapısı olarak verimsiz olabilir. yetersiz.

Örnekler

Bir örtük veri yapısının önemsiz bir örneği, bir liste için örtük bir veri yapısı olan ve yalnızca uzunluğun sabit ek yükünü gerektiren bir dizi veri yapısıdır ; Her bir veri öğesiyle ilişkilendirilmiş bir işaretçiye sahip olan ve bir öğeden diğerine açıkça ilişkiyi veren bağlantılı listeden farklı olarak . Benzer şekilde, boş sonlandırılmış bir dize , bir dize (karakter listesi) için örtük bir veri yapısıdır . Bunlar çok basit olarak kabul edilirler çünkü bunlar statik veri yapılarıdır (salt okunur) ve yalnızca öğeler üzerinde basit yineleme işlemini kabul eder.

Benzer şekilde basit, çok boyutlu bir diziyi boyutlarıyla birlikte tek boyutlu bir dizi olarak temsil etmek . Örneğin, bir m × n dizisini , m ve n sayılarıyla birlikte (her 1 boyutlu alt diziye yönelik 1 boyutlu bir işaretçi dizisi yerine) m·n uzunluğundaki tek bir liste olarak temsil etmek. Öğelerin aynı türde olması gerekmez ve bir veri tablosu (bir kayıt listesi ), benzer şekilde, her alanın uzunluğuyla birlikte, düz (1 boyutlu) bir liste olarak, her alan olduğu sürece örtük olarak temsil edilebilir. tek tip boyut (böylece kayıt başına değil, alan başına tek bir boyut kullanılabilir).

Daha az önemsiz bir örnek, ikili arama ile logaritmik zamanda aramaya izin veren, sıralanmış bir diziye göre sıralanmış bir listeyi temsil etmektir . Arama ağacıyla , özellikle de logaritmik zamanlı aramaya izin veren, ancak işaretçiler gerektiren ikili arama ağacıyla kontrast . Sıralanmış bir dizi, yalnızca statik bir veri yapısı olarak verimlidir, çünkü listeyi değiştirmek – ikili arama ağacının aksine – yavaştır, ancak bir ağacın ek yüküne ihtiyaç duymaz.

Örtük veri yapısının önemli bir örneği, mükemmel bir ikili ağacı artan derinlik sırasına göre, yani kök, ilk sol çocuk, ilk sağ çocuk, ilk sol çocuğun ilk sol çocuğu, vb. bir liste olarak temsil etmektir . Böyle bir ağaç özellikle oluşur. belirli bir derinliğe kadar bir soy haritası için ve örtük temsil bir Ahnentafel (ata tablosu) olarak bilinir .

Bu, örtük bir veri yapısının en iyi bilinen örneğini, yani bir öncelik sırası için örtük bir veri yapısı olan ikili yığını veren tam bir ikili ağaca (son seviyenin eksik olabileceği) genelleştirilebilir . Bu, birden çok işleme izin verdiği ve verimli bir dinamik veri yapısı olduğu için önceki örneklerden daha karmaşıktır (verilerin verimli bir şekilde değiştirilmesine izin verir): yalnızca top değil , aynı zamanda insert ve pop .

Daha karmaşık örtük veri yapıları, beap'i (iki ebeveynli yığın) içerir.

Tarih

Değer listelerinin veya tablolarının önemsiz örnekleri tarih öncesine kadar uzanırken, tarihsel olarak önemsiz olmayan örtük veri yapıları en azından 1590'da şecerede kullanılmak üzere Michaël Eytzinger tarafından tanıtılan Ahnentafel'e kadar uzanır . Biçimsel bilgisayar bilimi, ilk örtülü veri yapısı genelde tarafından tanıtıldı ikili arama için kullanılan sıralı liste, olarak kabul edilir John Mauchly içinde, 1946 yılında Moore Okulu Dersler , ilk herhangi bir bilgisayarla ilgili ilgili ders set başlık. İkili yığın tanıtıldı Williams (1964) uygulamak için Heapsort . Örtük bir veri yapısı kavramı, beap'in tanıtılması ve analiz edilmesinin bir parçası olarak Munro & Suwanda'da (1980) resmileştirildi .

Referanslar

daha fazla okuma

Hervé Brönnimann , J. Ian Munro ve Greg Frederickson'ın yayınlarına bakın .