Data Structures
Undergraduate, Giresun University, Computer Engineering, 2026
Data structures provide systematic ways to organize, store, and access data. Choosing an appropriate structure directly affects the efficiency of operations such as searching, insertion, deletion, and traversal. This course examines algorithm analysis, arrays, recursion, linked lists, lists, stacks, queues, trees, search trees, priority queues and heaps, hash tables, sets and disjoint sets, and graphs, with an emphasis on their implementations, complexity, and practical applications.
Ders Kitabı
Başlangıç Kaynakları
- Veri Yapılarında Önemli İsimler (HTML)
- Veri Yapıları İçin Ön Bilgiler (HTML)
- Dersin Haritası (HTML)
- Terim Sözlüğü (HTML)
Kısım I: Temeller
Bölüm 1: Giriş
Veri yapıları, verinin bellekte nasıl düzenleneceğini ve ona nasıl erişileceğini belirler. Bu bölümde verinin sayısal ortamda nasıl temsil edildiği, Java’daki ilkel ve referans tipler, referans kopyalama ve jenerikler ele alınır. Soyut veri tipi (hangi işlemlerin sunulduğu) ile veri yapısı (bu işlemlerin nasıl gerçeklendiği) arasındaki ayrım bir yığın örneğiyle gösterilir. Bölüm, veri yapısı seçimi ve dersteki temel yapıların kısa bir karşılaştırma tablosuyla kapanır.
- 🖼️Sunum-Giriş (HTML)
- 📄Sunum-Giriş (PDF)
- 📖Ders Notu - Giriş (HTML)
- 📝Çalışma Soruları - Giriş (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 2: Algoritma Analizi
Algoritma analizi, çözümleri uygulamadan önce karşılaştırmayı sağlar. Deneysel ölçüm ve katlama deneyi çalışma süresinin pratikte nasıl büyüdüğünü gösterir; ilkel işlemleri saymak ise makineden bağımsız bir ölçü verir. Büyük O, Büyük Omega ve Büyük Teta üst, alt ve sıkı sınırları anlatır; en iyi, ortalama ve en kötü durum ayrı ayrı incelenir. Döngü kalıpları, doğrusal ve ikili arama ile önek ortalamaları kodun yapısının karmaşıklığı nasıl belirlediğini gösterir. Alan karmaşıklığı, doğruluk ve sağlamlık da bu bölümdedir.
- 🖼️Sunum-Algoritma Analizi (HTML)
- 📄Sunum-Algoritma Analizi (PDF)
- 📖Ders Notu - Algoritma Analizi (HTML)
- 📝Çalışma Soruları - Algoritma Analizi (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 3: Diziler
Dizi, öğeleri bellekte ardışık yerleşen en temel veri yapısıdır; her öğeye indisiyle sabit sürede erişilir. Java’da dizi tanımlama, kopyalama, java.util.Arrays ve çok boyutlu diziler; ortalama, ortanca, mod ve tersine çevirme gibi temel dizi algoritmaları; matris işlemleri ve küçük bir XOX oyunu bu bölümde yer alır. Erişimin O(1), araya ekleme ve silmenin ise öğe kaydırma yüzünden O(n) olduğu gösterilir; seçimli ve eklemeli sıralama da dizi üzerinde incelenir.
- 🖼️Sunum-Diziler (HTML)
- 📄Sunum-Diziler (PDF)
- 📖Ders Notu - Diziler (HTML)
- 📝Çalışma Soruları - Diziler (HTML)
- 🕹️Dizi Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 4: Özyineleme
Özyineleme, bir problemi taban durumuna ulaşana kadar aynı problemin daha küçük örneklerine indirger. Her özyinelemeli çağrı çağrı yığınında kendi çerçevesini alır; bir özyinelemeli metodu izlemek bu çerçevelerin eklenip çıkarılmasını izlemektir. Doğrusal özyineleme (toplam, tersine çevirme, hızlı üs alma), ikili özyineleme (Fibonacci, ikili arama), Hanoi Kuleleri ve geri izleme örnekleri (alt kümeler, permütasyonlar) adım adım incelenir. Yineleme bağıntıları özyinelemeli algoritmaların zaman ve alan maliyetini verir; kuyruk özyinelemesi ve döngüye çevirme ile bölüm tamamlanır.
- 🖼️Sunum-Özyineleme (HTML)
- 📄Sunum-Özyineleme (PDF)
- 📖Ders Notu - Özyineleme (HTML)
- 📝Çalışma Soruları - Özyineleme (HTML)
- 🕹️Hanoi Kuleleri Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Kısım II: Doğrusal Yapılar
Bölüm 5: Bağlı Listeler
Bağlı liste, her biri veri ve bir sonraki düğüme referans taşıyan düğümlerden oluşur. Ardışık bellek gerektirmediği için başa ekleme ve silme sabit sürede yapılır; buna karşılık rastgele erişim yoktur ve bir öğeye ulaşmak için baştan gezinmek gerekir. Tek yönlü listede gezinme, ekleme, silme, tersine çevirme, tekrarları kaldırma ve sıralı listeleri birleştirme; çift yönlü listede bekçi düğümler; dairesel listede döngü tespiti ve döndürme bu bölümün konularıdır.
- 🖼️Sunum-Bağlı Listeler (HTML)
- 📄Sunum-Bağlı Listeler (PDF)
- 📖Ders Notu - Bağlı Listeler (HTML)
- 📝Çalışma Soruları - Bağlı Listeler (HTML)
- 🕹️Bağlı Liste Simülatörü (HTML)
- 🕹️Çift Yönlü Bağlı Liste Simülatörü (HTML)
- 🕹️Dairesel Bağlı Liste Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 6: Liste ADT ve Java Koleksiyonları
Liste, öğelerin sıralı bir dizisini temsil eden soyut veri tipidir; büyüyüp küçülebilir ve ekleme, silme, erişim ve gezinme işlemlerini destekler. Java’nın koleksiyon hiyerarşisi (Iterable, Collection, List), Iterator ve ListIterator ile gezinme ve gezinirken güvenli silme bu bölümde ele alınır. ArrayList’in dinamik dizi olarak büyümesi ve amortize analizi, LinkedList ile karşılaştırması, konumsal liste ADT’si, Vector, CopyOnWriteArrayList ve Arrays.asList de incelenir.
- 🖼️Sunum-Liste ADT ve Java Koleksiyonları (HTML)
- 📄Sunum-Liste ADT ve Java Koleksiyonları (PDF)
- 📖Ders Notu - Liste ADT ve Java Koleksiyonları (HTML)
- 📝Çalışma Soruları - Liste ADT ve Java Koleksiyonları (HTML)
- 🕹️Liste ADT Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 7: Yığınlar
Yığın, son giren ilk çıkar (LIFO) ilkesiyle çalışır: ekleme (push) ve çıkarma (pop) yalnızca üstten yapılır. Yığın ADT’si, dizi ve bağlı liste ile gerçeklenmesi ve işlemlerin maliyeti ele alınır. Geri/ileri gezinme, çağrı yığını, parantez kontrolü, sonraki büyük öğe, en küçük öğeyi tutan yığın, Hanoi Kulelerinin yığınla çözümü ve stock span problemi yığının uygulamalarıdır. Ara ek (infix), önek (prefix) ve sonek (postfix) gösterimleri arasında dönüşüm ve sonek ifadelerin değerlendirilmesi bölümü tamamlar.
- 🖼️Sunum-Yığınlar (HTML)
- 📄Sunum-Yığınlar (PDF)
- 📖Ders Notu - Yığınlar (HTML)
- 📝Çalışma Soruları - Yığınlar (HTML)
- 🕹️Yığın Simülatörü (HTML)
- 🕹️Stock Span Simülatörü (HTML)
- 🕹️Infix → Prefix Simülatörü (HTML)
- 🕹️Infix → Postfix Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 8: Kuyruklar ve Deque
Kuyruk, ilk giren ilk çıkar (FIFO) ilkesiyle çalışır: öğeler bir uçtan eklenir (enqueue), öbür uçtan çıkarılır (dequeue). Basit dizi kuyruğunun sorunu, dairesel kuyruk ve indis formülleri, dolu/boş ayrımı, kuyruğun büyütülmesi ve bağlı liste ile gerçekleme bu bölümdedir. İki uçtan da ekleme ve çıkarmaya izin veren deque, kayan pencere maksimumu gibi problemlerde kullanılır. Round robin çizelgeleme, Josephus problemi, ikilik sayıların üretilmesi ve iki yığınla kuyruk uygulama örnekleridir.
- 🖼️Sunum-Kuyruklar ve Deque (HTML)
- 📄Sunum-Kuyruklar ve Deque (PDF)
- 📖Ders Notu - Kuyruklar ve Deque (HTML)
- 📝Çalışma Soruları - Kuyruklar ve Deque (HTML)
- 🕹️Kuyruk Simülatörü (HTML)
- 🕹️Deque Simülatörü (HTML)
- 🕹️Dairesel Kuyruk Simülatörü (HTML)
- 🕹️Round Robin Çizelgeleyici Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Kısım III: Ağaçlar
Bölüm 9: Ağaçlar
Ağaç, düğümlerin kenarlarla bağlandığı hiyerarşik bir yapıdır: bir kökten başlar, her düğümün tek ebeveyni ve birden çok çocuğu olabilir. Dosya sistemleri, kurum şemaları ve HTML belgeleri ağaçla temsil edilir. Derece, derinlik ve yükseklik gibi temel kavramlar, ikili ağaç türleri (dolu, tam, mükemmel) ve özellikleri, dizi ve bağlı gösterimler incelenir. Kök önde, kök ortada, kök sonda ve düzey sırası gezinmeleri hem özyinelemeli hem yığın ve kuyrukla gerçeklenir; ifade ağaçları ve özyinelemeli ağaç fonksiyonları (boyut, yükseklik, yaprak sayısı) uygulamalardır.
- 🖼️Sunum-Ağaçlar (HTML)
- 📄Sunum-Ağaçlar (PDF)
- 📖Ders Notu - Ağaçlar (HTML)
- 📝Çalışma Soruları - Ağaçlar (HTML)
- 🕹️Genel Ağaç Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 10: Arama Ağaçları
İkili arama ağacında (BST) her düğümün sol alt ağacındaki anahtarlar düğümünkinden küçük, sağ alt ağacındakiler büyüktür. Arama, ekleme ve silme O(h) sürer; h ağacın yüksekliğidir. Dengeli ağaçta bu O(log n) olur, en kötü durumda O(n)’ye düşer. BST’de arama, ekleme, ardıl ve öncül, üç durumlu silme ve aralık sorguları incelendikten sonra yüksekliği sınırlı tutan AVL, kırmızı-siyah ve splay ağaçları ele alınır. Diskteki veriler için B-ağacı ve B+ ağacı gibi çok yollu arama ağaçları düğüm başına çok sayıda anahtar tutarak ağacı sığ tutar.
- 🖼️Sunum-Arama Ağaçları (HTML)
- 📄Sunum-Arama Ağaçları (PDF)
- 📖Ders Notu - Arama Ağaçları (HTML)
- 📝Çalışma Soruları - Arama Ağaçları (HTML)
- 🕹️İkili Arama Ağacı Simülatörü (HTML)
- 🕹️İkili Arama Ağacı Gezinme Simülatörü (HTML)
- 🕹️Kırmızı-Siyah Ağaç Simülatörü (HTML)
- 🕹️AVL Ağacı Simülatörü (HTML)
- 🕹️Splay Ağacı Simülatörü (HTML)
- 🕹️B-Ağacı Simülatörü (HTML)
- 🕹️B+ Ağacı Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 11: Öncelikli Kuyruklar ve Heap
Öncelikli kuyruk, her seferinde en yüksek (ya da en düşük) öncelikli öğeyi çıkaran soyut veri tipidir. Sırasız ve sıralı listeyle gerçeklemenin maliyetleri karşılaştırıldıktan sonra ikili heap incelenir: max-heap’te her ebeveyn çocuklarından büyük ya da onlara eşittir. Dizi gösterimi, yukarı ve aşağı süzmeyle (up-heap, down-heap) ekleme ve silme, uyarlanabilir öncelikli kuyruk, O(n) sürede heap oluşturma ve heap sort bu bölümdedir. Java’nın PriorityQueue sınıfı, k’ıncı en büyük öğe ve öncelikli çizelgeleyici uygulama örnekleridir.
- 🖼️Sunum-Öncelikli Kuyruklar ve Heap (HTML)
- 📄Sunum-Öncelikli Kuyruklar ve Heap (PDF)
- 📖Ders Notu - Öncelikli Kuyruklar ve Heap (HTML)
- 📝Çalışma Soruları - Öncelikli Kuyruklar ve Heap (HTML)
- 🕹️İkili Heap Simülatörü (HTML)
- 🕹️Öncelikli Kuyruk Simülatörü (HTML)
- 🕹️Öncelikli Çizelgeleyici Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Kısım IV: Eşlemeler, Kümeler ve Çizgeler
Bölüm 12: Eşlemeler ve Hash Tabloları
Eşleme (map), anahtarları değerlere bağlayan soyut veri tipidir. Hash tablosu, bir hash fonksiyonuyla anahtardan bir kova indisi hesaplar ve iyi dağılan anahtarlarla ekleme, silme ve aramayı ortalamada O(1) sürede yapar; en kötü durumda bu O(n)’ye çıkabilir. İyi bir hash fonksiyonunun özellikleri, Java’daki equals/hashCode sözleşmesi, çakışmaları çözmek için ayrı zincirleme ve açık adresleme (doğrusal yoklama, karesel yoklama, çift hash), yük faktörü ve yeniden boyutlandırma bu bölümün konularıdır. Java HashMap’in iç yapısı ve iki toplam gibi uygulamalarla bölüm tamamlanır.
- 🖼️Sunum-Eşlemeler ve Hash Tabloları (HTML)
- 📄Sunum-Eşlemeler ve Hash Tabloları (PDF)
- 📖Ders Notu - Eşlemeler ve Hash Tabloları (HTML)
- 📝Çalışma Soruları - Eşlemeler ve Hash Tabloları (HTML)
- 🕹️Hash Tablosu Simülatörü (HTML)
- 🕹️Eşleme Simülatörü (HTML)
- 🕹️Açık Adresleme Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 13: Kümeler ve Ayrık Kümeler
Küme, birbirinden farklı öğelerin sırasız topluluğudur; tekrar eden öğe içermez. Birleşim, kesişim ve fark işlemleri, Java’nın Set arayüzü ve hash tabanlı, ağaç tabanlı ve bit vektörü ile gerçeklemeler karşılaştırılır; çoklu küme ve çoklu eşleme de ele alınır. Ayrık kümeler (union-find) yapısı, boyuta ya da rütbeye göre birleştirme ve yol kısaltmayla bağlantı sorgularını neredeyse sabit amortize sürede yanıtlar; bağlantılı bileşen sayma bunun bir uygulamasıdır.
- 🖼️Sunum-Kümeler ve Ayrık Kümeler (HTML)
- 📄Sunum-Kümeler ve Ayrık Kümeler (PDF)
- 📖Ders Notu - Kümeler ve Ayrık Kümeler (HTML)
- 📝Çalışma Soruları - Kümeler ve Ayrık Kümeler (HTML)
- 🕹️Küme ADT Simülatörü (HTML)
- 🕹️Ayrık Kümeler Simülatörü (HTML)
- 💻Kod Örnekleri (GitHub)
Bölüm 14: Çizgeler
Çizge, nesneler arasındaki ilişkileri düğümler ve kenarlarla temsil eder. Ağaçlardan farklı olarak döngü ve iki düğüm arasında birden çok yol içerebilir; yönlü ya da yönsüz, ağırlıklı ya da ağırlıksız olabilir. Sosyal ağlar, yol haritaları ve bilgisayar ağları çizgeyle modellenir. Komşuluk matrisi ve komşuluk listesi gösterimleri, genişlik öncelikli (BFS) ve derinlik öncelikli (DFS) arama, bağlantılı bileşenler, iki parçalı çizgeler, topolojik sıralama ve yönlü döngü tespiti incelenir. Ağırlıksız en kısa yol ve Dijkstra algoritmasından sonra minimum kapsayan ağaç problemi ayrık kümelerle Kruskal, öncelikli kuyrukla Prim algoritması üzerinden çözülür.
Textbook
📕 Data Structures — the course book (PDF, 17 MB)
Getting Started
- Important People in Data Structures (HTML)
- Prerequisites for Data Structures (HTML)
- Course Map (HTML)
- Dictionary of Terms (HTML)
Part I: Foundations
Chapter 1: Introduction
A data structure decides how data sits in memory and how we get at it. This chapter starts with how text, numbers, images and sound become bits, then turns to Java: primitive and reference types, what copying a reference really copies, and how generics let one class hold any type. A stack example draws the line between an abstract data type, which says what the operations are, and a data structure, which says how they are carried out. The chapter ends with how to choose a structure and a side-by-side look at the ones covered in the course.
- 🖼️Slides – Introduction (HTML)
- 📄Slides – Introduction (PDF)
- 📖Lecture Notes – Introduction (HTML)
- 📝Study Questions – Introduction (HTML)
- 💻Code Examples (GitHub)
Chapter 2: Algorithm Analysis
Algorithm analysis lets us compare solutions before we write them. Timing experiments and the doubling test show how running time grows in practice, while counting primitive operations gives a measure that doesn’t depend on the machine. Big O, Big Omega and Big Theta express upper, lower and tight bounds, and we look at best, average and worst cases separately. Loop patterns, linear and binary search, and prefix averages show how the shape of the code sets its cost. The chapter also covers space complexity, correctness and robustness.
- 🖼️Slides – Algorithm Analysis (HTML)
- 📄Slides – Algorithm Analysis (PDF)
- 📖Lecture Notes – Algorithm Analysis (HTML)
- 📝Study Questions – Algorithm Analysis (HTML)
- 💻Code Examples (GitHub)
Chapter 3: Arrays
The array is the simplest data structure: its elements sit side by side in memory, and any of them can be reached by index in constant time. We declare and copy arrays in Java, use java.util.Arrays and multidimensional arrays, and write the everyday array algorithms — mean, median, mode, reversal — along with matrix operations and a small tic-tac-toe game. Access is O(1), but inserting or deleting in the middle is O(n) because the other elements have to shift; selection sort and insertion sort round out the chapter.
- 🖼️Slides – Arrays (HTML)
- 📄Slides – Arrays (PDF)
- 📖Lecture Notes – Arrays (HTML)
- 📝Study Questions – Arrays (HTML)
- 🕹️Array Simulator (HTML)
- 💻Code Examples (GitHub)
Chapter 4: Recursion
Recursion solves a problem by reducing it to smaller copies of itself until it reaches a base case. Each call gets its own frame on the call stack, so tracing a recursive method means watching frames being pushed and popped. We work step by step through linear recursion (summing, reversing, fast exponentiation), binary recursion (Fibonacci, binary search), the Towers of Hanoi and backtracking (subsets, permutations). Recurrence relations give the time and space a recursive algorithm needs, and the chapter closes with tail recursion and turning recursion into a loop.
- 🖼️Slides – Recursion (HTML)
- 📄Slides – Recursion (PDF)
- 📖Lecture Notes – Recursion (HTML)
- 📝Study Questions – Recursion (HTML)
- 🕹️Tower of Hanoi Simulator (HTML)
- 💻Code Examples (GitHub)
Part II: Linear Structures
Chapter 5: Linked Lists
A linked list is a chain of nodes, each holding a value and a reference to the next node. Because it needs no contiguous block of memory, inserting or removing at the front takes constant time; the price is that there is no random access, so reaching an element means walking from the head. For singly linked lists we cover traversal, insertion, deletion, reversal, removing duplicates and merging sorted lists; for doubly linked lists, sentinel nodes; and for circular lists, cycle detection and rotation.
- 🖼️Slides – Linked Lists (HTML)
- 📄Slides – Linked Lists (PDF)
- 📖Lecture Notes – Linked Lists (HTML)
- 📝Study Questions – Linked Lists (HTML)
- 🕹️Linked List Simulator (HTML)
- 🕹️Doubly Linked List Simulator (HTML)
- 🕹️Circular Linked List Simulator (HTML)
- 💻Code Examples (GitHub)
Chapter 6: The List ADT and Java Collections
The list is the abstract data type for an ordered sequence that can grow and shrink, with operations to add, remove, get and traverse elements. This chapter walks through Java’s collection hierarchy (Iterable, Collection, List), iterating with Iterator and ListIterator, and removing elements safely while iterating. We look at how ArrayList grows as a dynamic array and why its appends are cheap on average, compare it with LinkedList, and cover the positional list ADT, Vector, CopyOnWriteArrayList and Arrays.asList.
- 🖼️Slides – The List ADT and Java Collections (HTML)
- 📄Slides – The List ADT and Java Collections (PDF)
- 📖Lecture Notes – The List ADT and Java Collections (HTML)
- 📝Study Questions – The List ADT and Java Collections (HTML)
- 🕹️List ADT Simulator (HTML)
- 💻Code Examples (GitHub)
Chapter 7: Stacks
A stack is last in, first out (LIFO): items are added (push) and removed (pop) only at the top. We define the stack ADT, implement it with an array and with a linked list, and analyze the cost of each operation. The applications are many: back and forward navigation, the call stack, bracket matching, the next greater element, a stack that tracks its minimum, the Towers of Hanoi with an explicit stack, and the stock span problem. The chapter ends with converting between infix, prefix and postfix notation and evaluating postfix expressions.
- 🖼️Slides – Stacks (HTML)
- 📄Slides – Stacks (PDF)
- 📖Lecture Notes – Stacks (HTML)
- 📝Study Questions – Stacks (HTML)
- 🕹️Stack Simulator (HTML)
- 🕹️Stock Span Simulator (HTML)
- 🕹️Infix → Prefix Simulator (HTML)
- 🕹️Infix → Postfix Simulator (HTML)
- 💻Code Examples (GitHub)
Chapter 8: Queues and Deques
A queue is first in, first out (FIFO): items join at one end (enqueue) and leave from the other (dequeue). We see why a simple array queue runs into trouble, then build a circular queue with its index formulas, tell a full queue from an empty one, grow it when needed, and implement it with a linked list. The deque, which allows adding and removing at both ends, solves problems such as the sliding-window maximum. Round-robin scheduling, the Josephus problem, generating binary numbers and a queue built from two stacks are worked examples.
- 🖼️Slides – Queues and Deques (HTML)
- 📄Slides – Queues and Deques (PDF)
- 📖Lecture Notes – Queues and Deques (HTML)
- 📝Study Questions – Queues and Deques (HTML)
- 🕹️Queue Simulator (HTML)
- 🕹️Deque Simulator (HTML)
- 🕹️Circular Queue Simulator (HTML)
- 🕹️Round-Robin Scheduler Simulator (HTML)
- 💻Code Examples (GitHub)
Part III: Trees
Chapter 9: Trees
A tree is a hierarchy of nodes joined by edges: it starts at a root, and every other node has exactly one parent and any number of children. File systems, organization charts and HTML documents are all trees. We cover the basic vocabulary (degree, depth, height), the kinds of binary trees (full, complete, perfect) and their properties, and how to store a tree in an array or with linked nodes. Preorder, inorder, postorder and level-order traversals are written both recursively and with an explicit stack or queue; expression trees and recursive tree functions such as size, height and leaf count put them to use.
- 🖼️Slides – Trees (HTML)
- 📄Slides – Trees (PDF)
- 📖Lecture Notes – Trees (HTML)
- 📝Study Questions – Trees (HTML)
- 🕹️General Tree Simulator (HTML)
- 💻Code Examples (GitHub)
Chapter 10: Search Trees
In a binary search tree (BST), every key in a node’s left subtree is smaller than the node’s key and every key in its right subtree is larger. Search, insertion and deletion take O(h), where h is the height of the tree — O(log n) when the tree is balanced, but O(n) in the worst case. After search, insertion, successor and predecessor, three-case deletion and range queries on a plain BST, we study the AVL, red-black and splay trees, which keep the height in check. For data on disk, multiway trees such as the B-tree and B+ tree pack many keys into each node so the tree stays shallow.
- 🖼️Slides – Search Trees (HTML)
- 📄Slides – Search Trees (PDF)
- 📖Lecture Notes – Search Trees (HTML)
- 📝Study Questions – Search Trees (HTML)
- 🕹️Binary Search Tree Simulator (HTML)
- 🕹️Binary Search Tree Traversal Simulator (HTML)
- 🕹️Red-Black Tree Simulator (HTML)
- 🕹️AVL Tree Simulator (HTML)
- 🕹️Splay Tree Simulator (HTML)
- 🕹️B-Tree Simulator (HTML)
- 🕹️B+ Tree Simulator (HTML)
- 💻Code Examples (GitHub)
Chapter 11: Priority Queues and Heaps
A priority queue always removes the element with the highest (or lowest) priority. After comparing what unsorted and sorted lists cost, we turn to the binary heap: in a max-heap every parent is at least as large as its children. We store the heap in an array, insert and remove with up-heap and down-heap, update priorities in an adaptable priority queue, build a heap in O(n) time and use it for heap sort. Java’s PriorityQueue class, finding the k-th largest element and a priority scheduler are worked examples.
- 🖼️Slides – Priority Queues and Heaps (HTML)
- 📄Slides – Priority Queues and Heaps (PDF)
- 📖Lecture Notes – Priority Queues and Heaps (HTML)
- 📝Study Questions – Priority Queues and Heaps (HTML)
- 🕹️Binary Heap Simulator (HTML)
- 🕹️Priority Queue Simulator (HTML)
- 🕹️Priority Scheduler Simulator (HTML)
- 💻Code Examples (GitHub)
Part IV: Maps, Sets and Graphs
Chapter 12: Maps and Hash Tables
A map associates keys with values. A hash table turns a key into a bucket index with a hash function, and with well-spread keys it inserts, deletes and looks up in O(1) time on average, though the worst case can reach O(n). We discuss what makes a good hash function, Java’s equals/hashCode contract, and the two ways to resolve collisions — separate chaining and open addressing (linear probing, quadratic probing, double hashing) — along with the load factor and resizing. The chapter ends with a look inside Java’s HashMap and applications such as two-sum.
- 🖼️Slides – Maps and Hash Tables (HTML)
- 📄Slides – Maps and Hash Tables (PDF)
- 📖Lecture Notes – Maps and Hash Tables (HTML)
- 📝Study Questions – Maps and Hash Tables (HTML)
- 🕹️Hash Table Simulator (HTML)
- 🕹️Map Simulator (HTML)
- 🕹️Open Addressing Simulator (HTML)
- 💻Code Examples (GitHub)
Chapter 13: Sets and Disjoint Sets
A set is an unordered collection of distinct elements. We implement union, intersection and difference, use Java’s Set interface, and compare hash-based, tree-based and bit-vector implementations, then extend the idea to multisets and multimaps. The disjoint-set (union-find) structure, with union by size or rank and path compression, answers “are these two connected?” in nearly constant amortized time; counting connected components is one application.
- 🖼️Slides – Sets and Disjoint Sets (HTML)
- 📄Slides – Sets and Disjoint Sets (PDF)
- 📖Lecture Notes – Sets and Disjoint Sets (HTML)
- 📝Study Questions – Sets and Disjoint Sets (HTML)
- 🕹️Set ADT Simulator (HTML)
- 🕹️Disjoint Sets Simulator (HTML)
- 💻Code Examples (GitHub)
Chapter 14: Graphs
A graph models relationships between objects with vertices and edges. Unlike a tree, it can have cycles and several paths between two vertices, and its edges may be directed or undirected, weighted or unweighted. Social networks, road maps and computer networks are all graphs. We cover adjacency-matrix and adjacency-list representations, breadth-first (BFS) and depth-first (DFS) search, connected components, bipartite graphs, topological sorting and directed cycle detection. After unweighted shortest paths and Dijkstra’s algorithm, we solve the minimum spanning tree problem with Kruskal’s algorithm, using disjoint sets, and Prim’s algorithm, using a priority queue.