Fundamentale Datenstrukturen
Fundamentale Datenstrukturen sind die organisierten Methoden zur Speicherung und zum Zugriff auf Daten – Arrays, verkettete Listen, Hash-Tabellen, Bäume, Heaps und deren Verwandte –, die die Effizienz der darauf aufbauenden Operationen bestimmen.
Definition
Eine Datenstruktur ist eine Methode zur Organisation und Speicherung von Daten, sodass die durch ihren abstrakten Datentyp definierten Operationen effizient ausgeführt werden können; fundamentale Datenstrukturen sind die kleine Menge von Allzweckstrukturen, aus denen die meisten anderen aufgebaut sind.
Scope
Dieser Bereich umfasst die abstrakten Datentypen (Listen, Dictionaries, Prioritätswarteschlangen, Mengen) und die konkreten Strukturen, die diese implementieren, zusammen mit den Kosten ihrer Kernoperationen (Einfügen, Löschen, Suchen, Aktualisieren) unter Worst-Case- und amortisierter Analyse. Er behandelt, wie die Wahl der Struktur die Algorithmusleistung prägt und verbindet sich mit den Entwurfsparadigmen sowie den Graphen- und String-Algorithmen, die von diesen Strukturen abhängen. Er schließt die Datenbank- und Dateisystem-Speicherstrukturen aus, die in anderen Unterfeldern behandelt werden.
Sub-topics
Core questions
- Welchen abstrakten Datentyp benötigt eine Anwendung, und welche konkrete Struktur implementiert ihn am besten?
- Was sind die Worst-Case- und amortisierten Kosten jeder Operation auf einer gegebenen Struktur?
- Wie tauschen Strukturen Speicher gegen Zeit oder Lesegeschwindigkeit gegen Aktualisierungsgeschwindigkeit?
- Wie begrenzt die Aufrechterhaltung einer Invariante (Sortierung, Balance, Heap-Eigenschaft) die Operationskosten?
- Wann ist eine einfache Struktur einer asymptotisch schnelleren, aber komplexeren vorzuziehen?
Key concepts
- abstrakter Datentyp
- Arrays und verkettete Listen
- Stacks und Queues
- Hash-Tabellen
- Binäre Suchbäume
- balancierte Bäume
- Heaps und Prioritätswarteschlangen
- amortisierte Analyse
- Zeit-Speicher-Kompromisse
Key theories
- Abstrakte Datentypen versus Implementierungen
- Ein abstrakter Datentyp spezifiziert Operationen und deren Semantik unabhängig von der Repräsentation; mehrere konkrete Datenstrukturen können denselben ADT mit unterschiedlichen Leistungsprofilen implementieren, wodurch Designer Korrektheit und Kosten getrennt betrachten können.
- Amortisierte Analyse
- Einige Strukturen (dynamische Arrays, Splay-Bäume) haben gelegentlich teure Operationen, aber im Durchschnitt über eine Sequenz hinweg günstige Operationen; die amortisierte Analyse (Aggregat-, Buchhaltungs-, Potenzialmethoden) begrenzt diese Durchschnittskosten rigoros.
Clinical relevance
Fundamentale Datenstrukturen sind die Bausteine praktisch aller Software: Hash-Tabellen unterstützen Dictionaries und Datenbankindizes, balancierte Bäume und B-Bäume organisieren Dateisysteme und Datenbanken, Prioritätswarteschlangen steuern Scheduler und Ereignissimulationen, und die richtige Strukturwahl entscheidet oft darüber, ob ein System skaliert.
History
Grundlegende Datenstrukturen wurden in Knuths The Art of Computer Programming ab 1968 katalogisiert. Selbstbalancierende Bäume (AVL-Bäume, 1962; Rot-Schwarz-Bäume und B-Bäume in den 1970er Jahren) und fortgeschrittene Strukturen wie Fibonacci-Heaps und Splay-Bäume (1980er Jahre, maßgeblich durch Tarjan und Mitarbeiter) erweiterten das Feld, während die amortisierte Analyse eine rigorose Beschreibung ihrer Leistung lieferte.
Key figures
- Donald Knuth
- Robert Sedgewick
- Robert Tarjan
- Rudolf Bayer
Related topics
Seminal works
- knuth1997vol1
- cormen2009
- sedgewick2011
Frequently asked questions
- Wie wähle ich zwischen einer Hash-Tabelle und einem balancierten Suchbaum?
- Hash-Tabellen bieten eine erwartete O(1)-Such- und Einfügezeit, aber keine Ordnung, während balancierte Suchbäume O(log n)-Operationen ermöglichen und Schlüssel sortiert halten, was Bereichsabfragen und geordnete Traversierung unterstützt. Wählen Sie Hashing für reine Schlüsselabfragen und einen Baum, wenn Ordnung oder Bereichsoperationen wichtig sind.
- Was bedeutet amortisierte Kosten für eine Datenstruktur?
- Amortisierte Kosten sind die durchschnittlichen Kosten pro Operation über eine Worst-Case-Sequenz von Operationen. Ein dynamisches Array zahlt beispielsweise gelegentlich O(n) für die Größenänderung, hat aber im Durchschnitt O(1) pro Anfügevorgang, da Größenänderungen im Verhältnis zu günstigen Anfügevorgängen selten sind.