Übung — AFB III (Verallgemeinern und Reflektieren)

Musterlösung: enqueue(x) ist ein ein.push(x). Für dequeue wird, falls aus leer ist, der ganze Stapel ein Element für Element auf aus umgeladen; dadurch liegt das älteste Element oben, und aus.pop() liefert es. Ist aus nicht leer, genügt direkt aus.pop(). Einzelne dequeue-Aufrufe können teuer sein (alles umladen), aber jedes Element wird insgesamt nur einmal umgeladen — im Mittel ist der Aufwand pro Operation konstant.

Musterlösung: Liegt das oberste Element am Ende, entsprechen push und pop den Operationen append und delete(getLength() - 1); kein Element rückt nach. Liegt es an Index 0, verschiebt jedes push und pop alle übrigen Elemente. Beide Varianten sind korrekt, „oben = Ende“ ist deutlich effizienter.

Musterlösung: Jeder der n Knoten hat zwei Plätze für Teilbäume, zusammen 2n. Jeder Knoten außer der Wurzel ist Kind genau eines Knotens und belegt genau einen Platz: n − 1 Plätze sind besetzt. Auf allen übrigen Plätzen sitzt ein leerer Baum: 2n − (n − 1) = n + 1. Deshalb ruft eine rekursive Traversierung sich 2n + 1-mal auf.

Musterlösung: Für den leeren Baum und ein Blatt ist die Aussage klar. Für einen größeren Baum gibt die Inorder erst den linken Teilbaum aus — nach Annahme sortiert und mit lauter Werten kleiner als die Wurzel —, dann die Wurzel, dann den rechten Teilbaum — sortiert und mit lauter größeren Werten. Hintereinander ergibt das eine aufsteigende Folge. Da das für jeden Teilbaum gilt, gilt es für den ganzen Baum.

Musterlösung: Der Baum A mit linkem Kind B und der Baum A mit rechtem Kind B haben beide die Preorder A B und die Postorder B A — trotzdem sind es verschiedene Bäume. Pre- und Postorder verraten nicht, auf welcher Seite ein Einzelkind hängt. Die Inorder tut es: Sie liefert B A bzw. A B. Aus der Preorder kennt man jeweils die Wurzel, die Inorder teilt die übrigen Knoten eindeutig in linken und rechten Teilbaum; rekursiv angewandt entsteht genau ein Baum.

Musterlösung: Suchen: Die binäre Suche braucht garantiert etwa log₂ 5000 ≈ 13 Vergleiche; ein ausgeglichener Suchbaum ebenso, ein entarteter bis zu 5000. Einfügen: In der Reihung muss die Stelle gesucht und dann mit insertAt eingefügt werden — im Mittel rücken 2500 Elemente nach. Im Suchbaum wird ohne Verschieben ein Blatt angehängt. Weil täglich eingefügt wird, ist der Suchbaum besser — vorausgesetzt, die Nummern kommen nicht sortiert an (fortlaufende Kundennummern würden ihn entarten lassen). Dann wäre die sortierte Reihung die sicherere Wahl oder der Baum müsste regelmäßig ausgeglichen neu aufgebaut werden.

Musterlösung: Die Werte werden zunächst gesammelt (sie sind ja fast sortiert, ggf. kurz nachsortieren). Dann wird der mittlere Wert zuerst eingefügt, danach rekursiv die Mitten der linken und der rechten Hälfte usw. So teilt jede Wurzel ihre Werte in zwei gleich große Hälften; auf jeder Ebene verdoppelt sich die Zahl der Knoten, und die Höhe bleibt bei etwa log₂(n + 1). Alternative: Die Werte vor dem Einfügen zufällig mischen — dann ist der Baum mit hoher Wahrscheinlichkeit niedrig, aber nicht garantiert.

Musterlösung: Zuerst wird der Teilbaum b gesucht, dessen Wurzel den Schlüssel enthält. Ist b ein Blatt, genügt b.setEmpty() — an seiner Stelle steht dann ein leerer Baum. Hat b genau ein Kind, wird beim Elternknoten p der Teilbaum b durch den nicht leeren Teilbaum k von b ersetzt: p.setLeft(k), falls b links von p hing, sonst p.setRight(k). Alle Werte in k lagen schon auf derselben Seite von p wie b; deshalb bleibt die Ordnung erhalten. (Ist b die Wurzel des ganzen Baums, wird k die neue Wurzel.)

Musterlösung: Zunächst wird der ganze Baum auf den Stapel gelegt. Solange der Stapel nicht leer ist, wird ein Teilbaum entnommen; ist er nicht leer, wird seine Wurzel ausgegeben und danach erst der rechte, dann der linke Teilbaum abgelegt. Wegen LIFO wird der linke Teilbaum als Nächstes bearbeitet — vollständig, bevor der rechte an die Reihe kommt. Genau das verlangt W – L – R.

static void preorderIterativ(BinTree<String> baum) {
    Stack<BinTree<String>> s = new Stack<BinTree<String>>();
    s.push(baum);
    while (!s.isEmpty()) {
        BinTree<String> b = s.pop();
        if (!b.isEmpty()) {
            System.out.print(b.getItem() + " ");
            s.push(b.getRight());     // rechts zuerst ablegen ...
            s.push(b.getLeft());      // ... damit links zuerst herauskommt
        }
    }
}

Der eigene Stapel übernimmt die Rolle des Aufrufstapels der rekursiven Lösung.

Musterlösung: Einfügen bleibt einfach: Bei Gleichheit geht es wie bei „größer“ nach rechts; die Ordnung lautet dann „links kleiner, rechts größer oder gleich“. Die Suche darf beim ersten Treffer aber nicht abbrechen, wenn alle Vorkommen gezählt werden sollen: Sie muss im rechten Teilbaum weitersuchen. Kommen sehr viele gleiche Werte vor (z. B. 12 Punkte bei 30 Prüflingen), entsteht eine lange Kette und der Baum wird hoch. Besser ist oft, jeden Wert nur einmal zu speichern und einen Zähler mitzuführen (Inhaltsklasse mit Punktzahl und Anzahl). Die Regel ist also korrekt, aber bei vielen Duplikaten ineffizient.