Home > Informatik > Stufe Q1 > 12. Suchverfahren

12.3 Binäre Suchbäume

Überblick - Lineare Suche - Binäre Suche - binäre Suchbäume - Index- u. Interpolationssuche

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

asdf

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 innerer 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.

asdf

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.

Übung 12.3-1 (Heft, 4 Punkte)

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

Übung 12.3-2 (Heft, 4 Punkte)

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ösungshinweise:

asdf

Die beiden ersten Schritte bei der Suche nach der Zahl 21

In der Abbildung 3 sehen Sie die beiden ersten Schritte bei der Suche nach der Zahl 21. Die streng binäre Suche beginnt bei der 120, weil dies die "echte" Mitte der 19 Zahlen ist. Da 21 < 120, wird in der linken Partition weiter gesucht. Die rechte Partition kann ab sofort ignoriert werden. Die linke Partition besteht aus 9 Zahlen, auch hier gibt es also eine "echte" Mitte, die 61. Da 21 < 61, wird jetzt in der linken Partition der linken Partition weiter gesucht. Hier ist dann die 34 die "Mitte"

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...