Veri yapıları II

Geçen ders doğrusal yapılardı — veriler tek sıra hâlinde. Bu ders iki yeni boyut açıyor: hiyerarşi (ağaç, ikili arama ağacı, heap) ve ilişki ağı (graf); araya da yazılımın en çok kullanılan numarası giriyor: hash tablosu — Dictionary'nin O(1) sırrı. Veritabanı indeksinden yol tarifine, npm bağımlılıklarından önbelleğe; bu dersin dört yapısı, kullandığın hemen her sistemin omurgasıdır.

01Ne öğreneceksin

02Ağaç: hiyerarşinin yapısı

Ağaç, düğümlerin ebeveyn-çocuk ilişkisiyle bağlandığı hiyerarşik yapıdır: tek bir kök (root) vardır; her düğümün bir ebeveyni (kök hariç) ve sıfır ya da daha çok çocuğu olur; çocuğu olmayan düğüme yaprak (leaf) denir. Bilgisayarlar ters çizer — kök üstte:

            [ / ]                ← kök (derinlik 0)
           /     \
       [home]   [etc]            ← derinlik 1
        /   \
   [ali]   [ayse]                ← derinlik 2 — yapraklar
   yükseklik = en derin yaprağa uzaklık = 2

Terimleri sabitle: bir düğümün derinliği köke uzaklığı, ağacın yüksekliği en derin yaprağın derinliğidir; bir düğüm ve altındakiler alt ağaçtır — ağaç, özyinelemeli bir yapıdır: her çocuk kendi alt ağacının köküdür (bu bakış, ağaç algoritmalarının neden hep özyinelemeli yazıldığının cevabıdır; özyineleme 12. derste, tb-algoritma-teknik). Ağaçları zaten her gün kullanıyorsun: dosya sistemi (4. dersin dizin hiyerarşisi), HTML belgesinin DOM'u (Hat 08'de gezineceksin), bu sitenin hat → ders menüsü, organizasyon şemaları.

03İkili arama ağacı: sıralı düzenin ağacı

İkili ağaçta her düğümün en çok iki çocuğu olur (sol, sağ). İkili arama ağacı (BST) buna tek bir kural ekler: soldaki her şey düğümden küçük, sağdaki her şey büyük. Bu kural, aramayı her adımda yarıya indirir:

        [50]         37'yi ara:
       /    \        50'den küçük → sola
    [30]    [70]     30'dan büyük → sağa
    /  \    /  \
 [20] [37][60][80]   → BULUNDU: 3 adım (8 elemanda)

Dengeli bir BST'de arama, ekleme ve silme O(log n)'dir — 1 milyon kayıtta ~20 adım (log'un gücünü 10. ders resmîleştirecek). Üstelik sıralı gezinme bedavadır: sol-kök-sağ (inorder) sırayla dolaşırsan elemanlar küçükten büyüğe akar — hash tablosunun asla veremeyeceği özellik.

Tuzak — dengesizlik: BST'ye elemanları zaten sıralı eklersen (10, 20, 30, 40...) her yeni düğüm sağa asılır; ağaç, bağlı listeye yozlaşır ve tüm işlemler O(n)'e düşer. Çare, kendini dengeleyen ağaçlardır (AVL, kırmızı-siyah): ekleme-silme sırasında döndürmelerle yüksekliği log n'de tutarlar — mekanizmalarını değil varlıklarını ve garantilerini bil. C#'ta SortedDictionary<K,V> kırmızı-siyah ağaçtır: "anahtarlarım her an sıralı gezilsin" istiyorsan Dictionary yerine onu seçersin (bedeli: O(1) yerine O(log n)). En önemli köprü ise şu: veritabanı indeksleri (Hat 07, db-indeks) bu fikrin disk için evrilmiş hâli olan B-ağaçlarıdır — her düğümü bir disk sayfası kadar geniş tutarak (4. dersin sayfa kavramı) milyonlarca kayıtta 3-4 disk okumasıyla arama yapar. "İndeks neden hızlandırır?" sorusunun kökü bu bölümdür.

04Heap: her an tepede en öncelikli

Heap, şu tek soruyu ucuza cevaplamak için kurulmuş ağaçtır: "eldekilerin en küçüğü/büyüğü hangisi?" Min-heap kuralı: her düğüm, çocuklarından küçük ya da eşittir — dolayısıyla kök, her an en küçüktür. BST'den farkını karıştırma: heap'te sol-sağ sıralaması yoktur, yalnızca ebeveyn-çocuk ilişkisi kurallıdır; arama için kötü, "tepeyi al" için mükemmeldir: en küçüğü görmek O(1), almak ya da yeni eleman eklemek O(log n) (eleman yukarı/aşağı süzülür).

Zarif bir gerçekleme ayrıntısı: heap tam ikili ağaç olduğundan düğümler düz bir diziye döşenir — i. düğümün çocukları 2i+1 ve 2i+2'dedir; referans yok, düğüm nesnesi yok, önbellek dostu (8. dersin dizi avantajı burada da). Kullanım alanının adı öncelik kuyruğudur (priority queue): normal kuyruk geliş sırasına bakar, öncelik kuyruğu önem sırasına — hastane acili triyajı, işletim sisteminin öncelikli zamanlaması (3. ders), yol bulmada Dijkstra algoritması, "en yakın toplantı" ajandası. C#'ta hazır: PriorityQueue<TEleman, TOncelik>. Heapsort'a da temel olur (11. derste değinilecek).

İsim uyarısı — sınav ve mülakat tuzağı: buradaki heap ile 4. dersin bellek heap'i (new'lenen nesnelerin bölgesi) tamamen ilgisiz iki kavramdır; talihsiz bir isim çakışmasıdır. "Heap nedir?" sorusunda bağlama bak: veri yapısı mı soruluyor, bellek bölgesi mi — gerekirse ikisini de tanımlayıp ayır; bu ayrımı yapabilmek başlı başına puandır.

