Video 9-7: Einfügen und Löschen in BSTs

0:03 Okay, dann fangen wir hier wieder an. Ich hatte Ihnen gezeigt, binäre Suchbäume können suchen, aber eigentlich konnten wir schon suchen in einem sortierten Array. Das war nicht das Problem. Der Punkt war, dass wir eine dynamische Menge haben wollen und ein dynamisches Symbol Table. Ich muss also irgendwie auch neue Schlüssel einfügen können, neue Schlüssel zu neuen Werten assoziieren können. Und das ist der Punkt, wo binäre Suchbäume viel viel mehr können als was wir bisher gesehen haben. Insbesondere kann ich ähm neue Schlüssel einfügen an den Nullpointern. Da ist Platz. Überall sonst ist es ein bisschen komplizierter. Äh machen wir also den einfachen Fall. Und hier ist ein Beispiel, wo das gezeigt wird. Ähm, ich finde mir die Buchstaben gar nicht so angenehm, aber gut. Äh, wir bleiben mal hier auf dem Beispiel auf der Folie. Ich zeige ihn gleich noch was anderes. Äh wenn ich das L einfügen möchte als neuen Schlüssel, mit dem ich vielleicht dann auch noch irgendeinen Wert assoziiere, dann fange ich wieder in der Wurzel an zu suchen. Ich fange also mit der Suche genauso an, als würde ich diesen Schlüssel L suchen. Tatsächlich muss ich das eh machen, wenn Sie den Schritt zurücktreten. So eine Symp table soll ja auch prüfen, ob dieser Wert schon drin ist, bevor ich ähm den neu einfüge. Wenn der schon da drin ist, dann will ich den alten Wert überschreiben. Also suchen muss ich E, das mache ich also genauso wie bisher. L ist früher im Alphabet als S, also gehe ich links. L ist später im Alphabet als E, also gehe ich rechts und so weiter. Äh, bei dem M bin ich an der Stelle angekommen. L kommt vor M und da ist aber im Baum ein Nullpointer.

1:39 Das heißt zwei Dinge. Erstens, L ist nicht im Baum gespeichert. In dieser aktuellen Symbolle Table gibt's keinen Schlüssel L. Zweitens, falls L in dem in der Symbolle Table wäre, dann müsste es genau hier sein. Die zwei sagen zusammen. Heißt lassen Sie uns einfach dahinpacken und dann ist es in der Symbol Table und zwar an der richtigen Stelle. Das ist die Idee von Einfügen in Binären Suchbäumen. Ich mache das also immer ganz unten im Baum und ersetze einen Nullpointer durch einen neuen Knoten L.

2:13 Ähm noch mal, weil wir das Ah, okay, das hatte ich vorbereitet für was anderes, aber vergessen Sie mal, was Sie da auf dem Bildschirm sehen. Dazu kommen wir später. Ähm, mal ein bisschen kleiner. Das ist das gleiche Tool, das sie letztes Mal auch schon gesehen haben. Ist auch verlinkt unten, wo sie das äh online finden können. Hier ist mal irgendein zufällig generierter binärer Suchbaum und wir könnten hier mal einen neuen Wert einfügen. Hat jemand ein Vorschlag irgendeiner Zahl?

2:47 Machen mal teuflisch. Also, ich fange an der Wurzel an und vergleiche. Dieser Knoten ist größer als die Wurzel. Also gehe ich nach rechts. Dann bin ich hier. Ich vergleiche wieder. Der ist wieder größer als der Wert an der Wurzel. Ich gehe nach rechts. Jetzt ist er kleiner als der Wert an der Wurzel. gehe ich nach links, dann wieder rechts, wieder links, wieder rechts. Jetzt habe ich einen Nullpointer gefunden. Da darf also ein neuer Knoten hin.

