Datenstrukturen, Rekursion und Effizienz

Stack und Queue

Ein Stack (Stapel) arbeitet nach dem Prinzip LIFO (Last In, First Out): Das zuletzt abgelegte Element wird als erstes wieder entnommen, wie bei einem Tellerstapel. Eine Queue (Schlange) arbeitet nach dem Prinzip FIFO (First In, First Out): Wer zuerst kommt, wird zuerst bedient, wie an der Mensa-Kasse.

Beide sind dynamische Datenstrukturen: Ihre Größe ändert sich zur Laufzeit, man greift nur über wenige festgelegte Operationen zu. Das macht sie sicher und einfach zu verwenden. Im Abitur NRW stehen dafür die Java-Klassen Stack<ContentType>, Queue<ContentType> und BinarySearchTree<ContentType> zur Verfügung, die genau diese Operationen anbieten (intern z. B. als verkettete Liste aus Knotenobjekten umgesetzt: Jeder Knoten kennt seinen Nachfolger, push, pop, enqueue und dequeue ändern nur wenige Verweise).

Rekursion

Eine Methode ist rekursiv, wenn sie sich selbst aufruft, und zwar für ein kleineres Teilproblem. Zwei Bestandteile sind zwingend:

int fak(int n){

  if (n <= 1) return 1;      // Abbruchbedingung

  return n * fak(n - 1);     // rekursiver Aufruf

}

Jeder Aufruf legt einen Eintrag (Parameter, Rücksprungadresse) auf den Aufrufstack des Systems. Erst wenn der Anker erreicht ist, werden die Aufrufe von oben nach unten abgearbeitet.

Rekursion ist elegant, kann aber ineffizient sein. Beim Aufrufbaum der Fibonacci-Methode fib(n) = fib(n-1) + fib(n-2) verzweigt sich jeder Aufruf in zwei neue. Dieselben Teilprobleme werden immer wieder berechnet, die Zahl der Aufrufe wächst exponentiell. Eine iterative Lösung merkt sich nur die letzten beiden Werte und braucht $n$ Schritte und konstanten Speicher. (Alternative: bereits berechnete Werte speichern.)

int f(int n){ if (n == 0) return 0; return n + f(n - 1); }

int g(int n){ if (n <= 1) return 1; return g(n - 1) + g(n - 2); }

Der binäre Suchbaum

Ein Baum ist eine nichtlineare Datenstruktur aus Knoten mit Kindern. Im binären Baum hat jeder Knoten höchstens ein linkes und ein rechtes Kind. Ein binärer Suchbaum erfüllt zusätzlich: Alle Werte im linken Teilbaum sind kleiner, alle im rechten größer als der Wert des Knotens.

Einfügen: Beginne bei der Wurzel, gehe bei kleineren Werten nach links, bei größeren nach rechts, bis ein freier Platz da ist. Dieselbe Suche funktioniert beim Finden eines Wertes.

Drei Traversierungen besuchen jeden Knoten genau einmal (W = Wurzel, L = linker, R = rechter Teilbaum):

Die In-order-Ausgabe eines Suchbaums ist immer aufsteigend sortiert. Die Suche nach 60 braucht Vergleiche mit 50, 70 und 60, also 3 Vergleiche; sie folgt höchstens einem Pfad von der Wurzel zu einem Blatt, also der Höhe des Baums.

Suchen und Sortieren

Lineare Suche: Das Feld wird von vorn Element für Element durchlaufen, im schlechtesten Fall mit $n$ Vergleichen.

Binäre Suche (nur in einem sortierten Feld): Man vergleicht mit dem mittleren Element. Ist der gesuchte Wert kleiner, sucht man links weiter, ist er größer, rechts. Jeder Vergleich halbiert den Suchbereich.

Warum logarithmisch? Nach $k$ Halbierungen bleiben etwa $n/2^k$ Elemente. Der Bereich ist auf ein Element geschrumpft, wenn $2^k \geq n$ gilt, also nach etwa $\log_2 n$ Schritten. Für $n = 1.000$ sind das nur etwa 10 Vergleiche.

