Video 9-10: Rot-Schwarz-Bäume

0:02 Mit den zwei drei Bäumen hatten wir balsierte Suchbäume gesehen, die logarithmische Laufzeit für alle Operationen erlauben, weil sie die Höhe logarithmisch beschränken können. Äh, aber ich hatte Ihnen ein bisschen erklärt, dass sie unbequem zu implementieren sind, wenn auch äh nur ein bisschen unbequem. Und rotchwarzbäume bieten Alternative, die die Vorteile kombinieren. Letztlich sind die die Ärger, die Unruhestifte, die drei Knoten. Die zwei Knoten sind ja wie gehabt. Und ähm wenn ich die einfach anders darstelle intern, also logisch behandle ich sie immer noch als drei Knoten für die Algorithmen, aber realisieren im Speicher tue ich sie anders. Dann könnte ich verschiedene Varianten wählen. Ich könnte sie z.B. als kleinen binären Suchbaum realisieren, wie ich es auch vorhin schon angetesert hatte. Oder ich könnte sagen, das ist Teil von normalen Baum und ich habe so ein so ein Dummy Knoten, der einfach nur dafür da ist, damit das binär bleibt oder ich habe ähm eine andere Art von Kante.

1:06 Das klingt ein bisschen seltsam, aber dieser letzte Ansatz ist in der Tat äh was sich am bequemsten implementieren lässt. Ähm, das das sieht erstmal optisch genauso aus wie dieser erste Schritt. Der Unterschied ist, dass in diesem ersten Schritt völlig verloren ist, ob das jetzt ein Dreiknoten war oder einfach zwei zween, die eben in der Vaterkindbeziehung bestehen.

1:34 Die Idee wird also sein, dass man zwei, drei Knoten ähm abbildet auf normale binäre Suchbaumknoten. Für zwei Knoten ändert sich nichts. Also so ein zweiknoten hier wird einfach zu einem Knoten im binären Suchbaum. mit den normalen Kanten, den schwarzen Kanten. Das sind die echten Kanten im 23 Baum. Wenn aber ich einen Dreiknoten habe, dann mache ich da draus einen Minibaum, der über diese roten Kanten verbunden ist. Und an der Stelle ähm obwohl das hier also von den Erfindern selbst sozusagen äh beschrieben ist, ähm finde ich eine etwas andere Art, das zu malen fast noch intuitive.

2:16 Und an der Stelle habe ich online nichts gefunden, das genau das implementiert, wie diese neueste Variante es tut. Dementsprechend äh was zusammengestrickt selbst hier äh mit KI Hilfe, aber ähm der Code Code tut, was er soll. Ähm genau das gemalt, was auf den Folien sehen, aber die roten Kanten sind jetzt wagrecht. Perfekt. Damit haben wir hier einen 23 Baum als Beispiel. mit drei Knoten, mit diesen zwei Schlüsseln und zwei Knoten, aber ich kann auch auf diese Rot Schwarzbaumdarstellung wechseln, in der die Kanten jetzt so wie normalen Binärbaum gemalt sind. Aber sie sollten eigentlich immer an das hier denken. Für alle Algorithmen wollen sie so tun, als wären diese roten Kanten wagrecht und verschmelzen quasi diese zwei Knoten im binären Suchbaum in in einen logischen Dreiknoten.

3:15 Wenn Sie das verinnerlichen, sind all die Algorithmen, die kommen, rein mechanisch eine Umsetzung von dem, was wir auf zwei dreibäumen gemacht haben. Wenn sie das nicht tun, sie können auch axiomatisch sagen, ein rotchwarzbaum ist ein Baum, in dem es rote und schwarze Kanten gibt mit folgenden Eigenschaften. Es gibt zwei, niemals zwei rote Kanten in einer Folge. Jeder Knoten hat die gleiche Schwarztie. Wir können sie tun und dann ist es vollkommen unverständlich, warum das funktioniert und wie das funktioniert. Wenn Sie im Hinterkopf behalten, das ist eigentlich ein 3 23 Baum, indem die echte Tiefe definiert ist als ignoriere die roten Kanten für die Tiefe. Dann hat der Baum diese perfekte Balance, wie es zwei, drei Bäume immer haben. Von jedem Blatt zur Wurzel genau gleich viele Schritte, außer dass ich ab und zu mal so eine rote Kante zwischendrin habe. Was aber hier auch direkt sehen, dadurch, dass wir ja nichts Größeres als drei Knoten haben, kann ich nie mehr als eine so eine rote Kante haben, bevor ich diesen logischen Knoten wieder verlassen muss.

4:20 Und dann mache ich also auch einen echten Schritt nach oben. Ich sehe also sofort, die Höhe von so einem Rotschwarzbaum ist höchstens zweimal die Höhe von dem passenden zwei dre Baum. Im Worstcase habe ich in jedem Schritt zwischen einer schwarzen Kante eine rote zu benutzen. Können mal bisschen was größeres bauen, dann sehen Sie es vielleicht besser.

4:44 Also der 323 Baum, den Sie eigentlich im Kopf haben sollten, perfekt balanciert. Ja. Nehmen mal einen. Gibt's einen volleren? Okay, Zufall. Jetzt müssen wir auf Zufall hoffen. Na gut, also im schlimmsten Fall habe ich hier so einen Fad, da habe ich wirklich habe ich irgendwo einen, der perfekt abwechselnd rotchwarz ist. Hier schwarz, rot schwarz rot schwarz. Okay. Na ja.

5:15 Letzter Punkt dazu, warum habe ich hier die Knoten selbst auch bunt gemalt, statt nur die Kanten? Die Kanten gibt's im Code nicht. Die Kanten sind im Code einfach nur Referenzen. Das heißt, wir werden den die Farbe von den Kanten im Knoten speichern, wo die Kante hinführt. Deswegen ist das hier schon so gemalt. Ok.