Video 9-9: 2-3-Bäume

0:02 Wir hatten gesehen, binäre Suchbäume können alle Operationen, die man so haben möchte, eigentlich effizient unterstützen, aber die Laufzeit hängt von der Höhe vom Baum ab. Die richtige Lösung heißt also, wir müssen die Höhe von dem Baum im Worst Case beschränken. Und es stellt sich raus, das geht und das geht auf vielfältige Art und Weise. Und ähm wir werden das in zwei Schritten machen. Ich zeige Ihnen zuerst die konzeptionelle Lösung, die eigentlich sehr einfach und kompakt ist. Die ist ein bisschen unbequem zum Implementieren, deswegen gibt's dann eine Verfeinerung davon. Aber der wichtigste Teil, der sozusagen das Kernstück der ganzen Vorlesung, wenn Sie so möchten, ist eigentlich dieses hier, denn das zeigt auf schöne Weise, wie man mit einem etwas cleveren Trick eine sehr robuste Datenstruktur bekommt und die auch nicht kompliziert ist. Also Ziel wird sein überall hier ein logarithmisch äh also das ist groß O von äh in jedem Fall gilt glaube ich für alle diese Einträge.

1:06 Also die ganze Tabelle ist groß O von ja äh Ziel wird sein überall logarithmische Worst Case Laufzeit zu haben. Okay, wie machen wir das? Na ja, wir müssen irgendwie die Höhe beschränken. Das war aber irgendwie schwierig, denn wir müssen an beliebiger Stelle einfügen können. Wir müssen also ein bisschen uns mehr Freiraum geben. Wenn wir in der Höhe nicht mehr Freiraum zulassen wollen, dann müssen wir anderen Freiraum schaffen. Und den Freiraum, den wir hier schaffen mit diesen zwei, drei Bäumen, der besteht darin, dass jeder Knoten ein oder zwei Schlüssel speichern kann. Jetzt also jeder Knoten kann entweder so aussehen oder so. Warum heißen die dann zwei drei Bäume und nicht 1 z Bäume? Na ja, aber das sind halt die Anzahl Kinder. Wenn ich einen zwei Knoten habe, hat er ein linkes und ein rechtes Kind und wenn ich ein Dreiknoten habe, hat ein linkes, ein mittleres und ein rechtes. Gewöhnen sich dran. Die Zählweise ist halt für die Anzahl Kinder, nicht die Anzahl Knoten. Kinder sind wichtiger.

2:08 Äh, was wir beibehalten, ist diese Suchbaumeigenschaft, was für den zweierknoten das gleiche bedeutet wie bisher. Und für den Dreiknoten heißt es eben alles hier kleiner als der Schlüssel, dann alles hier zwischen den beiden Schlüsseln und alles hier größer als der rechte Schlüssel.

2:30 Okay, sie könnten sich auch vorstellen, dass man diesen Knoten Ej darstellt als einen Mini bei binären Suchbaum. Statt dieser drei hätte ich dann dieses Konstrukt.

2:52 Das wäre von der Suchbaumeigenschaft das gleiche. Dann sind auch die mittleren zwischen E und J. Links ist kleiner als E, rechts ist größer als J. Das genau gleiche möchten wir für diese drei Knoten haben. Okay, soweit so einfach. Äh, warum sollte mir das irgendwas bringen, dass ich jetzt mehr Knoten äh mehr Schlüssel in einen Knoten packen kann? Äh, die Behauptung ist, das reicht, um eine ganz krasse Inviariante zu kriegen, nämlich alle Pfade von der Wurzel zu den Blättern sind genau gleich lang. Also nicht nur die Höhe ist irgendwie beschränkt, sondern ganz ganz krass balanciert. Alle Fade sind gleich lang.

3:33 Das heißt, es gibt jetzt auch nur noch zwei Arten von Knoten. Es gibt die die nicht Blätter und die Blätter, die nur noch Nullpointer haben. Aber das ist erstmal nur ein ein Ziel, ein Versprechen, dass das am Ende so gehen wird. Wie das denn geht oder warum das denn gehen soll, ist ja vielleicht nicht offensichtlich.

