Brauchen wir den Schlüssel?

Worum geht es hier?

Unser Suchalgorithmus auf Binärbäumen beruht ebenso wie die binäre Suche auf dem Schlüssel (in unserem Beispiel der Schülernummer). Wenn wir unseren gesuchten Schlüssel nicht mit jedem Schlüssel vergleichen und sagen können, ob er größer oder kleiner als dieser ist, ist alles was wir getan haben obsolet.

Wie zum Beispiel funktioniert das eingangs erwähnte www.telefonbuch.de? Können wir unsere binäre Suche für solch einen praktischen Anwendungszweck eventuell garnicht benutzen und betreiben hier brotlose Kunst, bzw. Arbeit für nur einige Spezialfälle?

Es gibt mit Sicherheit Fälle, in denen es schwer ist binäre Suchbäume zu benutzen, aber ich würde zu behaupten wagen, dass es (fast) immer möglich ist.

Die Idee

Nach irgendetwas wird gesucht werden, sonst können wir natürlich keinen Suchbaum benutzen (aber das ist dann ja auch nicht schlimm). Es stellt sich also nur die Frage, wie wir die Größe von Objekten vergleichen, die keine Zahlen sind.

Wir werden dieses Problem lösen, indem wir uns aus den Suchkriterien einen Schlüssel konstruieren. Wir speichern also wie gehabt primär die Schlüssel in unseren Knoten und wenn jemand nach einem Objekt sucht, übergeben wir die Eingabe einer Funktion, die uns diese Eingabe in einen Schlüssel übersetzt.

Jetzt stellt sich nur die Frage, wie eine solche Funktion aussehen kann und (vor allem) ob sie überhaupt existiert. Um diese Frage zu beantworten, wollen wir uns überlegen, welche Voraussetzung unsere Funktion denn erfüllen muss, damit sie funktioniert.

Was unsere Schlüssel ausmacht, ist dass sie vergleichbar sind und zwei Schlüssel immer in eine der drei Relationen =, gesetzt werden können. Außerdem sind unsere Schlüssel eindeutig, das heißt dass wir keine zwei verschiedenen Knoten haben, die denselben Schlüssel haben.

Wir brauchen also eine Funktion die aus dem, was jemand eingibt auf eine Zahl abbildet und keine zwei verschiedenen Eingaben auf die selbe Zahl abbildet. Das können wir natürlich nicht allgemein machen, eine solche Funktion für Buchstaben sähe natürlich ganz anders aus, als eine solche Funktion für eine Kombination aus Zahlen und Buchstaben.

Ein Beispiel

Bleiben wir doch bei unserem Beispiel des Telefonbuchs. In unserem Telefonbuch wird nach Namen gesucht. Ein Name besteht aus einer beliebigen Kombination von 30 Zeichen (das Alphabet inklusive Umlauten und ß).

Jetzt wenden wir einfach das selbe Konzept an, welches unserem Zahlensystem zu Grunde liegt. Wenn Du dich damit noch nicht vertraut gemacht hast, schaust Du dir am besten nochmal unseren Abschnitt über Binär- und Hexadezimalzahlen hier an.

Auch unser Dezimalsystem ist eigentlich ein endliches Zeichenalphabet (bestehend aus den Ziffern 0, 1, 2, 3, 4, 5, 6, 7, 8 , 9), welches wir mithilfe einer Formel implizit auf die wirklichen Zahlen dahinter abbilden.

Im Dezimalsystem haben wir die Basis 10, denn in Wahrheit steht ja z.B. 15467 für 7*100 + 6*101 + 4*102 + 5*103 + 1*104.

Im Binärsystem sind wir genauso vorgegangen, nur haben wir da die Ziffern 0 und 1 und arbeiten zur Basis 2. Dort ist 10100 = 0*20 + 0*21 + 1*22 + 0*23 + 1*24.

Im Hexadezimalsystem ist der Zusammenhang noch klarer, wo wir ja die Zahlen 10-16 bereits durch A, B, C, D, E, F und G ersetzen. Wir interpretieren also einfach A als 1, B als 2, usw. Schließlich noch ä=27, ö=28, ü=29, ß=30.

Dann haben wir ein endliches Alphabet mit 30 Ziffern (die für die Zahlen 1-30) stehen und damit die Basis 30. So bilden wir dann unsere Funktion analog zu Binär- oder Hexadezimalzahlen ab. Folgende Tabelle gibt einen Überblick, wie das dann funktioniert:

Buchstaben Formel Wert
A 1*300 1
B 2*300 2
C 3*300 3
D 4*300 4
E 5*300 5
F 6*300 6
G 7*300 7
H 8*300 8
I 9*300 9
J 10*300 10
K 11*300 11
L 12*300 12
M 13*300 13
N 14*300 14
O 15*300 15
P 16*300 16
Q 17*300 17
R 18*300 18
S 19*300 19
T 20*300 20
U 21*300 21
V 22*300 22
W 23*300 23
X 24*300 24
Y 25*300 25
Z 26*300 26
Ä 27*300 27
Ö 28*300 28
Ü 29*300 29
ß 30*300 30
AA 1*300+1*301 31
AB 2*300+1*301 32
AC 3*300+1*301 33
AD 4*300+1*301 34
... ... ...
30*300+1*301 60
BA 1*300+2*301 61
BB 2*300+2*301 62
... ... ...
30*300+2*301 90
... ... ...

Sucht beispielsweise jemand nach dem Namen Jo Bach übersetzt unsere Funktion dies zu: 8*300 + 3*301 + 1*302 + 2*303 + 15*304 + 10*305.

So können wir mit 300 jede Zahl zwischen 0 und 29 abbilden, mit 301 30, 60, 90, ..., 870 und die dazwischenliegenden mit der Summe aus den Zahlen, die durch 300 und durch 301 entstehen. 302 liefer 900, 1800, ..., 24300, die Summe arbeitet wieder analog, usw.

Wir sehen also, dass keine Zahl aus zwei verschiedenen Namen resultieren kann (außer durch das nicht beachtete blank zwischen Vor- und Nachnamen, welches wir leicht ändern können, indem wir unsere Basis auf 31 erhöhen und dem blank die Ziffer 31 zuordnen). Und wir bilden offensichtlich auf Zahlen ab, haben unsere Funktion also gefunden!

Anmerkung: Wir haben hier nur am Beispiel unseres Alphabets gearbeitet, aber wenn Du dir die Erklärung für die Eindeutigkeit anschaust, siehst Du schnell, dass wir mit ähnlichen Funktionen das selbe für jede Zeichenkette bestehend aus einer endlichen Zahl an Zeichen machen können.

Wenn Du Lust hast, überlege dir doch einmal, wie eine solche verallgemeinerte Funktion in Abhängigkeit von einem endlichen Zeichenalphabet {a1, a2, ..., an}, also mit n Zeichen aussehen könnte.

X

Fehler melden

X

Suche