Kitap 12 · Özet sayfa

Veri Yapıları

Programların veriyi düzenlemek için kullandığı yapılar (listeler, yığınlar, ağaçlar, çizgeler) ve onları aramanın ve sıralamanın klasik yolları.

01Açgözlü Algoritma: Açgözlü algoritma, önceki kararları yeniden düşünmeden her adımda o an en iyi görünen seçimi yaparak çözümü adım adım kuran bir algoritmadır.
Açgözlü algoritma her zaman o an en iyi görünen seçimi alır ve asla geri dönmez.
Yalnızca problem açgözlü seçim özelliğine ve optimal alt yapıya sahip olduğunda optimaldir.
Örnekleri arasında Dijkstra algoritması, Huffman kodlaması ve Kruskal ile Prim'in minimum kapsayan ağaç algoritmaları bulunur.
02Ağaç: Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.
Ağacın bir kökü vardır ve diğer her düğümün tam olarak bir ebeveyni vardır.
Çocuğu olmayan düğümlere yaprak denir.
Dengeli bir ikili arama ağacı aramayı, eklemeyi ve silmeyi O(log n)'de yapar; dengesiz olan O(n)'e düşebilir.
03B-Tree: B-tree, düğümleri çok sayıda sıralı anahtar ve çocuk tutan, kendini dengeleyen arama ağacıdır; sığ kaldığından aramalar çok az disk ya da sayfa okuması ister.
B-tree düğümü çok sayıda sıralı anahtar ve çocuk işaretçisi tutar; bu yüzden ağaç geniş ve sığdır.
Tüm yapraklar aynı derinlikte olduğundan arama, ekleme ve silme O(log n) sürer.
Düğümler taştığında bölünür, fazla boşaldığında birleşir ve böylece ağaç dengeli kalır.
04Bağlı Liste: Bağlı liste, öğeleri ayrı düğümlerde saklayan bir veri yapısıdır; her düğüm bir değer ile zincirdeki sonraki düğüme bir referans tutar.
Her düğüm bir değer ve sonraki düğüme bir referans tutar.
Başa ekleme ya da baştan silme O(1) sürer.
Zinciri yürümeniz gerektiği için indeksle erişim ya da arama O(n) sürer.
05Bloom Filter: Bloom filter, çok az bellek kullanarak bir öğenin kümede kesinlikle olmadığını ya da büyük olasılıkla olduğunu söyleyen kompakt, olasılıksal bir veri yapısıdır.
Bloom filter küme üyeliği için ya kesinlikle hayır ya da büyük olasılıkla evet yanıtını verir.
Asla yanlış negatif vermez ama yanlış pozitif verebilir.
Öğeleri değil yalnızca bir bit dizisi sakladığı için çok az bellek kullanır.
06Böl ve Yönet: Böl ve yönet, bir problemi daha küçük bağımsız parçalara bölen, her birini özyinelemeyle çözen ve sonuçları birleştiren bir algoritma tasarım tekniğidir.
Böl ve yönet, bir problemi bağımsız alt problemlere böler, her birini özyinelemeyle çözer ve cevapları birleştirir.
Merge sort, quicksort, ikili arama ve hızlı Fourier dönüşümü klasik örneklerdir.
Çalışma süreleri T(n) = 2T(n/2) + O(n) gibi özyineleme bağıntılarıyla ifade edilir ve bu O(n log n) verir.
07Bubble SortKabarcık Sıralaması: Bubble sort (kabarcık sıralaması), sırası bozuk komşu öğeleri yer değiştiren basit bir sıralama algoritmasıdır; her geçiş kalan en büyük değeri sona taşır.
Bubble sort, sırası bozuk komşu öğeleri tekrar tekrar yer değiştirir.
Her geçiş kalan en büyük öğeyi sona taşır.
Ortalamada O(n²), erken çıkışla sıralı girdide O(n)'dir.
08Çizge: Çizge, kenarlarla bağlı düğümlerden (köşelerden) oluşan ve yollar, arkadaşlıklar ve bağımlılıklar gibi ilişkileri modellemekte kullanılan bir veri yapısıdır.
Çizge, kenarlarla bağlı düğümlerden (köşelerden) oluşan bir kümedir.
Kenarlar yönlü ya da yönsüz, ağırlıklı ya da ağırlıksız olabilir.
Komşuluk listesi O(V + E) bellek kullanır ve görece az kenarlı seyrek çizgeler için olağan seçimdir.
09Dengeli Ağaç: Dengeli ağaç, her değişiklikten sonra dengelenerek yüksekliğini log n civarında tutan ağaçtır; arama, ekleme ve silme en kötü durumda bile O(log n) kalır.
Dengeli ağaç yüksekliğini log n ile orantılı tutar.
Arama, ekleme ve silme, veri sıralı gelse bile O(log n) olarak garanti edilir.
AVL ağaçları ve kırmızı-siyah ağaçlar kendilerini rotasyonlarla yeniden dengeler.
10DequeÇift Uçlu Kuyruk: Deque, hem önden hem arkadan sabit sürede öğe eklemeye ve çıkarmaya izin veren çift uçlu bir kuyruktur; hem yığın hem kuyruk gibi davranabilir.
Deque hem önden hem arkadan O(1) sürede ekleme ve çıkarmayı destekler.
Yığın, kuyruk ya da ikisi birden olarak davranabilir.
Genellikle çift yönlü bağlı liste ya da dairesel tampon üzerine kurulur.
11Derinlik Öncelikli Arama: Derinlik öncelikli arama, bir yolu gidebildiği kadar izleyip sonra geri dönerek sıradaki ziyaret edilmemiş dalı keşfeden bir çizge gezinme algoritmasıdır.
DFS tek bir yolu olabildiğince derine izler, sonra geri döner.
Özyineleme ya da açık bir yığın, ayrıca döngüleri ele almak için bir ziyaret edilenler kümesi kullanır.
Komşuluk listesiyle O(V + E) sürede çalışır.
12Dijkstra Algoritması: Dijkstra algoritması, tüm kenar ağırlıkları sıfır ya da pozitifken bir başlangıç düğümünden diğer tüm düğümlere en kısa yolları bulan çizge algoritmasıdır.
Dijkstra algoritması, ağırlıklı bir çizgede tek bir kaynaktan diğer tüm düğümlere en kısa yolları bulur.
Her kenar ağırlığının sıfır ya da pozitif olmasını gerektirir.
Ziyaret edilmemiş en yakın düğümü tekrar tekrar kesinleştirir ve o düğümün kenarlarını gevşetir.
13Dinamik Programlama: Dinamik programlama, bir problemi çakışan alt problemlere bölüp her cevabı saklayarak hiçbirini iki kez çözmeden problemi çözme tekniğidir.
DP, bir problemin çakışan alt problemleri ve optimal alt yapısı olduğunda işe yarar.
Her farklı alt problem bir kez çözülür ve sonucu yeniden kullanılmak üzere saklanır.
Yukarıdan aşağı DP memoization'lı özyineleme kullanır; aşağıdan yukarı DP tabloyu en küçük durumlardan doldurur.
14Doğrusal Arama: Doğrusal arama (linear search), bir değeri listenin öğelerini baştan tek tek kontrol ederek eşleşme bulana ya da sona ulaşana kadar arar ve O(n) zaman alır.
Doğrusal arama, bir eşleşme bulana kadar öğeleri tek tek kontrol eder.
O(n) zaman alır ve sıralama ya da indeks gerektirmez.
Bağlı listelerde, akışlarda ve her arama koşulunda çalışır.
15Genişlik Öncelikli Arama: Genişlik öncelikli arama, düğümleri başlangıca uzaklık sırasıyla ziyaret eden ve derine inmeden önce tüm komşuları keşfeden bir çizge gezinme algoritmasıdır.
BFS bir çizgeyi seviye seviye keşfeder, en yakın düğümleri önce ziyaret eder.
Bir kuyruk ve hiçbir düğümün iki kez işlenmemesi için bir ziyaret edilenler kümesi kullanır.
Komşuluk listesiyle O(V + E) sürede çalışır ve O(V) ek bellek kullanır.
16Geri İzleme: Geri izleme, çözümü her seferinde bir seçimle kuran ve çıkmaza girdiğinde son seçimi geri alarak başka bir seçenek deneyen bir arama tekniğidir.
Geri izleme çözümü adım adım kurar ve çıkmaza götüren seçimleri geri alır.
Genellikle özyinelemelidir ve seç, keşfet, seçimi geri al kalıbını izler.
Geçersiz kısmi çözümleri erken budamak onu pratik kılan şeydir.
17Hash Çakışması: Hash çakışması, iki farklı girdinin aynı hash değerine ya da kovaya düşmesidir; hash tabloları bunu ele alır, kriptografik hash'lerde pratikte bulunamamalıdır.
Çakışma, farklı girdilerin bir hash değerini ya da kovayı paylaşmasıdır.
Doğum günü paradoksunun gösterdiği gibi çakışmalar kaçınılmazdır ve erken gelir.
Hash tabloları onları zincirleme ya da açık adreslemeyle ele alır ve doluluk oranına göre büyür.
18Hash Tablosu: Hash tablosu, anahtar-değer çiftlerini saklayan ve hash fonksiyonuyla herhangi bir anahtarın değerini ortalamada sabit sürede bulan bir veri yapısıdır.
Hash tablosu, bir hash fonksiyonu kullanarak anahtarları değerlere eşler.
Arama, ekleme ve silme ortalamada O(1), en kötü durumda O(n)'dir.
Çakışma iki anahtarın aynı bucket'a eşlenmesidir; chaining ve open addressing bunu çözer.
19Heap: Heap, en küçük ya da en büyük öğeyi kökünde tutan ağaç tabanlı bir veri yapısıdır; bu öğeyi O(1)'de okuyabilir ve O(log n)'de çıkarabilirsiniz.
Min-heap en küçük öğeyi, max-heap en büyük öğeyi kökte tutar.
Tepeye bakmak O(1), ekleme ve tepeyi çıkarma O(log n)'dir.
n öğeden heap oluşturmak O(n) sürer.
20Insertion SortEklemeli Sıralama: Insertion sort (eklemeli sıralama), sıralı listeyi öğe öğe kurar; her yeni öğeyi sıralanmışlar arasında yerine koyar, tıpkı eldeki kartları dizmek gibi.
Insertion sort her öğeyi sıralı bir ön kısım içinde yerine yerleştirir.
En kötü durumda O(n²), ama neredeyse sıralı veride O(n)'e yakındır.
Yerindedir, kararlıdır ve öğeleri geldikçe sıralayabilir.
21İkili Arama: İkili arama, sıralı bir listedeki bir değeri arama aralığını sürekli yarıya bölerek bulan bir algoritmadır; her öğeyi denetlemek yerine O(log n) sürer.
İkili arama, verinin sıralı olmasını gerektirir.
Doğrusal aramadaki O(n)'e karşılık O(log n) sürede çalışır.
Her karşılaştırma kalan öğelerin yarısını eler.
22İkili Arama Ağacı: İkili arama ağacı, her düğümün sol alt ağacında küçük, sağ alt ağacında büyük değerler bulunan ve hızlı sıralı aramaya olanak tanıyan bir ikili ağaçtır.
Her düğümün sol alt ağacı küçük, sağ alt ağacı büyük değerler tutar.
Arama, ekleme ve silme O(h) sürer; h ağacın yüksekliğidir.
Dengeli bir BST'nin yüksekliği yaklaşık log n'dir, dolayısıyla işlemler O(log n)'dir; dejenere olan O(n)'dir.
23Komşuluk Listesi: Komşuluk listesi, her düğümün bağlı olduğu düğümlerin listesini tuttuğu ve düğüm ile kenar sayısıyla orantılı bellek kullanan bir çizge saklama yöntemidir.
Komşuluk listesi her düğümü, kenarı olan düğümlerin listesine eşler.
O(V + E) bellek kullanır; bu da seyrek çizgelere uygundur.
Bir düğümün komşuları üzerinde gezinmek hızlıdır, ancak belirli bir kenarı kontrol etmek O(derece) sürer.
24Kuyruk: Kuyruk, öğeleri ilk giren ilk çıkar (FIFO) sırasıyla saklayan bir veri yapısıdır; en uzun süre bekleyen öğe her zaman çıkarılacak sonraki öğedir.
Kuyruk FIFO sırasını izler: ilk giren ilk çıkar.
Enqueue arkaya ekler, dequeue önden çıkarır; iyi uygulandığında her biri O(1) sürer.
Python'da list.pop(0) yerine collections.deque ile append() ve popleft() kullanın.
25LRU CacheEn Az Yakın Zamanda Kullanılan Önbellek: LRU (least recently used) cache, sabit sayıda öğe tutar ve dolunca en uzun süredir kullanılmayanı atar; son kullanılan verinin yine gerekeceğini varsayar.
LRU cache dolduğunda en uzun süredir kullanılmayan öğeyi çıkarır.
Yakın zamanda kullanılan verinin yakında yine gerekeceğini varsayar.
Bir hash map ile çift yönlü bağlı liste O(1) get ve put sağlar.
26Merge Sort: Merge sort, bir listeyi ikiye bölen, her yarıyı özyinelemeyle sıralayan ve sıralı yarıları O(n log n) sürede birleştiren böl ve yönet sıralama algoritmasıdır.
Merge sort bir listeyi ikiye böler, her yarıyı özyinelemeyle sıralar ve sonuçları birleştirir.
En iyi, ortalama ve en kötü durumda O(n log n) sürede çalışır.
Dizi sürümü O(n) ek bellek gerektirir.
27Öncelik Kuyruğu: Öncelik kuyruğu, her öğenin bir önceliği olduğu ve ne zaman eklendiğine bakılmaksızın en yüksek öncelikli öğenin her zaman önce çıkarıldığı bir koleksiyondur.
Öncelik kuyruğu her zaman en eskiyi değil, en yüksek öncelikli öğeyi önce çıkarır.
Soyut bir veri tipidir ve çoğunlukla ikili heap ile uygulanır.
Heap ile ekleme ve çıkarma O(log n), bakma O(1) sürer.
28Quicksort: Quicksort, öğeleri seçilen bir pivot etrafında bölümleyen, sonra küçük ve büyük grupları aynı şekilde sıralayan bir böl ve yönet sıralama algoritmasıdır.
Quicksort öğeleri bir pivot etrafında bölümler, sonra her tarafı özyinelemeyle sıralar.
Ortalamada O(n log n) sürer, ancak en kötü durumu O(n^2)'dir.
Rastgele ya da üçün ortancası pivot, en kötü durumu çok düşük olasılıklı yapar.
29Set: Set, her farklı değeri en fazla bir kez saklayan ve bir değerin içinde olup olmadığını çoğunlukla sabit sürede kontrol edebilen bir koleksiyondur.
Set her farklı değeri yalnızca bir kez saklar, bu yüzden yinelenenler yok sayılır.
Hash tabanlı setler ekleme, silme ve üyelik kontrolünü ortalamada O(1) sürede yapar.
Java'nın TreeSet yapısı gibi ağaç tabanlı setler değerleri işlem başına O(log n) maliyetle sıralı tutar.
30Sıralama Algoritması: Sıralama algoritması, öğeleri sayıları küçükten büyüğe ya da adları alfabetik olarak sıralamak gibi tanımlı bir düzene sokan adım adım bir yöntemdir.
Bubble, selection ve insertion sort gibi basit sıralamalar O(n^2) sürede çalışır.
Merge sort ve heap sort en kötü durumda bile O(n log n) sürer; quicksort ortalamada O(n log n) olur ama O(n^2)'ye çıkabilir.
Yalnızca karşılaştırmayla sıralama, en kötü durumda O(n log n)'i aşamaz.
31Sliding WindowKayan Pencere: Sliding window tekniği, dizi ya da string'in ardışık parçalarıyla ilgili problemleri alt dizileri baştan hesaplamadan, pencereyi kaydırıp güncelleyerek çözer.
Kayan pencere, ardışık bir aralığı izler ve adım adım günceller.
Her öğe bir kez girip bir kez çıkar; bu yüzden taramalar O(n)'dir.
Sabit pencereler k boyutunu korur; değişken pencereler bir koşula göre büyüyüp küçülür.
32Topolojik Sıralama: Topolojik sıralama, döngüsüz yönlü bir çizgenin düğümlerini, A'dan B'ye her kenar için listede A'nın B'den önce geleceği biçimde sıralayan algoritmadır.
Topolojik sıralama, yönlü bir çizgenin düğümlerini her kenar listede ileri işaret edecek biçimde sıralar.
Yalnızca döngüsüz yönlü çizgeler (DAG) için vardır.
Kahn algoritması ve DFS tabanlı yöntem O(V + E) sürede çalışır.
33Trie: Trie, string'leri karakter karakter saklayan ağaç biçimli bir veri yapısıdır; aynı öneki paylaşan tüm kelimeler kökten itibaren aynı yolu paylaşır.
Trie, string'leri her seviyede bir karakter olacak şekilde saklar ve ortak öneke sahip kelimeler düğümleri paylaşır.
Ekleme ve arama, kaç kelime saklandığından bağımsız olarak O(m) sürer; m kelimenin uzunluğudur.
Bir önekle başlayan tüm kelimeleri bulmak, önekə ulaşmak için O(m) artı toplanan eşleşmelerle orantılı zaman alır.
34Two Pointersİki İşaretçi: Two pointers tekniği, bir dizi ya da listeyi basit kurallarla ilerleyen iki indeksle tarar; iç içe döngü ister gibi görünen birçok problemi tek geçişte çözer.
Two pointers, bir diziyi tek geçişte iki indeksle tarar.
Zıt uçlardaki işaretçiler, sıralı dizilerdeki çift problemlerini O(n)'de çözer.
Hızlı ve yavaş işaretçiler bağlı listelerde döngüleri ve ortayı bulur.
35Union-FindAyrık Küme Birleşimi: Union-find (ayrık küme birleşimi), öğe gruplarını izleyip birleştiren ve iki öğenin bağlı olup olmadığını neredeyse anında söyleyen veri yapısıdır.
Union-find, hangi öğelerin aynı gruba ait olduğunu izler.
find bir grubun kökünü döndürür; union iki grubu birleştirir.
Yol sıkıştırma ve ranka göre birleştirme işlemleri neredeyse O(1) yapar.
36Yığın: Yığın, öğeleri son giren ilk çıkar (LIFO) sırasıyla saklayan bir veri yapısıdır; en son eklenen öğe her zaman ilk çıkarılan öğedir.
Yığın LIFO sırasını izler: son giren ilk çıkar.
Temel işlemler push, pop ve peek'tir ve her biri O(1) sürer.
Python'da list ile append() ve pop() yığın olarak çalışır; JavaScript'te push() ve pop() içeren bir dizi de öyle.

Kitaba dönİpucu: Bir kopyasını saklamak için yazdırma penceresinde “PDF olarak kaydet”i seçin.