Video 9-6: Binäre Suchbäume

0:01 Im nächsten Abschnitt schauen wir uns endgültig die Lösung an für das sortierte Symbolta Table Problem, von dem wir losgelaufen sind. Die Antwort wird binäre Suchbäume heißen. Noch mal zurück. Ähm was war das Problem bei den Symle Tables? Die einfachen Ansätze, die wir verfolgt hatten mit den linearen Listen, waren einfach nicht flexibel genug. Aber diese binären Bäume, wie sie Hiebs verwenden, die scheinen ein bisschen mehr Flexibilität zu erlauben, weil man mit diesen nicht nur ein Nachfolgerzeiger, sondern linker und rechter Nachfolger, also linkes rechtes Kind bisschen mehr ähm bisschen mehr Power hat, um Dinge schnell zu erreichen. Mal ganz wolkig gesprochen. Insbesondere gab es von der Wurzel ja ganz viele, aber alle kurze Pfade. Von der Wurzel kann ich jeden Knoten erreichen in logritten, zumindest wenn ich weiß, wo ich hinlaufen muss. Die Form von den HEBS ist aber zu star. Das kriegt man irgendwie nicht hin, dass man damit die allgemeinen äh Symbolle Tables implementiert. Also ist unsere unser Ansatz hier bei der Idee von binären Bäumen zu bleiben, aber nicht mehr diese starre Struktur von komplett ähm vollständig und nur das letzte Level so ein bisschen äh linksbündig.

1:22 Umgekehrt ist die Hiebordnung wiederum nicht streng genug. hatte ich schon angedeutet, wenn ich statt dem Maximum das Minimum suchen will, bin ich schon aufgeschmissen. Das kann fast überall sein und jeder andere Wert ist fast genauso schlimm. Ähm, da ist also das nicht stark genug. Wir wollen also etwas mit sortierter Reihenfolge. Nur dann kann ich sinnvoll Effizienz suchen. Aber was heißt das denn jetzt, dass ein Baum sortiert ist?

1:55 Na, die passende Eigenschaft ist diese fällt jetzt auch ein bisschen ähm vom Himmel. Sie werden aber gleich sehen, warum die ganz natürlich ist. Die Suchbaumeigenschaft sagt, der Schlüssel in der Wurzel von dem Baum ist größer als alles im linken Teilbaum, aber kleiner als alles im rechten Teilbaum. Und das gleiche gilt rekursiv in allen Teilbäumen. Also an jedem Knoten ist alles, was links davon im Teilbaum steht, kleiner als dieser Knoten und alles, was rechts davon steht, ist größer als dieser Knoten. Das ist die Eigenschaft. Warum ist das genau die richtige Eigenschaft? Na, wir möchten in diesen Konstrukten suchen können. Wir möchten effizient finden können. Ist ein Schlüssel vorhanden? Ja, nein. Ähm, was sind die Schlüssel, die nahe bei ihm sind? In sortier Reihenfolge, Floor und Ceiling, diese Sachen. Und auch einfügen möchte ich irgendwie mit binärer Suche starten können. Also, versuchen wir mal nach einem Schlüssel hier zu suchen, z.B.

2:58 die 79. Von dem binären Baum habe ich eigentlich immer nur die Wurzel als Einstiegsstelle. Also auch hier bleibt mir eigentlich gar nicht viel übrig, als bei der Wurzel anzufangen. Und jetzt sagt uns die Suchbaumeigenschaft, wo wir hin müssen, denn 79 ist größer als 77. Sprich, alle Schlüssel hier links sind ja kleiner als 77, also erst recht kleiner als 79. Das heißt hier, den ganzen Teilbaum hier, den brauche ich mir gar nicht angucken. Das ist genau, was bin Suche auch getan hat. Ich bin in die Mitte von dem Array gesprungen und habe gefragt, welche Hälfte kann ich komplett ignorieren für den nächsten Schritt? Hier ist es nicht so ganz perfekte Hälfte, aber ein Teilbaum von zweien immerhin. Wenn ich also links nicht suchen muss und die Wurzel nicht 79 speichert, dann suche ich weiter im rechten Teilbaum. Und da frage ich mich wieder, ist die 79 größer oder kleiner als dieser Schlüssel hier? In dem Fall ist sie kleiner. Das heißt, wir müssen nach links und können den rechten Teil ignorieren.

4:05 Bei der 80 passiert das gleiche. 79 ist wieder kleiner. Das heißt, wir gehen nach links und an der Stelle finde ich jetzt die 69 und kann dann tun, was auch immer so ein äh so eine Simple Table tun sollte. Das kommt jetzt drauf an, was ich eigentlich gemacht habe. Suche ist so ein allgemeines, finde mir den passenden Knoten. Ich könnte da jetzt den gespeicherten Wert zurückgeben oder ich könnte den Wert überschreiben. Put, all diese Dinge sind dann konzeptionell von dem Algorithmus, der abläuft, sehr ähnlich.

