Video 9-11: Red-Black Trees Operations

0:01 Dann sollten wir an der Stelle noch mal einsteigen. Wir hatten uns schon kurz angeschaut, wie man diese äh rotarzbäume verwenden kann, um zwei, drei Bäume zu realisieren, ohne dass man diese zwei Arten von Knotentypen hat. Ich habe den auch hier schon so ein paar Beispiele letztes Mal gezeigt, wo man das dynamischer umschalten kann. Also, ich habe hier äh einen 23 Baum. Wenn Sie mal das so tun, als wären diese gestrichelten Linien solide Knoten, dann ist es hier ein zufälliger Baum. mit manchmal drei äh manchmal drei Knoten, also mit einem drei Knoten, mit zwei Schlüsseln pro Knoten noch ein paar ähm uns anschauen oder auch ein paar größere. Ähm und dementsprechend ist das einem eine äh Variante von zwei drei Baumen, aber ich möchte die so darstellen, dass jeder Dreiknoten ein ähm Minibaum aus zwei Knoten ist mit einer roten Kante dazwischen. Und Ihnen fällt vielleicht hier auch schon auf, alle roten Kanten neigen sich nach links.

1:05 Das wäre grundsätzlich konzeptionell, wenn man hier äh in dieser 23 Welt lebt. Egal, ob diese Kante nach links oder nach rechts geht, das wäre beides in Ordnung. Ähm, das stellt sich auch heraus, es gibt beide Varianten und ähm die gebräuchlichere und ältere Variante aus diesem ersten Paper ist auch tatsächlich die Variante, wo es uns egal ist, ob die Kante nach links oder nach rechts geht, wenn es eine rote Kante gibt. Aber stellt sich raus, dass man einige Fälle entfernen kann, wenn man zu dieser moderneren Version von den Left Leaning Red Black Trees übergeht, wo wir also die rote Kante immer nach links haben möchten, so wie es auch hier ähm in der Animation ist. Also, wenn wir einen Dreiknoten haben, dann soll die rote Kante bitteschön immer nach links runter zeigen. Das ist eine strengere Invariante, die wird dafür sorgen, dass wir ein paar weniger Fälle haben und dadurch den Code deutlich kompakter machen.

2:19 Okay. Ähm, sonst hatten wir hier, glaube ich, alles mittlerweile abgehakt. Wie können wir mit diesen Bäumen suchen? Ähm, okay. Äquäquivalente Definition. Ich hatte ihn das letzte Mal kurz angeteasert. Je nach Lehrbuch finden Sie manchmal auch nichts über zwei dreibäume. Und stattdessen diese Definition, das ist ein spezieller Suchbaum, in dem die Knoten Farben haben können. Oft es so formuliert, dass ein Knoten rot ist, weil die Kante zu ihm rot ist. Das äh würden wir werden wir auch so implementieren, weil wir nur für die Knotenobjekte haben. Das heißt, da können wir so ein Bit speichern für die Farbe. Gemeint ist aber die Kante zu den zum Elternknoten.

2:59 Und dann ist ein solcher gefärbter Baum, ein gültiger rotschwarzbaum, wenn ich niemals zwei rote Kanten hintereinander habe, wenn jeder Pfad von der Wurzel zu einem Blatt die gleiche Anzahl schwarzer Kanten hat. Und zusätzlich hier für die left leaning Red Black Trees, wenn alle roten Kanten, wenn es einzeln sind, sich nach links lehnen.

3:20 Äh, um das Ganze noch verwirrender zu machen, gibt's auch noch Varianten, die 2 3 VI Bäume implementieren. Ich sage ihn das jetzt nicht, um sie noch mehr zu verwirren, sondern um sie zu warnen. Wenn Sie anderswo über Rotchwarz Bäume lesen, dann werden sie mindestens drei verschiedene Varianten finden. Tut mir leid, ist aber irgendwie nicht zu ändern. Ähm, wenn Sie die Variante sehen wollen, die ähm hier im im Modul verwendet wird und auch die Animation dazu, dann können Sie die von mir gebaute nehmen. Da habe ich halbwegs überprüft, dass das wirklich zu dem Code passt, den wir auch hier in der Vorlesung diskutieren. Also, man könnte auch äquivalent den Rotchwarzbaum so definieren, nur weiß man dann glaube ich gar nicht mehr, wo das herkommt.

4:06 Der Vorteil von diesem Left Leaning, abgesehen davon, dass es einen Fall entfernt ist auch, dass wir jetzt eine eins z ein Korrespondenz haben oder eine Biektion, wenn sie mögen, zwischen den Left leaning Red Black Trees und diesen zwei drei Bäumen, denn es gibt jetzt für jeden zwei, drei Baum genau eine eindeutig bestimmte Darstellung als Rot-Schwarzbaum und für jeden gültigen Rot-Schwarzbaum gibt's genau einen, zwei, drei Baum. Ähm, dementsprechend werden manche Sachen einfach dadurch ein bisschen eleganter.

4:40 Jetzt wollen wir das als Datenstruktur verwenden und nicht nur als kombinatorische Kuriosität. Äh, der einfachste Teil ist die Suche, denn auch dazu vielleicht [räuspern] einfach noch mal hier auf dieses Beispiel etwas größerer. Ähm, was muss ich ändern, um in diesem binären Suchbaum äh nach einem Schul zu suchen? Antwort: Gar nichts, denn der ist so wie er ist ein binärer Suchbaum. Ich ignoriere diese Farben einfach. Die haben mit dem mit der Suchbaumeigenschaft nichts zu tun. Das heißt, genau der gleiche Code, den wir vorher hatten für die Suche. Das war jener hier ähm funktioniert auch jetzt noch. Äh itterativ geschrieben, wir fangen bei der Wurzel an und vergleichen immer den Schlüssel, den wir suchen mit dem Schlüssel in der Wurzel und gehen entsprechend nach links oder nach rechts. Oder wir sind an der Stelle, wo der Schlüssel selbst ist. Dann kann ich je nachdem, was ich möchte, wenn ich Get möchte, dann kann ich zurückgeben, welcher Wert mit diesem Schlüssel assoziiert ist.

