Binärbaumsuche

Szene 5: Vertiefung von Binärbäumen oben zeigt nun anhand eines Wörterbuchs, wie eine konkrete geordnete Menge an Daten als Binärbaum gespeichert werden kann. Wird nach einem Wort gesucht, so wird erst überprüft, ob es in der ersten oder zweiten Hälfte des Buchs steht. Allerdings weiß eine Person meist nicht, wo genau sich die Hälfte des Buches befindet. Darum schlägt sie ungefähr in der Hälfte auf und betrachtet einen der Einträge, der dort zu finden ist. Ist es das gesuchte Wort, so ist die Suche beendet. Ist es das nicht, wird überprüft, ob vor- oder zurückgeblättert werden muss. In dem dadurch eingeschränkten Bereich wird fortgefahren, indem diese Schritte wiederholt werden:

1. Es wird ein zufälliger Eintrag betrachtet.
2. Wenn es nicht der gesuchte Eintrag ist, wird weiter vorne oder weiter hinten weiter gesucht.

Um diesen Vorgang möglichst effizient zu gestalten, sollte das “zufällige” Element immer genau in der Mitte der noch möglichen Kandidaten sein. Und da dieses Verfahren am Computer implementiert werden soll, ist zum Glück bekannt, welches das mittlere Element ist.

Angenommen, es soll ein Wörterbuch implementiert werden, das wie im Unterrichtsvideo aus den 15 englischen Wörtern ‘age’, ‘bird’, ‘date’, ‘effort’, ‘freedom’, ‘island’, ‘key’, ‘male’, ‘name’, ‘paper’, ‘rail’, ‘table’, ‘value’, ‘watch’, ‘year’ besteht. Das mittlere Wort ist ‘male’ und deswegen wird es als Wurzel des Baums genutzt. Es sollen anschließend zwei Kanten von diesem Knoten wegführen: Eine nach links zu allen Wörtern, die weiter vorne im Alphabet stehen, und eine nach rechts zu allen Wörtern, die weiter hinten im Alphabet stehen.

Nun werden die zwei Teillisten ‘age’, …, ‘key’ und ‘name’, …, ‘year’ betrachtet. Diese werden wieder genauso unterteilt: Das mittlere Element der ersten ist ‘effort’ und das der zweiten ist ‘table’.

Das wird so lange fortgesetzt, bis alle Elemente in den Baum eingearbeitet wurden.

Wird im Anschluss z. B. das Wort ‘island’ gesucht, fängt der Computer oben an der Wurzel an zu vergleichen:

1. ‘male’ ist nicht ‘island’.
2. Aber ‘island’ kommt vor ‘male’.
3. ‘effort’ ist nicht ‘island’.
4. Aber ‘island’ kommt nach ‘effort’.
5. ‘island’ ist ‘island’. Fertig.

Diese Baumsuche kann hier nun in einer dynamisch-interaktiven Visualisierung getestet werden:

Der Binärbaum speichert entweder eine zufällige Auswahl englischer Wörter – analog zu dem Wörterbuchbeispiel von oben – oder Zahlen, um das Prinzip der Baumsuche etwas allgemeiner zu zeigen. Links oben sind während der Suche die aktuellen Schritte des Algorithmus zu sehen.

Anleitung:

• Am Schieberegler rechts kann die Anzahl der Elemente der Datenmenge verändert werden. Durch die Zahlen- und Wörter-Knöpfe lassen sich die Einträge im Baum ändern.
• Ein Klick auf einen Knoten im Baum wählt diesen aus. Anschließend erlaubt der Suche!-Knopf die Baumsuche zu starten. Mit den Pause- und Weiter-Knöpfen links unten kann die Suche angehalten werden und der Schieberegler daneben erlaubt das Verändern der Suchgeschwindigkeit.
• Die Sprechblase oben links gibt die Schritte des oben vorgestellten Algorithmus wieder.

Weiterführende Informationen zu Bäumen als Datenstrukturen finden Sie in (Dietzfelbinger, Mehlhorn, & Sanders, 2014).

Aufgaben dazu …

Aufgaben 7, 10