..................................................................................................................85
3.1. Podstawowa terminologia .......................................................................................................................... 85
3.2. Drzewa jako abstrakcyjne obiekty danych................................................................................................. 92
4
SPIS TREŚCI
3.3. Implementacje drzew ................................................................................................................................. 95
3.4. Drzewa binarne ........................................................................................................................................ 102
Ćwiczenia ........................................................................................................................................................ 113
Uwagi bibliograficzne ..................................................................................................................................... 116
4
Podstawowe operacje na zbiorach .......................................................................117
4.1. Wprowadzenie do zbiorów....................................................................................................................... 117
4.2. Słowniki ................................................................................................................................................... 129
4.3. Tablice haszowane ................................................................................................................................... 132
4.4. Implementacja abstrakcyjnego typu danych MAPPING ......................................................................... 146
4.5. Kolejki priorytetowe ................................................................................................................................ 148
4.6. Przykłady złożonych struktur zbiorowych............................................................................................... 156
Ćwiczenia ........................................................................................................................................................ 163
Uwagi bibliograficzne ..................................................................................................................................... 165
5
Zaawansowane metody reprezentowania zbiorów ..............................................167
5.1. Binarne drzewa wyszukiwawcze ............................................................................................................. 167
5.2. Analiza złożoności operacji wykonywanych na binarnym drzewie wyszukiwawczym.......................... 171
5.3. Drzewa trie ............................................................................................................................................... 175
5.4. Implementacja zbiorów w postaci drzew wyważonych — 2-3-drzewa................................................... 181
5.5. Operacje MERGE i FIND ........................................................................................................................ 193
5.6. Abstrakcyjny typ danych z operacjami MERGE i SPLIT ....................................................................... 202
Ćwiczenia ........................................................................................................................................................ 207
Uwagi bibliograficzne ..................................................................................................................................... 209
6
Grafy skierowane .................................................................................................211
6.1. Podstawowe pojęcia ................................................................................................................................. 211
6.2. Reprezentacje grafów skierowanych........................................................................................................ 213
6.3. Graf skierowany jako abstrakcyjny typ danych ....................................................................................... 215
6.4. Znajdowanie najkrótszych ścieżek o wspólnym początku....................................................................... 217
6.5. Znajdowanie najkrótszych ścieżek między każdą parą wierzchołków .................................................... 221
6.6. Przechodzenie przez grafy skierowane — przeszukiwanie zstępujące.................................................... 229
6.7. Silna spójność i silnie spójne składowe digrafu....................................................................................... 237
Ćwiczenia ........................................................................................................................................................ 240
Uwagi bibliograficzne ..................................................................................................................................... 242
7
Grafy nieskierowane ............................................................................................243
7.1. Definicje ................................................................................................................................................... 243
7.2. Metody reprezentowania grafów.............................................................................................................. 245