Video 9-8: Ordered Symbol Table Operations in BSTs

0:03 Jetzt haben wir über ähm die ganzen Operationen von Dictionaries gesprochen, aber nicht über die Operation von sortedictionaries, von sortierten Symbol Tables sollte ich sagen. Also, die drei können wir schon. Ähm, was ist denn mit den anderen Operationen? Was gab's da noch so? Da gab's das Minimum und Maximum finden. Das ist nicht so schwierig, kommen wir gleich zu. Äh, aber was ist mit Flore und Ceiling oder Rank und Select? Die gab's ja auch alle noch und die wollen wir uns anschauen. Die sind mit binären Suchbäumen nämlich auch alle möglich. Also, erstens, wo finde ich das Minimum und Maximum? Na ja, ganz links und ganz rechts. Das Ding ist ja sortiert. Aber was heißt das jetzt im Code? Wie finde ich das Minimum? Ich laufe von der Wurzel immer nach links, bis ich nicht mehr nach links kann. Also links abbiegen, links abbiegen, links abbiegen, bis ich hier an der Stelle bin. Es gibt kein linkes Kind mehr, also ist das das Minimum im Baum und Maximum symmetrisch. Das ist ganz einfach.

1:04 Ähm, als Randbemerkung taucht am Ende in der Tabelle für die Laufzeiten auf. Da zwei feste Werte sind, könnte ich auch während der ganzen Einfügation immer das aktuelle Minimum oder Maximum explizit pflegen. Dann könnte ich in Konstantzeit darauf zugreifen. Während hier laufe ich eben den Baum runter, also wieder beschränkt durch die Höhe vom Baum. Das war so zum warm werden nach der Pause. Die eigentlichen spannenden Operationen kommen jetzt erst. FL und Sealing waren ja im Wesentlichen, finde mir, für einen Schlüssel, wenn er schon nicht selbst im Simple Table drin ist, den größten, der kleiner ist oder den kleinsten, der größer ist.

1:46 Und äh z.B. hier für diesen Knoten ähm für diesen Baum, wenn ich nach G suche, dann ist äh ich finde dies mit den Buchstaben echt eine doof Idee. Also EMG ist zwischen E und H, nicht? Äh, das heißt, der Flor [schnauben] von G wäre E. Das ist der bei am weitesten hinten im Alphabet stehende Buchstabe, der aber vor G kommt. Sperrig und H ist der erste danach. Ähm, hier ist aber gezeigt für andere Buchstaben. Ceing von Q, äh, also PQR, hier wäre das Q. R ist das nächste dazwischen. Wie finde ich die?

2:38 Wir machen ein Beispiel von Floor. Ähm, der erste Fall ist, ich finde K selbst im Baum. Wie das geht, wissen wir schon. Wir suchen nach diesem Schlüssel und äh wenn ich dann ähm genau den Schlüssel finde, den ich gesucht habe, dann bin ich fertig. dass der also Spezialfall von Laur und Sealing in beiden Fällen ist erlaubt, dass ich genau den Schlüssel zurückgebe. Äh, was sind die anderen Fälle? Na ja, während der Suche kann es mir auch passieren, dass der Schlüssel, den ich jetzt im in der Wurzel von dem Teilbaum sehe, größer oder kleiner ist als den Schlüssel, den ich suche. Also z.B. könnte ähm der Schlüssel kleiner sein. K ist kleiner als der Schlüssel in der Wurzel. der Wurzel, der Schlüssel der Wurzel ist größer. Äh, was heißt es? Also hier im Beispiel mit G. Ich suche und jetzt finde ich, dass äh hier G vor S kommt. Das heißt, ich äh weiß noch nicht genau, wo mein Flore sein wird.

3:35 Wenn es das Gibt, muss ich auf jeden Fall links weiter gucken. Ja, definitiv ist nichts weiter rechts von dem jetzt eh schon zu großen Schlüssel die Rückgabe. Also hier kann ich ähm kann ich nie einen Wert haben jenseits von S, denn das S ist ja schon zu groß. Also schaue ich rekursiv im linken Teilbaum weiter. Der spannendere Fall ist der zweite, der hier gemalt ist. Wenn der Schlüssel im Teilbaum [räuspern] äh in der Wurzel kleiner ist als das, wonach ich suche, dann gibt's nämlich zwei Fälle. Einerseits könnte dieser Schlüssel selbst das Floor sein, kann ich noch nicht ausschließen. Das wäre dann der Fall, wenn ich hier genau dazwischen bin, so wie es hier mit G auch dann passiert. Der andere Fall ist, gimten Teilbaum, dann ist das Ergebnis strickt in diesem rechten Teilbaum. Beides kann ich aber erst rauskriegen, indem ich diesen Teilbaum weiter untersuche. Das heißt, rekursiv gehe ich auf jeden Fall nach rechts, aber ich muss mir merken, es gab diese zwei Fälle. Ich muss mir diesen Knoten noch äh vorhalten, denn eventuell ist der das Ergebnis.