3:57 Ähm, Punkt 1, erstmal, wie wie suche ich in so einem Baum? Und dafür wechsel ich noch mal auf mein meine Animation. Die kann dankenswerte auch diese zwei, drei Bäume malen. Und da habe ich mal wieder welche zufällig erzeugt. Wie suchen wir in so einem äh in so einem 23 Baum?

4:27 Äh, ich fange wie immer mit, ich vergleiche wie immer meinen Schlüssel, den ich suche, mit Schlüsseln im in der Wurzel. Hier in dem Fall habe ich nur ein Schlüssel, das heißt äh ich vergleiche den und da die 666 größer ist als der Schlüssel in der Wurzel 453, gehe ich den rechten Pfad. Das ist wie gehabt. In so einem Dreierknoten mache ich natürlich das Übliche. Ich vergleiche mit beiden Schlüsseln und guck, wie verhält sich die 666 zu den? In dem Fall ist es kleiner als beide. Das heißt, ich verfolge den linkesten der Kindzeiger.

4:58 Ähm, in dem Fall mache ich das gleiche. Jetzt ist größer als beide und dann finde ich das hier in dem Blatt. Äh, vielleicht hätte ich mal ein Beispiel wählen sollen, wo man irgendwo dazwischen landet. Machen wir mal noch äh den hier 616. Dann verfolge ich erstmal den gleichen Fad. Aber hier habe ich jetzt der den Schlüssel, den ich suche, der ist zwischen den beiden. Das heißt, jetzt verfolge ich das mittlere, verfolge den Pfad zum mittleren Kind und da finde ich ihn nicht, weil er nicht in dem Schlüssel gespeichert ist. Okay. Äh, also kurz um, was soll Ihnen das zeigen? Suchen ist einfach. Suchen ist genauso wie vorher. Wenn ich mir im Prinzip vorstelle, dass ich diese drei Knoten intern so handhabe, als wären das mini binäres Suchbäumleinchen ähm in diesem Knoten.

5:48 Vielleicht hätte ich das sogar anders malen sollen. Lass mich mal das anders malen. Eigentlich wollen wir doch das so malen. Ich habe hier intern, da gibt's von oben irgend so ein Eingang. Dann habe ich wirklich ein Miniäumchen im Knoten. Das ist eigentlich die bessere Intuition. Also suchen ist einfach und langweilig. Was machen wir mit Insert? Wir müssen irgendwie Schlüssel einfügen können und dabei tunst die Höhe von diesem Baum oder na ja, nicht die Höhe, sondern müssen die Länge aller Pfade von Wurzel zu Blatt identisch halten, den ganzen Baum. Das ist einfach, wenn das Element, dass ich einfügen möchte, also G hier ist ja gehört in diesen Knoten. Der hat noch Platz für einen zweiten Schlüssel, also packe ich den da rein und bin fertig. An der Stelle sehen Sie jetzt das erste Mal ganz offensichtlich hilft es, dass ich ein bisschen Flexibilität habe in den Knoten, denn ich kann jetzt einfach diesen zusätzlichen Schlüssel aufnehmen, ohne den Baum strukturell zu verändern.

6:52 Kein Pad ist länger oder kürzer geworden. Natürlich passiert das nicht immer so schön. Manchmal möchte ich einfügen Z. Fang hier an. Größer, größer. Bin hier drin. Jetzt äh weiß ich, ich bin an den Blättern. Das sind alles Nullpointer. Ich würde gerne Z hier irgendwie noch in diesen Baum mit aufnehmen, diesen Knoten, aber der hat ja der ist schon voll besetzt. In dem Fall kann ich das nicht. Das heißt, ich habe hier diesen temporären Knoten mit drei Schlüsseln, den ich aber so nicht lassen darf. Das heißt, ich nehme den und befördere das X nach oben. Das heißt, ich mache das hier zu so einem Miniäumchen mit drei zweier Knoten. Damit kann ich mir natürlich Ärger einhandeln, weil das heißt jetzt, ich habe das Problem nur delegiert. Ich habe das X jetzt nach oben geschoben. Das ist so wie eine rekursive Einfügung ein Level drüber. In diesem Beispiel ging das gut, weil der Knoten 1 oben drüber Platz hatte.

