Datenstrukturen: Übungsfragen mit Erklärungen

1Was eine Datenstruktur ist

Eine Datenstruktur ist eine Art, Daten im Speicher so zu organisieren, dass bestimmte Operationen schnell sind: ein Element finden, eines hinzufügen, eines entfernen.

Keine Struktur ist bei allem schnell. Eine Struktur zu wählen heißt zu wählen, welche Operationen günstig sein sollen. Ihre Kosten werden in Big O angegeben, wobei n die Anzahl der Elemente ist.

Die beiden grundlegenden Bausteine sind das Array und die verkettete Liste.

Ein Array speichert seine Elemente in einem Speicherblock, eines nach dem anderen. Der Computer kann berechnen, wo Element i liegt, daher kostet das Lesen von a[i] O(1). Das Einfügen am Anfang erfordert das Verschieben jedes Elements: O(n).

Eine verkettete Liste speichert jedes Element in einem Knoten mit einem Zeiger auf den nächsten Knoten. Der letzte Zeiger ist null. Das Einfügen am Kopf (h) ändert nur einen Zeiger: O(1). Um aber Element i zu erreichen, musst du i Zeigern folgen: O(n).

Eine doppelt verkettete Liste hat zusätzlich einen Zeiger auf den vorherigen Knoten, sodass du in beide Richtungen laufen kannst.

2Stapel und Warteschlangen

Ein Stapel (stack) ist wie ein Stapel Teller: Du legst nur oben auf und nimmst nur oben weg. Das zuletzt hineingelegte Element kommt als erstes wieder heraus: LIFO.

• push legt ein Element oben auf, pop entfernt das oberste Element, peek liest das oberste, ohne es zu entfernen. Alle kosten O(1).
• Verwendung: die Rückgängig-Funktion eines Editors, der Aufrufstapel eines Programms, die Prüfung, ob Klammern ausgeglichen sind, Tiefensuche.

Eine Warteschlange (queue) ist wie eine Schlange an der Kasse: Du stellst dich hinten an und gehst vorne weg. Das zuerst hineingekommene Element kommt als erstes wieder heraus: FIFO.

• enqueue fügt hinten hinzu, dequeue entfernt vorne. Beide kosten O(1).
• Verwendung: Druckaufträge, wartende Nachrichten, Breitensuche.

Eine Deque (doppelseitige Warteschlange) erlaubt Hinzufügen und Entfernen an beiden Enden. Eine Prioritätswarteschlange entfernt immer zuerst das Element mit der höchsten Priorität; sie wird meist als Heap gebaut.

3Bäume, Heaps, Hashtabellen und Graphen

Ein Baum hat einen obersten Knoten, die Wurzel. Jeder andere Knoten hat genau einen Elternknoten. Knoten ohne Kinder sind Blätter. Ein Baum mit n Knoten hat n − 1 Kanten.

In einem Binärbaum hat jeder Knoten höchstens zwei Kinder. Ein binärer Suchbaum (BST) fügt eine Regel hinzu: Schlüssel im linken Teilbaum sind kleiner als der Knoten, Schlüssel im rechten Teilbaum sind größer.

Das Suchen in einem BST folgt einem Pfad nach unten und kostet daher O(Höhe). Ein ausgeglichener Baum (AVL, Rot-Schwarz) hält die Höhe nahe log₂ n. Schlüssel, die in sortierter Reihenfolge eingefügt werden, ergeben eine Kette der Höhe n.

Ein Heap ist ein Binärbaum, in dem jeder Elternknoten kleiner als seine Kinder (Min-Heap) oder größer (Max-Heap) ist. Das Minimum oder Maximum liegt an der Wurzel, und Einfügen und Entfernen kosten O(log n).

Eine Hashtabelle speichert Schlüssel-Wert-Paare. Eine Hashfunktion macht aus dem Schlüssel einen Index, sodass Einfügen und Nachschlagen im Mittel O(1) kosten. Zwei Schlüssel mit demselben Index sind eine Kollision, die durch Verkettung (eine Liste pro Platz) oder offene Adressierung (einen anderen Platz probieren) gelöst wird.

Ein Graph hat Knoten, die durch Kanten verbunden sind, welche eine Richtung oder ein Gewicht haben können. Er wird als Adjazenzmatrix mit O(V²) Speicher oder als Adjazenzlisten mit O(V + E) gespeichert.

4Das Verfahren Schritt für Schritt

Fragen beschreiben oft eine Aufgabe und fragen, welche Struktur passt, oder fragen, wie eine Struktur nach einigen Operationen aussieht.

1. Finde die Operation, die schnell sein muss: Zugriff über die Position, über den Schlüssel, das neueste Element, das älteste Element, das kleinste Element oder ein Bereich.
2. Ordne ihr eine Struktur zu: Index → Array, Schlüssel → Hashtabelle, neuestes → Stapel, ältestes → Warteschlange, kleinstes oder größtes → Heap, sortierte Reihenfolge oder Bereiche → ausgeglichener Suchbaum.
3. Prüfe die Kosten der anderen Operationen, die die Aufgabe braucht, in Big O.
4. Führe bei einer Ablaufaufgabe die Operationen eine nach der anderen aus und schreibe den Zustand nach jeder auf.
5. Prüfe den Endzustand an der Regel der Struktur: LIFO, FIFO, die BST-Ordnung oder die Heap-Ordnung.

5Ein durchgerechnetes Beispiel

Folge jedem Schritt. Versuche, den nächsten vorherzusagen, bevor du ihn öffnest.

6Häufige Fehler

• LIFO und FIFO verwechseln. Ein Stapel gibt das neueste Element zurück, eine Warteschlange das älteste.
• Denken, eine verkettete Liste erlaube schnellen Zugriff über den Index. Sie muss vom Kopf aus laufen.
• Annehmen, ein BST sei immer O(log n). Nur ein ausgeglichener Baum ist es; sortiertes Einfügen ergibt O(n).
• Kollisionen in einer Hashtabelle vergessen. O(1) ist der Mittelwert, nicht der schlechteste Fall.
• Die Traversierungen verwechseln. Preorder: Knoten zuerst. Inorder: Knoten in der Mitte. Postorder: Knoten zuletzt.
• Eine Adjazenzmatrix für einen großen dünn besetzten Graphen verwenden. Sie verschwendet O(V²) Speicher.

7So sehen Prüfungsaufgaben aus

• Leicht: Begriffe und Fakten. LIFO und FIFO, was ein Knoten, eine Wurzel oder ein Blatt ist, die BST-Regel, was eine Hashfunktion tut.
• Mittel: Anwendung der Konzepte. Welche Struktur zu einer Aufgabe passt, das Ergebnis von push und pop oder von BST-Einfügungen, Baumtraversierungen, eine Hashtabelle mit linearem Sondieren, Kosten in Big O.
• Schwer: Fälle und Analyse. Ausgeglichene Bäume, Heaps in Arrays, B-Bäume, Tries, Union-Find, Bloomfilter und Entwürfe wie ein LRU-Cache.

Bei einem Heap, der ab Index 0 in einem Array gespeichert ist, liegen die Kinder von Index i bei 2i + 1 und 2i + 2, und sein Elternknoten liegt bei ⌊(i − 1) / 2⌋.