Datenstrukturen, Rekursion und Effizienz

Stack und Queue

Ein Stack (Stapel) und eine Queue (Warteschlange) sind lineare Datenstrukturen. Man darf Elemente nur an bestimmten Stellen einfügen und entfernen. Das macht sie einfach und für viele Aufgaben genau richtig. Im Zentralabitur NRW begegnen Ihnen diese Strukturen als vorgegebene Java-Klassen Stack, Queue und BinaryTree mit Methoden wie isEmpty(), push(...), pop(), top(), enqueue(...), dequeue(), front() und getContent(). Die Bezeichnungen können dort leicht von den hier verwendeten abweichen.

Warum diese Einschränkung? Sie macht jede Operation schnell: Es muss immer nur an einem Ende (Stack) bzw. an je einem Ende (Queue) gearbeitet werden, nie in der Mitte.

Rekursion

Eine Methode heißt rekursiv, wenn sie sich selbst aufruft. Das Problem wird dabei auf ein kleineres Problem derselben Art zurückgeführt.

Fehlt eine der beiden Komponenten, ruft sich die Methode endlos auf und das Programm bricht mit einem Stapelüberlauf (StackOverflowError) ab.

Jeder offene Aufruf liegt mit seinen Variablen auf dem Aufrufstack. Bei s(3) sind es zuletzt vier Einträge gleichzeitig. Die Rekursionstiefe bestimmt also den Speicherbedarf.

Mehrfache Rekursion

Ruft sich eine Methode mehrmals pro Aufruf selbst auf, verzweigt sich die Aufrufkette zu einem Aufrufbaum. Typisches Beispiel sind Fibonacci-artige Folgen wie g(n) = g(n - 1) + g(n - 2). Die Zahl der Aufrufe $C(n)$ erfüllt $C(n) = 1 + C(n-1) + C(n-2)$, sie wächst also pro Schritt etwa um den Faktor 1,6 (goldener Schnitt). Das nennt man exponentielles Wachstum.

Der Grund für die Verschwendung: Dieselben Teilprobleme werden immer wieder neu berechnet. Abhilfe schafft eine iterative Lösung (Schleife mit zwei Hilfsvariablen) oder das Merken bereits berechneter Werte in einem Feld (Memoisierung). Die Schleife braucht nur konstant viel Speicher, die Rekursion dagegen Platz für die Rekursionstiefe auf dem Aufrufstack.

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); }

Binärer Suchbaum

Ein Baum ist eine nichtlineare Datenstruktur aus Knoten. Der oberste Knoten ist die Wurzel, Knoten ohne Nachfolger heißen Blätter. In einem binären Baum hat jeder Knoten höchstens zwei Kinder (linkes und rechtes).

Einfügen: Man beginnt an der Wurzel. Ist der neue Wert kleiner, geht man nach links, sonst nach rechts, bis man auf einen leeren Platz trifft. Dort wird ein neues Blatt angelegt. Suchen geht genauso: In jedem Knoten vergleicht man und entscheidet, in welchem Teilbaum es weitergeht.

Dieser Baum entsteht beim Einfügen der Folge 5, 2, 8, 1.

Traversierung

Um alle Knoten auszugeben, besucht man den Baum rekursiv. Die drei klassischen Reihenfolgen unterscheiden sich darin, wann die Wurzel eines Teilbaums „dran“ ist:

Effizienz: Bei der Suche steigt man pro Vergleich eine Ebene tiefer. Die Anzahl der Vergleiche ist höchstens die Höhe des Baums plus 1 (Anzahl der Ebenen). Ein ausgeglichener Baum mit $n$ Knoten hat etwa $\log_2 n$ Ebenen. Wird aber eine bereits sortierte Folge eingefügt, entartet der Baum zu einer Kette, und die Suche braucht bis zu $n$ Vergleiche.

Suchen und Sortieren

Lineare und binäre Suche

Bei der linearen Suche prüft man ein Feld Element für Element von vorn. Im schlechtesten Fall braucht man $n$ Vergleiche.

Die binäre Suche setzt ein sortiertes Feld voraus. Man vergleicht mit dem mittleren Element. Ist der gesuchte Wert kleiner, sucht man in der linken Hälfte weiter, ist er größer, in der rechten. So halbiert sich der Suchbereich mit jedem Vergleich.

Warum $\log_2 n$? Nach jedem Vergleich bleibt höchstens die Hälfte der Elemente übrig: $n, \frac{n}{2}, \frac{n}{4}, \dots$. Nach $k$ Halbierungen ist höchstens ein Element übrig, wenn $2^k \ge n$ gilt. Für $n = 2^k$ ist das $k = \log_2 n$ Mal der Fall, dazu kommt ein letzter Vergleich. Für $n = 256 = 2^8$ sind es also höchstens $8 + 1 = 9$ Vergleiche, während die lineare Suche bis zu 256 braucht.