3:11 Weshalb ich die Animation hier ganz gern mag, ist genau dieser Schritt zeigt äh was inhaltlich passiert, nämlich, dass wir Platz machen. Wir schieben alle Knoten, die da auf der rechten Seite sind, einen Schritt weiter nach rechts, aber eigentlich ist es nur für die Zeichnung, für die Visualisierung. Da wird nicht wirklich was verschoben. Das sind ja alles nur Referenzen auf Objekte, die sich gar nicht bewegt haben in diesem Schritt. Wir haben nur hier ein neues Objekt eingefügt und damit es schön gemalt ist, logisch, so dass von links nach rechts die sortierte Reihenfolge aufrechterhalten bleibt, äh machen wir da Platz. Aber das zeigt Ihnen eben genau, warum binäre Suchbäume an beliebiger Stelle einfügen können, ohne dass man wirklich Daten bewegt. Okay, das wollen wir natürlich auch im Code formulieren. Ähm hier ist es tatsächlich rekursiv, sonst äh wird es kompliziert. Es ist deshalb rekursiv, weil im Allgemeinen hier jetzt Pointer verändert werden. Bei der Suche kam das nie vor. Die Suche ist eine reine Leseoperation, da verändere ich den Baum nicht. Einfügen muss natürlich den Baum verändern dürfen. Und insbesondere habe ich jetzt hier ein Knoten, von dem aus, als ich dieses L besucht habe und gefragt habe, ist das L kleiner oder größer und ich bin dann links gegangen, da wusste ich noch nicht unbedingt, dass jetzt das L genau mein neues Kind wird. Ich hätte natürlich gucken können und ein extra Fall machen können, wenn mein linkes Kind Nullpointer ist und ich gehe jetzt darin, dann weiß ich schon, dass das L mein neues Kind wird. Aber man kann viel kompakter den Code schreiben, wenn man da keine Fallunterscheidung macht.

4:52 Und das bekommt man hin, indem man diese Einfügeoperation den Zeiger oder eine Referenz auf die Wurzel von diesem Teilbaum zurückgeben lässt, in den wir jetzt reinspringen. Stift ist wieder weg. Ich habe schon eingeschrottet dieses Semester geht auch noch. Die allermeisten Aufrufe von dieser Rekursion geben den gleichen Knoten zurück, mit dem ich auch abgestiegen bin. Also, ich habe hier einen Aufruf von E zu R und ich bekomme auch das R wieder zurück. Das heißt, da ändert sich nichts. Aber für diesen einen Fall hier unten ändert sich was. Und in der rekursiven Methode ist es eben äh schön in einen Fall zu pressen. Ich habe also diesen Aufruf mit dem mit der Wurzel vom aktuellen Teilbaum und dem Schlüssel, den ich neu einfügen will. Wenn der aktuelle Teilbaum ein Nullpointer ist, dann erzeuge ich diesen neuen Knoten und gebe den zurück, damit der Elternknoten, von dem ich komme, den ich aber an diesem rekursiven Aufruf jetzt gar nicht mehr parat habe, sein Kindzeiger aktualisieren kann.

5:59 Ähm, falls das nicht der Fall ist, bin ich noch in diesem Suchpfadmodus. Das heißt, ich vergleiche mit dem mit dem Schlüssel, den dieser Knoten X dann hat, die Wurzel von dem Teilbaum. Und dann mache ich entweder weiter im linken Teilbaum oder im rechten Teilbaum. Äh, der dritte Fall hier ist der, der Schlüssel ist schon da und ich muss nur den Wert aktualisieren, aber den Baum strukturell gar nicht verändern. Und für diese beiden rekursiven Aufrufe links und rechts sehen Sie, dass wir einfach den Zeiger auf diesen Teilbaum ersetzen durch was immer der Rückgabewert ist. Auch da wieder die meisten dieser auf dieser Aufrufe sind unverändert von was auch immer jetzt gerade X. left ist, aber für diesen einen Fall, dass wir bei einem Nullpointer waren, kriege ich eben einen neuen neue Referenz zurück.

6:56 Auch hier ist die Laufzeit ähm im Wesentlichen die Höhe von diesem Baum. Es ist jetzt ein bisschen weniger offensichtlich eine Schleife, sondern eine Rekursion, aber wir wissen, die kann man grundsätzlich auch eininander überführen, auch wenn der Code weniger kompakt ist.