5:34 Sie kennt das Spiel. Auch die anderen Operationen, die nur lesend auf den Baum zugreifen, bleiben im Wesentlichen unverändert. Sie können sich so im im Hinterkopf Selection war dieses Rang nach Selection by Rank. Sie können da schon mal im Hinterkopf behalten. Wir werden wahrscheinlich auch wieder Teilbaumrößen pflegen wollen, um die volle ähm die volle Operationsspanne von diesen Order Symle Tables zu implementieren. Da müssen wir uns dann bei den Updates auch wieder drum kümmern, dass die aktuell bleiben. Aber erstmal soweit ist äh alles beim Alten. Alle lesenden Operationen können einfach die Farben ignorieren und arbeiten auf einem Suchbaum wie bisher.

6:22 Wie speichern wir jetzt diese Farben? Ich hat's schon angedeutet. Wir werden eine Klasse für die Knoten, aber nichts für die Kanten haben. Dementsprechend haben die Knoten ein eine bullche ein bullsches Feld ähm Farbe und ich habe einfach zwei Konstanten, die für rot und blau schwarz stehen. Ich könnte natürlich da auch immer true und false schreiben und mich immer verwirren. Ähm, das ist so ein bisschen best practice, den Dingen immer ein Namen zu geben. Man könnte an der Stelle auch stattdessen einen Innamen verwenden.

6:58 Kleine Performance Tradeoffs an der Stelle wahrscheinlich nicht groß relevant. Ähm da gibt's ein einen schönen Trick, wenn man das in der Lowlevel Sprache wie C++ macht, dass man diese Farbe, dieses eine Bit in die Pointer mit reinschmuckelt, dann kostet es nicht mal extra Speicher. Äh kann man in Java nicht machen und vielleicht wollen wir das auch hier gar nicht mal. Okay, also sonst ändert sich nicht viel. Wir speichern in jedem Knoten seine Farbe und die Farbe gehört zur Kante zu den Eltern und es gibt eine Methode, die das nachprüft und da möchte ich drauf hinweisen, dass sie so ein bisschen trickreich geschrieben ist. Im Prinzip sind diese Farben rot und schwarz ja symmetrisch. Wenn ich ähm das Feld hier überprüfe, dann ist es entweder rot oder schwarz, nicht? Wah! Äh diese Methode ist red, die darf ich aber auch aufrufen auf so einem Nullpointer. Da hatten wir bisher, da gibt's kein Objekt für. Das heißt, ich kann nicht in ein Level druntergehen, um die Farbe auszulesen. Und da muss man jetzt einfach eine Konvention treffen, welche Farbe die haben sollen. Macht wahrscheinlich so, wie die Bäume dann aufgebaut sind, nicht mal einen Unterschied. Aber hier ist die Definition eben, dass die äh schwarz sind.

8:09 Deswegen merken Sie sich, dass man diese Methode is red aufrufen kann, auch wenn das Argument null ist, wenn ich das auf einem Nullpointer habe. Das ist manchmal dann wieder für den Abbruch in der Rekursion bequem.

8:29 damit wissen wir, wie die Dinge im Speicher aussehen. Sie sehen, insbesondere left and right Key und Value sind unverändert, deswegen funktionieren die Suchoperationen nach wie vor. Jetzt wollen wir aber auch einfügen können in so ein Brotschwarzbaum, genauso wie wir es bei den zwei drei Bäumen gemacht hatten. Weil das ein bisschen her ist, lassen Sie mich vielleicht noch mal ganz kurz die Erinnerung auffrischen.

8:52 Sollten heute eigentlich genug Zeit haben auch mit ein paar extra Parten extra ausflügen. Das hier war noch mal so ein ähm 23 Baum. Ähm, wir fügen einen zufälligen Schlüssel ein. 348. Wie machen wir das? Wir suchen erstmal, wo der Schlüssel wäre, wenn er schon im Baum ist. Äh, in diesem Fall ist er nicht im Baum. Ich vergleiche den Schlüssel mit der Wurzel. Der ist kleiner, das heißt der geht in den linken Teil bauen. In dem Dreiknoten habe ich drei Optionen. Der hier ist größer als alle beiden Schlüssel. Das heiß geht in den rechten Teilbaum. Hier habe ich wieder drei Knoten. Kleiner als beide geht nach links. Wenn ich an den Blättern angekommen bin, dann büge ich diesen Knoten hier in den Sch den Schlüssel in den Knoten ein, sofern hier noch Platz ist. In diesem Fall kann ich aus dem zweiknotenen drei dreiknoten machen und habe aber den Schlüssel damit untergebracht. Ähm, wenn wir jetzt noch so eine Einfügung machen, Glück gehabt mit dem Schlüssel.

9:57 der wandert auch wieder hier rein in das gleiche Blatt. Jetzt habe ich keinen Platz mehr für den Schlüssel. Das heißt, das ist erstmal ein vierknoten, den wir aber nicht so belassen. Wir nehmen das mittlere Element und äh schieben das in den Elternknoten. Das ist rekursiv eine Einfügung, die hier auch wieder dazu führt, dass sich das aufspaltet. Und dann passiert das Ganze noch mal und noch mal und dann sind wir an der Wurzel fertig. Hätte auch manchmal noch ein Level höher gehen können, dann wächst der Baum eine Ebene. So ging das in den zwei drei Bäumen. Also, erster Schritt, wir suchen das passende Blatt. Zweiter Schritt, wir fügen den neuen Schlüssel ein. Dritter Schritt, wir reparieren nach oben, falls wir jetzt unzulässige vierknoten produziert haben.