4:40 Ein bisschen Notation dazu. Ähm, hatte ich teilweise schon so verwendet. Hier sind noch mal auch die englischen Begriffe dazu. Wir haben von dem Baum eine Wurzel. Wir haben ein linkes und ein rechtes Kind oder eine Kante zu einem linken und rechten Kind. Ein Teilbaum ist ein Knoten mit allem, was darunter ist. Ähm auch intuitiv, denke ich. Äh in den Bildchen hier sind diese Nullpinter so eingezeichnet mit Strichen. Ich habe den noch so eine kleine Box verpasst, dass man sie auch nicht übersieht. Ähm das sind aber ein wesentlichen Stellen, in denen der Baum einfach zu Ende geht. Ich habe die Nullpointer genannt in im Vorg darauf, wie wir sie ja implementieren. Ähm die Suchbaumeigenschaft ist in der Literatur manchmal auch als Symmetric Order bezeichnet. Äh finde ich weniger intuitiv, obwohl Suchbaumeigenschaft ist vielleicht nicht selbsterklärend. Suchbaum ist ein Suchbaum ist ein Baum mit Suchbaumeigenschaft. Ähm können sich aussuchen, was Ihnen lieber ist. Ähm heißt aber genau das gleiche. Ja, alles im ähm linken Teilbaum ist kleiner als die Wurzel. Äh und alles im rechten Teilbaum ist größer.

5:49 Wir machen keine volle Implementierung heute, aber ich möchte Ihnen kurz schon sagen, wie wir das äh wie wir die Knoten oder den Baum in Java repräsentieren werden. Es wird eine Klasse Knoten geben, so wie es auch eine Knotenklasse für die verketteten Listen gab. Und tatsächlich sieht die auch ähnlich aus. Ich habe einen Schlüssel und einen Wert, den ich hier speichere. Und bei der Liste hatte ich eben Zeiger für Vorgänger Nachfolger eventuell. Hier habe ich Zeiger für linkes und rechtes Kind. Und das sind eben Referenzen auf andere Note Objekte. Äh, sie können das natürlich so malen, dass das sozusagen ähm rekursiv ineinander enthalten ist oder sie erinnern sich an dieses Python Tutter mit jedes Objekt ist eine Box und die haben eben links zweeinander, dann wäre eben einfach die Wurzel ein so eine Box, die Wurzel vom linken und vom rechten Teilbaum wäre eine Box und dann wäre hier der linke Zeiger und der rechte Zeiger dementsprechend auf diese Objekte gebogen.

6:56 Also im großen und ganzen ähm gar nicht so anders von der Interface wie verkettete Listen, aber wir werden diese Zeiger für linken und rechten Teilbaum natürlich anders verwenden, damit ähm das so einen Suchbaum mit der Suchbaumeigenschaft gibt.

7:19 Und äh ganz ganz grob schon mal die grobstruktur der Klasse, die wir dann implementieren werden, sieht so aus. Äh da gibt's dann die ganzen Operationen, die so eine Symboltabelle haben soll. Und wir haben die Knoten wieder als statische innere Klasse, die sollte wir vermutlich möchte man die statisch haben. Es ist jedenfalls eine innere Klasse von dieser ähm binäre Suchbaumklasse. BST steht für Binary Search Tree.

7:53 Sie brauchen in der Algorithmik gar nicht so viele Akronyme im Vergleich zu der technischen Informatik wissen, aber BST, BST sollten Sie kennen, weil das einfach sehr gebräuchlich ist. Und als letztes ähm ist hier noch der Code für die Suche, die wir eben am Beispiel schon besprochen hatten. Wenn ich einen Schlüssel in so einem Baum suche, fange ich an der Wurzel an. Solange ich noch nicht bei einem Nullpointer angekommen bin, vergleiche ich meinen Schlüssel mit dem Schlüssel in diesem Knoten. Wenn die gleich sind, dann habe ich den entsprechenden Knoten gefunden und für GET gebe ich dann den gespeicherten Wert zurück, der mit diesem Schlüssel assoziiert ist. Und für die beiden anderen Fälle habe ich, was wir im Beispiel hatten, entweder einen oder den einen oder den anderen Teilbaum ausgeschlossen. Wenn mein Schlüssel, den Schlüssel, den ich suche, kleiner ist als der Schlüssel im Knoten, dann gehe ich zum linken Teilbaum und wenn mein Schlüssel größer ist, dann gehe ich in den rechten Teilbaum.

8:55 Okay, also eine einfache äh kompakte rekursive Prozedur, die im Wesentlichen das macht, was binäre Suche auch macht. Aber statt, dass wir Indizes in Array äh einschränken und immer engere Bereiche anschauen, verfolgen wir Pointer Referenzen auf Teilbäume. Ja.