Eigentlich ist dieses Thema ja erst später dran, in Folge 17. Aber wenn wir uns hier schon einmal mit binären Suchverfahren beschäftigen, dann sollten wir auch einen kurzen Blick auf die binären Suchbäume werfen. In Folge 17 werden wir das Thema dann vertiefen.
Ein Beispiel für einen binären Suchbaum
Ein binärer Suchbaum
Das in der Abbildung gezeigte "Gebilde" wird als Baum bezeichnet, der aus einer Wurzel (ganz oben) und vielen Knoten besteht. Knoten, die keinen Nachfolger mehr haben (wie zum Beispiel A oder D) nennt man auch Blätter, während Knoten mit mindestens einem Nachfolger als innere Knoten bezeichnet werden.
Bei einem binäreren Baum (kurz: Binärbaum) hat jeder Knoten maximal zwei Nachfolger.
Bei einem binären Suchbaum sind die Knoten bzw. ihre Nachfolger nach einem bestimmten System geordnet. Beliebt ist folgendes System: Alle Nachfolgerknoten links eines betrachteten Knoten enthalten einen kleineren Wert als der betrachtete Knoten. Aller Nachfolgerknoten rechts dieses Knotens enthalten den gleichen oder einen größeren Wert.
Das kann man an dem Baum in der Abbildung gut erkennen. Links vom Knoten M befinden sich die Knoten C, A, E und D; alle diese Knoten haben einen kleineren Wert als M. Alle Knoten rechts von M haben einen größeren Wert.
Dieses Prinzip wiederholt sich auch bei den linken und rechten Unterbäumen des Knotens M. Alle Knoten links von Q haben einen kleineren Wert, alle Knoten rechts von Q einen größeren.
Das Suchen in einem binären Suchbaum
In der Abbildung 2 sind die gleichen Buchstaben des binären Suchbaums als lineare sortierte Liste angeordnet. Startet man hier eine lineare Suche, so sind sechs Vergleiche notwendig, bis man den Buchstaben N gefunden hat. Sucht man den gleichen Buchstaben dagegen in dem binären Suchbaum, so sind nur drei Vergleiche notwendig. Mit einer binären Suche würde man den Buchstaben N in der linearen Liste ebenfalls in wenigen Schritten finden, mit einigem Glück sogar gleich beim ersten Vergleich, wenn nämlich N als "Mitte" der Liste gewählt wird.
Erstellen Sie auf dem Papier einen binären Suchbaum, der sich durch Einfügen der folgenden Zahlen ergibt:
100 - 50 - 160 - 34 - 77 - 122 - 200 - 21 - 45 - 61 - 93 - 111 - 130 - 188 - 220 - 210 - 240 - 120 - 230
Es sollen nun die folgenden Zahlen in diesem Baum gesucht werden:
50 - 61 - 130 - 210
Ermitteln Sie, wie viele Vergleiche zum Finden dieser Zahlen im Durchschnitt benötigt werden.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Schreiben Sie die Zahlen aus der Übung 12.3-1 aufsteigend sortiert auf und suchen Sie dann die angegebenen Suchzahlen mit Hilfe einer streng binären Suche. Wenn eine Partition der Liste eine gerade Anzahl von Elementen hat, nehmen Sie bitte immer die links der virtuellen Mitte stehende Zahl als "Mitte".
Beispiel:
Die "Mitte" der Partition 21 - 34 - 45 - 50 ist die Zahl 34, weil sie links von der nicht sichtbaren Mitte steht.
Ermitteln Sie auch hier, wie viele Vergleiche zum Finden dieser Zahlen im Durchschnitt benötigt werden.
Lösung (Hinweise für Lehrerinnen und Lehrer) / Nähere Infos dazu
Neben diesen binären Suchbäumen gibt es viele andere Arten von Suchbäumen. Die Knoten können auch drei, vier oder noch mehr Nachfolger haben, was die Zahl der Ebenen und somit auch die Zahl der Vergleiche drastisch reduziert. Bei den sogenannten B-Bäumen enthält jeder Knoten Hunderte bis Tausende von Daten, die innerhalb des Knotens aufsteigend sortiert sind. Mit sehr wenigen Vergleichen kommt man schnell zum passenden Knoten, und innerhalb des Knotens führt dann eine binäre Suche sehr schnell zum gewünschten Ergebnis.
Wie das alles genau funktioniert und wie man solche Bäume implementiert, wird später im Verlauf des Kurses erläutert. Bis dahin müssen Sie sich noch etwas gedulden.
Seitenanfang -
Weiter mit der Interpolationssuche...