10:48 Das gleiche machen wir äh natürlich auch in unseren Left Leaning Red Black Trees, denn die sind ja im Prinzip ein 23 Baum äh in versteckter Form.

10:57 Das heißt, wir müssen während dieser Operation ähm die Suchformigenschaft erhalten und wir werden uns insbesondere strick dran halten, dass die Höhe von dem 23 Baum nicht verletzt wird, nicht verändert wird. Also, was meine ich mit Höhe nicht verletzt wird? Alle Blätter sollen gleich gleich hoch sein und gleich lang gleich weit von der Wurzel entfernt sein. Das betrifft die die schwarzen Kanten. Ähm, wie machen wir das in so einem Rot-Schwarzbaum? Da können wir müssen wir irgendwie abbilden, wie wir diese äh drei Operationen haben. Einen Knoten in ein einen neuen Schlüssel in einen Knoten einfügen, einen Schlüssel ähm aufspalten, der in vier Knoten geworden ist, all diese Operationen. Und die zwei ähm Grundoperationen, die man dafür verwenden kann, sind Rotationen und Color Flips.

11:48 Ich zeig's Ihnen auf der Folie kurz und dann aber noch mal in der Animation, wo es viel viel klarer zu sehen ist, glaube ich. Eine Rotation ist bezüglich einer Kante und dreht diese Kante hier von einer Kante, die von einem Knoten zu einem rechten zu einem linken rechten Kind wandert, so rum für sie. ähm zu einer, die jetzt nach links wandert, indem ich den Knoten S zum Elternknoten von E mache. Das heißt, S wandert ein Level hoch, E wandert ein Level runter und die Teilbäume bleiben im Wesentlichen an ihrer Position.

12:29 Also, es sieht dann so aus, sieht man aber hier nicht ganz so gut. Äh, was ich sehe, nebendran ist der Code, der ganz klar zeigt, dass ich da nur eine Handvoll Referenzen umbiegen muss. Ähm, ich würde aber behaupten, viel klarer sehen Sie es in dem Beispiel, wo sich das langsam bewegt. Also noch mal hier rüber.

12:54 Das hier ist ein binärer Suchbaum. Der hat jetzt erstmal nichts mit Rot-Schwarzbäumen zu tun, denn Rotation kann man in jedem binären Suchbaum durchführen. Das ist eine lokale Operation, die die Struktur des Baums verändert, aber nicht die Suchbaumeigenschaft verletzt. Darum darum geht's. Ich habe jetzt hier mal diesen Knoten ausgewählt. Das heißt, wir werden diese Kante rotieren.

13:19 Also, das ist die Kante, die jetzt verändert wird. Und hier sind die drei Teilbäume, die äh sozusagen mit bewegt werden. Wichtig ist aber, dass sich die Teilbäume selbst gar nicht verändern, sondern die werden genau in dieser Reihenfolge und unverändert, wie sie sind, wieder in den Baum eingehängt, aber sie verschieben sich ein bisschen. Also, was passiert? Ähm, dieser Knoten, dieser, der jetzt das Kind ist, wird das neue wird der neue Elternknoten von dem bisherigen Elternknoten. Und der Elternknoten von diesem bisherigen weiter oben befindlichen Knoten, der zeigt jetzt auf diesen Knoten. Und umgekehrt äh müssen wir bei den Kindknoten auch noch eine Änderung vornehmen. Diese zwei ähm Referenzen bleiben unverändert, aber der hier hat ja jetzt ähm dieses Kind verloren. Das heißt, der adoptiert jetzt den grünen Teilbaum in der Mitte. Und wenn Sie das ähm in diesem hin und her bewegen sehen, dann dann dann wird, glaube ich, klar, wie wenig sich im Baum verändert. Insbesondere verändern sich diese drei Teilbäume intern nicht. Es verändert sich die relative Linksrechtsreihenfolge aller Knoten nicht. Also die Suchbaumeigenschaft bleibt erhalten. Das einzige, was sich wirklich ändert, ist die Elternkindbeziehung dieser beiden Knoten. Das ist das einzige. Und weil das so ein paar Auswirkungen hat, wie eingehende Kanten nach oben und unten verlaufen können, muss ich auch den Elternknoten und diesen einen Kindknoten aktualisieren. Da springen die Kanten sozusagen von einem zu einem anderen Knoten. Okay, ich kann das Ganze auch wieder rückgängig machen, indem ich die gleiche Rotation einfach noch mal mache und dann sind wir wieder da, wo wir waren. Ich hoffe, sie sehen optisch. Wir sind jetzt äh also eine umkehrbare Operation. Ich kann hin und wieder zurückrotieren. Ist vielleicht offensichtlich, aber ähm hilft, glaube ich, einfach um zu verstehen, warum das äh funktionieren kann.

15:25 Also hier noch mal im Code ist ähm aufgeschrieben, welche Referenzen ich umbiegen muss. Und äh vielleicht sollten wir auch noch mal präzise sein, wie das Rot wie das Rotieren hier funktioniert. Wir haben keine Elternzeiger, keine Referenzen auf den Vater Elternknoten. Das heißt, um diese Rotation durchführen zu können, müssen wir irgendwie ähm an die Knoten rankommen. Wir starten die Rotation mit einer Referenz auf den oberen der beiden Knoten, deren Kante rotiert werden soll. Das ist anders als in der Animation. Da hatte ich auf den Knoten geklickt, dessen Elternkante rotiert werden soll. Nicht verwirren lassen. Hier bekommen wir den oberen Knoten, weil nur von dem kann ich dann diese passende ähm Kante angeben. Woher weiß ich jetzt, welche der beiden Kindkanten ich rotieren soll? Na ja, weil Rotate left nur Sinn macht mit der Kante nach rechts, mit dem mit der rechten Kindkante. Und es gibt eine symmetrische Operation äh Rotate, die das gleiche in die andere Richtung tut.