7:56 Dann kann ich das X da reinstecken und fertig. Im schlimmsten Fall geht das den ganzen Pfad bis hoch zur Wurzel. Und falls die Wurzel auch schon voll ist und ich auch da diesen Schritt machen muss, dann und nur dann wächst der Baum mal um ein Level größer. Alle anderen Schritte hatten das ja gar nie bewirkt. Irgendwann muss der Baum ja aber mal wachsen dürfen. Okay. Äh auch dazu vielleicht in aller Kürze ein paar Beispiele. Ich fange mal mit einem äh kleineren Baum an. Wir machen das mal vielleicht ohne Animation. Der fügt jetzt zufällige ein. Ähm ich mache mal ein Z. So. Jetzt machen mal hier ein bisschen langsamer. Also, wir fügen ein neues Element ein. 865. Das ist größer als alles hier. Das heißt, es wird in den rechten Baum eingefügt werden. Da habe ich Platz. Plup, mache ich einen zweierknoten draus und fertig. Ja, machen wir noch einen. Ähm, das hier ist kleiner. Das wird in den linken Teilbaum eingefügt. Da habe ich auch noch Platz.

8:59 Werde ich Platz schaffen. Passiert. Äh, mal schauen, was jetzt passiert. Aha. Äh, wir sind wieder im rechten Teilbaum. Der ist zu groß. Kann ich so nicht lassen. Der hat keinen Platz. Also erstmal temporär können wir uns vorstellen, kommt er da rein. Aber jetzt muss ich eben hier diesen mittleren Knoten nach oben packen. Und jetzt habe ich hier wieder ein Problem. Wieder zu groß. Das heißt, der äh teilt sich noch mal auf und jetzt ist der Baum um eins gewachsen. Okay.

9:34 Langenswerterweise ist das aber auch alles. So funktioniert das Einfügen in diesen zwei drei Bäumen. Ähm der Schlüssel war, dass diese Transformation, die wir ab und zu machen mussten, nämlich aus so einem Vierknoten, der drei Schlüssel hat, was jetzt nicht erlaubt war, einen zu machen, der wieder gültig ist. Das ist eine lokale Transformation. Auch wenn ich das ähm irgendwo in der Mitte vom Baum machen muss, was mir ja dann beim Aufstieg passieren kann, ist es nur eine lokale Änderung von der Handvoll Pointern, also ein bisschen eine größere eine Alien Handvoll von Pointern, aber konstant viele, die ich ändern muss. Deshalb geht das immer noch in konstanter Zeit pro äh Level im Baum und damit in konstanter Zeit ähm mal der Höhe.

10:27 Dadurch, dass diese Bäume so wunderbar balanciert sind, sprich von der Wurzel zum Platz sind immer gleich viele Schritte, können wir ähm relativ starke Eigenschaften zeigen. Also erstmal diese Invariante, die bleibt erhalten, weil Insert sie nicht kaputt macht. Ähm ist hier noch mal gezeigt, also nur an der Wurzel kann ich überhaupt wachsen. Ähm und dann sind hier noch die anderen Fälle aufgemalt. Wenn ich so einen vierknoten aufspalte und der das der Elternknoten ist ein Zweiknoten, dann nimmt er einfach das Element auf und die Höhe von keinem der Pfade hat sich verändert. Ja, diese ganzen Blätter hier unten, die waren auf Höhe 2 hier und die sind es immer noch und symmetrisch, wenn ich auf der rechten Seite bin. Ähm etwas spannender passiert es, wenn mein Elternknoten auch voll ist. Ja, dann äh habe ich hier diesen Knoten erzeugt, der jetzt auch wieder übervoll ist. Aber der wichtige Punkt ist, die die Tiefe dieser ganzen Blätter, die hier drunter hängen, die bleibt gleich. die wandern nicht hoch oder runter, die bleiben genau auf der gleichen Höhe vertikal gesehen.

