Video 9-12: Löschen in 2-3 Bäumen

0:01 Im nächsten Abschnitt schauen wir uns noch das Löschen an. Jetzt in etwas höherem in höherer Flughöhe als Überblick und nicht mehr ganz mit all den Fallunterscheidungen in vollem Detailgrad werden Sie glaube ich zu schätzen wissen. Trotzdem ist Löschen natürlich wichtig. Bisher können wir in unsere Bäume einfügen und werden die Schlüssel nicht mehr los. Das wäre nicht ganz befriedigend. Ähm noch mal zur Erinnerung, wie funktioniert das Einfügen, insbesondere in zwei dre Bäumen? Äh, da kann man sich, glaube ich, die Intuition gut merken. Wir wir laufen durch den Baum, bis wir an der Blatt Blattebene angekommen sind. Da packen wir den neuen Schlüssel in den Knoten, den wir da finden. Falls das den Knoten zum Überlaufen bringt, also ein temporärer Vierknoten erzeugt wird, dann spalten wir den sofort auf, indem wir den mittleren Knoten nach oben weiterkeben und rekursiv in den Elternknoten einfügen, was dann äh sukzessive dazu führen kann, dass da noch mehr Knoten nach oben durchgereicht werden und der Baum letztlich um den Level wächst.

1:01 Wenn ich das umkehren will, dann ähm muss ich im Wesentlichen ja nur das Einfügen rückgängig machen. Ich war löschen ist ja immer einfach das Einfügen rückgängig machen. Ähm, erster Punkt, wie auch immer, wie wie wir wie wir auch das in den unbalancierten binären Suchbäumen ähm getan hatten, gibt's diese drei Fälle, wenn ich einen Knoten löschen möchte, ist es einer, der kein Kind hat oder ein Kind hat oder zwei Kinder hat? Und sie erinnern sich, der unangenehme Fall ist, wenn der zwei Kinder hat, den wir aber auch schon gelöst hatten. Ich vertausche den Schlüssel durch den äh ich vertausche den den Schlüssel in diesem Knoten mit dem Nachfolger von den Schlüsseln, dem nächst größeren eben der Menge. Und dann kann ich stattdessen den Knoten löschen. Er ist dann immer einer, der kein linkes Teil Kind haben kann, also einer der einfachen Fälle, indem ich einfach den Knoten entfernen kann und einmal den Elternzeige auf das ein auf das einzelne Kind, das ich vielleicht habe, umbiege.

2:03 Wir werden also im folgenden schon davon ausgehen, dass diese Vertauschung schon gemacht ist. Das ist immer der erste Schritt. Wir suchen den Knoten, den wir löschen wollen. Falls der überhaupt im Baum drinne ist, werden wir überhaupt erst aktiv, sonst brechen wir das Löschen ab. Und falls wir den Knoten finden und er einen Knoten mit zwei Kindern ist, dann vertauschen wir schon Schlüssel, sodass wir einen Knoten rekursiv löschen, der nur ein Kind hat. Okay, also das ist das ist die Annahme hier für den Rest.

2:38 Ein Knoten mit nur einem Kind habe ich hier nicht binär genannt. Äh vielleicht im Nachgang. ähm soll keine Geschlechtsaussage sein. Auch hier gibt's ähm mindestens zwei völlig unterschiedliche Ansätze, wie man das in zwei, drei Bäumen lösen kann. Ich will Ihnen beide kurz skizzieren, denn beide haben ihre Daseinsberechtigung.

3:03 Äh, wir werden aber dann die zweite Variante tatsächlich verwenden. Die erste besteht darin, ähm, genauso wie beim Einfügen, erstmal runter zu den Blättern zu laufen. Also, Klammer auf. Ähm, wenn ich in dem 23 Baum einen Schlüssel lösche, dann kann ich immer dafür sorgen durch Vertauschen mit Nachfolgern, dass das in dem Blatt passiert. Das ist quasi die Annahme mit dem nicht binären Knoten löschen.