05Hash tablosu: Dictionary'nin O(1) sırrı

8. dersin sonunda açık kalan soru: "değere göre hızlı bulma" nasıl O(1) olur? Cevap, aramayı hesaba çevirmektir. Hash tablosu üç parçadan oluşur: bir dizi (kovalar/buckets), bir hash fonksiyonu (anahtarı sayıya çevirir) ve yerleşim kuralı:

indeks = hash(anahtar) mod kova_sayısı

"ali"  → hash: 48291 → mod 8 → kova 3   →  [3] → ("ali", 5501)
"ayse" → hash: 17756 → mod 8 → kova 4   →  [4] → ("ayse", 5502)
arama = aynı hesap + kovaya bakış → eleman sayısından BAĞIMSIZ: O(1)

İki anahtar aynı kovaya düşebilir — çarpışma (collision). Kaçınılmazdır (anahtar evreni kova sayısından büyüktür); yönetilir: en yaygın yöntem zincirlemedir (kovada küçük liste tutulur), alternatifi açık adresleme (doluysa sonraki uygun kovaya yerleş). Tablo dolunca (doluluk oranı eşiği aşınca) kova sayısı büyütülüp herkes yeniden yerleştirilir — List'in ikiye katlamasının (8. ders) akrabası. Bu yüzden dürüst maliyet cümlesi şudur: ortalama O(1); hash fonksiyonu kötüyse (herkes aynı kovaya düşerse) en kötü O(n).

C# köprüsü — Dictionary<K,V> ve HashSet<T> (Hat 01, 7. ders) tam bu yapıdır ve iki üretim kuralı doğurur: (1) Anahtar tipin GetHashCode ile Equals tutarlı olmalıdır — eşit iki nesne aynı hash'i vermelidir; kendi sınıfını anahtar yapacaksan ikisini birlikte ezersin (Hat 03'te record'lar bunu bedava verir). (2) Anahtar değişmez (immutable) olmalıdır: nesne sözlüğe girdikten sonra hash'ini etkileyen bir alanı değişirse nesne "yanlış kovada" kalır — sözlükte durduğu hâlde bulunamaz. Sinsi, ünlü ve mülakatta sorulan bir hatadır.

06Graf: ilişkilerin haritası

Graf, en genel yapıdır: düğümler (vertex) ve onları bağlayan kenarlar (edge); hiyerarşi şartı yok, herkes herkese bağlanabilir. Ağaç, grafın özel hâlidir (bağlantılı + döngüsüz). Çeşitleri: yönlü/yönsüz (Instagram takibi tek yönlü; arkadaşlık çift yönlü) ve ağırlıklı (kenarın maliyeti var: km, ms, ücret). Modellediği dünyalar: yol ağları ve navigasyon, sosyal ağlar, ağ topolojisi (6. dersin router'ları), paket bağımlılıkları (npm/NuGet'in "önce şunu kur" sıralaması), öneri sistemleri.

İki standart gösterim — sınavda karşılaştırması sorulur: komşuluk listesi (her düğümün komşu listesi; Dictionary<string, List<string>> — seyrek graflarda bellek dostu, standart tercih) ve komşuluk matrisi (n×n tablo; "u-v bağlı mı?" O(1) ama bellek O(n²) — küçük/yoğun graflara).