16:33 Ja, noch einmal zurück. Ähm, ich kann also zu diesem Knoten hier kommen, weil ich den Kindzeiger verfolgen kann. Ich kann zu diesen drei Teilbäumen kommen, indem ich die Kindzeiger verfolge. Aber ich habe ja auch den Elternknoten zu aktualisieren. An den komme ich nicht dran. Wir haben keine Referenzen auf die Eltern dieser Implementierung. Deshalb geben wir hier wieder den neuen die neue Wurzel von diesem Teilbaum zurück, damit dann rekursiv der Aufrufer von dieser Methode die Referenz setzen kann, die hier von oben kommt. Okay, das ist das gleiche Muster wie den ganzen Operationen und macht den Code sehr kompakt, aber ich glaube, es ist subtil genug, dass man noch mal drauf hinweisen muss.

17:13 Also sehen hier, X ist dann der neue Elternknoten, auf den sollte der Zeiger von oben zeigen. Das Rotieren nach rechts ist das gleiche symmetrisch. Ähm, im Code kommt man nicht, um hier das zweimal aufzuschreiben. Sofern man eben die Kindzeiger anders benannt hat, kann man das nicht symmetrisch bauen. Ähm, funktioniert aber genauso.

17:43 Es gibt hier noch eine Besonderheit, ähm, die ich vielleicht noch hervorheben möchte. Äh, wir setzen hier immer diese Farbe auf rot. Das liegt daran, dass wir diese Rotation in den Rotschwarzbäumen nur an dieser Stelle verwenden, um eine rote Kante nach links und rechts rotieren zu lassen. Wenn Sie diesen Teil streichen, haben Sie eine allgemeine Rotationsmethode, die auch für andere Arten von balsierten Suchbäumen verwendet wird. Können Sie aber für die Vorlesung hier vergessen, wir belassen es bei dieser einen Variante von rotchwarzbäumen. Ich denke, die reicht. Es gibt noch so einen einen kleinen Zoo von anderen Alternativen Möglichkeiten, wie man die bauen kann. und viele davon bauen auf solchen Rotationen auf. Da würde der Farbteil dann wegfallen. Okay, das heißt, wir können nach links und nach rechts rotieren. Der die dritte Operation, die wir verwenden, um die Balance in diesen rotchwarzbäumen wiederherzustellen, ist ein ein Color Flip. Wenn ich so einen temporären Vierknoten habe, sie erinnern sich, das hier heißt eigentlich, ich habe einen Vierknoten, denn die sind ja die roten Kanten sind ja ähm Intraknotenkanten, das sind quasi fake.

18:52 Die gibt's nicht wirklich im 23 Baum. Was aber hier ist, ich habe hier einen Vierknoten. Das kann ich nur haben in so einer temporären Situation nach dem Einfügen. Dementsprechend muss diese ähm dieser mittlere Knoten jetzt nach oben und die beiden formen dann so einen Dreiknoten ohne den mittleren. Das heißt, ich möchte von dieser Konstellation gehen zu einer ähm na Quatsch mit dem Dreiknoten. Die werden ja zu einzelnen Woher so? Hinterher sind das drei zween. Äh, wie mache ich das? Na ja, hier die Kanten möchte ich einfach schwarz machen und den oberen, den möchte ich in den Elternknoten einfügen. Also wird die Kante hier nach oben rot. Damit ist der Knoten dann automatisch in den Elternknoten eingefügt. Also einfach zack von hier die zwei rot zu der Elternkante rot. Deswegen Color Flip. Wir tauschen von diesen drei Kanten genau einmal die Farben durch. Ähm, sehen Sie dann hier auch im Code, der dementsprechend implementiert Ja, lassen wir ich zeige Ihnen erst den den Code. Äh, wir machen erst ein paar einfache Beispiele und dann schauen wir uns die Animation noch mal an.

20:20 Um das jetzt alles zusammenzupusseln, ich habe jetzt diese drei ähm primitiven Operationen, links rotieren, rechts rotieren und Color Flip. Aber wie baue ich damit Einfügungen zusammen? Lass uns das an einem Miniispiel anschauen, nämlich einem Rot-Schwarzbaum, der nur aus einem einzigen Schlüssel besteht. Und dann kann ich an zwei Stellen einfügen, noch kleiner als dieser Schlüssel oder eben größer. Wenn ich an eine kleinere Stelle einfüge, was kann ich machen? Ich ähm habe jetzt zwei Knoten und die werden nicht in meinem binären Baum nicht auf gleicher Höhe sein. Also den einzigen Baum, den ich ja bauen kann, sinnvollerweise ist dieser oder ich könnte den ändern zu diesem. Das ist alles, was ich mit den Schlüsseln A und B legal bauen kann als binären Baum, als binären Suchbaum.