3:49 Wenn ich einen Knot einen Schlüssel aus einem Knoten löschen möchte in dem 23 Baum, insbesondere am der untersten Ebene, dann gibt's einen einfachen Fall, nämlich das ist ein Dreiknoten, der auch mit einem Schlüssel auskommen kann. Dann entferne ich den Schlüssel und bin fertig. Das ist der einfache Fall. Die andere Variante ist, ich habe jetzt einen Zweiknoten, dem ich den einzigen Schlüssel wegnehme, den er hatte. Das heißt, der ist jetzt leer. Den können wir nicht so belassen, denn das würde die Höhe ähm verändern und gb es Knoten mit geringer Höhe, geringerer Höhe, wenn das vorher ein zweiknoten war und es gibt aber einen Dreiknoten, Geschwisterknoten. Drei. Ja, war richtig. Klingt nur komisch. Also, es gibt irgendwie hier einen Geschwisterknoten, wie immer das da oben drüber aussieht, der ähm ein Dreiknoten ist, also zwei Schlüssel hat. Dann kann ich mir letztlich diesen Knoten, diesen Schlüssel hier in den Elternknoten geben und der Schlüssel, der hier uns beide separiert hat, hier runtergeben.

4:55 Dann habe ich quasi einmal durchrotiert und mir den Schlüssel von meinem Geschwister geborgt. geborgt ist gut, weil den geben wir nie zurück, aber so ist es vielleicht manchmal. Man könnte sagen, das ist so eine Art Rotation über den Elternknoten und das funktioniert nach links oder nach rechts. Wenn einer der Geschwister in Dreiknoten ist, kann ich das machen. Und dann bleibt nur der letzte Fall übrig. Der Knoten, aus dem wir löschen wollen, sind zwei Knoten und alle Geschwister sind auch zwei Knoten.

5:29 Könnte ein Dreiknoten sein oder es könnte so ein Fall sein. Dann ähm sagen wir, wir löschen den hier. Dann hole ich mir einen Schlüssel aus dem Elternknoten und verschiebe den hier rein. Und das ist dann rekursiv eine Löschung aus dem Elternknoten. Und die behandle ich genauso wie gehabt. Und auch hier, wenn ich hier den Schlüssel aus dem Schlüssel löschen will, dann borge ich mir hier den Schlüssel und muss eben rekursiv damit ähm nach oben mit der gleichen mit dem gleichen äh Vorgehen weitermachen und da den gelöschten Schlüssel ersetzen.

6:12 Das ist z.B. die Variante, die implementiert ist aus in diesem Tool, dass ich ihn eben gezeigt hatte, das Neiley Trees. Ähm, okay. Da brauche ich jetzt wieder meine Tastatur.

6:32 Äh, vielleicht schauen Sie es daheim an. Also, es macht genau das, was ich gesagt hatte. Ähm, das ist auch nicht die Variante, die wir die wir verwenden am Ende. Also, von mir aus müssen Sie die nicht im Detail kennen. Sagen wir mal, die ist äh in dieser Form nicht Prüfungsstoff. Ähm hängt mein Herz nicht so sehr dran. Der Punkt war nur, um sie ein bisschen vorzuwarnen, wie das in anderen Möglichkeiten passiert. Wir werden, ich werde gleich noch was dazu sagen, wo die vorkommt.

7:01 Insbesondere für zwei dre Knoten haben wir schon hier ein paar Fälle gehabt. Wenn Sie das auf Rot-Schwarzbäume übertragen, woher alles noch mal ausgefaltet ist in rote, schwarze Kanten und all diesen Spaß, äh explodiert die Anzahl Fälle noch mehr. Deswegen ist die Variante da irgendwie unbequem. Ich kann auch anders löschen. Und die zweite Variante ist näher an dieser Idee, das Einfügen rückgängig zu machen. Ähm, die Komplikation, die wenn die also diese diese äh dieser banale Spruch hier löschen ist das Einfügen rückig machen. Der hat hier das folgende Problem, dass beim Einfügen ersten Schlüssel hinzugefügt wird und dann der Baum verändert wird. Aber das Baum verändern passiert natürlich, nachdem der Schlüssel da drin ist und ich weiß, wie ich ihn verändern muss. Wenn ich das beim Löschen rückgängig machen möchte, dann muss ich erst den Baum verändern und dann den Schlüssel entfernen, ohne eventuell vorher genauso zu wissen, wie ich den Baum eigentlich verändern soll. Deswegen ist es ein bisschen hummelig und wir werden uns nicht skisch an diese ähm an diese Idee halten. Stattdessen versuchen wir eine gute Invariante äh zu bekommen.

