Datenstrukturen erklärt
Jedes Programm legt Daten irgendwo ab, und wie es das tut, entscheidet darüber, was schnell und was langsam ist. Eine Liste mit einer Million Namen lässt sich Name für Name durchsuchen oder so anordnen, dass zwanzig Vergleiche jeden Namen finden. Datenstrukturen sind solche Anordnungen: eine Handvoll Ideen, die meisten älter als der Personal Computer, die in jeder Datenbank, jedem Betriebssystem, jedem Browser und jedem Spiel stecken.
Wozu eine Datenstruktur dient
Eine Datenstruktur wird nach den Fragen gewählt, die sie beantworten muss. Die Anrufliste eines Telefons braucht den letzten Anruf zuerst, die Aufträge eines Druckers den ältesten zuerst, ein Wörterbuch die Bedeutung eines Wortes unter hunderttausend, ein Routenplaner die nächste unbesuchte Kreuzung. Jede Struktur macht einige Operationen schnell, indem sie andere aufgibt, und die O-Notation beschreibt diesen Tausch: O(1) heißt, die Zeit wächst nicht mit der Anzahl n der Elemente, O(log n), dass eine Verdopplung von n einen Schritt mehr kostet, und O(n), dass die Zeit proportional zu n wächst.
Stapel, Warteschlangen und Deques
Ein Stapel fügt am selben Ende hinzu und entfernt dort: zuletzt hinein, zuerst hinaus. Rückgängig-Verläufe, die Zurück-Taste und die Aufrufe eines laufenden Programms sind Stapel. Eine Warteschlange fügt hinten an und entnimmt vorn: zuerst hinein, zuerst hinaus, wie Tastatureingaben oder eine Druckwarteschlange. Eine Deque erlaubt beides an beiden Enden. Alle drei brauchen konstante Zeit pro Operation. Eine Warteschlange liegt oft in einem Ringpuffer, einem festen Array, in dem Anfang und Ende über dessen Ende hinweg umlaufen; wird er voll, werden die Elemente in ein doppelt so großes Array kopiert. Das Kopieren kostet O(n), geschieht aber so selten, dass jede Operation im Mittel trotzdem O(1) kostet, was man eine amortisierte Schranke nennt.
Verkettete Listen
Eine verkettete Liste speichert jeden Wert in einem Knoten mit einem Zeiger auf den nächsten Knoten. Einfügen oder Löschen biegt nur einen oder zwei Zeiger um, nichts muss verschoben werden, aber man kann nicht zum zehnten Knoten springen: Man folgt den Verweisen ab dem Kopf. Eine Liste, die nur ihren Kopf kennt, erreicht das Ende in O(n) Schritten; echte Listen halten meist auch einen Endzeiger, und doppelt verkettete Listen einen Zeiger zurück, so sind ein Browserverlauf oder ein LRU-Cache gebaut.
Binäre Suchbäume
Ein binärer Suchbaum hält an jedem Knoten kleinere Werte im linken Teilbaum und größere im rechten. Eine Suche vergleicht und geht nach links oder rechts, und ein In-Order-Durchlauf liest die Werte sortiert. Ein Blatt zu löschen entfernt es einfach, ein Knoten mit einem Kind wird durch dieses Kind ersetzt, und ein Knoten mit zwei Kindern durch seinen In-Order-Nachfolger, den kleinsten Wert in seinem rechten Teilbaum. All das braucht Zeit proportional zur Höhe des Baums: etwa log n, wenn der Baum buschig ist, aber n, wenn die Werte sortiert eintreffen und der Baum zu einer Liste entartet.
AVL- und Rot-Schwarz-Bäume
Selbstbalancierende Bäume reparieren ihre Form nach jeder Änderung. Ein AVL-Baum, 1962 von Adelson-Velsky und Landis erfunden, hält die Höhen der beiden Teilbäume jedes Knotens höchstens eins auseinander; erreicht der Balancefaktor eines Knotens ±2, stellen eine Rotation (die Fälle LL und RR) oder zwei (LR und RL) das Gleichgewicht wieder her. Ein Rot-Schwarz-Baum färbt seine Knoten so, dass die Wurzel schwarz ist, kein roter Knoten ein rotes Kind hat und jeder Weg nach unten gleich viele schwarze Knoten passiert, was den längsten Weg höchstens doppelt so lang wie den kürzesten hält. Er repariert sich durch Umfärben und höchstens wenige Rotationen und ist der Baum in Javas TreeMap, in std::map von C++ und im Linux-Scheduler.
Heaps und Prioritätswarteschlangen
Ein binärer Heap ist ein vollständiger Binärbaum, der ohne Zeiger in einem Array liegt: Die Kinder von Position i stehen bei 2i + 1 und 2i + 2. In einem Min-Heap ist jeder Elternknoten höchstens so groß wie seine Kinder, der kleinste Wert steht also immer an der Wurzel. Ein neuer Wert kommt ans Ende und steigt an größeren Eltern vorbei auf; beim Entnehmen der Wurzel wandert der letzte Wert nach oben und sinkt ab. Beides kostet O(log n), und ein ganzes Array lässt sich in O(n) zu einem Heap machen. Heaps treiben Prioritätswarteschlangen in Dijkstras kürzesten Wegen, in Ereignissimulationen und in Betriebssystem-Schedulern an, und sie ergeben Heapsort.
Hashtabellen
Eine Hashtabelle macht mit einer Hashfunktion aus einem Schlüssel einen Array-Index und geht direkt dorthin. Verschiedene Schlüssel können auf demselben Index landen, eine Kollision. Verkettung hält in jedem Bucket eine kleine Liste; offene Adressierung wie lineares Sondieren probiert die nächsten Plätze, bis sie einen freien findet, und muss beim Löschen eines Schlüssels einen Grabstein hinterlassen, damit spätere Suchen weitersondieren. Mit einer guten Hashfunktion und einem niedrigen Belegungsfaktor (Schlüssel pro Bucket), den das Wachsen der Tabelle sichert, kosten Einfügen, Suchen und Löschen im Durchschnitt O(1). Eine schwache Funktion, etwa das Addieren der Zeichencodes eines Wortes, schickt Anagramme in denselben Bucket. Hashtabellen stecken hinter Pythons dict, JavaScript-Objekten und Datenbankindizes.
Tries und Union-Find
Ein Trie oder Präfixbaum speichert Zeichenketten mit einem Zeichen pro Ebene, sodass Wörter mit gleichem Anfang einen Weg teilen und ein Knoten markiert, wo ein Wort endet. Ein Wort der Länge L zu finden braucht L Schritte, egal wie viele Wörter gespeichert sind, und alle Wörter mit einem bestimmten Präfix liegen in einem Teilbaum, so arbeiten Autovervollständigung und Rechtschreibprüfung. Union-Find hält Elemente in disjunkten Mengen, jede ein Baum, dessen Wurzel die Menge benennt. Find folgt den Elternverweisen bis zur Wurzel; Union hängt eine Wurzel unter eine andere. Mit Vereinigung nach Rang und Pfadkompression kostet eine lange Folge von Operationen pro Operation fast konstante Zeit, die inverse Ackermann-Funktion α(n), die für jedes realistische n höchstens 4 ist. Kruskals Algorithmus für minimale Spannbäume stützt sich darauf.
Häufig gestellte Fragen
Was ist der Unterschied zwischen einem Array und einer verketteten Liste?
Ein Array hält seine Elemente nebeneinander im Speicher, jede Position ist also sofort erreichbar, aber Einfügen in der Mitte heißt, alles dahinter zu verschieben. Eine verkettete Liste kann überall durch Ändern von Zeigern einfügen, aber eine Position zu erreichen heißt, ab dem Kopf zu laufen. Arrays nutzen außerdem den Cache des Prozessors viel besser, weshalb sie in der Praxis meist schneller sind.
Was bedeutet amortisierte Zeit?
Die durchschnittlichen Kosten pro Operation über eine lange Folge, auch wenn eine einzelne Operation manchmal teuer ist. Ein Ringpuffer, der sich verdoppelt, wenn er voll ist, kopiert ab und zu alle n Elemente, aber weil die Kopien seltener werden, je größer der Puffer wird, kosten n Einfügungen insgesamt O(n), also im Mittel O(1) pro Stück.
Ist ein Heap dasselbe wie ein binärer Suchbaum?
Nein. Ein binärer Suchbaum ordnet jeden linken Teilbaum vor seinem Knoten und jeden rechten danach ein, er kann also alle Werte sortiert auflisten und jeden Wert schnell finden. Ein Heap verspricht nur, dass jeder Elternknoten vor seinen Kindern kommt, was reicht, um Minimum oder Maximum sofort zu finden, aber nicht, um nach einem beliebigen Wert zu suchen.
Wie erkennt Union-Find, ob zwei Elemente verbunden sind?
Es folgt von jedem Element den Elternverweisen bis zur Wurzel seines Baums. Kommen beide bei derselben Wurzel an, sind sie in derselben Menge. Die Pfadkompression lässt danach jeden Knoten auf dem Weg direkt auf die Wurzel zeigen, sodass die nächste Frage zu ihnen einen einzigen Schritt braucht.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Den Datenstruktur-Visualisierer öffnen