11:39 Und das ist auch ähm in jedem der drei möglichen Fälle, wo dieser über äh fließende dieser über vollle Knoten liegt, ähm ist es das gleiche Ergebnis. Ja, hatten sie glaube ich in der Animation einfach direkt gesehen.

11:55 Ähm vielleicht noch mal einfach etwas schneller mit ein paar mehr Beispielen. Also, wir fügen noch ein paar mehr Knoten ein und sie achten, sie achten einfach mal nur darauf, dass an keiner Stelle irgendwie ein Fah von der Wurzel zu den Blättern anders lang ist. Selbst wenn da auch mal ein bisschen mehr gespalten wird.

12:22 Jetzt wird's dann mal knallen. Irgendwann schlägt's auf die Wurzel durch. Genau. Äh da wächst dann das ganze mal, aber es war wandern dann eben, wie Sie sehen, alle Blätter gleichzeitig ein Level nach unten. Okay. Ähm Beweis durch Beispiel ist natürlich so eine Sache, aber im Prinzip gibt es nur diese Fälle, die hier auf der Folie sind und in jedem dieser Fälle äh ändert sich die Höhe der Blätter nicht. Also per Induktion ist die Invariante erfüllt. Da das der Fall ist, können wir die Höhe von diesem Baum genau ausdrücken. In Anzahl Knoten ist sozusagen die der die Länge von der Wurzel zu jedem Blatt gleich. Was heißt es jetzt über die Anzahl Schlüssel, die da gespeichert sind? Da gibt's halt den besten und schlimmsten Fall. Der Worst Case ist bezüglich für die Anzahl Schlüssel, wenn ich in jedem Knoten nur einen Schlüssel habe. Und der Best Case ist für die Höhe, wenn ich den Baum so voll packe wie möglich und dann kriegen sie halt einfach diese zwei Extremfälle.

13:23 Ähm, der eine ist wie der perfekt balancierte binäre Baum und der andere ist jetzt ein bisschen besser in der Höhe, weil wir ja mehr pro Knoten unterbringen. Also, wenn jeder wenn jeder Knoten ein Dreiknoten ist, dann verzweige ich immer in drei Teile. Also mit jedem Schritt drittle ich die Anzahl Schlüssel, die noch in den Teilbäumen sind. Nach log zur Basis 3 von n. solchen Drittlungsschritten bin ich bei leer und damit ist das die Höhe für diesen Baum im Bestase. Aber der wichtigere Punkt ist ja selbst im schlimmsten Fall ist die Höhe logarithmisch beschränkt. Das ist für die ab für die Operationen wichtig.

14:09 Das heißt, damit haben wir das erste Mal eine konzeptionelle Implementierung, die diese ähm alle Operationen in logarithmischer Zeit unterstützt. Äh, ich möchte vorgeben, dass wir über Delete noch nicht gesprochen haben. Ich verspreche Ihnen sozusagen vorab, das wird gehen, aber wir werden heute nicht mehr die Zeit haben, das äh im Detail zu besprechen.

14:37 Bleibt die Frage, wie würde ich das in Java implementieren? Und die Antwort ist hier so ein bisschen ähm aufgeschrieben mit dem Titel Fantasy Code, denn so wie es da steht, geht's leider nicht direkt. Das ist jetzt mehr so ein bisschen, denken Sie mal ein bisschen darüber nach. Natürlich geht es, ich kann das machen, aber es ist aus verschiedenen Gründen ein bisschen unbequem. Ich habe diese zwei Knotentypen, die ich irgendwie handhaben muss. Entweder verschenke ich Platz oder ich habe zwei Typen. Beides ist ein bisschen nervig. Ähm, ich habe diese in den Knoten die Vergleiche. Es ist ähm bisschen aufwendiger als wenn ich das äh systematischer habe wie in den normalen binären Suchbäumen. Äh wir müssen auf dem rekursiven Aufstieg wiederum äh noch was arbeiten. Das war zumindest in den binären Suchbäumen nicht der Fall. Aber letztlich der der Hauptpunkt ist, dass es relativ viele Fallunterscheidungen gibt, weil ich an jeder Stelle mich fragen muss, welchen Typ haben die Knoten, die da jetzt gerade involviert sind und was passiert in dem Fall. M.