Einführung in die Suche mit Hilfe von Binärbäumen

Wie findet ein Computer die Anwort so schnell? Du selbst wirst dir auf keinen Fall das Telefonbuch von Bonn hernehmen und dieses, beginnend mit der ersten Zeile, Namen für Namen bis zum Dümmler-Verlag durcharbeiten. Vielmehr wirst du so ungefähr dort das Buch öffnen, wo du die mit D beginnenden Namen erwartest, also etwa im ersten Viertel. Danach blätterst du, den ersten oder letzten Namen der Seite betrachtend, vor oder zurück. Zuletzt wirst du innerhalb einer Spalte der Seite suchen.

Ein ähnlich effektives Verfahren hat die Programmiererin oder der Programmierer auch für den Suchalgorithmus mit dem Computer vorgesehen. Ein solches Verfahren wollen wir in diesem Kapitel beschreiben, so dass du es in deiner Programmierumgebung selbst erstellen kannst.

In der Informationstheorie heißt eines der Verfahren zum schnellen Auffinden von Informationen binärer Suchbaum.

Damit die Informationen später schnell wieder gefunden werden, sind sie schon bei der Erfassung auf spezielle Art geordnet worden. Das wollen wir jetzt erklären. Dazu verwenden wir eine Liste kurzer Begriffe, die wir hier in alphabetischer Reihenfolge angeben. Die alphabetische Reihenfolge wählen wir, weil sonst das Suchen sehr erschwert wird.

Bad, Erz, Gut, Hut, Jod, Kur, Mut, Not, Ort, Pol, Rad, Sog, Tau, Wut, Zoo.

Du musst bei der Bearbeitung der Aufgabe 1 nicht besonders viele Wörter lesen, um fest zu stellen, dass Lot nicht in der Liste enthalten ist. Das liegt daran, dass du schon so ungefähr abschätzt, wo du in der Zeile zu lesen beginnst. Eine solche ungefähre Abschätzung aber ist für einen Computer nicht möglich. Er benötigt einen genau definierten Algorithmus, der ihn zum Ziel führt.

Einen besonders effektiven Suchalgorithmus erhältst du, wenn du die Schlüsselworte, nach denen du suchst, auf besondere Weise baumartig anordnest. Die folgende Abbildung enthält eine solche Anordnung in einem binären Suchbaum. Wir haben alle Begriffe obiger Liste darin geordnet untergebracht.

Binärer Suchbaum

Unser Baum steht auf dem Kopf. Stellen, an denen Äste beginnen oder enden, heißen Knoten. Oben ist die Wurzel. Dort beginnen zwei Äste. An jedem Knoten beginnen wieder zwei Äste, die in Knoten münden. Der Knoten am Ende eines jeden langes Astet nennen wir Blatt. An unteren Ende befinden sich also nur Blätter. Unser Baum hat vier Ebenen.

Den Entscheidungs-Algorithmus für die Suche des Begriffs Lot in diesem Baum kannst du formulieren, wenn du bei der Wurzel beginnst. Liegt der gesuchte Begriff in der lexiko­gra­fi­schen Anordnung vor dem Begriff, der in der Wurzel steht, dann gehe links weiter, sonst rechts. Auf diese Weise hangelst du dich Knoten für Knoten bis zu dem gesuchten Begriff vor. Kommst du bei einem Blatt an, ohne den Begriff zu finden, dann ist er sicher nicht im Such­baum enthalten.

Erweiter dein Wissen zu diesem Thema mit den Aufgaben 3-7

Bevor wir uns in Aufgabe 8 daran machen, einen solchen binären Suchbaum in unserer Program­mier­umgebung zu verwirklichen, wollen wir noch einmal zusammen fassen, was wir bis jetzt über binäre Suchbäume erfahren haben. Alles, was du bisher über binäre Suchbäume gelernt hast, ist unabhängig von einer Realisierung mit Hilfe eines Computers. Informationen können unabhängig von Computern baumartig strukturiert werden.

Binärer Suchbaum

Ein binärer Suchbaum ist eine strukturierte Anordnung von Knoten und Ästen.
Die Äste heißen auch Verweise, denn sie verweisen auf den nächsten Knoten.
Der Ausgangsknoten des binären Suchbaumes ist die Wurzel.
Von der Wurzel verweisen zwei Äste auf je einen weiteren Knoten.
So kann sich von Ebene zu Ebene die Anzahl der Knoten verdoppeln.
Blätter heißen die Knoten, die auf keine weiteren Knoten verweisen.

Du hast einen Weg kennen gelernt, wie du Begriffe in einem solchen Baum suchen kannst und wie du den Baum erweitern kannst.

Du hast erlebt, dass unser Suchalgorithmus in einem ausgeglichenen binären Suchbaum besonders effektiv ist.

Ein vollständiger ausgeglichener Binärbaum mit n Ebenen enthält 2ⁿ - 1 Knoten.