Selectionsort

Beim Selectionsort (Sortieren durch Auswählen) sucht man im noch unsortierten Teil das kleinste Element und tauscht es an den Anfang dieses Teils. Dann wiederholt man das mit dem restlichen Teil.

Selectionsort braucht unabhängig von der Eingabe stets $\frac{n(n-1)}{2} \approx \frac{n^2}{2}$ Vergleiche. Verdoppelt man $n$, vervierfacht sich also die Arbeit.

Effizienz und Mergesort

Die Effizienz eines Algorithmus beschreibt, wie viel Zeit (Anzahl der Operationen, z. B. Vergleiche) und wie viel Speicher er in Abhängigkeit von der Eingabegröße $n$ benötigt. Entscheidend ist die Größenordnung für große $n$, nicht die genaue Sekundenzahl auf einem bestimmten Rechner.

Teile und herrsche

Beim Prinzip Teile und herrsche (Divide and Conquer) teilt man ein Problem in kleinere Teilprobleme, löst diese (meist rekursiv) und setzt die Teillösungen zusammen. Mergesort (Sortieren durch Mischen) macht genau das:

1. Teile das Feld in zwei Hälften.

2. Sortiere beide Hälften rekursiv mit Mergesort (Abbruch: Länge 1 ist sortiert).

3. Mische die zwei sortierten Hälften: Vergleiche immer die beiden vordersten Elemente und übernimm das kleinere.

Warum $n \cdot \log_2 n$? Bei $n = 2^k$ kann man das Feld $k$-mal halbieren, bis Länge 1 erreicht ist. Es entstehen also $k = \log_2 n$ Ebenen. Auf jeder Ebene liegen insgesamt $n$ Elemente, und beim Mischen braucht man dort höchstens $n$ Vergleiche. Zusammen sind das höchstens $n \cdot \log_2 n$ Vergleiche. Dafür braucht Mergesort zusätzlichen Speicher von der Größenordnung $n$ für die Hilfsfelder, Selectionsort sortiert dagegen „an Ort und Stelle“.

Anwendung: Klammerprüfung und systematisches Testen

Ob ein Ausdruck korrekt geklammert ist, lässt sich mit einem Stack prüfen. Das Prinzip: Die zuletzt geöffnete Klammer muss als erste wieder geschlossen werden. Das ist genau LIFO.

Systematisches Testen

Eine Implementierung testet man mit gezielt gewählten Testfällen, die alle relevanten Situationen abdecken, nicht mit beliebigen Beispielen. Üblich sind:

• ein Normalfall (korrekte, typische Eingabe),

• Grenzfälle (leere Eingabe, ein einzelnes Zeichen),

• Fehlerfälle (jede Art von Fehler mindestens einmal),

• zu jedem Testfall das erwartete Ergebnis, das vor dem Test feststeht.

Vom Anfang zurück: Der Browser-Verlauf ist ein Stack (zuletzt besuchte Seite zuerst), die Druckerwarteschlange eine Queue (der älteste Auftrag zuerst). Welcher Algorithmus auch bei vielen Daten schnell genug ist, entscheidet die Größenordnung der Operationen: $n \cdot \log_2 n$ (Mergesort) schlägt $\frac{n^2}{2}$ (Selectionsort) bei großen $n$ deutlich.

Auf einen Blick

• Stack (LIFO): push, pop; Queue (FIFO): enqueue, dequeue. Sie sind lineare Datenstrukturen mit eingeschränktem Zugriff.

• Rekursion braucht Abbruchbedingung und rekursiven Aufruf mit kleinerem Argument. Mehrfache Rekursion kann exponentiell viele Aufrufe erzeugen, eine Iteration spart Rechenzeit und Aufrufstack.

• Binärer Suchbaum: links kleiner, rechts größer. Die In-order-Ausgabe ist sortiert, die Suchdauer hängt von der Höhe des Baums ab.

• Binäre Suche (sortiertes Feld): höchstens etwa $\log_2 n + 1$ Vergleiche. Selectionsort: $\frac{n(n-1)}{2}$ Vergleiche. Mergesort (Teile und herrsche): etwa $n \cdot \log_2 n$ Vergleiche.

• Die Klammerprüfung mit einem Stack und systematische Testfälle (Normal-, Grenz-, Fehlerfälle) sichern die Korrektheit.

Prüfen Sie sich selbst: Können Sie ...

• den Zustand eines Stacks bzw. einer Queue nach einer Operationsfolge angeben?

• eine rekursive Methode auswerten und ihre Abbruchbedingung benennen?

• einen Suchbaum zeichnen und die drei Traversierungen angeben?

• die Effizienz von Such- und Sortierverfahren begründen und vergleichen?

• Testfälle für einen Algorithmus beschreiben?