Datenstrukturen und effiziente Algorithmen: Band 1: Sortieren und Suchen

I. Grundlagen.- I.1. Maschinenmodelle: RAM und RASP.- I.2. Berechnungen mit Zufallszahlen.- I.3. Eine höhere Programmiersprache.- I.4. Strukturierte Datentypen.- I.4.1. Schlangen und Keller.- I.4.2. Listen.- I.4.3. Bäume.- I.5. Rekursion.- I.6. Asymptotische Aussagen.- I.7. Hintergrundspeicher.- I.8. Übungen.- I.9. Bibliographische Anmerkungen.- II. Sortieren.- II.1. Allgemeine Sortierverfahren.- II.1.1. Sortieren durch Auswahl, ein erster Versuch.- II.1.2. Sortieren durch Auswahl: Heapsort.- II.1.3. Sortieren durch Teilen: Quicksort.- II.1.4. Sortieren durch Mischen.- II.1.5. Vergleich mehrerer Algorithmen.- II.1.6. Untere Schranken.- II.2. Sortieren durch Verteilen.- II.2.1. Sortieren von Wörtern durch Verteilen.- II.2.2. Sortieren reeller Zahlen durch Verteilen.- II.3. Nochmals: Untere Schranken für Sortieren.- II.4. Der lineare Median-Algorithmus.- II.5. Übungen.- II.6. Bibliographische Anmerkungen.- III. Mengen.- III.1. Digitale Suchbäume.- III.1.1. TRIES.- III.1.2. Statische TRIES oder Komprimierung dünnbesetzter Tafeln.- III.2. Hashing.- III.2.1. Hashing mit Verkettung.- III.2.2. Hashing mit offener Adressierung.- III.2.3. Perfektes Hashing.- III.2.4. Universelles Hashing.- III.2.5. Erweiterbares Hashing.- III.3. Suchen in geordneten Mengen.- III.3.1. Binäre Suche und Suchbäume.- III.3.2. Interpolationssuche.- III.4. Gewichtete Bäume.- III.4.1. Optimale gewichtete Bäume, dynamisches Programmieren und Mustererkennung.- III.4.2. Nahezu optimale binäre Suchbäume.- III.5. Balancierte Bäume.- III.5.1. Gewichtsbalancierte Bäume.- III.5.2. Höhenbalancierte Bäume.- III.5.3. Weitere Betrachtungen zu (a,b)-Bäumen.- III.5.3.1. Mischbare Warteschlangen.- III.5.3.2. Amortisierung von Rebalancierungskosten und Sortieren vorsortierter Files.- III.5.3.3. Fingerbäume.- III.5.3.4. Randanalyse.- III.6. Dynamische gewichtete Bäume.- III.6.1. Selbstorganisierende Datenstrukturen - Analyse im amortisierten und im mittleren Fall.- III.6.1.1. Selbstorganisierende lineare Listen.- III.6.1.2. Splay-Bäume.- III.6.2. D-Bäume.- III.6.3. Eine Anwendung auf mehrdimensionales Suchen.- III.7. Ein Vergleich von Suchstrukturen.- III.8. Teilmengen eines kleinen Universums.- III.8.1. Das boolesche Feld (Bitvektor).- III.8.2. Verwaltung dynamischer Partitionen von linearen Listen.- III.8.3. Das Union-Find-Problem.- III.9. Übungen.- III.10. Bibliographische Anmerkungen.