7:13 Also können wir auch einfügen. Zum Löschen sage ich später noch was. Äh, wir bleiben erstmal noch bei einfach nur einfügen und auslesen. Ähm, die Frage ist, wie diese äh Bäume aussehen, denn wie gut diese Höhe von dem Baum ist oder die die Tiefe von dem Knoten, den ich erreiche, das ist nicht a priori klar. Die Struktur von dem Baum anders als bei den Hiebs ist nicht festgeschrieben. Die können beliebige Form haben. Sie können insbesondere diese schöne balsierte Form haben, sowie Hiebs, in denen die Höhe logarithmisch begrenzt ist. Der typische Fall ist ehrlich ist tatsächlich recht nah da dran, wenn wir gleich noch ein bisschen mehr zu sehen, aber ich kann auch diesen schlechtesten Fall haben, indem z.B. alle Knoten eine lange Folge bilden und das ist ein Extremfall, dass ich die in sortierter Reihenfolge eingefügt habe. Aber es gibt auch andere Varianten, die so ein bisschen Zickzack hin und her gehen und die sind natürlich nicht wirklich besser.

8:13 Auch da habe ich letztlich eine lineare Höhe. Also hier hätte ich Höhe n - 1, ein exponentieller Unterschied. Insbesondere, wenn unsere Bäume in der Regel so aussähen konjunktiv, dann wären wir genauso schlecht wie eine verkettete Liste. In gewisser Weise ist das eine verkettete Liste. Ich benutze immer nur einen Nachfolgerzeiger. Ich habe überhaupt keine Verzweigung. Das wäre also ziemlicher Mist, wenn das der typische Fall wäre. Dankenswerterweise ist das aber nicht der typische Fall. Äh hier ist ein Video, was auf der Website von dem äh roten Buch zu finden ist, wo man ähm wo man sieht, wie nacheinander zufällig gewählte Schlüssel eingefügt werden. Also, sie können sich das vorstellen, als würde ich einfach Zufallszahlen wählen, eine nach der anderen unabhängig vinander und die einfügend, dann kriege ich in der Regel so einen Baum. Und sie hatten auch schon gesehen, ähm das ist, was hier in dem Gnarly Trees Tool gemacht wird. Wenn ich auf Random drücke, dann fügt es äh zehn zufällige Schlüssel ein. Und wenn ich das ein paar mal mache, haben wir jetzt tatsächlich so ein Extremfall, dass die Wurzel nur ein rechtes Kind hat. Aber wenn ich das noch ein bisschen weiter mache, wird es immer unwahrscheinlicher.

9:31 Und der Rest vom Baum ist im Wesentlichen balanciert, nicht so ganz, ne? Es ist schon ein bisschen ähm gibt so ein paar Teile, die tiefer sind, paar Teile, die größer sind. Was darunter regnet, sind Duplikate, die nicht eingefügt wurden, weil einfach wirklich zufällige Zahlen nimmt, unabhängig davon, ob es die im Baum schon gibt.

9:59 Ist das jetzt gut oder nicht so gut? Also rein optisch ist es weit weg von der linearen Liste. Das heißt, es ist relativ gut. Ähm, wir würden das gerne natürlich etwas genauer quantifizieren. Und um zu motivieren, dass wir das können, schauen wir uns mal folgende Idee an. Ich habe einen binären Suchbaum, in den kann ich Elemente einfügen. Also mache ich das mal mit allen meinen Schlüsseln, die ich in einer Liste habe und versuche damit zu sortieren. Der Punkt ist in einem binären Suchbaum. Sehen wir hier vielleicht noch mal das Beispiel. Okay, das ist super klein, aber sie sehen, die Schlüssel sind von links nach rechts in sortierter Reihenfolge in diesem Baum. Wenn ich also irgendwie von links nach rechts die Schlüssel auslesen kann, dann bekomme ich genau die sortierte Reihenfolge der Schlüssel zurück. Das ist die Inorder Traversierung von dem Baum. Haben wir offiziell hier in der Vorlesung nicht drüber gesprochen. Ich weiß nicht, ob Sie es in der anderen anderen Veranstaltung schon gesehen haben. Äh, ich habe fest vor Ihnen das in den Übungsaufgaben noch anzutun. Das heißt, ähm kleiner Vorg, wir werden das dann noch sehen. Äh, das ist relativ einfach mit einer rekursiven Prozedur zu machen.