8:10 Nämlich, wenn ich dafür sorge, dass ich nie aus einem Zweiknoten löschen muss, dann habe ich auch nie ein Problem, denn aus einem Dreiknoten kann ich ja immer löschen. Und wir lassen da, ich habe das ähm hier explizit som formuliert, denn wir lassen hier auch temporäre vier Knoten zu. Werden Sie gleich sehen, was das heißt. Aber wenn ich irgendwie im rekursiven Abstieg sicherstellen kann, dass ich nie in einem Zweiknoten stecken bleibe, dann habe ich kein Problem mit dem Löschen per se. Also lassen Sie uns das machen. Ähm, was wir dafür aber beachten müssen, ist, dass wir die Höhe von dem Baum nicht kaputt machen dürfen. Ich darf Schlüssel hin und her schieben, aber die Höhe von meinem 23 Baum soll nicht verändert werden. Also temporär ist okay, vier Knoten zu haben. Äh und jetzt gibt's mehrere Fälle wieder zu unterscheiden, aber es ist artet nicht ganz so arg aus, versprochen. Zumindest weniger als im anderen Fall.

9:07 Wenn der nächste Knoten, zu dem ich absteigen will, also ich mache wieder eine Suche nach dem Schlüssel, den ich löschen möchte, der ist irgendwo ähm in meinem Baum. Wenn der nächste Knoten, in den ich jetzt absteigen möchte, um daraus zu löschen, ein Dreiknoten ist, dann bin ich schon zufrieden. Ausdem könnte ich löschen, falls das das Ende der Suche ist und dann lasse ich den einfach wie er ist. Ein Problem bekomme ich nur dann, wenn der nächste Knoten, in den ich ste absteigen möchte, jetzt ein Zweiknoten ist.

9:35 Da ich aber nach der Invariante aktuell aus einem Dreoten oder gar vier Knoten komme, habe ich immer mindestens einen Schlüssel übrig, den ich nach unten schieben kann in diesen zwei Knoten und dann ist es kein Zweiknoten mehr, sondern ein Dreiknoten. Das ist die Idee und äh das ist im Wesentlichen, was wir hier versuchen. Jetzt gibt's ähm manchmal Auswahl, welchen von verschiedenen Schlüsseln ich runterdrücken möchte in das Kind. Ähm, wenn wenn der rekursive Abstieg in das linkeste oder rechteste Kind von dem Dreiknoten erfolgt, dann habe ich nur eine Wahl. Da kann ich nur den den anliegenden Schlüssel äh in das Kind runtergeben. Wenn ich einen mittleren, wenn ich beim Abstieg in ein mittleres Kind gehe, dann habe ich die Auswahl. Also, das ist der Fall hier. Ich habe einen Dreiknoten und ich möchte jetzt rekursiv 4 draus löschen. Dann kann ich mich entscheiden, welchen von diesen beiden Schlüssel ich da jetzt runtergeben möchte. Ähm und die Invariante hier ist, wir nehmen dann den linken Schlüssel, der hier dann mit runterwandert.

10:46 Sie sehen natürlich schon, ich habe hier dann äh mit den zwei Kanten, die dann noch anliegen, ein Problem. Ich werde mich da dann nachher drum kümmern müssen, dass das wieder ein gültiger Baum ist. Äh, wenn man einen vierknoten hat, den wir ja temporär erlauben, äh, also mit drei Schlüsseln und vier Kindern, dann geben wir niemals den mittleren Schlüssel nach unten, sondern immer einen der beiden Äußeren. Das ist so die Regel.

