Veri yapıları açıklandı
Her program veriyi bir yerde saklar ve onu nasıl sakladığı neyin hızlı, neyin yavaş olacağını belirler. Bir milyon isimlik bir liste isim isim taranabilir ya da yirmi karşılaştırmanın herhangi bir ismi bulacağı biçimde düzenlenebilir. Veri yapıları bu düzenlemelerdir: çoğu kişisel bilgisayardan eski bir avuç fikir; her veritabanının, işletim sisteminin, tarayıcının ve oyunun içinde bulunurlar.
Bir veri yapısı ne işe yarar
Bir veri yapısı yanıtlaması gereken sorulara göre seçilir. Bir telefonun arama kaydı önce son aramayı, bir yazıcının işleri önce en eskisini, bir sözlük yüz bin kelime arasından birinin anlamını, bir rota planlayıcı ziyaret edilmemiş en yakın kavşağı ister. Her yapı bazı işlemleri, başkalarından vazgeçerek hızlandırır; büyük O gösterimi bu takası anlatır: O(1), sürenin öğe sayısı n ile büyümediği, O(log n), n'yi ikiye katlamanın bir adım eklediği, O(n) ise sürenin n ile orantılı büyüdüğü anlamına gelir.
Yığınlar, kuyruklar ve deque'ler
Yığın aynı uçta ekler ve çıkarır: son giren ilk çıkar. Geri alma geçmişleri, geri düğmesi ve çalışan bir programın çağrıları yığındır. Kuyruk arkaya ekler ve önden çıkarır: ilk giren ilk çıkar, tıpkı klavye girişi ya da bir yazdırma kuyruğu gibi. Deque iki uçta da ikisine izin verir. Üçü de işlem başına sabit süre alır. Kuyruk çoğu zaman dairesel bir arabellekte tutulur; bu, ön ve arkanın son yuvadan sonra başa döndüğü sabit bir dizidir; dolduğunda öğeler iki kat büyük bir diziye kopyalanır. Kopyalama O(n) tutar, ama o kadar seyrek olur ki her işlem yine ortalama O(1) tutar; buna amortize sınır denir.
Bağlı listeler
Bağlı liste her değeri, bir sonraki düğüme işaretçisi olan bir düğümde saklar. Ekleme ya da silme yalnızca bir iki işaretçiyi değiştirir, hiçbir şey kaydırılmaz, ama onuncu düğüme atlanamaz: bağlantılar baştan izlenir. Yalnızca başını tutan bir liste kuyruğa O(n) adımda ulaşır; gerçek listeler genellikle bir kuyruk işaretçisi de tutar, çift bağlı listeler ise geriye bir işaretçi; bir tarayıcı geçmişi ya da LRU önbelleği böyle kurulur.
İkili arama ağaçları
İkili arama ağacı her düğümde küçük değerleri sol alt ağaçta, büyükleri sağda tutar. Bir arama karşılaştırır ve sola ya da sağa gider; ortadan dolaşma değerleri sıralı okur. Bir yaprağı silmek onu çıkarmaktır, tek çocuklu bir düğümün yerine o çocuk geçer, iki çocuklu bir düğümün yerine ise ortadan sıradaki ardılı, yani sağ alt ağacındaki en küçük değer geçer. Bunların hepsi ağacın yüksekliğiyle orantılı süre alır: ağaç gürken yaklaşık log n, ama değerler sıralı geldiğinde ve ağaç bir listeye dönüştüğünde n.
AVL ve kırmızı-siyah ağaçlar
Kendini dengeleyen ağaçlar her değişiklikten sonra biçimlerini onarır. Adelson-Velsky ve Landis'in 1962'de bulduğu AVL ağacı, her düğümün iki alt ağacının yüksekliklerini birbirinden en fazla bir farklı tutar; bir düğümün denge çarpanı ±2'ye ulaştığında bir döndürme (LL ve RR durumları) ya da iki döndürme (LR ve RL) dengeyi geri getirir. Kırmızı-siyah ağaç düğümlerini kök siyah olacak, hiçbir kırmızı düğümün kırmızı çocuğu olmayacak ve aşağı inen her yol aynı sayıda siyah düğümden geçecek biçimde boyar; bu da en uzun yolu en kısanın en fazla iki katında tutar. Yeniden boyayarak ve en fazla birkaç döndürmeyle kendini onarır; Java'nın TreeMap'inin, C++'ın std::map'inin ve Linux zamanlayıcısının içindeki ağaç odur.
Heap'ler ve öncelik kuyrukları
İkili heap, hiç işaretçi olmadan bir dizide saklanan tam bir ikili ağaçtır: i konumunun çocukları 2i + 1 ve 2i + 2'dedir. Bir min-heap'te her ebeveyn en fazla çocukları kadar büyüktür, bu yüzden en küçük değer hep köktedir. Yeni bir değer sona gider ve daha büyük ebeveynleri geçerek yükselir; kök çıkarılınca son değer tepeye taşınır ve aşağı iner. İkisi de O(log n) tutar ve bütün bir dizi O(n) sürede heap'e dönüştürülebilir. Heap'ler Dijkstra'nın en kısa yollarındaki, olay benzetimlerindeki ve işletim sistemi zamanlayıcılarındaki öncelik kuyruklarını çalıştırır ve heap sıralamasını verir.
Özet tabloları
Özet tablosu bir anahtarı özet fonksiyonuyla bir dizi indeksine çevirir ve doğrudan oraya gider. Farklı anahtarlar aynı indekse düşebilir: bu bir çakışmadır. Zincirleme her kovada küçük bir liste tutar; doğrusal yoklama gibi açık adresleme boş bir yuva bulana kadar sonraki yuvaları dener ve bir anahtar silindiğinde, sonraki aramaların yoklamaya devam etmesi için bir mezar taşı bırakmak zorundadır. İyi bir özet fonksiyonu ve tablo büyütülerek düşük tutulan bir doluluk oranıyla (kova başına anahtar) ekleme, arama ve silme ortalama O(1) tutar. Bir kelimenin karakter kodlarını toplamak gibi zayıf bir fonksiyon anagramları aynı kovaya gönderir. Python'un dict'inin, JavaScript nesnelerinin ve veritabanı indekslerinin arkasında özet tabloları vardır.
Trie ve union-find
Trie, yani önek ağacı, dizeleri her düzeyde bir karakter olacak biçimde saklar; böylece aynı biçimde başlayan kelimeler bir yolu paylaşır ve bir düğüm bir kelimenin nerede bittiğini işaretler. L uzunluğunda bir kelimeyi bulmak, kaç kelime saklanırsa saklansın L adım sürer ve belirli bir önekle başlayan bütün kelimeler tek bir alt ağaçtadır; otomatik tamamlama ve yazım denetimi böyle çalışır. Union-find öğeleri ayrık kümelerde tutar; her küme, kökü kümeye adını veren bir ağaçtır. Find ebeveyn bağlantılarını köke kadar izler; union bir kökü diğerinin altına asar. Ranka göre birleştirme ve yol sıkıştırmayla uzun bir işlem dizisi işlem başına neredeyse sabit süre tutar: ters Ackermann fonksiyonu α(n), gerçekçi her n için en fazla 4'tür. Kruskal'ın en küçük kapsayan ağaç algoritması buna dayanır.
Sık sorulan sorular
Dizi ile bağlı liste arasındaki fark nedir?
Dizi öğelerini bellekte yan yana tutar, bu yüzden her konuma hemen ulaşılır, ama ortaya eklemek arkadaki her şeyi kaydırmak demektir. Bağlı liste işaretçileri değiştirerek her yere ekleyebilir, ama bir konuma ulaşmak baştan yürümek demektir. Diziler ayrıca işlemcinin önbelleğini çok daha iyi kullanır; bu yüzden uygulamada genellikle daha hızlıdırlar.
Amortize süre ne demektir?
Tek bir işlem bazen pahalı olsa bile, uzun bir dizi boyunca işlem başına ortalama maliyet. Dolunca ikiye katlanan dairesel bir arabellek ara sıra n öğesinin hepsini kopyalar, ama arabellek büyüdükçe kopyalar seyrekleştiği için n ekleme toplamda O(n), yani her biri ortalama O(1) tutar.
Heap ile ikili arama ağacı aynı şey mi?
Hayır. İkili arama ağacı her sol alt ağacı düğümünden önce, her sağ alt ağacı sonra yerleştirir; bu yüzden bütün değerleri sırayla listeleyebilir ve herhangi bir değeri hızla bulabilir. Heap yalnızca her ebeveynin çocuklarından önce geldiğini vaat eder; bu, en küçüğü ya da en büyüğü hemen bulmaya yeter, ama rastgele bir değeri aramaya yetmez.
Union-find iki öğenin bağlı olup olmadığını nasıl bilir?
Her öğeden ebeveyn bağlantılarını ağacının köküne kadar izler. İkisi de aynı köke varırsa aynı kümededirler. Ardından yol sıkıştırma, yol üzerindeki her düğümün doğrudan kökü göstermesini sağlar; böylece onlarla ilgili bir sonraki soru tek adım sürer.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Veri yapısı görselleştiriciyi açın