Bäume als Datenstruktur

Aufgaben 6-10

Aufgabe 6

Welche der folgenden Punkte beschreiben Vorteile der Binärbaumsuche gegenüber der gewöhnlichen, linearen Suche in einer Liste?

Es können eine oder alle Antwortmöglichkeiten richtig sein. Klicken Sie diese an.

Aufgabe 7

Betrachten Sie den bekannten Binärbaum zur Wörtersuche.

Wie viele Knoten müssen in diesem Baum mindestens überprüft werden, um ein Wort zu finden?

Klicken Sie die richtige Antwort an.

Wie viele Knoten müssen in diesem Baum höchstens überprüft werden, um ein Wort zu finden?

Klicken Sie die richtige Antwort an.

Aufgabe 8

Gegeben sei ein Binärbaum mit $n$ Ebenen, also $2^n - 1$ Knoten, zur Wörtersuche. Welche der nachfolgenden Formel beschreibt, wie viele Knoten im Durchschnitt überprüft werden müssen, um eine Wort zu finden?

Klicken Sie die richtige Antwort an.

Aufgabe 9

Gegeben sei ein Wörterbuch mit $N$ Einträgen, das wie hier beschrieben in einem Binärbaum gespeichert wurde. Verdreifacht man nun die Anzahl der Wörter, die man speichern möchte, wird ein größerer Baum benötigt. Wie viele Suchschritte (sprich, Ja-Nein-Fragen) mehr werden in dem neuen Baum im Vergleich zum alten höchstens benötigt, um dort ein Wort zu finden?

Klicken Sie die richtige Antwort an.

Aufgabe 10

Der wesentliche Teil der hier vorgestellten Baumsuche ist, dass an jedem Knoten (der nicht den gesuchten Eintrag enthält) eine Ja-Nein- beziehungsweise Größer-Kleiner-Frage gestellt wird. Je nach Antwort läuft der Suchalgorithmus dann nach links oder rechts. Damit das funktioniert, muss in dem verwendeten Baum jeder Knoten, der kein Blatt ist, genau zwei Kinder haben. Allerdings muss er nicht, wie in den Beispielen in diesem Modul, symmetrisch sein. Dadurch können häufig gesuchte Einträge viel weiter oben gespeichert und folglich auch schneller gefunden werden, als selten gesuchte Einträge. Unten sehen Sie einen so verallgemeinerten Suchbaum. Zur besseren Übersicht ist dieser Baum gerichtet gezeichnet.

Sortieren sie die gegebenen elf Wörter so in den Baum ein, dass der Suchalgorithmus, der hier vorgestellt wurde, immer noch genauso funktioniert. Insbesondere sollen alle Wörter, die links eines Knotens sitzen, weiter vorne im Alphabet stehen, als das Wort im Knoten; und analog alle Wörter rechts weiter hinten. (Die gegebenen Wörter sind bereits in alphabetischer Reihung.)