11:17 Also, ich könnte mit meinen binären Suchbaum Bäumen einen Sortieralgorithmus bauen. Kleiner Einwand, ja, der sortiert nicht wirklich. Wenn der Duplikate sind, dann verwirft der Baum die während ein Sortieralgorithmus sollte das vielleicht nicht tun. Aber wenn es keine Duplikate sind, was ähm sind die Eigenschaften von diesem Sortierealgorithmus?

11:39 Und ähm was dahinter steckt, ähm die Folie gibt vielleicht die Message vorweg, so tada, es hat was mit Quicksot zu tun, aber geben Sie mir ein Moment zu motivieren, warum die so unglaublich nah verwandt sind. Sehen sich an Quicksort hatten wir vor ein paar Wochen Wochen drüber gesprochen. Ähm sie vergessen mal tunst, was ich Ihnen damals gesagt habe über Inplays partitionieren. Wir machen hier eine etwas einfache andere Version, die erste, die ich ihn damals gezeigt hatte. Und wir wählen auch das Pivot in einer ganz ganz gefährlichen Art und Weise. Ignorieren Sie sozusagen, was ich Ihnen damals über Sortieren gesagt habe für einen Moment, nur für 5 Minuten. Danach wieder aktivieren fürs Sortieren. Also, wie funktioniert Quicksort? Ich wähle ein Pivot. Wir wählen hier das erste Element und das Partitionieren bringt dann alle Schlüssel, die kleiner sind als mein Pivot auf die linke Seite und alle größeren nach rechts. Und ich habe hier jetzt, das ist sozusagen für die Illustration wichtig, die Reihenfolge dieser Schlüssel ist gleich geblieben. Unter allen, die kleiner sind, ist die Reihenfolge immer noch genauso.

12:40 Das kann man so machen. Äh ist dann nicht in place, aber geht. Danach habe ich mein Pivot an die richtige Stelle gebracht und ich sortiere rekursiv die beiden Teile sehen in sich. Ich mache das mal ein bisschen im Schnelldurchlauf. Irgendwann sind wir fertig, weil die Teilprobleme einzelne Elemente sind. Und dann habe ich, wenn ich jetzt hier so ein bisschen mit den Sprüngen nach oben lese, von links nach rechts die Liste sortiert. Alter Hut. Ja. Ähm, wenn Sie sich angucken, was Quicksot als rekursiver Algorithmus tut, dann hat er immer nach diesem partitionieren zwei rekursive Aufrufe, ein für das linke und eines für das rechte Teilproblem.

13:20 Ich kann jetzt mit diesen rekursiven Aufrufen jeweils den Wert von dem Pivot assoziieren. Also, jeder rekursiver Aufruf stammt ja von einem äh Vater Elternaufruf, der irgendein Pivot äh verwendet hatte. Sagen wir mal, wir nehmen das als den Repräsentant für diesen Aufruf und dann hat der zwei Kindaufrufe und die haben wieder Pivots. Das heißt, sie sehen, da entsteht so ein binärer Bau. Okay, jetzt machen wir was anderes. Jetzt nehmen wir die gleiche Liste und fügen die in unseren binären Suchbaum ein. Sieben kommt in die Wurzel, sondern mal eine schöne Wiederholung vom Algorithmus von eben. Wenn ich noch kein Element habe, dann ist Root null und ich füge direkt den ersten Schlüssel da ein. Die vier ist kleiner als sieben, wird also linkes Kind von der sieben landen. Die zwei ist noch kleiner als die vier. Das heißt, die wird hier ganz links reinkommen und so weiter und so fort. Auch da mal ein bisschen äh aufs Gas gedrückt.