4:49 Okay. Ähm, sieht den Code dann auch wieder so aus. Wir haben eine äh eine rekursive Prozedur, diese Suche realisiert. Ähm den Spezialfall an der Wurzel mal abgesehen. Also ähm wir vergleichen den Schlüssel eben der Wurzel mit dem Schlüssel, den wir suchen. Wenn ich den schon gefunden habe, wenn die gleich sind, dann bin ich fertig. Ist der einfache Fall. Und wenn der Schlüssel, den ich suche, kleiner ist als der Schlüssel in der Wurzel, das ist also hier dieser erste Fall, dann gehe ich einfach nach links. Das war der einfache Teil. Für den schwierigen Fall müssen wir jetzt diese beiden Fälle unterscheiden. Jetzt bin ich an dieser Stelle, wo ich hier bei E den Aufruf hatte. Da rufe ich auf dem rechten Teilbaum Flor auf und schau mal, wart mal ab, was passiert. Und da gibt's diese zwei Optionen. Entweder die das Floor von G im rechten Teilbaum ist ein sinnvoller Wert, weil es einen Schlüssel im rechten Teilbaum gibt, der noch kleiner ist als G.

5:56 Dann bekomme ich hier was zurück. Für unser Beispiel mit G ist es nicht der Fall. Wenn ich Null zurückbekomme, dann ist G kleiner als das Minimum im rechten Teilbaum und dann ist die Rückgabe die richtige das E. Und das habe ich mir gemerkt an dieser Stelle, indem ich einfach äh den rekursiven Aufruf hier abwarte, bis der zurückkommt. Okay, so kann man floor machen. Sealing ist natürlich genauso einfach symmetrisch. Da habe ich diese beiden Fälle da in der umgekehrten Richtung.

6:31 Soweit so gut. Bisher mussten wir nur ein bisschen clever über die binären Suchbäume nachdenken, aber wir mussten sie nicht noch zusätzlich verändern oder irgendwas zusätzliches mit ihnen machen.

6:41 Das ändert sich jetzt, wenn Sie überlegen, wie könnte ich den Schlüssel an Position 42 in der sortierten Reihenfolge finden oder an Index 42? Ähm, ich glaube, wir arbeiten nullbasiert. ähm müsste man dem Code noch mal genau nachschauen. Äh, also was ist das 42 kleinste Element in meiner Symbol Table? Wie kriege ich das denn raus? Ich stehe an der Wurzel und alles, was ich habe, ist der Schlüssel der Wurzel und diese nutzlose Zahl 42.

7:12 Ich habe aber erstmal jetzt keine Information, ob ich bei der Wurzel richtig bin oder ob ich in den linken Teilbaum oder in den rechten Teilbaum gehen muss. An der Stelle fehlt uns tatsächlich relevante Information. Das heißt, wir müssen an der Stelle für diese Operation unseren Suchbaum aufbohren, also verbessern.

7:31 Und die Lösung vorweggenommen ist, für jeden Knoten speichern wir, wie viele Schlüssel sind insgesamt im Teilbaum unterhalb von diesem Knoten, inklusive dem Knoten selbst. Also z.B. hier steht eine zwei, weil ich zwei Schlüssel unterhalb von A habe, nämlich A und C. Bei der Wurzel steht dementsprechend immer die Gesamtgröße von unserem unserer Symbol Table. Ähm und ich kann das rekursiv so haben. Wir äh ich verspreche Ihnen mal, diese Zahlen kann man auch aktualisieren, wenn wir einfügen und löschen. Das ist natürlich wichtig, denn die Innvariante muss gelten, dass diese Zahlen immer korrekt sind und die ändern sich ja, weil ich einfügen und löschen kann. Dazu kommen wir gleich, aber mal angenommen, wir hätten das. Ich habe an jedem Knoten diese Teilbaumröße stehen. Wie hilft mir das denn, um ähm den 22 größten zu finden? Na ja, bei 42 äh würde ich in dem Fall natürlich sofort sagen, so viele habe ich gar nicht. Ähm, suchen wir mal den fünftgrößten äh fünf kleinsten.

8:42 Hatte ich vorhin größter gesagt, kleinste. Also, ersetzen Sie überall, wo ich größter sage, durch kleinstes ähm und links ist ein bisschen natürlicher. Wie würde ich das machen? Also, ich fange an der Wurzel an.