21:06 Und beide haben unterschiedliche Tiefe für diese beiden Schlüssel, für diese beiden Knoten. Wenn ich da also eine schwarze Kante hinmache, dann ist es kein gültiger Rotschwarzbaum. Also muss die Kante rot werden. Und dann sind wir aber left leaning. Das heißt, dieser hier ist nicht erlaubt. Damit darf ich nur den da machen. Okay, keine andere Möglichkeit. Äh, wenn ich links Efüge, dann passiert das sozusagen von alleine, dass der sich nach links neigt und ich mache einfach diese Kante rot. Wenn ich nach auf der rechten Seite einfüge einen Schlüssel, der größer ist als ähm der in der Wurzel, dann mache ich auch erstmal diese Kante temporär rot. Wenn ich jetzt hier bei der Einfügung an den Blättern angekommen bin, dann merke ich, okay, jetzt ist meine Arbeit mit dem Einfügen erledigt, jetzt muss ich reparieren und dann sehe ich hier insbesondere, ich habe eine nach rechts geneigte rote Kante. Dann mache ich hier eine Linksrotation, um diese Kante nach links zu bringen.

22:08 Okay, wenn wir einen etwas größeren Baum haben, dann sollten Sie sich immer vor Augen führen, was der zugehörige 23 Baum tun würde und dann ergibt sich im Grunde was sie tun müssen. Wenn wir z.B. in diesem äh Baum das C einfügen, dann machen wir erst die Suche wir von der Wurzel bis zu dieser Stelle. Hier muss das C hin. Ich füge es da erstmal ein. indem ich dem immer eine neue rote Kante gebe, denn die rote Kante ist die, die die Höhe im 23 Baum nicht verändert. Im 23 Baum hieße das ja immer, ich versuche den neuen Schlüssel in den Knoten in dieses Blatt erstmal einzufügen. Eventuell ist das Blatt dann zu voll, dann muss ich was tun. Vielleicht habe ich aber auch Glück, wie in diesem Fall, da könnte ich das C ja hier in dieses ähm in den Knoten A damit einfügen und alles ist gut. Dementsprechend ist das auch der 23 Baum, wie am Ende aussieht. Für den Rotschwarzbaum haben wir jetzt aber wieder eine Kante, die sich nach rechts neigt. Das heißt, ich muss hier noch einmal diese Rotation machen, um wieder meine left leaning in Variante zu erfüllen.

23:26 Gehen wir einen Schritt größer. Wir haben jetzt alle Möglichkeiten hier aufgemalt, wo ich einfügen kann, wenn ich zwei Knoten habe. Sehen sich, wenn ich zwei Knoten habe, gibt's nur einen Rotschwarzbaum, der gültig ist. Aber es gibt diese drei Optionen, wo ich einfügen könnte. Wenn ich hier auf der rechten Seite einfüge, nehme ich eine rote Kante. Jetzt habe ich ähm zwei rote Kanten hier rum. Das heißt, das ist eigentlich jetzt ein Dreiknoten im 23 ein vier Knoten im 23 Baum. Dann mache ich einen Color Flip und hätte hier noch eine rote Kante nach oben, wenn es da weiterging. Also als 23 Baum habe ich jetzt einen kleines Bäumchen mit 32 Knoten.

24:05 Andere Option, ich füge ganz am linken Ende ein. Die neue eingefügte Kante wird immer rot, können Sie schon merken. Dann habe ich jetzt hier äh zwei rote Kanten hintereinander. Dann muss ich einmal rüber rotieren, um von diesem in diesen Fall zu kommen entlang der oberen Kante. Und dann kann ich wieder, dann habe ich wieder ein Dreiknoten, ein vier Knoten mit drei Schlüsseln. Mit einem Colorflip mache ich daraus die ähm Konstellation wie vorher mit 32 Knoten.

24:43 Wenn ich zwischen den beiden Schlüsseln was einfüge, dann habe ich auch wieder zwei rote Kanten hintereinander. In dem Fall rotiere ich diese Kante erst nach links, dass ich erkenne sozusagen, dass diese zweite Kante hier kommt noch nicht. Erstmal mache ich die left leaning. Dann prüfe ich hier wieder den Fall zwei aufeinander folgende linke Kanten. Die darf ich nicht haben. Mit einer Rotation und einem Colorflip bin ich auch wieder in der ursprünglichen Situation. Schauen wir uns ein paar ähm Beispiele in der Animation an. Äh wo vielleicht einfacher zu sehen ist ähm was da so passiert. Ich ma mal einen zufälligen, aber nicht ganz so großen Baum.

25:28 Wir machen erstmal die äh Idee im 23 Baum. Und jetzt brauche ich doch meine Tastatur noch, oder? Wir können neue ich drum um ich kann mir die 19 borgen. Fügt die 19 ein. Das heißt, die wird hier unten in diesem drei zwei in dem Dreiknoten landen, den zu einen vier Knoten machen. Dann muss ich aufteilen und noch mal aufteilen und der Baum wächst. Okay, also erstmal hier, wir fügen hier unten ein. Jetzt habe ich lokal diesen Knoten, der zu groß ist. Der mittlere wird nach oben gegeben in den Elternknoten. Da habe ich die gleiche Situation wieder. Das heißt, der wird wieder nach oben gegeben und der Baum wächst um ein Level.

26:14 Das war die Welt im 23 Baum, aber wir sind ja jetzt bei den Rotchwarzbäumen. Also wieder ich füge hier unten ein, dann habe ich zwei rote Kanten anliegend. Ich habe einen einen Knoten, der zwei rote Kanten hat. Das ist ein Vierknoten. Das kann nicht so bleiben. Da mache ich ein Color Flip. Also noch mal hier einfach nur die Farben gewechselt. Jetzt habe ich hier die Situation einfach rekursiv noch mal Colorflip und noch mal und das war's. Sie sehen, dass äh im Rotschwarzbaum für diesen Fall die Struktur sich gar nicht ändert. Ich habe nur so ein paar Farben rumgeschupst. Aber was das eben bedeutet im 23 Baum ist genau dieses Wachsen vom Baum.

