Kitap 12
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ı.
İçindekiler
- 01Açgözlü Algoritma1Aç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.
- 02Ağaç2Ağ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.
- 03B-Tree3B-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.
- 04Bağlı Liste4Bağ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.
- 05Bloom Filter5Bloom 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.
- 06Böl ve Yönet6Bö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.
- 07Bubble SortKabarcık Sıralaması7Bubble 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.
- 08Çizge8Ç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.
- 09Dengeli Ağaç9Dengeli 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.
- 10DequeÇift Uçlu Kuyruk10Deque, 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.
- 11Derinlik Öncelikli Arama11Derinlik ö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.
- 12Dijkstra Algoritması12Dijkstra 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.
- 13Dinamik Programlama13Dinamik programlama, bir problemi çakışan alt problemlere bölüp her cevabı saklayarak hiçbirini iki kez çözmeden problemi çözme tekniğidir.
- 14Doğrusal Arama14Doğ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.
- 15Genişlik Öncelikli Arama15Geniş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.
- 16Geri İzleme16Geri 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.
- 17Hash Çakışması17Hash ç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.
- 18Hash Tablosu18Hash 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.
- 19Heap19Heap, 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.
- 20Insertion SortEklemeli Sıralama20Insertion 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.
- 21İkili Arama21İ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.
- 22İkili Arama Ağacı22İ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.
- 23Komşuluk Listesi23Komş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.
- 24Kuyruk24Kuyruk, öğ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.
- 25LRU CacheEn Az Yakın Zamanda Kullanılan Önbellek25LRU (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.
- 26Merge Sort26Merge 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.
- 27Öncelik Kuyruğu27Ö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.
- 28Quicksort28Quicksort, öğ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.
- 29Set29Set, 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.
- 30Sıralama Algoritması30Sı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.
- 31Sliding WindowKayan Pencere31Sliding 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.
- 32Topolojik Sıralama32Topolojik 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.
- 33Trie33Trie, 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.
- 34Two Pointersİki İşaretçi34Two 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.
- 35Union-FindAyrık Küme Birleşimi35Union-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.
- 36Yığın36Yığı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.