8:58 Was weiß ich über die Wurzel? Na ja, ich weiß, dass sie acht Schlüssel unter sich hat. Okay, das hilft mir zumindest zu wissen, dass der fünf kleinste irgendwie daunter legen wird. Äh, aber sonst nicht so viel. Ich muss in den linken Teilbaum gucken. Der sagt mir nämlich, wie viele im linken Teilbaum sind und der sagt, das sind sechs. Der fünf kleinste äh von links gezählt. Und ich projiziere die mal hier so runter, damit wir das ein bisschen leichter nachvollziehen können. Ähm jetzt würde ich wirklich gerne die gleichen Indizes verwenden.

9:44 Also die ähm die Frage, die wir bei Rank bei Select sagen, ist echt kleiner. Das heißt, lassen Sie mich mal sagen, Index 5 und wir fangen ab null an zu zählen. Machen wir dann vier draus. Das heißt, dieser Knoten hat Index 0 2 1 2 3 4 5.

10:04 Also das Ziel ist diesen Knoten M zu finden. Das soll die Rückgabe sein von der viertkleinste ist eben eigentlich der Knoten an Positionen an Index 4 in der sortierten in dem sortierten Array mit den Elementen. Damit wir konsistent mit Arrays bleiben, fangen wir bei 0 an zu zählen. Das ist das ist alles mit der Verwirrung. Es geht nur um plus oder -1. Ähm, noch mal an der Wurzel weiß ich nur, ich habe acht Knoten unter mir. Damit wird der Index 4 auch dabei sein. Wenn ich zum linken Teilbaum schaue, das sind insgesamt sechs Knoten drin. Das enthält Index 4, ganz sicher. Also kann ich in diesen linken Teilbaum gehen. Ich muss den rechten Teilbaum nicht mehr weiter betrachten. Hier stelle ich mir wieder die Frage, wo muss ich jetzt hin? Ich schaue in den linken Teilbaum, da sind zwei Schlüssel drin, also die Indizes 0 und 1. Wenn ich von da von diesem Teilbaum an adressiere, das enthält den Index 4 nicht, also muss ich nach rechts gehen.

11:08 Jetzt muss ich mir aber merken, dass ich diese zwei Indizes ausgeschlossen habe. Also wir sind jetzt nur noch in diesem Teilbaum. Das heißt, hier rekursiv suche ich jetzt bezogen auf den Teilbaum, den ich mir noch angucke. Ähm, diesen Teilbaum. Also, wir können auch den, wir wissen, das sind zwei im linken Teilbaum und noch einer in der Wurzel, das sind alles noch nicht genug. Ich muss also in den rechten Teilbaum gehen, aber innerhalb von diesem Teilbaum suche ich jetzt nach Index 4 - 3, denn ich habe drei Schlüssel ausgeschlossen. Die sind zu klein, die interessieren mich nicht mehr. Aber damit ich mit der rekursiven Methode weiterarbeiten kann, suche ich bezogen auf diesen Teilbaum jetzt nach Index 1. Ja, okay, dann machen wir das. Äh, auch hier wieder gleiches rekursives Vorgehen. Ich schaue von der Wurzel in den linken Teilbaum. Hat der linke Teilbaum genug Elemente, damit er den Index 1 enthält? Ja, denn er hat zwei Elemente und Index 1 ist der zweite davon. Also gehe ich hier in den linken Teilbaum und sie sehen die Asymmetrie. Wenn ich nach links gehe, muss ich den Index nicht anpassen. Wenn ich nach rechts gehe, muss ich das, weil ich diesen linken Präfix übersprungen habe.

12:22 Okay. Und dann ähm haben wir noch einmal den Fall, linker Teilbaum ist leer. Plus die Wurzel reicht auch nicht. Ich muss also hier Index 2 -1 suchen. 1 - 1, also Index 0. Und in diesem Baum finde ich dann den kleinsten Schlüssel.

12:42 Äh da der linke Teilbaum leer ist, ist das die Wurzel. Also ist m der Schlüssel mit Index 4. Okay. Ist von den ähm Succhalgorithmen der etwas äh komplizierteste ähm mit ein paar mehr Fällen zu unterscheiden.