27:01 Was man auch im Rotschwarzbaum sieht, ist, dass hinterher die Schwarzhöhe gewachsen ist. Also noch mal ganz mal zurück auch hier. Wie viele äh schwarze Kanten sind es bis zu den Blättern? Immer genau zwei. Egal zu welchem Blatt ich gehe, egal wie weit das wirklich unten ist, ich habe genau zwei schwarze Kanten. Nachdem ich diese Color Flips gemacht habe, sind es genau drei überall. Okay, das war ein Fall. Ähm, Wir fangen wieder im 23 Baum an. Diesmal werde ich werde ich ähm 11 ist natürlich schlecht.

27:55 Okay, ich brauche meine Tastatur. Dann kommt er hier unten in den Knoten, macht einen Vierknoten draus, den spalte ich auf, gebe ihn nach oben und jetzt bin ich fertig. Sind gültiger zwei, drei Baum. Okay, mehr passiert nicht.

28:25 Wir gehen zurück in die Welt der Rotschwarzbäume. Ich füge den hier unten ein. Ich mache einen Color Flip und ich bin fertig. Okay. Ähm, dann machen wir das ist ein schlechter Baum.

29:01 Die wandert hier rein und ist fertig. Ja, in der 23 Baumwelt passiert da gar nicht viel. Im der Rotschwarzwelt habe ich hier die Einführung mit der neuen roten Kante. Die die lehnt sich aber nach rechts. Da darf sie nicht bleiben. Das heißt, ich mache eine Rotation und damit lehnt sich jetzt die Kante nach links. Sie sehen das die gleiche Animation auch hier in den zwei, drei Bäumen. Da fällt es sozusagen nicht so auf, dass die Kante hier jetzt zu einem anderen von den beiden Knoten intern geht.

29:48 dann machen wir mal noch die 3,7 und dann belassen wir es dabei. Also auch hier wieder in vierknoten. Ich spalte nach auf, gehe nach oben und bin fertig im zwei dre Baum. Im Rotchwarzbaum habe ich wieder einen Fall mehr. Ich habe hier unten einen Knoten mit zwei roten Kanten. Das heißt, ich ma ein Colorflip. Dann habe ich jetzt hier einen Knoten mit einer roten Kante, aber die lehnt sich auf die falsche Seite. Das heißt, ich mache noch eine Rotation. Und jetzt ist die Rotschwarzbaumeigenschaft wieder hergestellt.

30:21 Okay. Äh diverse Fälle, die ähm es zu beachten gibt. Ähm werden sicher noch mal drauf zurückkommen. Also, das sind die das sind die Basisfälle.

30:41 habe ich eine eine Kaskade von Fällen, durch die ich immer wieder durchlaufe. Ich füge einen Knoten an dem Blattlevel ein, ein neues Blatt mit einer roten Kante. Dann gibt's z.B. den Fall, dass beide Kinder äh jetzt eine rote Kante haben. Ähm, also erstmal äh die die Reihenfolge ist wie hier gemalt. Wenn ich zwei aufeinander folgende rote Kanten habe, dann müssen die nach links gehen. Wir haben nur left leaning red edges im Baum oben, die noch nicht kaputt ist. Wenn die neue Kante so ist, dass wir dass die sich beide nach links lehen, dann rotiere ich, damit ich einen Knoten habe, einzelnen Knoten mit zwei roten Kindern. Dann kann ich einen Colorflip machen und habe damit meine rote Kante nach oben weitergegeben. Und in dem Fall bin ich dann fast fertig. Hier jetzt einen Knoten mit einer roten Kante. Die lehnt sich nur noch auf die falsche Seite, also muss ich noch mal rotieren. Das sind die drei Fälle, die man prüfen muss. Verletzung der rotschwarze Eigenschaft kann sein, zwei rote Kanten aufeinander folgend, also Eltern und Großeltern beide rote Kante oder zwei rote Kanten am gleichen Knoten oder einzelne rote Kante, aber in die falsche Richtung.

31:51 Mehr kann dann eigentlich auch nicht schiefgehen. Hat man jetzt alle auch schon gesehen im Beispiel. Das einzige, was dazu kommt, ist, dass ich das rekursiv nach oben im Baum mehrfach haben kann. Hatten wir in den Beispielen schon gesehen. Also hier ist noch mal ein konkretes Beispiel, wo das passiert. Ich füge hier unten ein, dann habe ich den Fall, dass beide ähm Kinder groß sind. Das heiß, ich mache ein Color Flip, geb die Kante hier nach oben. Jetzt habe ich hier einen Knoten, der hat eine Kante, die rot ist, die muss aber nach links. Also rotiere ich nach links. Jetzt habe ich zwei Katten, die aufeinander folgen. Also rotiere ich nach rechts. Jetzt habe ich einen Knoten mit zwei roten Kindern. Also mache ich Colorflip. Immer das gleiche. Okay, in Java sieht das unfassbar kompakt aus dafür, dass wir so viele verschiedene Fälle haben.

32:45 Das gibt den normalen Suchteil, der sich nur darum kümmert, abzusteigen rekursiv in den Teilbaum bei der bei der Suche nach dem Schlüssel, den ich jetzt neu einfügen möchte. Ich bin hier unten in diesem Fall angekommen. Ähm, wenn ich einen neuen Schlüssel einfüge, dann habe ich hier oben den Abbruch. Das ähm wenn ich hier in diesem Fall bin, dann ist es der einfachste, dann habe ich nur den Schlüssel aktualisiert. Normalerweise gehe ich hier in den linken oder rechten Teil, bis ich einen Nullpointer finde und dann würde ich da einen neuen Knoten erzeugen, initial mit einer roten Kante nach oben. Okay, dann kommen wir hier aus dem rekursiven Aufruf zurück, haben die Elternkante aktualisiert von einem dieser Aufrufe. Und jetzt habe ich diese drei potenziellen Verletzungen zu prüfen. Und wenn ich die in der richtigen Reihenfolge prüfe, dann kann ich das mit diesen drei Zeilen Code machen. Also der erste prüft, ob ich nur eine rote Kante habe, die sich in die falsche Richtung lehnt. Ja, also die rechte ist rot, aber linke ist schwarz bzw. nicht rot. äh könnte ein Nullpointer sein, wobei wir die zu schwarz definiert hatten. Ähm in dem Fall rotiere ich nach links, dann ist die rote Kante nach links.