11:20 Was heißt es jetzt, einen Schlüssel runterzugeben? Das kann ich nicht wirklich machen, ohne den Baum zu verändern. Und was wir dabei effektiv tun, vielleicht hier noch mal am Bild, bevor ich Ihnen die Animation zeige. Ich habe ja hier irgendeinen Knoten und hier irgendein Knoten. Von dem weiß ich, es sind zwei Knoten. Von dem hier außen weiß ich es nicht unbedingt. Ich drücke den Schlüssel hier runter. Das heißt, ich verschmelze diese zwei jetzt zu einem mit dem neuen Knoten, mit dem neuen Schlüssel, der hier mit reinwandert. Das heißt, ich habe hier einen temporären Vierknoten erzeugt, aber ich habe dann jetzt nur noch eine Kante von diesem Knoten zu meinem Elternknoten. Also vielleicht ja male ich das noch mal neu mit vorher nachher, dann ist es etwas klarer.

12:13 Also hier habe ich irgendeinen Schlüssel. Hier möchte ich löschen. Der da wandert jetzt nach unten. Und wie sieht das hinterher aus? Ich habe hier einen Vierknoten mit dem X in der Mitte und den beiden Schlüsseln von vorher außenrum. Der Elternknoten ist jetzt ein Zweiknoten und hat diese beiden Kinder. Wichtig, die Höhe von allen Blättern unterhalb hat sich nicht verändert. Also alles, was hier auf der Ebene war, was hier unten drunter ist, hat immer noch die gleiche Anzahl Kanten zur Würzeln nach oben. Das ist wichtig. Äh, was mir jetzt passieren kann bei diesem das runterdrücken heißt, ich verschmelze zwei Geschwisterknoten und ich gebe noch einen Schlüssel dazu. Selbst wenn das beides ähm drei zwei Knoten waren, habe ich ähm jetzt mindestens einen vier Knoten und vielleicht sogar einen fünf Knoten erzeugt. Wenn der Knoten, in den ich in den ich rekursiv löschen möchte zwei Knoten ist, das Geschwistern drei Knoten und noch ein Schlüssel dazu kommt, sind vier Schlüssel insgesamt, also ein fünf Knoten.

13:23 Den würde ich dann direkt wieder aufteilen in den zwei und drei Knoten und quasi die den Schlüssel wieder in die Eltern zurückgeben, aber so rum, dass jetzt der Dreiknoten ist, auf dem ich die Rekursion, das Löschen weiterführe.

13:39 So kommen wir durch. Das sind alle Fälle, die man braucht beim Abstieg, sodass ich immer in einen mindestens drei Knoten rekursiv weitergehe, um was zu löschen. Dann mache ich irgendwann meine Löschung und im rekursiven Aufstieg spalte ich diese vier Knoten wieder auf, indem ich den mittleren Schlüssel nach oben reiche. Das muss immer gehen, weil der kam immer von oben, da muss dann immer Platz sein. Der Teil ist so ein bisschen nicht ganz offensichtlich. Ähm, lassen Sie mich das noch mal an dem Beispiel wieder zeigen.

14:13 Das ist jetzt natürlich viel zu groß und ich brauche wieder meine Tastatur. Wir schauen uns das nur in der 23 Version an und ich zeige ihn dann gleich den Code, wie er für Rot-Schwarzbäume aussieht. Auch da der Code nicht besonders umfangreich, aber man hat dann noch ein paar ähm ein zwei fallende Scheidungen mehr und dann reicht's vielleicht irgendwann. Ähm wir löschen mal den Knoten, den Schlüssel 20. Das ist dieser hier.