14:25 Letzter drin. Und was ihnen jetzt auffallen sollte, ist, dass diese zwei Bäume genau gleich sind. Und das ist auch kein Zufall, das nicht irgendwie besonders gewählte Liste. Das ist systematisch so und auch ganz klar, wenn man sich anguckt, wie die Algorithmen arbeiten. Das einzige ist, die Reihenfolge, in der sie manche Schritte machen, ist anders. Quicksort bekommt die ganze Eingabe von Anfang an, wählt dann das Pivot und sagt dann: "Okay, alle Elemente, die kleine sind, nach links, alle größer nach rechts. Das mache ich jetzt sofort und danach kümmere ich mich um alle kleineren in einem Schritt." Binäre Suchbäume machen das anders. die sagen: "Ah, ich kenne jetzt die sieben, packe ich dahin und fertig." Danach kommen sukzessive alle anderen Schlüssel und alle, die kleiner als sieben sind, die leite ich nach links weiter, aber die kommen eben einer nach dem anderen. Aber über die Ausführung der der beiden Algorithmen sozusagen einerseits Quicksort, anderserseits alle Elemente einfügen, mache ich die gleichen Vergleiche, exakt die gleiche Menge oder Multimenge von Vergleichen zwischen zwischen Schlüsseln in beiden Algorithmen. Nur die die Zeit, die Reihenfolge ist eine andere. Wenn ich aber nur zählen möchte, wie teuer war das? Also die Kosten Anzahl äh Vergleiche in in Quicksort oder in diesem binären Suchbaum, dann ist mir egal in welcher Reihenfolge die kommen und dann sind die Kosten von diesen beiden Algorithmen genau gleich.

15:47 Sie können sogar soweit gehen, ähm sousagen binäre Suchbäume sind so ein bisschen ein eingefrorener Schnappschuss von Quicksord und ich könnte den an jeder Stelle dann noch weiterführen oder auch nicht.

16:03 Dementsprechend alles, was wir über Quicksot gelernt haben, über seine guten Eigenschaften im Average Case, gilt auch für unsere Suchbäume, zumindest für diese ähm für diese hypothetische Anwendung alle Schlüssel einzufügen. Aber insbesondere ähm folgt daraus auch direkt, wenn die Höhe von diesem Baum sehr hoch sein sollte, dann hätte auch Quicksort viel bezahlt. dass man bekommt daraus direkt ähm Analyse geschenkt, die wir einfach nur wieder verwenden können. Ähm z.B. kann man zeigen, dass die die typische Tiefe von Schlüsseln zweimal log äh zur Basis E von N ist. Das ist sogar also Basis E ist ja größer als 2,7 irgendwas. Äh das ist 1,39 log zur Basis 2 von N. Also wir sind nur um etwa 40% schlechter als der perfekt balancierte Baum, wenn die Schlüssel jetzt in zufälliger Reihenfolge kommen.

17:06 So wie bei Quicksot die Annahme nötig war, dass wir im Average Case arbeiten. Äh wir hatten damals nicht die exakte Konstante hergeleitet. Sie erinnern sich an den Tobsuchtanfall Quicksort. Wir hatten nur eine obere Schranke gezeigt. Äh das kommt raus, wenn man die Rekursion exakt löst. sehen Sie in effiziente Algorithmen, wenn Sie es sehen wollen äh oder wenn Sie es sehen müssen in Data Science. Also diese äh diese diese direkte Zusammenhang mit Quicksord erlaubt einem einfach entweder das eine oder das andere zu analysieren, was auch immer ihnen besser gefällt. Und dann ist es, wie das ähm Mathematiker und Forscher dann so machen, kann man natürlich noch genauer hingucken. Das hier ist die die erwartete Anzahl Vergleiche für einen Schritt einfügen und löschen. Das ist aber nicht die Höhe vom Baum, sondern die mittlere Tiefe über alle über alle Knoten. Die exakte Höhe vom Baum ist ein bisschen schlechter. Faktor 2 ungefähr mehr. Ähm deutlich komplizierter zu beweisen, brauchen wir hier auch nicht machen, aber wir wenn Sie es interessiert, dann können Sie es können Sie den Vergleich hier anstellen. Aber aber aber der Westcase ist natürlich immer noch der gleiche wie vorher.