34:01 Dann gibt's auch den Fall, dass ich äh linksrot und mein Elternknoten rot ist. äh nicht der Elternknoten, sondern dass zwei rote Kanten in einer Reihe liegen. Ich prüfe das aber immer von hier oben. Ich kann ja nicht auf die Eltern zugreifen. In dem Fall mache ich eine Rechtsrotation, dann bekomme ich diese eine Kante als linkes Kind und die andere Kante als rechtes Kind. Wenn ich also in diesem Fall angekommen bin, habe ich potenziell jetzt zwei rote Kanten in meinen Kindern. Dann mache ich noch mal Colorflip. Und die drei Zeilen sorgen dafür, dass wir diese ähm Eigenschaften lokal an dem Knoten H wieder reparieren. Sehen hier in dem Diagramm die die potenziellen Fälle, durch die man da äh laufen kann.

34:53 Und dann muss ich aber rekursiv im ab im Aufstieg wieder zurück zur Wurzel das potenziell an jedem Knoten machen. Erst dann ist die Eigenschaft wiederhergestellt.

35:14 Schauen uns noch ein zwei Beispiele an, um es noch mal ähm plastischer zu machen. und sie versuchen diese drei Fälle im Kopf durchzugehen. Also, wir erinnern uns, ähm wir prüfen zuerst, ob wir eine einzelne Kante haben, die sich in die falsche Richtung neigt. Danach prüfen wir, ob wir zwei Kanten von diesem Knoten nach unten nach links haben und danach machen wir ein Colorflip, falls der Knoten zwei rote Kanten als Kindkanten hat. Okay.

35:43 Ähm, ich füg mal irgendwas äh zufälliges ein. Also, wo wir wo die 8,5 landen? Hier unterhalb von der 8. Eine neue rote Kante. Erster Schritt, der Knoten hat keine Kinder, also ist er äh glücklich, was diese Eigenschaften angeht. Wir gehen zu seinem Elternknoten. Die acht. Die acht ist nicht glücklich, denn die hat nur eine rote Kante und die geht in die falsche Richtung. Also muss ich einmal nach links rotieren und habe dann jetzt diesen hier als den Knoten, den ich betrachte. Als nächstes prüft dieser Knoten auch hier noch mal ähm die Subtilität hier ist, dass wir das H aktualisieren auf den Rückgabewert der Rotation, auf den neuen Wurzelknoten von diesem Teilbaum. Ähm, wir haben also jetzt diesen Knoten hier und fragen uns: Verletzung sind zwei sukzessive rote Kanten. Junk, Junk, da gibt's aber nur eine rote Kante, also alles gut. zweite Verletzung, die wir noch prüfen müssen oder die dritte insgesamt hat der zwei rote Kanten?

36:58 Nein, hat er nicht. Also ist der Knoten happy. Und wir gehen zum Elternknoten. Bei den Elternknoten hat sich jeweils nichts verändert. Das heißt, da gibt's keine weitere Verletzung. Noch ein Beispiel. Äh, machen wir mal noch mal weiter mit der 8,8. Dann ken wir hier unten wieder ein. Wir fügen hier ein neuen Knoten ein. Der Knoten ist glücklich. Der hat keine Kinder mit irgendwelchen Verletzungen. Immer wichtig für Eltern. Dann gehe ich zum Elternknoten. Erste Überprüfung. Hat der einen rechte rote Kante? Nein, hat er nicht. Hat zwei. Nächste Überprüfung. Hat er zwei rote Kanten nach links runter? Nein, hat er nicht. Hat nur eine hier links. Zweite Überprüfung. Hat er zwei rote Kinder? Ja, hat er. Also machen wir Colorflip. Okay, jetzt ist der Knoten glücklich und wir schauen uns den Elternknoten an. Was prüfe ich als erstes? Einzelne Kante nach rechts. Okay, einfach reinplen, sonst bin ich so ungeduldig. Einzelk nach rechts hat er. Also müssen wir rotieren.

38:03 Machen wir das. Jetzt schauen wir uns den Knoten an. Nächste mögliche Verletzung. Zwei zwei rote Kanten. Genau. Hat er nicht. Also ist okay. Dritte mögliche Genau. Zwei rote Kinder hatte nicht. Also gehen wir weiter zu den Eltern und da sich hier nichts mehr verändert hat, passiert sonst nichts mehr. Okay, ich glaube in dem Baum ähm kriege ich nicht so weiter nicht so ohne weiteres. Ah, doch, doch, doch, doch. Wir machen noch, wir hatten noch nicht den einen letzten Fall einmal gesehen. Vielleicht kann man uns das noch mal an. Also hier noch mal ein Schnelldurchlauf. Der Knoten ist happy. Wir gehen zum Elternknoten. Der hat keine einzelne rechte Kante, aber und auch keine doppelte linke Kante, aber dann eine doppelte zwei rote Kanten nach unten. Also ma mal Colorflip. Der hier ist jetzt glücklich. Wir gehen zum Elternknoten. Wir prüfen wieder. Keine einzelne rechte rote Kante. Gut. Zwei nach links unten. Nein. Auch gut. Hat er eine zwei roten Kanten? Nein.