14:54 Was sollte passieren? Also, ich möchte rekursiv absteigen und möchte da möchte sichergehen, dass ich immer einen Dreiknoten auf meinem Weg habe. Die Wurzel sieht erstmal okay aus, aber der hier ist nicht in Ordnung. Das heißt, ich muss von der Wurzelnen Knoten hier runterschieben, damit dieser hier zu einem Dreiknoten wird. Der Stelle sehen Sie schon, was im Rotschwarzbaum passieren muss, damit ich das tun kann, muss eine rote Kante wandern. können wir erstmal ignorieren. Was ich dann hier ähm tatsächlich mache, ist diese zwei Geschwister verschmelzen und ich habe den Knoten hier aus der Wurzel nach unten gegeben. Temporär ein vierknoten, aber das okay, wir sind ja beim Löschen, der wird noch kleiner werden. Dann ähm ist der nächste Schritt hier runter zu dem Knoten. Das ist schon ein Dreiknoten, das heißt, da sind wir schon zufrieden. Aber der nächste Schritt äh ich würde dann ja hier zur 20 weiter absteigen und sie dann auch finden. Das ist aber ein Zweiknoten. Das heißt, da bin ich nicht zufrieden und ich versuche wieder einen Knoten aus dem Elternknoten runterzudrücken. Sprich diese zwei Geschwister verschmelzen und das passiert dann. Jetzt kann ich die 20 entfernen. Weg ist sie. Und dann wird auf dem Weg nach oben wieder repariert. Im 23 Baum heißt es nur, dass die Vierknoten wieder aufgespalten werden und wieder nach oben den Schlüssel durchreichen. Wenn Sie genau geguckt haben, haben Sie gesehen, im Schrotchwarzbaum machen wir die gleichen drei Verletzungsregeln wie beim Einfügen. Dankenswerterweise.

16:27 Rote Kanten, die nach rechts gehen, wie hier werden getauscht. Und ähm vier Knoten sind zwei aufeinander folgende rote Kanten, die dann eventuell noch rotiert werden, damit ich sie ähm am gleichen Knoten anliegen habe und dann bin ich fertig. Das sind so die Fälle. Ähm, noch ein Beispiel vielleicht, wo es ein bisschen noch mehr äh kaskadiert. Löschen wir mal die 16. Also, hier ist die 16. Ich fange der Wurzel an und möchte rekursiv nie in einem Zweiknoten stecken bleiben. Die 15 hier ist ein Zweiknoten, also wird der anliegende Knoten, die 11. In diesem Fall ist immer der linke. Ja, von dem hier hätte ich jetzt beide Schlüssel theoretisch nehmen können, aber ich verschmelze mit dem linken, weil das zu den leftaning Red Black Trees passt. Die 11 wird runtergepackt, verschmelzt mir den beiden zu einem vier Knoten. Ist temporär, wir gehen weiter Richtung 16 komme ich zur 17. Ist auch ein Zweiknoten. Das heißt, ich gebe die 15 hier runter, hab dann wieder so einen temporären Vierknoten.

17:37 Und dann gehe ich hier weiter zur 16. Das wieder ein zwei Knoten. Das heißt, ich gebe die 17 runter und verschmelz die beiden zu einem Viererknoten. Dann kann ich die 15 tatsächlich entfernen, die 16. Und dann mache ich auf dem Rückweg wieder das Reparieren. Genau wie beim Einfügen. Können wir ja vielleicht zum Spaß jetzt mal wechseln. Versprochen. Auf dem Rückweg ist es gleich wie beim Einfügen. Was prüfen wir als erstes? Ob ich eine einzelne Kante nach rechts habe, die rot ist? Wenn ja, dann wird rotiert. Dann ist der hier happy. Und wir gehen zum Elternknoten. Der ist happy so wie er ist. Er hat keine einzelne Kante nach rechts, hat keine doppelte nach links und auch keine zwei roten Kanten. Das heißt, ich gehe zum nächsten und hier sind alle sozusagen schon zufrieden, so wie sie sind.