18:16 All diese Analysen hier nehmen an, dass wir die Eingabe in zufälliger Reihenfolge bekommen. Bei Quicksort war das kein wirkliches Thema, denn wir haben im Zweifel die Möglichkeit gehabt, zufällige Pivots zu wählen oder sogar ähm noch krasser, wir bevor wir anfangen zu sortieren, schffeln wir erstmal die Liste zufällig durch und dann legen wir los. Das heißt, da konnten wir erzwingen, dass das ist, was auch äh tatsächlich passiert, zumindest in Erwartung über diesen randomisierten Algorithmus.

18:57 Für binäre Suchbäume haben wir die Option nicht. Äh ist hier als Frage formuliert. Ähm vielleicht denken Sie ein Moment drüber nach und ich sage ihn erstmal hier noch mal die Zusammenfassung. Also binäre Suchbäume können einfügen und löschen. Beides im Worst case in Linearzeit, genauso schlecht wie hier unsere alten sequenziellen Listen. Der Average Case ist aber viel viel besser. Noch mal bei Quicksort war das kein Thema. Ich konnte den Average Case in einen erwarteten Fall über einen randomisierten Algorithmus überführen und das war kein Thema. Warum geht es hier nicht? Traut sich jemand spontan?

19:38 Also was ich hier machen müsste, ist die Reihenfolge der Einfügungen zu permutieren zufällig. Und manchmal geht es vielleicht, aber im Allgemeinen bekomme ich einen Element nach der anderen nach dem anderen zum Einfügen und ich kann leider nicht die Zeit permutieren, in der die Dinge kommen. Das heißt, die Option, die haben wir hier einfach nicht.

20:03 Jetzt können wir einfügen. Vielleicht wollen wir auch löschen. Äh, wenn ich einfügen kann, dann möchte ich Schlüssel auch wieder loswerden können. Und im Grunde ist das ähm nicht besonders äh viel schwieriger, aber es gibt an der Stelle jetzt ein paar Fälle. Der einfache Fall ist der, wenn wir ein äh einen Schlüssel suchen, der in einem Blatt vorkommt. Also, machen wir das mal. Wir machen die Suche. Wir fangen wie immer an in der Wurzel und ich möchte 11 löschen aus diesem Baum. 11 ist kleiner als 77, das heißt, ich gehe hier rüber, noch kleiner als 12 gehe ich hier rüber. Da habe ich meinen Schlüssel gefunden und der hat Nullpinter in beiden Kindern. Das heißt, ich kann diesen Schlüssel einfach entfernen. Das heißt, 12 setzt seinen linken Kindzeiger auf Nall und der der Schlüssel ist fort. Hat keine Änderung sonst im Baum hervorgerufen. Ähnlich ist es äh wenn ich einen Knoten finde. Also, ich mache wieder meine Suche. 69 laufe ich hier lang. Ja, da finde ich die 69 hier.

21:11 Hier habe ich jetzt ein Kind, aber eben nur eins. Das heißt, ich kann wieder diesen Schlüssel einfach entfernen und biege den Zeiger von meinem Elternknoten um auf diesen dieses einzelne Kind, dass ich habe. Also die die Großeltern adoptieren hier dieses Einzelkind. Wenn ich aber mehr als ein Kind habe, dann sind die Großeltern vielleicht überfordert. Ähm, das heißt, in diesem Fall komme ich hier zu der 85 und die hat eben zwei Kinder. Die Großeltern haben nur einen Slot auf dieser Seite. An der Stelle muss ich jetzt also was tun. Und um konsistent mit dem Code zu bleiben, äh machen wir die symmetrische Variante. Es gibt in der sortierten Reihenfolge, die ja hier unten gezeigt ist, zwei benachbarte Schlüssel zu 85, der Vorgänger und der Nachfolger in der sortierten Reihenfolge. Wenn ich die 85 durch 88 ersetze, dann kann ich stattdessen die 88 löschen und dann habe ich auch die 85 entfernt und die sortierte Reihenfolge ist immer noch äh wiederhergestellt, denn ich habe ja hier die 85 nur entfernt, 82 88. Die anderen Schlüssel sind alle noch in der richtigen Reihenfolge.