12:59 Bisher hatte ich jetzt einfach angenommen, wir wir kennen diese Teilbaumgrößen. Wir können uns einfach wünschen, dass es da so eine Methode Size gibt, die uns sagt, hier sind acht Schlüssel unter mir. Wie machen wir das, wenn sich die aber ständig ändert durch Einfügung und Löschung? Na ja, wir müssen sie aktualisieren. Äh und die Lösung dafür ist also erstmal jeder Knoten speichert das. Dann gibt's eine Methode Size, die bequemerweise äh null zu ähm korrekt behandelt. Also äh kann ich die einfach aufrufen auch auf Nullpointer Teilbäum.

13:34 Und jetzt wannmer ich die die Größe von dem Baum potenziell verändere, muss ich mitschleppen, dass ich diese Größenfelder aktualisieren muss. Und das machen wir hier bei Put. Und den Code vorher für Delete. Der enthielt diese Zeile schon. Die hatte ich damals durchgestrichen, damit sie nicht verwirrt sind. Aber die gehört da natürlich mit rein, um diese Größen aufricht zuerhalten.

13:58 Ähm, das Schöne ist, wenn wir aus dem rekursiven Aufstieg zurückkommen, dann haben wir das Element schon eingefügt. Das heißt, ich bin jetzt hier an dieser Stelle, ich habe einen Schlüssel X, ich habe eventuell hier, sagen wir mal nach links den Teilbaum verändert. Da habe ich mein Put aufgeruft aufgerufen. Äh und ich komme jetzt zurück. Da ist die Einfügung an dieser Stelle schon passiert. Das heißt, der Baum ist jetzt wieder fest und statisch und ich kann das ist jetzt eine Induktion über die über die Anwendung über die Höhe. In dem Teilbaum sind die Größen schon aktualisiert. Wenn das stimmt, dann kann ich die Größe für X jetzt einfach neu berechnen, indem ich sie setze auf ein Knoten für die Wurzel plus die Größe vom linken und rechten Teilbaum, die ja induktiv korrekt sind. Und das macht dann diese einfache Formel.

14:57 Und ähnlich mache ich es beim Löschen. Dafür müssten wir noch mal ins letzte Kapitel zurückspringen. Da hat ich hier auch diesen Aufruf. Genau das gleiche Muster. Nachdem ich rekursiv erledigt habe, was ich tun muss zum Löschen, gehen wir jetzt nicht noch mal im Detail rein, sind die Teilbäume schon korrekt aktualisiert. Und um dann den aktuellen Knoten zu aktualisieren, berechne ich die Größe einfach neu. Dadurch ist das relativ einfach und vielleicht zeigt Ihnen das eben äh rückwirkend auch, warum wir äh hier die Teilbaumgrößen speichern und nicht vielleicht direkt den Index von dem Element. Das würde ja hier diese diesen Aufruf viel viel einfacher machen, wenn ich an jedem Knoten gespeichert hätte, was ist denn der Index von diesem Schlüssel in der sortierten Reihenfolge. Dann könnte ich direkt binäre Suche machen und auch das Rank, die zweite Operation, zu der wir gleich kommen, ist noch viel leichter. Das könnte ich aber nicht aktuell halten, denn eine Einfügung kann alle Indizes um eins nach rechts schieben.

16:07 Wenn ich ein neues Minimum einfüge, werden alle Indizs eins größer. Ich habe nicht die Zeit, die alles zu aktualisieren, zu viel Buchhaltung. Die Teilbaumgrößen ändern sich dagegen nur da, wo ich einen neuen Knoten in meinem Teilbaum gewonnen habe. Und das ist eben nur entlang von dem Suchpfad, wo die Einfügung passiert ist. Wenn ich hier einen neuen Knoten eingefügt habe, sieht dieser Teilbaum hier nichts davon. seine Teilgröße bleibt und genauso für alle anderen, die hier so an der Seite noch äh hängen mögen, nur diese Knoten entlang vom Suchpfad, deren Teilbaumgröße wird jetzt zum einen Knoten hier diesen neuen größer und die besuche ich sowieso, wenn während ich da runterlaufe. Das heißt, das ganze ist sozusagen umsonst. Ich muss ein ein Infield pro Knoten mehr speichern, aber laufzeitmäßig ist es fast umsonst.

17:09 Okay, dann hat man noch eine ähm die Methode, die sozusagen das Gegenstück zu dem ist, was ich Ihnen am Beispiel gezeigt hatte. Rank fragt für einen gegebenen Schlüssel, wie viele Schlüssel in meiner Simple Table sind echt kleiner? Das gibt Ihnen dann sozusagen den Index zurück. Vorhin hatten wir gesagt, hier ist ein Index, welcher Schlüssel steht da in der sortierten Reihenfolge jetzt mal was umgekehrt. Hier ist ein Schlüssel. Wo steht der denn? An welchem Index? Und äh das ist was einfacher ähm denn dann suche ich entsprechend nach dem Schlüssel. Also machen wir hier ähm vielleicht auch das Beispiel mit G.

