Veri yapıları: açıklamalı alıştırma soruları

1Veri yapısı nedir

Veri yapısı, verileri bellekte, belirli işlemler hızlı olsun diye düzenlemenin bir yoludur: bir öğeyi bulmak, eklemek, silmek.

Hiçbir yapı her şeyde hızlı değildir. Birini seçmek hangi işlemlerin ucuz olacağını seçmektir. Maliyetleri Büyük O ile yazılır, n öğe sayısıdır.

İki temel yapı taşı dizi ve bağlı listedir.

Dizi öğelerini belleğin tek bir bloğunda art arda saklar. Bilgisayar i. öğenin yerini hesaplayabilir, bu yüzden a[i] okumak O(1) sürer. Başa eklemek her öğeyi kaydırmak demektir: O(n).

Bağlı liste, her öğeyi bir sonraki düğüme işaretçisi olan bir düğümde saklar. Son işaretçi null’dır. Başa (h) eklemek yalnızca bir işaretçiyi değiştirir: O(1). Ama i. öğeye ulaşmak için i işaretçiyi izlemeniz gerekir: O(n).

Çift bağlı liste ayrıca önceki düğüme bir işaretçiye sahiptir, böylece iki yönde de yürüyebilirsiniz.

2Yığınlar ve kuyruklar

Yığın (stack) bir tabak yığını gibidir: yalnızca üstten eklersiniz ve çıkarırsınız. İlk giren son çıkar: LIFO.

• push bir öğeyi üste koyar, pop üstteki öğeyi çıkarır, peek üsttekini çıkarmadan okur. Hepsi O(1)’dir.
• Kullanımlar: bir editörün geri al işlevi, bir programın çağrı yığını, parantezlerin dengeli olduğunu denetlemek, derinlik öncelikli arama.

Kuyruk (queue) bir kasanın önündeki sıra gibidir: arkadan katılır, önden ayrılırsınız. İlk giren ilk çıkar: FIFO.

• enqueue arkaya ekler, dequeue önden çıkarır. İkisi de O(1)’dir.
• Kullanımlar: yazdırma işleri, işlenmeyi bekleyen mesajlar, genişlik öncelikli arama.

Deque (çift uçlu kuyruk), her iki uçta ekleme ve çıkarmaya izin verir. Öncelik kuyruğu her zaman önce en yüksek öncelikli öğeyi çıkarır; genellikle bir yığın (heap) olarak kurulur.

3Ağaçlar, yığınlar (heap), karma tabloları ve graflar

Ağacın bir üst düğümü vardır, kök. Diğer her düğümün tam olarak bir ebeveyni vardır. Çocuğu olmayan düğümlere yaprak denir. n düğümlü bir ağacın n − 1 kenarı vardır.

İkili ağaçta her düğümün en fazla iki çocuğu vardır. İkili arama ağacı (BST) bir kural ekler: sol alt ağaçtaki anahtarlar düğümden küçük, sağ alt ağaçtakiler büyüktür.

BST’de arama aşağı tek bir yolu izler, bu yüzden maliyeti O(yükseklik)’tir. Dengeli bir ağaç (AVL, kırmızı-siyah) yüksekliği log₂ n civarında tutar. Sıralı eklenen anahtarlar n yüksekliğinde bir zincir oluşturur.

Yığın (heap), her ebeveynin çocuklarından küçük (min-heap) ya da büyük (max-heap) olduğu ikili ağaçtır. Minimum ya da maksimum kökte durur ve ekleme ile çıkarma O(log n) maliyetlidir.

Karma tablosu anahtar–değer çiftlerini saklar. Bir karma işlevi anahtarı bir indekse çevirir, bu yüzden ekleme ve arama ortalamada O(1) sürer. Aynı indeksli iki anahtar bir çakışmadır ve zincirleme (her göz için bir liste) ya da açık adresleme (başka bir göz deneme) ile çözülür.

Graf, yönü veya ağırlığı olabilen kenarlarla birleşen düğümlere (vertex) sahiptir. Bir komşuluk matrisi (O(V²) bellek) veya komşuluk listeleri (O(V + E)) olarak saklanır.

4Adım adım yöntem

Sorular çoğu zaman bir görevi anlatıp hangi yapının uyduğunu sorar ya da bazı işlemlerden sonra bir yapının nasıl göründüğünü sorar.

1. Hızlı olması gereken işlemi bulun: konuma, anahtara göre erişim, en yeni öğe, en eski öğe, en küçük öğe ya da bir aralık.
2. Bir yapıyla eşleştirin: indeks → dizi, anahtar → karma tablosu, en yeni → yığın (stack), en eski → kuyruk, en küçük ya da en büyük → heap, sıralı düzen ya da aralıklar → dengeli arama ağacı.
3. Görevin ihtiyaç duyduğu diğer işlemlerin maliyetini Büyük O ile kontrol edin.
4. İzleme (trace) sorusunda işlemleri tek tek uygulayın ve her birinden sonra durumu yazın.
5. Son durumu yapının kuralına göre kontrol edin: LIFO, FIFO, BST sırası ya da heap sırası.

5Çözümlü bir örnek

Her adımı izleyin. Açmadan önce bir sonrakini tahmin etmeye çalışın.

6Sık yapılan hatalar

• LIFO ile FIFO’yu karıştırmak. Yığın en yeni öğeyi, kuyruk en eskisini döndürür.
• Bağlı listenin indekse göre hızlı erişim verdiğini sanmak. Başlangıçtan yürümek zorundadır.
• BST’nin her zaman O(log n) olduğunu varsaymak. Yalnızca dengeli ağaç öyledir; sıralı eklemeler O(n) verir.
• Karma tablosunda çakışmaları unutmak. O(1) ortalamadır, en kötü durum değil.
• Dolaşımları karıştırmak. Önce-kök (preorder): düğüm ilk. Ortadan sıralı (in-order): düğüm ortada. Sonra-kök (postorder): düğüm son.
• Büyük seyrek bir graf için komşuluk matrisi kullanmak. O(V²) bellek israf eder.

7Sınav soruları nasıl görünür

• Kolay: anahtar terimler ve olgular. LIFO ve FIFO, düğüm, kök ya da yaprağın ne olduğu, BST kuralı, bir karma işlevinin ne yaptığı.
• Orta: kavramları uygulama. Bir göreve hangi yapının uyduğu, push ve pop ya da BST eklemelerinin sonucu, ağaç dolaşımları, doğrusal yoklamalı karma tablosu, Büyük O maliyetleri.
• Zor: olgular ve analiz. Dengeli ağaçlar, dizilerde heap, B-ağaçları, trie’ler, union-find, Bloom filtreleri ve LRU önbelleği gibi tasarımlar.

0 indeksinden başlayarak bir dizide saklanan heap için i indeksinin çocukları 2i + 1 ve 2i + 2’dedir, ebeveyni ⌊(i − 1) / 2⌋’dedir.