18:27 Ähm, gut, belassen wir es vielleicht dabei. Wenn Sie mögen, können Sie ja noch mehr spielen. Äh, was ich noch kurz zeigen möchte, ist wie das dann im Code aussieht. In Rot-Schwarzbäumen verwenden wir diese zweite Variante, weil die etwas weniger Ärger macht. Ähm, etwas weniger Ärger ist immer noch relativ. Äh, die Hauptmethode ist diese hier auf der rechten Seite. Ähm, worüber ich mich äh so ein bisschen hinweggesetzt habe, ist Ihnen genauer zu sagen, was in der Wurzel passiert. Ähm, das hier war so ein bisschen äh das hier war so ein bisschen geschummelt, denn die Invariante gilt eventuell an der Wurzel nicht. An der Wurzel fange ich an und ich kann nicht garantieren, dass die ein Dreiknoten ist. In meinem wohlgewählten Beispiel in der Simulation war sie ein Dreiknoten. Falls die Wurzel kein Dreiknoten ist, haben wir einmal den Fall, dass wir gerne eventuell zu einem Zweiknotenkind einen einen Schlüssel borgen würden, den wir aber nicht haben.

19:32 Wir haben ja nur einen in der Wurzel. In dem Fall ist die Wurzel aber dann äh der einzige Punkt, wo ich den Baum schrumpfen darf und sozusagen meinen einzigen Schlüssel an mein Kind gebe. Und dadurch wird der ganze Baum eine Ebene kürzer. Das passiert, wenn dann nur an der Wurzel und auch nur da wä es erlaubt. Ähm schlägt sich im Code in diesem ersten Teil hier nieder. Da steht, wenn Sie es bisschen entziffern, dass beide Kanten schwarz sind. Das heißt, ich bin ein zweiknoten. Das kann überhaupt nur an der Wurzel passieren. Das kann eigentlich gar nicht mehr rekursiv passieren, denn wir haben ja explizit verhindert, dass wir in den zweiknoten landen. Das hier ist nur an der Wurzel.

20:21 Der übliche Fall ist, dass wir in diesem Zweig hier sind. Ähm, wenn ich wenn der link, wenn die linke Kante rot ist, dann bin ich mindestens in dem Dreiknoten. Ja, ich hab mindestens zwei Schlüssel, die ich verbunden habe. Dann kann ich einfach ähm jetzt kommt's noch an, wo ich lösche, ne? Ähm, das ist aus dem Kontext daraus nicht intuitiv, warum wir hier die Rotation direkt machen.

20:58 Also, man sorgt an der Stelle ähm dafür, dass die die rote Kante nach rechts nach rechts zeigt, ähm um sozusagen Platz zu schaffen für den neuen Knoten. Äh na ja. Weiß nicht, ob es da eine gute Intuition für gibt. Ist einfach eine kompaktere Variante vom Code. Ähm, wenn wir den Schlüssel äh gefunden haben, wir haben also den äh Schlüssel, den wir löschen wollen, in unserem aktuellen Knoten gefunden und die der rechte Knoten ist leer. Äh, der rechte Zeiger ist leer. Dann habe ich einen unähen Knoten. Dann entferne ich den hier einfach und gebe Nall zurück. Ansonsten habe ich äh diverse Fälle, wie ich zu diesem zu dieser Invariante komme, dass ich immer in den drei oder vier Knoten rekursiv reingehe. Ähm, die Formulierung hier ist auch wieder auf diese Primitiven zurückgeführt, ähm, die hier auf der zweiten Folie sind. Ich habe das Rechts rotieren und das Links rotieren. Das ist genau wie vorher. Das Flip Colors ist fast genau wie vorher. Es ist aber hier ein echtes Invertieren der Farben, denn wir brauchen es hier in beide Richtungen.

22:16 Ansonsten ist es wie vorher. Und es gibt dann noch so eine zusammengesetzte Operation Move Red Left und Move Red Right, die letztlich ähm mit dem Left Leaning zu tun haben. Äh was was wir eigentlich da gerne hätten, ist was in den zwei drei Bäumen intuitiv passiert, dass ich so einen einen temporären fünf Knoten wieder aufspalte. Und das ist äh im im Code als Rot-Schwarzbaum relativ kompakt so ausdrückbar, aber ich finde es ähm es führt uns zu weit dann in alle Details abzusteigen, wie die wie die einzelnen Fälle sich in den Code übersetzen. Sie müssen also hier auch nur die die 23 Baumvariante vom Löschen kennen. Ich wollte aber den Code trotzdem in der vollen Form auf den Folien haben, damit sie sozusagen nicht an dieser unbefriedigten Stelle sind, nicht wirklich gesehen zu haben, wie wie man das umsetzen könnte. Also, das ist der Code, wie er dann vollständig auch funktioniert. Das hier ist der rekursive Aufstieg, wo wir diese drei Bedingungen prüfen. Das ist genau wie von ähm dem Umbruch geschuldet, dass es nicht drei Zeilen sind. Ansonsten ist es genauso.