Gezinmenin iki temel stratejisi, geçen dersin iki yapısını göreve çağırır — bu simetri, iki dersin en güzel bağıdır:

• BFS (genişlemesine) — kuyrukla: başlangıcın komşuları, sonra onların komşuları... halka halka yayılır. Ağırlıksız grafta en kısa yolu bulur (hedefe ilk ulaşan halka, en kısa mesafedir).
• DFS (derinlemesine) — stack'le (ya da özyinelemeyle — çağrı yığını da stack'ti): bir yolu sonuna kadar iner, geri dönüp öbür dalı dener. Döngü tespiti, labirent, bağımlılık sıralaması gibi işlerin temelidir.

Her ikisinde de ziyaret edilenler kümesi (HashSet!) tutulur — yoksa döngülü grafta sonsuza dek dönersin. Ağırlıklı grafta en kısa yolun algoritması Dijkstra'dır: BFS'in kuyruğunu öncelik kuyruğuyla (heap — bu dersin 4. bölümü) değiştirir; adını ve bu akrabalığını bil, gerçeklemesi bu hattın işi değil.

07Karar rehberi: dört yapı, tek soru

İki dersin ortak final tablosu — soru hep aynıdır: en sık yaptığın işlem ne?

Mülakat kalibrasyonu: "1 milyon kullanıcıda kullanıcı adından profile erişim" → Dictionary; "skor tablosunu her an sıralı tut" → SortedDictionary (ya da periyodik sıralama — 11. ders); "iş kuyruğunda acilleri öne al" → PriorityQueue; "iki kişi arasındaki en kısa tanıdık zinciri" → graf + BFS. Bu cümleleri kurabilmek, dersin hedefidir.

08Mini alıştırma — Ağacı gez, sözlüğü yarıştır

09Kendini sına

İkili arama ağacının kuralı nedir? Dengeli BST'de arama neden O(log n)'dir ve dengesizlik bunu nasıl bozar?

Her düğümün sol alt ağacındaki tüm değerler düğümden küçük, sağdakiler büyüktür. Aramada her karşılaştırma, kalan adayların yarısını eler — dengeli ağaçta yükseklik log n olduğundan en çok log n adım atılır (1M eleman ≈ 20). Sıralı veri eklenirse düğümler tek yöne asılır, ağaç bağlı listeye yozlaşır ve yükseklik n olur → tüm işlemler O(n). Çare kendini dengeleyen ağaçlardır (AVL, kırmızı-siyah — C#'ta SortedDictionary).

Hash tablosunda çarpışma nedir, nasıl yönetilir? "Ortalama O(1), en kötü O(n)" cümlesini gerekçelendir.

İki farklı anahtarın aynı kovaya düşmesidir; anahtar evreni kova sayısından büyük olduğu için kaçınılmazdır. Yönetim: zincirleme (kovada liste) ya da açık adresleme (sonraki boş kova); doluluk eşiği aşılınca tablo büyütülüp yeniden yerleştirilir. İyi hash fonksiyonu anahtarları düzgün dağıtır → kova başına birkaç eleman → O(1). Kötü fonksiyon herkesi aynı kovaya yığar → tek uzun liste → arama O(n).

Veri yapısı olan heap ile bellek bölgesi olan heap'in farkını açıkla; veri yapısı heap nerede kullanılır?

İsim çakışması dışında ilgisizdirler. Bellek heap'i, new ile açılan nesnelerin yaşadığı, GC'nin yönettiği bölgedir. Veri yapısı heap ise "ebeveyn ≤ çocuk" (min-heap) kuralı taşıyan, dizi üzerine döşenen tam ikili ağaçtır: tepede her an en küçük/büyük durur — tepe O(1), ekleme/alma O(log n). Kullanımı öncelik kuyruğudur: triyaj, öncelikli zamanlama, Dijkstra; C#'ta PriorityQueue, ayrıca heapsort'un temeli.

BFS ile DFS hangi yardımcı yapıyla çalışır, hangisi ne zaman tercih edilir? Ziyaret kümesi neden şarttır?

BFS kuyrukla halka halka yayılır; ağırlıksız grafta en kısa yolu garanti eder (hedefe ilk ulaşan halka en yakındır) — "en az adım" sorularında seçilir. DFS stack'le ya da özyinelemeyle bir dalı sonuna kadar iner — döngü tespiti, labirent, bağımlılık sıralaması gibi "tüm yolları/yapıyı keşfet" işlerinde. Ziyaret kümesi (HashSet) olmadan döngülü grafta aynı düğümlere sonsuza dek dönülür; her düğüm bir kez işlensin diye şarttır.

10Sınav köşesi