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