39:04 Also gut. Gehen wir zum Elternknoten. Noch mal Schritt zurück. Elternknoten hat nicht eine einzelne rechte rote Kante, okay, aber zwei nach links unten. Also machen wir eine Rechtsrotation hier. Und ich möchte mal drauf hinweisen, was da passiert. Das hier war der Knoten, der vorher unglücklich war. Wir wollen jetzt einen produzieren, der immer noch unglücklich ist, aber zwei rote Kinder hat. Das bekommen wir mit der Rechtsrotation hin. Aber der das äh der Elternknoten ist jetzt der mittlere. Der hat jetzt diese beiden rechten roten Kanten. Damit sind wir wieder in diesem Fall und machen den Colorflip. Okay, jetzt haben wir hier noch einmal den schönen Fall. Einzelne rechte rote Kante. Wir rotieren sie rüber. Damit ist jetzt dieser Knoten happy, aber die Wurzel noch nicht. Da haben wir wieder den Fall zwei rote Kanten. Ich muss rechts rotieren und noch mal ein Colorflip. Wenn sie ein paar Beispiele durchgespielt haben, irgendwann können sie die drei Regeln auswendig, glauben Sie mir.

40:02 Ähm, man muss sich nur die Reihenfolge merken, indem man die prüfen muss. Damit lassen wir das erstmal gut sein. Ähm, ich hoffe, das Einfügen ist halbexplosibel geworden. Es sind ein paar Fälle, aber glauben Sie mir auch, es geht noch viel schlimmer. Die ursprünglichen Varianten von den Rot-Schwarzbäumen haben noch mehr Fallunterscheidung. Ähm, das hier ist schon die schönere Variante. Äh, ganz kurz noch ein paar Kommentare zu, wie gut diese Bäume funktionieren. Ähm, das hat hatten wir auch in der Animation letztes Mal schon ein bisschen uns angeschaut, wenn ich so einen Baum baue mit zufälligen ähm Knoten, zufällige Einfügung, dann ist der quasi immer balanciert.

40:52 Und das ist schon die Rotschwarzmalung, ne? Hier ist er ja perfekt balanciert nach per Definition, aber auch der Rotschwarzbaum hat sehr wenig Varianz. Was hier sehen ist noch extremer. Wenn man die Schlüssel in aufsteigender Reihenfolge einfügt, dann wird der Baum zufälligerweise komplett komplett balanciert. Ich habe gar keine roten Kanten am Ende. Das ist jetzt mehr ähm mehr Zufall als äh Verstand. Das gleiche passiert, wenn ich sie in absteigende Reihenfolge einfüge. Obwohl wir dieses Left leaning äh was ja doch ein Symmetriebruch ist, ähm verwenden, macht's scheinbar keinen Unterschied, sobald ich bei einer zweier Potenz -1 bin. Äh zufällige Einfügung hatte ich Ihnen eben auch ein Beispiel gezeigt, hat man dann so eine gewissen Anteil an roter Kanten. Wir wissen natürlich auch, die Höhe ist nie mehr als zweimal die bestmögliche Höhe. Also, der Baum hat minimale Höhe. Im schlimmsten Fall kann der allgemeine Baum zweimal so hoch werden, weil ich ja nur eine rote Kante haben kann, bevor die nächste schwarze kommen muss.

42:03 Also, worst case steht schon fest. Zweimal log Höhe, mehr kann es nicht werden. Log wäre das Optimum. Der Beweis ist, was ich eben sagte, ähm eine Eigenschaft, die nicht mathematisch bewiesen ist, meines Wissens ist äh ausrechnen, was der Erwartungswert ist, der Höhe, wenn man zufällige Einfügung macht, ist ein offenes Problem. Das kann man da da hat keiner bisher eine exakte Lösung für gefunden. Das scheint einfach mathematisch wirklich schwierig zu sein. Empirisch kann ich natürlich simulieren und ähm kriege raus, dass es ungefähr 1,0 mal login ist. Ich glaube, man weiß aber, dass es nicht exakt ein ist. sind eine Konstante echt größer einmal login, aber im der der positive Punkt oder der das die Takeaway Message aus praktischer Sicht ist sicherlich, dass es sehr viel näher an der unteren Schranke ist als an der oberen Schranke, wenn man zufällige Einfügung hat. Ähm, der Hauptselling Point für Rotchwarzbäume ist aber diese Seite, die Worst Case Garantie, die wir bekommen.

43:09 Völlig egal, welche Einfügung ich habe, in welcher Reihenfolge oder wie auch immer sie das mit mit Löschungen mischen, über die wir gleich noch reden müssen. Die Höhe bleibt immer auf maximal zweimal log beschränkt und das gibt ihn dann auch lauf die Beschränkung für die Laufzeiten der Operation. Und damit sind wir jetzt das erste Mal bei einer praktischen Implementierung. die sie auf der Folie gesehen haben. Das ist der komplette Einfüge Code. Der war zwar kompliziert nachzuvollziehen, aber zum runterschreiben ist er nicht kompliziert. Äh eine vollständige Implementierung, die also hier diese ähm logarithmische Laufzeit für alle Operationen im Worst Case garantieren kann.

43:51 Ein paar Kommentare kommen später noch dazu, aber nur damit sie sozusagen motiviert bleiben. Rot-Schwarzbäume sind auch genau das, was in der Java Bibliothek in Treemap und Treset verwendet wird. Ja, ist auch die am häufigsten verwendete Implementierung von balsierten Zuchbäumen. Quasi alle Programmiersprachen haben einen eingebaut. In der Regel Rot Schwarzbäume. Eine Ausnahme ist Python. Da haben Sie keinen Suchraum in der Standardbibliothek zumindest.

44:17 Так.