MINT lernen

In einen Suchbaum einfügen

Zwei Abituraufgaben zum Einfügen — von der Highscore-Liste bis zum Terminkalender.

Dein Fortschritt:
0 / 0 Aufgaben
1

Die Highscore-Liste

AFB I–II

Ein Geschicklichkeitsspiel speichert die erreichten Punktzahlen in einem binären Suchbaum vom Typ BinTree<Integer> (Ergänzende Hinweise 2025). Gleiche Punktzahlen werden nur einmal gespeichert. An einem Nachmittag werden nacheinander diese Punktzahlen erreicht:

520, 310, 780, 150, 400, 690, 900, 350

  1. Stellen Sie den Suchbaum dar, der entsteht, wenn die Punktzahlen in dieser Reihenfolge in einen leeren Baum eingefügt werden. 3 BE
  2. Geben Sie die Inorder-Folge des Baums an und nennen Sie die Eigenschaft, die sie bei jedem Suchbaum hat. 2 BE
  3. Die Highscore-Liste soll mit der höchsten Punktzahl beginnen. Verändern Sie die rekursive Inorder-Traversierung zu einer Methode static void rangliste(BinTree<Integer> b), die alle Punktzahlen absteigend ausgibt. 4 BE
  4. Implementieren Sie die Methode static void einfuegen(BinTree<Integer> b, int x) ohne Rekursion. 5 BE

Insgesamt 14 BE

Hinweise

Hinweis zu Aufgabe a)
Jede Zahl wird einzeln von der Wurzel aus einsortiert; die 350 landet unter der 400.
Hinweis zu Aufgabe b)
L – W – R; überlegen Sie, was „links kleiner, rechts größer“ für die Ausgabereihenfolge bedeutet.
Hinweis zu Aufgabe c)
Vertauschen Sie die Reihenfolge der beiden rekursiven Aufrufe.
Hinweis zu Aufgabe d)
Mit einer Schleife den Suchpfad hinablaufen, bis ein leerer Baum erreicht oder x gefunden ist. Nach den Ergänzenden Hinweisen 2025 bekommt ein leerer Baum bei setItem zwei leere Teilbäume.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
150310350400520690780900

520 ist die Wurzel. 350 < 520, 350 > 310, 350 < 400: linkes Kind von 400.

Erwartungshorizont zu Aufgabe b)

Inorder: 150, 310, 350, 400, 520, 690, 780, 900. Bei jedem Suchbaum liefert die Inorder-Traversierung die Werte aufsteigend sortiert, weil für jeden Knoten erst alle kleineren (links), dann er selbst, dann alle größeren (rechts) ausgegeben werden.

Erwartungshorizont zu Aufgabe c)
static void rangliste(BinTree<Integer> b) {
    if (!b.isEmpty()) {
        rangliste(b.getRight());          // erst die größeren Punktzahlen
        System.out.print(b.getItem() + " ");
        rangliste(b.getLeft());           // dann die kleineren
    }
}

Ausgabe: 900 780 690 520 400 350 310 150 (Reihenfolge R – W – L).

Erwartungshorizont zu Aufgabe d)
static void einfuegen(BinTree<Integer> b, int x) {
    while (!b.isEmpty() && x != b.getItem()) {
        if (x < b.getItem()) {
            b = b.getLeft();
        } else {
            b = b.getRight();
        }
    }
    if (b.isEmpty()) {
        b.setItem(x);                     // leerer Teilbaum wird zum Blatt
    }
}

Die Schleife endet am leeren Teilbaum (dort wird eingefügt) oder bei einem Treffer (dann bleibt der Baum unverändert). Weil b auf den Teilbaum im Baum verweist, hängt das neue Blatt sofort an der richtigen Stelle.

2

Der Terminkalender

AFB II–III