17:54 Was wäre Rank von G? Dafür fange ich an der Wurzel anzuchen. Äh G ist kleiner als S, das heißt, ich muss in den linken Teilbaum. G ist weiter hinten im Alphabet als E, das heißt, ich muss in den rechten Teilbaum. Aber wir haben hier jetzt Schlüssel übersprungen, nämlich all diese hier, den Teilbaum hier und den Knoten selbst. die zählen natürlich in den Index von G mit rein. Das heißt, ich merke mir, ich hatte hier 2 + 1, die am Schluss auf den Index, den ich rekursiv berechne, aufiert werden müssen.

18:37 Dann bin ich hier ähm bei R kommt G wieder davor und bei H auch. Das heißt, wir würden G hier finden, wenn es denn da wäre. Also in diesem Teilbaum hätte G äh Index 0 und das ist dann auch der der Rang. Wie viele Schüsse sind echt kleine? Also in diesem Teilbaum keiner. Aber ich addiere die drei darauf, die ich im rekursiven Abstieg gefunden habe, die ja kleiner waren als G. Im Code ist es auch wieder als kompakte rekursive Prozedur ähm fast schon äh versteckt. Einfach ich habe wieder die die den Vergleich zwischen dem Schlüssel, den ich suche und dem aktuellen äh der aktuellen Teilbaumwurzel. Und dann gebe ich entweder den ähm im linken Aufruf direkt zurück, was ich da bekomme. Da muss ich nichts addieren. Wenn ich nach rechts absteigen musste, muss ich addieren, was ich übersprungen habe, nämlich die Wurzel plus die Größe vom linken Teilbaum.

19:39 Gut, damit haben wir jetzt tatsächlich alle sortierten Symboltabellenoperationen besprochen. Ähm, Select hatte ich im Beispiel gezeigt. Rank hat sie Code gerade gesehen. Floor und Cealing hatten wir floor gemacht. Ce ist symmetrisch und Min hatten wir. Alle diese sind im Wesentlichen einen Abstieg in den Baum und wieder einen Aufstieg rekursiv. Also alle haben Laufzeit beschränkt ähm in der Höhe von diesem Baum. Es wäre also wirklich wichtig Höhe von diesem Baum zu beschränken. Sie erinnern sich Quicksort und all diese Sachen. Wenn ich die Einfügung zufällig habe, dann ist alles gut. Höhe höchstens 4,31 log zur Basis E von N. Immer gut zu wissen. Aber was ist, wenn ich sie nicht in zufälliger Reihenfolge bekomme?

21:09 Okay, das mal ein Moment. Immer schön. Also dankenswerterweise ähm waren wir im Prinzip am Ende. Einmal reicht äh ein Mini Nachtrag an der Stelle noch. Wir hatten diese Animation schon gesehen und da sagte ich, wir haben nur Einfügung. Dann haben wir drüber gesprochen, wir können auch löschen und wir wollen auch löschen. Ähm, selbst wenn ich zufällige Elemente einfüge und zufällige Elemente lösche, ist leider dieser gute Average Case kaputt. Und der Grund liegt darin und zwar sogar relativ deutlich, wenn Sie sich die Asymptotik anschauen, der Grund liegt darin, dass dieses Löschen eine systematische Asymmetrie hat. Wenn ich einen Schlüssel lösche, dann gehe ich in den rechten Teilbaum und finde das Minimum, den Nachfolger und lösche den effektiv. Und das bedeutet, wenn ich das über lange Zeit wiederhole, immer wieder einfügen, löschen, dann wird der Baum so ein bisschen links, der hat ein Linkstrall systematisch und das heißt die Höhe, die man da im Average hat, wenn man nur einfügt, die ist gilt nicht mehr.

22:36 Also, selbst wenn sie zufällige Einfügungen haben, sobald Sie mit Löschen anfangen, ähm ist alles kaputt oder zumindest deutlich schlechter. Wurzeln ist jetzt immer noch nicht linear, aber ist äh viel viel schlechter, als wir es gerne hätten mit logarithmisch. Also noch mal sozusagen ein kleiner äh eine kleine Nuance zu diesem Average Case versus äh Worst Case, der hier im ersten Schritt ganz gut aussah. Sobald man Löschen dazu nimmt, hat man da schon ein Problem ähm sich eingehandelt. Und bevor wir jetzt versuchen, das Löschen irgendwie symmetrischer zu gestalten oder irgendwas derartiges, äh machen wir lieber die richtige Lösung. Ja.