23:25 Also den Code mehr als als Orientierungshilfe nehmen auf dem Abstraktionslevel bzw. Also wie sie es in der Animation gesehen haben, ist der Teil ähm der zum Stoff gehört. Ähm das ist, denke ich noch überschaubar. Das sind ein paar Fälle zu unterscheiden, aber äh nicht nicht ganz so unintuitiv wie dann äh die Rot-Schwarzbaum Implementierung.

23:53 Dann lassen Sie mich langsam zum Ende kommen von dem Kapitel. Ich habe noch einen kleinen Nachtrag, aber erstmal noch eine Übersichtsfolie, was wir geschafft haben. Ähm, insbesondere haben wir balancierte binäre Suchbäume jetzt auch mitlöschen. Ähm, die gleiche Tabelle wie oben, aber noch mal explizit aufgeführt, weil ich sie gegenüberstellen will zu etwas, was hier gleich noch kommt. Ähm, das sind die ganzen Operationen von sortierten Symle Tables, wie wir sie jetzt gesehen haben und die man alle mit den Rotschwarzbäumen effizient implementieren kann.

24:24 Wir hatten uns ja in diesem Kapitel auch die binären HEBS und Priority Cues angeschaut und wenn Sie die so vergleichen, dann haben die ja doch einigermaßen ähnliche Operationen. Im in gewissem Sinne sind diese Hiebs so eine Teilmenge der Operationen dessen, was die Binien Suchbäume können. Und wenn man sich genau die Laufzeiten anschaut, kann man durchaus fragen, wozu überhaupt diese Hiebs machen. mal dieses Construct äh also aus einer gegebenen Liste einen Hieb bauen. Wenn man davon mal absieht, dann erlauben balancierte binäre Suchbäume die gleichen groß O Laufzeiten wie binäre Hiebs. Die binären HBs haben da null Vorteil. In der Praxis ist das durchaus ähm bisschen anders, weil die binären Hiebes kompakt in einem Array gespeichert sind, haben die da ein bisschen Vorteile, aber sind konstante Faktoren und die sind auch nicht gigantisch. Also, man könnte an der Ab an dem ähm Schritt sozusagen daran zweifeln, warum wir uns mit diesen HEBS da rumgeplagt haben und warum wir überhaupt über Priority Cues gesprochen haben. Und ein bisschen als Vorgriff möchte ich dazu sagen, dass einerseits natürlich wie immer die Abstraktion von diesen Priority Cues hilfreich sein kann, um dem Benutzer oder dem dem Leser ihres Codes mitzuteilen, dass sie hier nicht die volle das volle Menü der binären Suchbaumoperation brauchen. Aber viel wesentlicher ist, es gibt eben bessere Priority Queue Implementierungen, die wie gesagt ein bisschen zu weit fühlen für das Modul. Hier können Sie wiederkommen zur anderen Vorlesung, äh dann lernen Sie mehr dazu und die sind eben dann doch deutlich schneller. Die schaffen außer das Delete Max alle Operationen in konstanter Zeit und an der Stelle insbesondere insert in konstanter Zeit, das kann ein binärer Suchbaum eben nicht leisten.

26:15 Aus diesem Grund ähm ist mindestens die Abstraktion oder die der abstrakte Datentyp von den Prioritys wichtig, denn ich kann keine bessere Implementierung generieren, wenn diese im Prinzip best möglich ist. Da werden wir auch noch mal äh wenn es in den Videos was zu sehen. Ähm im Grunde sind diese benährend Suchbäume, wenn man alle diese Operationen braucht, das Beste, was geht. Nur wenn ich die Operation mehr einschränke, kann ich noch mehr machen.