22:34 Das heißt, wir müssen uns nur überlegen, wie machen wir das denn, dass wir jetzt diesen Nachfolger finden? Und in dem in dem Beispiel ist es äh sehr einfach, weil es sehr klein ist. Lassen Sie mich vielleicht mal noch ein zufälliges größeres bauen stattdessen.

23:16 dann äh kümmere ich mich gleich in der Pause drum. Ähm im Allgemeinen, wie finde ich den Nachfolger von dem Schlüssel? Der muss in meinem rechten Teilbaum sein, denn der ist größer als ich bin. Aber in meinem Teilbaum ist es das Minimum. Das heißt, ich folge einen Zeiger nach rechts zum rechten Kind und dann so weit nach links, wie ich laufen kann, bis ich das erste Mal hier einen Nullpinter finde und dann habe ich meinen Nachfolger gefunden. M.

24:01 schwierige Case für diese schwierige Fall vom Löschen hat eben diese zwei Schritte. Ich finde zuerst den Knoten, den ich löschen will und dann muss ich ihn durch seinen Nachfolger ersetzen, bevor ich ihn entfernen kann.

24:13 Äh im Code wieder ähm relativ kompakt. Wir machen das in zwei Schritten. Wir haben eine extra Prozedur, die das Minimum aus einem Teilbaum entfernt. Die hat also einen Knoten von dem, was wir loslaufen und die macht dann genau, dass wir laufen nach links, solange wir können. Das ist diese ähm dieser Schritt hier rekursiv.

24:39 Ähm das kommt erst später, können Sie noch ignorieren. Vergessen Sie die Zeile für den Moment. Also, wenn wir schon äh einen Nullpointer als linken Knoten haben, dann geben wir den rechten Knoten hier zurück, um das Minimum zu entfernen. Das ist dann immer schon der Löschschritt mitgemacht. Ich habe ja dann den Fall, dass ich ein einen Schlüssel lösche, der nur maximal ein Kind hat. Und dann muss ich für den Eltern Knoten hier den linken Kindzeiger umbiegen. Das mache ich hier wieder, indem ich den zurückgebe. Ähm, also wieder so wie beim Einfügen. Der Rückgabewert ist die neue Wurzel von dem Teilbaum, aus dem ich zurückkomme. Äh, entweder habe ich also schon ein Nullpointer, dann gebe ich das rechte Kind von diesem Knot zurück, damit überspringe ich den und falls das rechte Kind nall war, tut es auch das Richtige. Und falls ich noch ein linkes Kind habe, dann rekursiv in das Kind absteigen.

25:41 Das löscht das Minimum und die allgemeine Löschfunktion ist dann hier aufgeschrieben. Die hat diese verschiedenen Fälle, wenn man sie auch nicht ähm ganz so gut mehr sieht. Also, wir starten wieder mit einer Suche. Auch die ist wieder rekursiv. Also, ich vergleiche mit dem Schlüssel in der Wurzel und dann gehe entsprechend in den linken oder rechten Teilbaum. Wenn ich dann in diesem Els Fall, das ist ja ähm der Fall, dass ich also meinen Schlüssel gefunden habe in X, wenn einer der beiden Kinder Null ist, dann kann ich einfach das andere zurückgeben. Das sind die beiden einfachen Fälle. kompakt in einer Abfrage. Ähm, wenn ich hier noch überlebt habe, diese zwei Returns, wenn das nicht gefeiert hat, dann bin ich in dem Fall, in dem ich den Nachfolger finden muss. Das heißt, ich finde das Minimum im rechten Teilbaum von diesem ähm Knoten X.

26:39 Dann lösche ich das und ähm setze meinen Zeiger auf das äh auf das auf den Rückgabewert. damit haben wir jetzt alle Operationen durch. Wir können in diesen Symboltabellen einfügen und löschen und Werte äh auslesen.