MINT lernen

Suchen im binären Suchbaum

Zwei Abituraufgaben zum Suchbaum — von der Mediathek bis zum Wörterbuch.

Dein Fortschritt:
0 / 0 Aufgaben
1

Die Mediathek

AFB I–II

Die Mediathek einer Schule verwaltet ihre Medien in einem binären Suchbaum vom Typ BinTree<Medium>. Geordnet wird nach der Mediennummer; jede Nummer kommt höchstens einmal vor. Die Klasse Medium bietet die Operationen getNummer(): Ganzzahl und getTitel(): Zeichenkette.

Material: Ausschnitt des Suchbaums der Mediathek (Mediennummern)
1570284031003920523060107460812088509400
  1. Beschreiben Sie die Eigenschaft, die einen binären Suchbaum auszeichnet, und zeigen Sie an zwei Knoten des Materials, dass sie erfüllt ist. 3 BE
  2. Stellen Sie die Suche nach den Nummern 3100 und 8500 jeweils in einer Tabelle mit den Spalten Knoten, Vergleich und weiter dar. 4 BE
  3. Implementieren Sie die Methode static String titelZu(BinTree<Medium> b, int nr), die den Titel des Mediums mit der Nummer nr liefert oder den leeren Text, falls es keines gibt. 5 BE
  4. Die Kreismediathek hat 100 000 Medien. Schätzen Sie ab, wie viele Vergleiche eine Suche im ungünstigsten Fall braucht, wenn der Baum ausgeglichen ist bzw. wenn die Medien in der Reihenfolge ihrer Nummern eingefügt wurden. 4 BE

Insgesamt 16 BE

Hinweise

Hinweis zu Aufgabe a)
Die Eigenschaft gilt für ganze Teilbäume, nicht nur für die Kinder.
Hinweis zu Aufgabe b)
Eine erfolglose Suche endet an einem leeren Teilbaum — nennen Sie ihn in der letzten Zeile.
Hinweis zu Aufgabe c)
Eine Schleife mit einer Hilfsvariablen genügt; vergleichen Sie nr mit getItem().getNummer().
Hinweis zu Aufgabe d)
Nutzen Sie \(n\le 2^h-1\). Was passiert, wenn aufsteigend sortierte Nummern eingefügt werden?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Für jeden Knoten gilt: Alle Nummern im linken Teilbaum sind kleiner, alle im rechten Teilbaum größer als seine Nummer. Beispiel 2840: links 1570 < 2840, rechts 3920 und 3100 > 2840. Beispiel 5230: links stehen nur Nummern unter 5230 (höchstens 3920), rechts nur Nummern über 5230 (ab 6010).

Erwartungshorizont zu Aufgabe b)

Suche nach 3100:

KnotenVergleichweiter
52303100 < 5230links
28403100 > 2840rechts
39203100 < 3920links
31003100 = 3100gefunden

Suche nach 8500:

KnotenVergleichweiter
52308500 > 5230rechts
74608500 > 7460rechts
88508500 < 8850links
81208500 > 8120rechts
leerer Baum—nicht vorhanden
Erwartungshorizont zu Aufgabe c)
static String titelZu(BinTree<Medium> b, int nr) {
    while (!b.isEmpty()) {
        Medium m = b.getItem();
        if (nr == m.getNummer()) {
            return m.getTitel();
        }
        if (nr < m.getNummer()) {
            b = b.getLeft();
        } else {
            b = b.getRight();
        }
    }
    return "";
}

Eine rekursive Lösung mit dem leeren Baum als Abbruch ist gleichwertig.

Erwartungshorizont zu Aufgabe d)

Ausgeglichen: Aus \(100\,000\le 2^h-1\) folgt \(h\ge\log_2(100\,001)\approx 16{,}6\), also h = 17 — höchstens 17 Vergleiche. Nach Nummern sortiert eingefügt, wird jede neue Nummer rechts an die vorige gehängt: Der Baum ist eine Kette der Höhe 100 000, im ungünstigsten Fall sind 100 000 Vergleiche nötig — nicht besser als die lineare Suche.

2

Das Wörterbuch

AFB II–III

Ein Rechtschreibprogramm speichert alle bekannten Wörter (nur Kleinbuchstaben) in einem binären Suchbaum vom Typ BinTree<String>. Geordnet wird lexikographisch mit compareTo: a.compareTo(b) ist negativ, wenn a vor b steht, 0 bei Gleichheit und sonst positiv. Ein Praktikant hat folgende Prüfmethode geschrieben:

static boolean pruefe(BinTree<String> b) {
    if (b.isEmpty() || b.isLeaf()) {
        return true;
    }
    String w = b.getItem();
    if (!b.getLeft().isEmpty() && b.getLeft().getItem().compareTo(w) >= 0) {
        return false;
    }
    if (!b.getRight().isEmpty() && b.getRight().getItem().compareTo(w) <= 0) {
        return false;
    }
    return pruefe(b.getLeft()) && pruefe(b.getRight());
}
Material: Suchbaum w
haustischmond
  1. Erläutern Sie, wie beim Suchen eines Wortes mit compareTo entschieden wird, in welchem Teilbaum weitergesucht wird. 3 BE
  2. Entwerfen Sie eine Methode static String kleinstesWort(BinTree<String> b), die für einen nicht leeren Suchbaum das alphabetisch erste Wort liefert, ohne alle Knoten zu betrachten. 3 BE
  3. Widerlegen Sie mithilfe des Baums w die Behauptung, pruefe erkenne jeden fehlerhaften Suchbaum, und erweitern Sie die Prüfung zu einer korrekten Methode static boolean istSuchbaum(BinTree<String> b, String min, String max). 6 BE
  4. Alternativ könnten die Wörter sortiert in einer dynamischen Reihung stehen und mit der binären Suche gesucht werden. Beurteilen Sie beide Lösungen für ein Wörterbuch, das beim Schreiben ständig um neue Wörter ergänzt wird. 4 BE

Insgesamt 16 BE

Hinweise

Hinweis zu Aufgabe a)
Unterscheiden Sie die drei möglichen Vorzeichen des Rückgabewerts.
Hinweis zu Aufgabe b)
Wo steht im Suchbaum das kleinste Element?
Hinweis zu Aufgabe c)
Welche Knoten vergleicht pruefe gar nicht miteinander? Für den Baum w: Wo steht „tisch“ im Verhältnis zu „mond“? Für die Korrektur: Jeder Teilbaum hat einen erlaubten Bereich (min, max); beim Abstieg wird er enger.
Hinweis zu Aufgabe d)
Kriterien: Aufwand für Suchen und für Einfügen, Abhängigkeit von der Reihenfolge der neuen Wörter.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Das gesuchte Wort x wird mit dem Wort der Wurzel verglichen: x.compareTo(b.getItem()). Ist das Ergebnis 0, ist das Wort gefunden. Ist es negativ, steht x alphabetisch vor dem Wurzelwort und kann nur im linken Teilbaum stehen; ist es positiv, nur im rechten. Ist der Teilbaum leer, ist das Wort unbekannt.

Erwartungshorizont zu Aufgabe b)
static String kleinstesWort(BinTree<String> b) {
    while (!b.getLeft().isEmpty()) {
        b = b.getLeft();                   // immer links hinab
    }
    return b.getItem();
}

Es wird nur der linke Rand des Baums betrachtet — höchstens h Knoten.

Erwartungshorizont zu Aufgabe c)

Im Baum w vergleicht pruefe nur „haus“ mit „mond“ (richtig: haus < mond) und „tisch“ mit „haus“ (richtig: tisch > haus). Sie liefert true. „tisch“ steht aber im linken Teilbaum von „mond“, obwohl tisch > mond — w ist kein Suchbaum. Die Behauptung ist widerlegt: Die Methode prüft nur direkte Kinder, nicht ganze Teilbäume.

static boolean istSuchbaum(BinTree<String> b, String min, String max) {
    if (b.isEmpty()) {
        return true;
    }
    String w = b.getItem();
    if (min != null && w.compareTo(min) <= 0) {
        return false;                              // zu klein für diesen Teilbaum
    }
    if (max != null && w.compareTo(max) >= 0) {
        return false;                              // zu groß für diesen Teilbaum
    }
    return istSuchbaum(b.getLeft(), min, w) && istSuchbaum(b.getRight(), w, max);
}

Aufruf mit istSuchbaum(w, null, null); null steht für „keine Grenze“. Für w liefert sie false.

Erwartungshorizont zu Aufgabe d)

Suchen: Beide brauchen im günstigen Fall etwa \(\log_2 n\) Vergleiche; die binäre Suche garantiert das, der Suchbaum nur, wenn er ausgeglichen ist. Einfügen: In der sortierten Reihung muss nach der Suche mit insertAt eingefügt werden — im Mittel rücken n/2 Wörter nach. Im Suchbaum wird das Wort ohne Verschieben als Blatt angehängt (etwa \(\log_2 n\) Schritte). Da ständig neue Wörter hinzukommen, ist der Suchbaum vorzuziehen — solange die Wörter nicht alphabetisch sortiert eintreffen, denn dann entartet er. Sinnvoll wäre, den Baum gelegentlich neu ausgeglichen aufzubauen.