Selectionsort: Suche im unsortierten Rest das kleinste Element und tausche es an die erste freie Stelle. Wiederhole dies für den verbleibenden Rest.

Allgemein sind es $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$ Vergleiche, unabhängig von der Anordnung der Eingabe. Die Laufzeit wächst quadratisch: Verdoppelt man $n$, vervierfacht sich der Aufwand.

Mergesort und Effizienz

Selectionsort ist für große Datenmengen zu langsam. Mergesort nutzt das Prinzip „Teile und herrsche“:

1. Teilen: Das Feld in zwei Hälften zerlegen.

2. Herrschen: Beide Hälften rekursiv sortieren (Anker: Länge 1 ist schon sortiert).

3. Mischen: Die beiden sortierten Hälften zu einem sortierten Feld zusammenführen, indem man immer die vorderen Elemente vergleicht und das kleinere übernimmt.

Aufwand: Bei $n = 2^k$ wird $k$-mal halbiert, es gibt also $k = \log_2 n$ Ebenen. Auf jeder Ebene werden insgesamt höchstens $n$ Elemente gemischt, also höchstens $n$ Vergleiche. Gesamt: etwa $n \cdot \log_2 n$ Vergleiche.

Mergesort benötigt aber zusätzlichen Speicher für die gemischten Teilfelder. Es gibt also einen Zielkonflikt zwischen Laufzeit und Speicherplatz, den man bei der Wahl eines Verfahrens begründen muss.

Stack-Anwendung und systematisches Testen

Ein Stack eignet sich, wenn das zuletzt Geöffnete zuerst geschlossen werden muss. Das ist bei Klammern der Fall. Algorithmus zur Prüfung auf korrekte Klammerung:

• Lies den Ausdruck von links nach rechts.

• Öffnende Klammer: push.

• Schließende Klammer: Ist der Stack leer oder passt das oberste Element nicht zum Typ, ist der Ausdruck falsch. Sonst pop.

• Am Ende ist der Ausdruck korrekt, wenn der Stack leer ist.

Systematisches Testen: Eine Implementierung wird mit Testfällen geprüft, die Normalfälle, Grenzfälle und Fehlerfälle abdecken. Zu jedem Testfall legt man die erwartete Ausgabe vorher fest. Gute Testfälle für die Klammerprüfung:

Zurück zum Anfang: Das Ticketsystem passt zur Queue (FIFO), der Zurück-Button zum Stack (LIFO). Bei einer Million Einträge und $10^8$ Vergleichen pro Sekunde macht der Unterschied zwischen Selectionsort ($\approx n^2/2$) und Mergesort ($\approx n \cdot \log_2 n$) aus knapp 1,4 Stunden Rechenzeit nur den Bruchteil einer Sekunde.

Auf einen Blick

• Stack (LIFO: push, pop) und Queue (FIFO: enqueue, dequeue) sind dynamische Datenstrukturen mit festen Zugriffsoperationen.

• Rekursion braucht eine Abbruchbedingung und einen rekursiven Aufruf mit kleinerem Problem. Mehrfachberechnung (Fibonacci) macht sie exponentiell langsam, und jeder offene Aufruf belegt Speicher auf dem Aufrufstack.

• Im binären Suchbaum liegen kleinere Werte links, größere rechts. Pre-, In- und Post-order sind die Traversierungen; In-order liefert sortierte Werte.

• Binäre Suche (sortiertes Feld) braucht etwa $\log_2 n$ Vergleiche, lineare Suche bis zu $n$.

• Selectionsort braucht $\frac{n(n-1)}{2}$ Vergleiche, Mergesort („Teile und herrsche“) etwa $n \cdot \log_2 n$, benötigt dafür aber zusätzlichen Speicher.

• Systematisches Testen deckt Normal-, Grenz- und Fehlerfälle mit vorher festgelegten Erwartungen ab.

• Operatoren: nennen Sie Operationen und Prinzipien, führen Sie aus Algorithmen Schritt für Schritt, begründen Sie Aufwandsabschätzungen und vergleichen Sie Verfahren.