Eine Kalender-App speichert Termine in einem binären Suchbaum; der Schlüssel ist das Datum als Ganzzahl im Format JJJJMMTT (z. B. 20270315 für den 15.03.2027). Pro Tag gibt es höchstens einen Termin. Eine Nutzerin überträgt alle 365 Termine ihres Jahresplans — in der Reihenfolge, in der sie im Papierkalender stehen, also chronologisch.

  1. Analysieren Sie, welche Form der Suchbaum durch das chronologische Einfügen erhält, und welche Folgen das für das Suchen hat. 4 BE
  2. Schätzen Sie ab, wie viele Vergleiche das chronologische Einfügen aller 365 Termine insgesamt kostet, und vergleichen Sie mit einem ausgeglichenen Baum (Höhe 9, in dem die Tiefen aller Knoten zusammen 2418 ergeben). 4 BE
  3. Die Termine liegen bereits sortiert in einer Reihung int[] sortiert vor. Entwerfen eine rekursive Methode static void baueAusgeglichen(BinTree<Integer> b, int[] sortiert, int von, int bis), die die Termine so einfügt, dass ein möglichst niedriger Baum entsteht. Die Methode einfuegen darf verwendet werden. 5 BE
  4. Ein Mitschüler meint, für die Erinnerungsfunktion („Was ist mein nächster Termin?“) sei eine Schlange besser als ein Suchbaum, weil die Termine ohnehin chronologisch eingetragen werden. Erörtern Sie diese Aussage. 4 BE

Insgesamt 17 BE

Hinweise

Hinweis zu Aufgabe a)
Wo landet ein Termin, der später ist als alle bisherigen?
Hinweis zu Aufgabe b)
Beim chronologischen Einfügen vergleicht der k-te Termin mit allen k − 1 vorherigen. Nutzen Sie die Summenformel.
Hinweis zu Aufgabe c)
Der mittlere Wert eines Bereichs wird zuerst eingefügt, dann rekursiv die beiden Hälften. Abbruch: leerer Bereich.
Hinweis zu Aufgabe d)
Was passiert, wenn später ein Termin eingetragen wird, der vor anderen liegt? Wo steht im Suchbaum der früheste Termin?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Jeder neue Termin ist größer als alle vorhandenen und wird deshalb immer rechts an den zuletzt eingefügten Knoten gehängt. Der Baum entartet zu einer Kette nach rechts mit Höhe 365; jeder Knoten hat nur ein rechtes Kind. Folge: Eine Suche braucht im ungünstigsten Fall 365 Vergleiche — so viel wie die lineare Suche; der Vorteil des Suchbaums ist verloren.

Erwartungshorizont zu Aufgabe b)

Chronologisch: \(0+1+\dots+364=\frac{365\cdot 364}{2}=66\,430\) Vergleiche. Ausgeglichen: Jeder Termin braucht so viele Vergleiche, wie seine Tiefe angibt — zusammen 2418. Das chronologische Einfügen ist also etwa 27-mal so aufwendig; bei doppelt so vielen Terminen wächst der Aufwand etwa auf das Vierfache, im ausgeglichenen Fall nur etwas mehr als auf das Doppelte.

Erwartungshorizont zu Aufgabe c)
static void baueAusgeglichen(BinTree<Integer> b, int[] sortiert, int von, int bis) {
    if (von > bis) {
        return;                           // kein Wert mehr in diesem Bereich
    }
    int mitte = (von + bis) / 2;
    einfuegen(b, sortiert[mitte]);        // Mitte zuerst: wird Wurzel des Teilbaums
    baueAusgeglichen(b, sortiert, von, mitte - 1);
    baueAusgeglichen(b, sortiert, mitte + 1, bis);
}

Aufruf: baueAusgeglichen(baum, sortiert, 0, sortiert.length - 1). Für 365 Termine entsteht ein Baum der Höhe 9.

Erwartungshorizont zu Aufgabe d)

Pro Schlange: Werden Termine wirklich nur chronologisch eingetragen, liefert head() sofort den nächsten Termin, dequeue() entfernt vergangene — sehr einfach. Contra: Wird später ein Termin eingetragen, der vor bereits gespeicherten liegt (Arzttermin nächste Woche), müsste er mitten in die Schlange — das kann eine Schlange nicht; man müsste sie vollständig umladen. Auch die Suche nach dem Termin an einem bestimmten Tag erfordert das Durchlaufen der ganzen Schlange. Im Suchbaum ist der nächste Termin der linkeste Knoten (höchstens h Schritte), neue Termine lassen sich an jeder Stelle einfügen und gezielt suchen. Fazit: Die Schlange genügt nur, wenn nie nachträglich Termine eingeschoben werden; im Alltag ist der (ausgeglichene) Suchbaum die bessere Wahl.