WEBVTT 00:07.130 --> 00:08.960 Okay, fangen wir mal langsam an. 00:11.200 --> 00:19.560 Wir hatten letzte Woche mit dem sozusagen Höhepunkt unserer Folge von 00:19.560 --> 00:24.260 Kapiteln über Datenstrukturen angefangen, Datenstrukturen für 00:24.260 --> 00:31.680 sortierte Folgen, die wir hier implementieren in einer Weise, die 00:31.680 --> 00:33.660 zumindest das Buch stark nahelegt. 00:33.660 --> 00:37.880 Wir wissen schon, wie doppelt verknettete Listen gehen, mit dem Dummy 00:37.880 --> 00:40.080 -Element, dem wir jetzt den Schlüssel unendlich geben. 00:40.480 --> 00:45.360 Wir haben jetzt die zusätzliche Datenstruktur-Invariante, dass die 00:45.360 --> 00:49.280 Elemente Schlüssel haben und bezüglich dieser Schlüssel sortiert sind. 00:50.660 --> 00:56.100 Und wir nutzen das, um schnelle Suchoperationen zu unterstützen, und 00:56.100 --> 00:59.120 zwar mithilfe einer zusätzlichen Datenstruktur, die ich jetzt mal eine 00:59.120 --> 01:03.820 Navigationsdatenstruktur genannt habe, die halt gegeben ein Schlüssel 01:03.820 --> 01:05.020 und schnell hier hinführt. 01:08.140 --> 01:13.300 Dann hatte ich erst mal das vorgeführt für eine statische sortierte 01:13.300 --> 01:16.820 Folgendatenstruktur, wo man einfach ein sortiertes Feld nehmen kann. 01:17.860 --> 01:21.580 Im dynamischen Fall brauchen wir zusätzlich Einfügen und Löschen. 01:22.920 --> 01:26.560 Und Update, sofern das den Schlüssel ändert, ist sowas wie ein 01:26.560 --> 01:28.460 Löschen, ein Anschließen, ein Einfügen. 01:29.780 --> 01:37.140 Aber die sozusagen paradigmatische Operation für sortierte Folgen ist 01:37.140 --> 01:42.020 diese Locate-Operation, wie man das kleinste Element größer gleich an 01:42.020 --> 01:43.340 einem gegebenen Schlüssel findet. 01:44.600 --> 01:47.300 Und ich habe darauf hingewiesen, dass das ein großer Unterschied ist 01:47.300 --> 01:51.140 zu zum Beispiel Hashtabellen, wo ich nur sagen kann, dass ein Element 01:51.140 --> 01:53.100 mit genau dem Schlüssel ist drin oder nicht. 01:53.220 --> 01:56.720 Und es gibt eine Reihe von Anwendungen, wo man diese allgemeine Reform 01:56.720 --> 01:57.100 braucht. 01:57.280 --> 01:59.600 Wenn es nicht drin ist, gibt mir das nächste sozusagen. 02:01.220 --> 02:05.880 Ich hatte weitere Operationen erwähnt, Minimum, Maximum, Bereichsuche, 02:06.040 --> 02:11.260 wofür man dann sehr gut diese verketteten Listen brauchen kann, Aufbau 02:11.260 --> 02:18.260 aus einer sortierten Folge von Elementen aufspalten und zusammenfügen 02:20.120 --> 02:24.800 und sagen, gib mir das unzuvielte Element in der Liste, sag mir das, 02:24.900 --> 02:29.860 wieviel der Element das ist, wie groß ist sein Bereich, Fingersuche, 02:29.980 --> 02:32.800 also es gibt eine ganze Menge Operationen. 02:33.600 --> 02:37.840 Ich hatte die Abgrenzung diskutiert, Hashtabellen sind spezieller, 02:37.940 --> 02:41.820 weil sie keine Ordnung kennen, sortierte Felder sind spezieller, weil 02:41.820 --> 02:45.440 sie keine dynamischen Updates erlauben, beziehungsweise weil die dort 02:45.440 --> 02:49.460 sehr langsam sind, Mobilitätslisten unterstützen nur bestimmte 02:49.460 --> 02:55.300 Operationen, die dann aber schneller, wobei das bei den Binary Heaps 02:55.300 --> 02:58.360 dann eher so ein konstanter Faktor ist, den wir gewinnen, wir könnten 02:58.360 --> 03:02.820 auch alles über Suchbäume machen, aber es gibt eben diese 03:02.820 --> 03:07.080 adressierbaren Prioritätslisten, die dann Decrease Key und Merge viel 03:07.080 --> 03:08.060 schneller unterstützen. 03:11.700 --> 03:17.340 Ich habe ein paar Anwendungen erwähnt, insbesondere ein konkretes 03:17.340 --> 03:22.940 Beispiel vorgeführt, für eine Greedy Heuristik für Binpacking. 03:24.140 --> 03:32.760 Man gesagt hat, wir öffnen so wenig Kisten wie möglich und packen neue 03:32.760 --> 03:36.860 Gegenstände immer wenn möglich in Kisten, die bereits geöffnet sind, 03:37.300 --> 03:40.320 und zwar in die, wo es am besten reinpasst, also wo man am wenigsten 03:40.320 --> 03:40.960 Luft lässt. 03:42.260 --> 03:44.700 Dafür brauchte man genau diese Locate-Operation. 03:46.240 --> 03:52.600 Dann hatte ich angefangen, eine relativ einfache Implementierung für 03:52.600 --> 03:56.540 die Navigationsdatenstruktur vorzuführen, nämlich binäre Suchbäume. 03:59.560 --> 04:05.500 Da haben wir also innere Knoten, die die Navigationsdatenstruktur 04:05.500 --> 04:13.040 ausmachen, mit Schlüsseln, die einem sagen, aha, wenn das gesuchte 04:13.040 --> 04:16.780 Element kleiner gleich diesem Schlüssel in dem inneren Knoten ist, 04:17.220 --> 04:18.060 suche zur linken. 04:19.160 --> 04:20.740 Das war sozusagen die Operation. 04:26.720 --> 04:28.640 Varianten davon habe ich vorgeführt. 04:29.120 --> 04:30.500 Das Wichtige war das Locate. 04:32.140 --> 04:39.720 Da hilft einem halt diese Schlüssel in den inneren Knoten, um ja, das 04:39.720 --> 04:41.280 richtige Element fast zu finden. 04:41.960 --> 04:46.660 Es kann vorkommen, das war dieser Fall hier, wo das gesuchte Element 04:46.660 --> 04:49.140 nicht das ist, wo man dann landet, sondern einen weiter. 04:49.580 --> 04:52.940 Aber da hilft uns halt auch die verkettete Liste, um mit dem Fall 04:52.940 --> 04:53.860 korrekt umzugehen. 04:58.110 --> 04:59.970 Genau, also soweit waren wir. 05:00.070 --> 05:05.930 Gibt es an der Stelle Fragen dazu, wie das Locate für binäre Suchbäume 05:05.930 --> 05:06.950 funktioniert? 05:07.130 --> 05:11.810 Weil darauf baut jetzt alles andere auf, in gewisser Weise sind auch 05:11.810 --> 05:14.350 die AB-Bäume, die ich dann als nächstes vorstelle, eine 05:14.350 --> 05:16.470 Verallgemeinerung von binären Suchbäumen. 05:18.030 --> 05:19.450 Okay, dann machen wir da mal weiter. 05:20.070 --> 05:23.550 Genau, ich hatte dann ein bisschen formaler erklärt, warum das 05:23.550 --> 05:24.210 funktioniert. 05:24.210 --> 05:30.450 Mit Hilfe einer Invariante für Locate, eigentlich ist das so etwas wie 05:30.450 --> 05:34.490 eine Vorbedingung für den rekursiven Aufruf, die im Wesentlichen sagt, 05:35.430 --> 05:39.010 wenn wir hier mittendrin in der Navigationsdatenstruktur sind, an 05:39.010 --> 05:44.470 einem Knoten X, dann weiß ich, der linke Teilbaum enthält Schlüssel 05:44.470 --> 05:48.830 kleiner gleich X, der rechte enthält Schlüssel größer X, das ist aus 05:48.830 --> 05:54.210 der Datenstruktur-Invariante und das, was weiter links ist im Baum, 05:54.330 --> 05:57.730 ist kleiner dem gesuchten Schlüssel, das, was weiter rechts ist, ist 05:57.730 --> 06:00.930 größer dem gesuchten Schlüssel und daraus kann man dann, wenn man an 06:00.930 --> 06:05.830 einem Blatt angelangt ist, folgern, dass unsere Funktion korrekt ist, 06:06.350 --> 06:09.370 dass aber dann tatsächlich auch diese beiden Fälle hier unterschieden 06:09.370 --> 06:12.030 werden müssen, um die Korrektheit hinzubekommen. 06:12.030 --> 06:12.930 Ja, 06:16.210 --> 06:20.750 die Laufzeit ist proportional zur Höhe dieses Baumes und entsprechend 06:20.750 --> 06:23.170 ist natürlich die spannende Frage, wie hoch ist denn der? 06:23.690 --> 06:27.110 Der beste Fall ist logarithmisch, das ist das, was wir haben wollen am 06:27.110 --> 06:27.390 Ende. 06:28.410 --> 06:32.850 Leider ist der schlechteste Fall linear und dann habe ich sozusagen 06:32.850 --> 06:36.730 eine sehr komplizierte und teure Art, eine verkettete Liste zu 06:36.730 --> 06:38.570 durchsuchen und das hilft mir nicht weiter. 06:38.570 --> 06:43.630 Gucken wir uns mal an, wie das passieren kann und zwar jetzt mithilfe 06:43.630 --> 06:48.250 einer Einfügeoperation für binäre Bäume, die aber ziemlich naiv 06:48.250 --> 06:48.850 vorgeht. 06:50.030 --> 06:54.850 Also wir wollen Element E einfügen, jetzt suchen wir das erstmal, also 06:54.850 --> 06:58.110 machen Locate, sagen wir mal, wir finden ein Element E Strich. 06:59.170 --> 07:07.530 Zum Beispiel hier ist ein innerer Knoten U, Element E Strich ist hier 07:07.530 --> 07:10.130 und rechts ist irgendein Teilbaum, das könnte auch wieder ein Element 07:10.130 --> 07:12.970 sein oder ein ganzer Teilbaum, es kann auch sein, dass hier drüber 07:12.970 --> 07:19.750 noch irgendwas ist, das ist alles egal, aber jetzt weiß ich und nehmen 07:19.750 --> 07:22.390 wir mal an, dass E Strich ist hier der linke Nachfolger. 07:22.390 --> 07:27.690 Wir wissen jetzt, E ist kleiner gleich E Strich, dann machen wir doch 07:27.690 --> 07:30.970 einfach folgendes, wir machen hier einen neuen inneren Knoten, der 07:30.970 --> 07:34.750 erst das E und dann das E Strich aufführt und das U verweist jetzt auf 07:34.750 --> 07:35.670 den neuen Knoten. 07:36.210 --> 07:39.410 Man kann sich überlegen, damit sind alle Invarianten erfüllt, man kann 07:39.410 --> 07:40.610 jetzt alles korrekt finden. 07:42.250 --> 07:45.910 Das Ganze ist, sobald ich das E Strich gefunden habe, konstante Zeit, 07:45.910 --> 07:50.450 also man muss eine Speicherverwaltungsoperation durchführen, ein neues 07:50.450 --> 07:57.550 Item für einen inneren Knoten generieren, ein paar Zeiger umbiegen und 07:57.550 --> 07:58.010 fertig. 07:58.970 --> 08:00.350 Das ist erstmal eine gute Nachricht. 08:00.950 --> 08:03.690 Genauso funktioniert das, wenn E Strich der rechte Nachfolger ist, 08:04.890 --> 08:08.670 dann kommt das E nach links und das E Strich nach rechts. 08:09.610 --> 08:11.930 In dem neuen Item. 08:12.270 --> 08:13.250 Gibt es dazu Fragen? 08:15.310 --> 08:19.270 Also auch recht einfach, jetzt gucken wir uns mal ein Beispiel an. 08:19.350 --> 08:21.950 Wir haben am Anfang eine Liste, die nur die 19 enthält. 08:22.470 --> 08:28.170 Zügen wir die 17 ein, 17 ist kleiner gleich 19, also neues List-Item, 08:28.690 --> 08:30.350 erst die 17, dann die 19. 08:32.010 --> 08:36.010 Der Splitter hier bleibt und der kriegt natürlich die 17 als neues 08:36.010 --> 08:36.930 Navigations -Element. 08:36.930 --> 08:41.170 Sieht nicht schlecht aus, so muss es wohl sein, wenn wir dieses 08:41.170 --> 08:42.570 unendliche Ding noch haben wollen. 08:42.950 --> 08:47.090 Wollen wir weiter, die 13, aha, wir suchen die, die ist hier, neues 08:47.090 --> 08:50.710 List -Item, 13, 17, 19, prima. 08:51.710 --> 08:56.310 Die 11 suchen wir, kommt hier rein. 08:57.230 --> 09:01.050 Aber Sie sehen schon, wo das hinführt, wenn ich absteigend sortierte 09:01.050 --> 09:04.570 Elemente einfüge, kriege ich hier im Prinzip eine lange verkettete 09:04.570 --> 09:08.810 Liste und die Navigationsdatenstruktur hat lineare Höhe. 09:09.950 --> 09:12.990 Und wenn ich da drin jetzt ganz oft suche, ist das viel zu teuer. 09:14.610 --> 09:20.410 Dieser Baum kann also bei der naiven Einfügeoperation beliebig 09:20.410 --> 09:23.830 unbalanciert werden und damit ist das Ganze langsam im schlechtesten 09:23.830 --> 09:24.130 Fall. 09:27.910 --> 09:32.270 So, die meisten Vorlesungen über Datenstrukturen würden an der Stelle 09:32.270 --> 09:36.550 jetzt sagen, aha, wir wollen die Suchbäume balancieren. 09:37.850 --> 09:39.370 Wie machen wir das? 09:41.350 --> 09:46.950 Idealerweise perfekte Balance, man hätte gerne Höhe Log N aufgerundet 09:46.950 --> 09:47.570 oder sowas. 09:47.910 --> 09:50.250 Das kann man erreichen, ist aber auch wieder sehr teuer. 09:50.250 --> 09:56.730 Da kann man dann Operationenfolgen definieren, wo man super linear 09:56.730 --> 09:58.650 viel Arbeit leistet. 10:00.310 --> 10:02.270 Offenbar ist es so einfach nicht. 10:03.790 --> 10:06.530 Also da muss man einfach viel zu viel reorganisieren. 10:10.520 --> 10:15.440 Dieses Geräusch, kommt das von außen oder ist das irgendein 10:15.440 --> 10:19.580 Technikproblem im Hörsaal, wie man das lokalisiert? 10:27.840 --> 10:29.520 Das müssen wir wahrscheinlich mitleben. 10:32.360 --> 10:37.420 Der nächste Schritt ist, dass man sagt, es reicht uns Höhe U von Log 10:37.420 --> 10:37.660 N. 10:38.220 --> 10:43.720 Und da gibt es tatsächlich einen ganzen Zoo von Möglichkeiten, das zu 10:43.720 --> 10:48.660 erreichen, die Sie in Lehrbüchern nachlesen können, die in vielen 10:48.660 --> 10:50.500 Vorlesungen detailliert behandelt werden. 10:52.740 --> 10:57.940 Das ist auch durchaus sinnvoll, man kriegt da Algorithmen, die 10:57.940 --> 11:00.360 wirklich auch in der Praxis verwendet werden. 11:01.500 --> 11:04.360 Wir haben aber in dem Buch und auch in der Vorlesung entschieden, das 11:04.360 --> 11:05.400 anders zu machen. 11:07.620 --> 11:13.300 Man kann sozusagen die Höhe von perfekter Balance auf vernünftige 11:13.300 --> 11:14.560 Balance relaxieren. 11:14.560 --> 11:18.540 Man kann aber auch was anderes machen, man sagt, die Höhe ist perfekt, 11:19.720 --> 11:24.120 aber der Knotengrad, den variieren wir. 11:24.680 --> 11:30.340 Und dann kommen wir auf ein Konzept, das sind AB-Bäume, die aus meiner 11:30.340 --> 11:33.800 Sicht konzeptuell einfacher sind und die in der Praxis auch bessere 11:33.800 --> 11:34.780 Performance liefern. 11:35.240 --> 11:39.920 Weil was man dann kriegt, sind etwas größere Knoten als interne 11:39.920 --> 11:43.540 Knoten, und wenn man das in einer bestimmten Implementierung auch als 11:43.540 --> 11:46.520 Blätter, und das macht die Datenstruktur cache-effizienter. 11:47.940 --> 11:50.540 Und deshalb haben wir uns entschieden, die AB-Bäume vorzuführen. 11:50.640 --> 11:55.540 Die sind konzeptionell relativ einfach, sind in der Praxis schnell. 11:56.540 --> 12:00.820 Der einzige Nachteil ist, dass ein paar Implementierungsdetails ein 12:00.820 --> 12:01.740 bisschen hässlich sind. 12:03.500 --> 12:06.700 Was dann dazu führt, dass wir hier in der Vorlesung einige von diesen 12:06.700 --> 12:07.720 Details dann weglassen. 12:07.720 --> 12:11.420 Aber die Konzepte sind schön und einfach und das stellen wir vor. 12:14.700 --> 12:16.640 Also was sind diese AB-Bäume? 12:18.600 --> 12:20.880 Ich habe hier erstmal ein paar Beispiele vorgestellt. 12:21.040 --> 12:25.380 Mit unserem Dummy ist der einfachste AB-Baum sozusagen der, der die 12:25.380 --> 12:27.060 leere Folge repräsentiert. 12:27.860 --> 12:30.760 Also nur dieses Dummy-Element als doppeltverkettete Liste. 12:30.880 --> 12:34.160 Es gibt nur eine Wurzel mit Grad 1, das ist so eine Art Spezialfall. 12:35.440 --> 12:39.760 Hier ist jetzt mal eine etwas größere Liste, 2, 3, 5, 7, 11, 13, 17, 12:39.880 --> 12:40.280 19. 12:42.040 --> 12:46.920 Dann habe ich eine Wurzel mit einem Grad 3, mit einem Nachfolger von 12:46.920 --> 12:49.700 Grad 3, einem von Grad 4, einem von Grad 2. 12:50.180 --> 12:52.720 Und sagen wir mal, das wäre jetzt ein Beispiel für einen 2-4-Baum. 12:53.320 --> 12:57.080 Das ist tatsächlich eine Wahl von Parametern, die man häufig 12:57.080 --> 12:57.580 verwendet. 12:57.580 --> 13:03.340 Sie werden auch in der Übung am Mittwoch lernen, dass das ganz gute 13:03.340 --> 13:04.180 Gründe dafür gibt. 13:04.320 --> 13:09.780 Also 2-4-Bäume sind Isomorph sozusagen zu einem bestimmten binären 13:09.780 --> 13:11.500 Suchbaum -Datentyp. 13:13.380 --> 13:17.420 Sodass wir hier eigentlich auch nebenbei noch die binären Suchbäume 13:17.420 --> 13:20.400 lernen in einer etwas anderen Darstellung. 13:25.480 --> 13:29.060 So, jetzt aber, was sind die allgemeinen Invarianten dieser A-B-Baum 13:29.060 --> 13:29.820 -Datenstruktur? 13:32.140 --> 13:36.660 Die Blätter unseres Baums sind wie gehabt die Listen-Elemente. 13:37.960 --> 13:40.980 Und der Trick ist, die sind alle in der gleichen Tiefe, das ist, was 13:40.980 --> 13:43.940 ich gesagt habe, der ist perfekt in diesem Sinne. 13:43.940 --> 13:50.800 Also alle Blätter sind in gleicher Tiefe und die sollen logarithmisch 13:50.800 --> 13:52.000 sein, das sehen wir dann später. 13:52.540 --> 13:57.460 Die inneren Knoten haben fast alle, gerade zwischen A und B, da kommen 13:57.460 --> 13:59.440 diese beiden Parameter A und B her. 14:00.020 --> 14:05.940 Wir werden später Bedingungen für die Werte von A und B kennenlernen, 14:05.940 --> 14:10.960 aber im Wesentlichen läuft es immer darauf hinaus, dass B sowas wie 2 14:10.960 --> 14:11.800 mal A ist. 14:12.400 --> 14:14.860 Oder größer gleich 2 mal A. 14:15.380 --> 14:18.540 Wir werden sehen, es reicht sogar 2 mal A minus 1, aber dann handelt 14:18.540 --> 14:21.100 man sich ein paar andere Probleme ein oder es ist nicht ganz so 14:21.100 --> 14:21.620 effizient. 14:25.500 --> 14:30.360 Die inneren Knoten haben alle gerade zwischen A und B, dann sieht man, 14:30.480 --> 14:33.180 dass das für die Wurzel nicht funktioniert, da muss man ein bisschen 14:33.180 --> 14:37.580 flexibler sein, die hat gerade zwischen 2 und B und tatsächlich in dem 14:37.580 --> 14:41.760 Fall eigentlich sogar zwischen 1 und B, aber 1 ist nur erlaubt für die 14:41.760 --> 14:43.340 Lehrerliste. 14:44.800 --> 14:51.200 Also ganz grob, AB-Bäume sind Bäume, in denen alle Blätter in der 14:51.200 --> 14:56.120 gleichen Tiefe liegen und bei denen alle inneren Knoten gerade 14:56.120 --> 14:59.540 zwischen A und B haben und für die Wurzel muss man halt dann noch ein 14:59.540 --> 15:03.440 paar Zusatzregeln machen, aber auch die hat gerade höchstens B und 15:03.440 --> 15:05.540 mindestens 2 außer für die leere Folge. 15:06.740 --> 15:10.220 Das ist also die Datenstrukturinvariante und daraus folgt schon fast 15:10.220 --> 15:10.920 alles andere. 15:11.560 --> 15:16.320 Und natürlich gilt das Gleiche wie bei Suchbäumen, die Elemente sind 15:16.320 --> 15:22.360 sortiert und die Splitter sagen einem, wo in dem Baum muss ich 15:22.360 --> 15:24.900 weitersuchen, um ein Element mit diesem Schlüssel zu finden. 15:32.860 --> 15:35.700 In gewisser Weise ist das hier das Einzige, was Sie sich wirklich 15:35.700 --> 15:38.240 merken müssen, den Rest kann man sich herleihen. 15:39.180 --> 15:41.620 Bloß natürlich ein paar algorithmische Ideen, die ich jetzt auch 15:41.620 --> 15:42.120 erkläre. 15:43.200 --> 15:46.960 Es wird jetzt im Laufe dieser Vorlesungen immer komplizierter, die 15:46.960 --> 15:51.040 Details, die müssen Sie aber dann nicht alle auswendig lernen. 15:51.140 --> 15:54.220 Wenn Sie das hier können und verstanden haben, was ich hier erkläre, 15:54.300 --> 15:56.400 kann man sich die Details immer wieder neu herleihen. 15:59.180 --> 16:02.060 So, aber jetzt gehen wir mal ein bisschen in den Pseudocode rein, auch 16:02.060 --> 16:04.180 um komplizierter zu werden. 16:04.260 --> 16:08.360 Wir haben wieder so Handles, das sind so etwas wie Zeiger auf die 16:08.360 --> 16:13.680 Items, beziehungsweise haben wir hier diesen Fall, dass die Zeiger 16:13.680 --> 16:16.900 entweder auf innere Knoten verweisen oder eben auf diese 16:16.900 --> 16:17.400 Listenelemente. 16:18.060 --> 16:21.520 Deshalb habe ich hier geschrieben, AB-Item sind die inneren Knoten und 16:21.520 --> 16:25.360 Item sind die Items einer doppeltverketteten Liste. 16:27.180 --> 16:33.520 Dann die Items selber sehen so aus, die speichern in Grad, Anzahl 16:33.520 --> 16:36.100 Kinder, ein Wert zwischen 1 und B. 16:37.480 --> 16:44.380 Und zwei Arrays, eins mit Splittern, da brauche ich maximal B-1 viele 16:44.380 --> 16:49.280 und eins mit Zeigern auf die Kindknoten, davon brauche ich B Stück. 16:50.120 --> 16:53.780 Und das D sagt uns im Prinzip, wie viele davon gültig sind, also die 16:53.780 --> 16:58.380 von 1 bis D sind gültig und die von 1 bis D-1 hier sind gültig. 16:58.380 --> 17:03.780 Und jetzt muss ich die Invariante noch ein bisschen konkreter machen, 17:03.880 --> 17:07.000 ich habe da eben so ein bisschen mit den Händen gewedelt, was jetzt 17:07.000 --> 17:08.020 diese Splitter sind. 17:09.280 --> 17:15.560 Also die Invariante kann man so formulieren, wenn ein Element über den 17:15.560 --> 17:21.260 Iten -Kindzeiger erreichbar ist, dann muss sein Schlüssel zwischen dem 17:21.260 --> 17:24.320 Splitter SI-1 und SI liegen. 17:25.120 --> 17:28.720 Das ist also jetzt im Prinzip diese Verallgemeinerung der Invariante 17:28.720 --> 17:36.720 von binären Suchbäumen auf innere Knoten mit mehreren Nachfolgern und 17:36.720 --> 17:41.000 dann brauche ich auch entsprechend mehrere Spaltschlüssel, die mir die 17:41.000 --> 17:43.860 Entscheidung ermöglichen, wo ich jetzt weitersuchen soll. 17:46.100 --> 17:51.500 Also mit anderen Worten, die Splitter-Elemente hier sagen uns, wenn 17:51.500 --> 17:56.160 ich was suche, muss ich gucken, wo liegt das innerhalb dieser Splitter 17:56.160 --> 18:01.400 -Elemente in einem Baum, ich finde das nächstgrößere und das sagt mir, 18:01.640 --> 18:05.960 welchen entsprechenden Nachfolgezeiger ich verfolgen muss. 18:05.960 --> 18:09.220 Und dann gibt es immer einen Zeiger, für den es keinen Splitter gibt, 18:09.320 --> 18:14.680 das ist halt, wenn der Schlüssel größer ist als der größte Splitter, 18:14.820 --> 18:17.040 dann gehe ich auf den rechten Nachfolger. 18:20.520 --> 18:23.480 Und damit die ganzen Invarianten hier Sinn machen, kann man sich 18:23.480 --> 18:27.060 wieder so Wächter-Element-Annahmen machen, dass S0 gleich 18:27.060 --> 18:31.420 minusunendlich und SD und SD plus 1 gleich unendlich sind. 18:32.340 --> 18:35.380 Und wie bei der binären Suche auch, ist das jetzt ein rein 18:35.380 --> 18:40.800 konzeptuelles Wächter-Element, weil auf die Dinger tatsächlich niemals 18:40.800 --> 18:42.400 wirklich zugegriffen wird. 18:42.600 --> 18:44.660 Das heißt, ich muss die nicht wirklich abspeichern. 18:46.020 --> 18:51.440 Gibt es Fragen zur Datenstruktur-Invariante für AB-Bäume? 18:52.100 --> 18:54.100 Ja, was AB-Bäume sind. 18:54.940 --> 18:57.480 Wir müssen noch nicht hundertprozentig verstanden haben, wie ich jetzt 18:57.480 --> 19:00.920 die Operationen durchführe, aber vielleicht schon, wie die Dinger 19:00.920 --> 19:01.400 aussehen. 19:01.780 --> 19:04.160 Also ich habe hier auch jeweils Beispiele. 19:04.680 --> 19:07.740 Wir haben Zeiger nach unten, wie bei binären Bäumen auch. 19:07.860 --> 19:11.560 Ich lande bei den Blättern, das sind diese Dublin-List-Items. 19:13.500 --> 19:14.660 Fragen dazu soweit? 19:16.200 --> 19:18.020 Dann fangen wir mal langsam an. 19:18.120 --> 19:19.940 Jetzt deklarieren wir die Klasse-AB-Tree. 19:20.500 --> 19:24.780 Achso, vielleicht noch was zu den Konstruktoren von AB-Items. 19:25.300 --> 19:29.680 Also ich übergebe eine Folge von Splittern und eine Folge von Kindern 19:29.680 --> 19:30.740 bei der Konstruktion. 19:32.260 --> 19:35.160 Jetzt eine Klasse für die AB-Trees selber. 19:35.440 --> 19:37.000 Da übergebe ich nur das A und B. 19:39.620 --> 19:44.040 Und man könnte jetzt sogar argumentieren, in C++ wären das vielleicht 19:44.040 --> 19:45.240 auch Template-Parameter. 19:45.680 --> 19:48.760 Also Konstanten, die man zur Compile-Zeit festlegen kann. 19:49.280 --> 19:53.420 Und dann kann man das Speicher-Layout festlegen zur Compile-Zeit schon 19:53.420 --> 19:54.960 und dann wird einiges effizienter. 19:56.700 --> 19:59.980 Aber konzeptuell können das genauso gut natürlich auch Sachen sein, 20:00.040 --> 20:04.120 die mitgegeben werden, wenn ich meinen AB-Tree konstruiere. 20:04.120 --> 20:06.640 Und ich könnte dann auch verschiedene AB-Trees mit verschiedenen 20:06.640 --> 20:07.740 Parametern bauen. 20:08.620 --> 20:13.080 Und hier wieder an Generizität, die Elemente können irgendwelche 20:13.080 --> 20:15.640 Datentypen sein, wo es eine Funktion Key gibt. 20:18.060 --> 20:21.020 Ich initialisiere das hier mit der leeren Folge. 20:22.740 --> 20:27.320 Der speichert einerseits diese doppeltverkettete Liste L, die ich da 20:27.320 --> 20:27.960 generiere. 20:29.620 --> 20:32.540 Andererseits ein Zeiger auf die Wurzel. 20:33.860 --> 20:38.620 Und die Wurzel ist am Anfang ein AB-Item ohne Splitter. 20:40.160 --> 20:44.400 Und nur einen einzigen Nachfolger, nämlich das Zeiger auf das Dummy 20:44.400 --> 20:46.780 -Element von der doppeltverketteten Liste. 20:47.660 --> 20:52.380 Und die Höhe ist 1, weil wir hier einen Zeiger verfolgen müssen, um 20:52.380 --> 20:54.860 ein Blatt des Baumes zu erreichen. 20:56.680 --> 20:57.320 So. 20:59.040 --> 21:02.080 Dann werde ich als nächstes das Locate einführen. 21:02.860 --> 21:05.940 Wobei auf der AB-Tree-Ebene gibt es halt das, was man sich vorstellt, 21:06.020 --> 21:07.020 Locate -Key. 21:07.700 --> 21:13.020 Das wird aber implementiert durch Aufruf einer rekursiven Funktion auf 21:13.020 --> 21:14.660 einem AB-Tree-Item. 21:17.800 --> 21:23.720 Dem man den Schlüssel auch wieder übergibt, das auf dem Item operiert. 21:23.720 --> 21:26.320 Und der als zusätzlichen Parameter die Höhe kriegt. 21:26.880 --> 21:30.020 Am Anfang ist das die Gesamthöhe des Baumes und wenn ich absteige, 21:30.420 --> 21:31.560 geht das dann immer runter. 21:32.380 --> 21:35.580 Das Spannende ist jetzt natürlich, wie sieht diese rekursive Funktion 21:35.580 --> 21:36.040 aus? 21:39.100 --> 21:40.700 Wir haben da eigentlich sogar zwei. 21:40.820 --> 21:44.720 Einer ist erstmal, wie man lokal etwas findet. 21:45.320 --> 21:47.340 Das habe ich hier einfach deklarativ hingeschrieben. 21:49.040 --> 21:52.940 Im Prinzip, ich könnte ja einfach durch die Splitter durchgehen und 21:52.940 --> 21:57.180 finde dasjenige, das kleiner gleich SI ist. 21:57.640 --> 22:02.240 Beziehungsweise ich muss dann, wenn mein K größer dem letzten explizit 22:02.240 --> 22:04.860 gespeicherten SI ist, muss ich sagen, aha, dann ist es da. 22:05.300 --> 22:09.960 Ohne einen expliziten Vergleich mit diesem Wächter-Element zu machen, 22:10.040 --> 22:11.420 das ich gar nicht wirklich speichere. 22:13.180 --> 22:15.500 Der spannende Teil ist jetzt das Locate-Rekursive. 22:16.580 --> 22:18.600 Wie gesagt, es kriegt den Schlüssel und die Höhe. 22:20.060 --> 22:21.620 Ich mache jetzt das Locate-Locally. 22:23.380 --> 22:30.020 Und hier an diesem Beispiel, jetzt habe ich dieses Ding zum Beispiel 22:30.020 --> 22:30.660 gefunden. 22:33.060 --> 22:34.880 Und jetzt gibt es zwei Möglichkeiten. 22:35.920 --> 22:40.860 Wenn Höhe gleich 1 ist, heißt das, das ist bereits ein Blatt. 22:40.860 --> 22:43.660 Also ich muss noch einen Zeiger verfolgen und der geht dann zu einem 22:43.660 --> 22:45.140 Blatt, also zu einem List-Item. 22:45.820 --> 22:49.260 Und jetzt bin ich in genau der gleichen Situation wie bei den binären 22:49.260 --> 22:50.020 Suchbäumen. 22:50.160 --> 22:54.240 Entweder ich habe das gesuchte Element gefunden, dann muss aber 22:54.240 --> 22:56.980 gelten, dass das größer gleich meinem Schlüssel ist. 22:58.120 --> 22:59.860 Und dann gebe ich das auch zurück. 23:00.000 --> 23:02.180 CI ist Child I oder It ist Kind. 23:02.820 --> 23:04.340 Sonst gebe ich das nächste zurück. 23:05.480 --> 23:07.280 Das ist also der Basisfall. 23:08.240 --> 23:11.620 Und der andere ist ein rekursiver Aufruf auf CI. 23:12.820 --> 23:17.960 Also CI, Locate-Rekursive, gleicher Schlüssel, Höhe ist 1 niedriger. 23:23.840 --> 23:28.640 Und die Invariante ist auch wieder analog zu dem, was ich bei der 23:28.640 --> 23:29.600 binären Suche hatte. 23:31.260 --> 23:32.660 Fragen zu dem Locate. 23:34.040 --> 23:39.600 Also das ist jetzt genau wie bei den binären Suchbäumen, das Locate 23:39.600 --> 23:45.200 ist sozusagen die Funktion, an der ich schon alles darüber lernen 23:45.200 --> 23:49.000 kann, wie die Struktur des Baumes aufgebaut ist und was der eigentlich 23:49.000 --> 23:51.040 tut und wie ich mit der Invariante arbeite. 23:52.180 --> 23:56.460 Und die Einfügen und Löschen-Operationen, die müssen halt ein bisschen 23:56.460 --> 23:59.900 mehr machen, aber das Grundprinzip bleibt das gleiche. 23:59.900 --> 24:02.980 Es ist wichtig, dass Sie das hier verstehen und darauf kann man dann 24:02.980 --> 24:03.760 gut aufbauen. 24:04.580 --> 24:07.200 Also wenn es da jetzt Fragen gibt, möglichst jetzt fragen. 24:13.360 --> 24:24.340 Achso, also CI ist ja ein Zeiger auf ein List-Item. 24:26.760 --> 24:29.540 Das hier ist dann Methodenausruf. 24:29.960 --> 24:33.260 In dem Ding, was ist denn da das Nächste? 24:33.900 --> 24:40.080 Also diese Doubly Linked List Items haben ja eine Folge Member Next, 24:40.580 --> 24:43.420 nämlich das nächste Element in dieser doppeltverketteten Liste gibt. 24:45.480 --> 24:46.400 Weitere Fragen? 24:54.650 --> 24:56.070 Genau, also das ist das Locate. 24:57.270 --> 25:05.430 Laufzeit, na gut, also die haben innerhalb, also das Locate Locally 25:05.430 --> 25:08.910 braucht, wenn ich da linear durchsuche, O von B Zeit. 25:09.850 --> 25:14.110 Sie können sich überlegen, wie Sie das in Log B Zeit schaffen, nicht 25:14.110 --> 25:14.830 so schwierig. 25:16.990 --> 25:22.930 Und ich habe höchstens Höhe des Baumes Rekursionsebenen, also O von B 25:22.930 --> 25:23.550 mal Höhe. 25:25.450 --> 25:29.550 Und jetzt beweisen wir ausnahmsweise mal formal, dass die Höhe 25:29.550 --> 25:31.410 tatsächlich logarithmisch in N ist. 25:32.290 --> 25:38.330 Oder genauer gesagt ist h kleiner gleich 1 plus log zur Basis A von N 25:38.330 --> 25:39.950 plus 1 halber abgerundet. 25:41.130 --> 25:44.550 Und das möchte ich jetzt mal nachweisen, warum das so ist. 25:44.650 --> 25:46.490 Klassische vollständige Induktion. 25:47.550 --> 25:52.930 Für N gleich 1 steht hier, ok, 1 plus 1 durch 2 ist 1. 25:53.490 --> 25:58.290 Log zur Basis A von 1 ist 0, 0 abgerundet ist 0, plus 1 ist 1. 25:58.470 --> 25:59.910 Stimmt Höhe 1, prima. 26:00.510 --> 26:02.170 So, Fall N größer 1. 26:05.710 --> 26:11.270 Ich weiß, die Wurzel hat Grad größer gleich 2 und innere Knoten haben 26:11.270 --> 26:13.010 den Grad größer gleich A. 26:13.010 --> 26:18.230 Das heißt, es gibt größer gleich 2 mal A hoch H plus 1 Blätter. 26:19.270 --> 26:22.370 Oder mit anderen Worten, die Nachfolger der Wurzel haben alle 26:22.370 --> 26:24.810 mindestens A hoch H minus 1 Blätter. 26:25.370 --> 26:30.170 Da es mindestens 2 Nachfolger der Wurzel gibt, wird das 2 mal A hoch H 26:30.170 --> 26:30.890 minus 1. 26:37.270 --> 26:40.330 Also, wir wissen außerdem, es gibt N plus 1 Blätter. 26:40.950 --> 26:43.430 Nicht nur N, weil wir noch dieses Dummy-Element haben. 26:45.370 --> 26:53.050 Entsprechend gilt N plus 1 ist größer gleich 2 mal A hoch H minus 1. 26:53.630 --> 26:56.050 Und das kann ich jetzt im Wesentlichen nach H auflösen. 26:56.150 --> 27:00.750 Dann kriege ich H kleiner gleich 1 plus Log zur Basis A N plus 1 27:00.750 --> 27:01.330 halbe. 27:02.270 --> 27:05.530 Also, vielleicht noch ein bisschen mehr zu Fuß. 27:05.650 --> 27:09.150 Ich kann die 2 hier rüberbringen, dann steht hier N plus 1 halbe. 27:09.810 --> 27:14.530 Dann mache ich einen Logarithmus zur Basis H, dann steht hier Log zur 27:14.530 --> 27:20.610 Basis A, dann steht hier Log zur Basis A N plus 1 halbe größer gleich 27:20.610 --> 27:25.630 H minus 1 mal Log A. 27:27.410 --> 27:30.270 Aber Log zur Basis A von A ist 1. 27:30.270 --> 27:34.310 Das fällt dann weg, also steht da dann Log zur Basis A N plus 1 halbe 27:34.310 --> 27:37.570 größer gleich A minus 1. 27:37.910 --> 27:40.970 Dann bringe ich die 1 hier noch rüber, dann steht da H kleiner gleich 27:40.970 --> 27:44.770 1 plus Log zur Basis A N plus 1 halbe. 27:47.570 --> 27:51.650 Und jetzt behaupte ich ja etwas stärkeres, das ist kleiner gleich das 27:51.650 --> 27:52.650 Ding abgerundet. 27:52.650 --> 27:55.510 Aber naja, H ist immer eine ganze Zahl. 27:56.610 --> 28:01.270 Also wenn aus der Berechnung irgendwie 3,42 rauskommt, dann kann es in 28:01.270 --> 28:02.770 Wirklichkeit nur Größe 3 haben. 28:03.310 --> 28:04.330 Ich darf also abrunden. 28:05.550 --> 28:06.510 Fragen dazu? 28:11.010 --> 28:16.150 Also grob gesagt ist das Logarithmus zur Basis A von N, was ich da 28:16.150 --> 28:19.090 kriege, bis auf additive Fehler. 28:24.630 --> 28:28.230 Also das hier sagt, es kann einer mehr sein, das hier sagt, dafür 28:28.230 --> 28:32.270 teile ich das durch zwei, aber im Wesentlichen Log zur Basis A von N, 28:32.870 --> 28:36.330 wenn A eine Konstante ist, ist das O von Log N, wenn A keine Konstante 28:36.330 --> 28:37.550 ist, ist das sogar noch flacher. 28:38.450 --> 28:43.290 Das ist jetzt tatsächlich so, dass wenn man zum Beispiel AB-Bäume in 28:43.290 --> 28:48.310 Datenbänken sich anschaut, die im Sekundärspeicher liegen, dann sorgt 28:48.310 --> 28:51.550 man oft dafür, dass A sehr groß ist, vielleicht ein paar Tausend 28:51.550 --> 28:55.730 sogar, und dann kriegt man im Wesentlichen sowas wie H gleich zwei 28:55.730 --> 28:56.730 oder so. 28:59.590 --> 29:00.950 Selbst für große Eingaben. 29:02.530 --> 29:05.790 So, jetzt kommen wir mal zu den etwas komplizierteren Operationen. 29:06.210 --> 29:06.690 Einfügen. 29:08.690 --> 29:12.590 Da werde ich jetzt erstmal eine Algorithmen-Skizze vorführen, die Sie 29:12.590 --> 29:16.150 verstehen sollten im Detail und sich auch merken und vor allem die 29:16.150 --> 29:16.870 Ideen dahinter. 29:17.770 --> 29:22.530 Und dann gehe ich auf die Implementierungsdetails, die man dann 29:22.530 --> 29:25.330 vermutlich auch wieder vergisst, aber wo es natürlich auch gut ist, 29:25.390 --> 29:28.310 wenn man sie sich genau anguckt, dass man sie auch verstehen kann und 29:28.310 --> 29:31.470 es vielleicht mit ein bisschen Aufwand auch reproduzieren kann. 29:32.230 --> 29:34.990 Aber vermutlich wird man das dann nicht reproduzieren innerhalb der 29:34.990 --> 29:38.430 Klausur, dass man da dann detaillierte Codes für sowas aufschreiben 29:38.430 --> 29:38.770 muss. 29:40.450 --> 29:43.730 Also wir wollen Element E einfügen, jetzt machen wir erstmal ein 29:43.730 --> 29:44.150 Locate. 29:44.150 --> 29:47.130 Also wir suchen das nächste Element in der Liste E'. 29:48.690 --> 29:51.830 Das haben wir beim binären Suchbaum ja auch so gemacht und da unten 29:51.830 --> 29:54.330 haben wir dann an dem Baum rummanipuliert und das ging dann aber 29:54.330 --> 29:55.010 leider schief. 29:56.070 --> 29:58.230 Deshalb sehen wir schon, aha, da muss jetzt ein bisschen was 29:58.230 --> 30:00.850 passieren, um die Invarianten zu reparieren. 30:02.050 --> 30:04.910 Die mir ja dieses Logarithmische dann am Ende auch garantieren. 30:08.310 --> 30:10.710 Also, aber in der Liste ist das erstmal simpel. 30:10.710 --> 30:14.790 Ich füge das einfach vor E' ein und die Definition von Locate sagt 30:14.790 --> 30:17.990 mir, das ist genau die richtige Stelle, um es in der doppelt 30:17.990 --> 30:19.490 verketteten Liste einzufügen. 30:19.870 --> 30:23.530 Ich muss jetzt nur noch die Navigationsdatenstruktur reparieren. 30:24.490 --> 30:26.450 Aber das ist schon mal sinnvoll. 30:27.890 --> 30:35.090 Die Idee ist jetzt, ich füge den Schlüssel von E als neuen Spalter in 30:35.090 --> 30:38.730 den Vorgänger ein, in der Navigationsdatenstruktur. 30:40.390 --> 30:41.530 Nennen wir den mal U. 30:46.000 --> 30:49.320 Also stellen wir uns vor, wir sind hier ganz unten, da drunter sind 30:49.320 --> 30:53.500 nur noch die List-Items und dann ist da das U und da füge ich jetzt 30:53.500 --> 30:54.720 ein neues Element rein. 30:55.220 --> 31:00.060 Das kann ich machen, nur da gibt es ja auch eine Invariante, der sagt, 31:00.420 --> 31:04.440 aha, der hat Grad zwischen A und B. 31:05.480 --> 31:08.780 Wenn der vorher schon Grad B hatte, dann hat er jetzt Grad B plus 1, 31:08.880 --> 31:11.020 das verletzt die Invariante, da muss ich was machen. 31:12.520 --> 31:17.860 Und der Trick ist, in dem Fall, wenn der Grad zu groß wird, spalte ich 31:17.860 --> 31:21.100 diesen Knoten in zwei Knoten auf. 31:21.480 --> 31:26.280 Also ich erzeuge einen neuen Knoten, verteile die B plus 1 Elemente zu 31:26.280 --> 31:30.900 gleichen Teilen auf die neuen Knoten, also der linke kriegt B plus 1 31:30.900 --> 31:36.480 halber abgerundet, der rechte B plus 1 halber aufgerundet, viele 31:36.480 --> 31:37.980 Elemente. 31:41.480 --> 31:44.960 Und gucken wir uns mal den Fall hier an, hier drunter ist die Liste, 31:45.560 --> 31:50.140 hier habe ich jetzt eins mit B plus Grad B, das wird aufgespalten in 31:50.140 --> 31:55.180 zwei Dinger mit Grad B halbe und B halbe plus 1 oder sowas. 32:00.460 --> 32:04.820 Das ist jetzt ganz interessant, wir haben jetzt diesen Knoten da 32:04.820 --> 32:10.060 aufgespalten und das setzt sich jetzt nach oben fort. 32:10.180 --> 32:13.400 Das Aufspalten des Knotens bedeutet, ich brauche in dem Knoten da 32:13.400 --> 32:18.340 drüber jetzt auch einen neuen Splitdown, einen neuen Nachfolger, das 32:18.340 --> 32:22.000 ist also sozusagen wieder eine Einfügung eines neuen Elements, aber 32:22.000 --> 32:22.880 einen weiter oben. 32:23.780 --> 32:28.300 Und natürlich kann weiter oben das gleiche Problem passieren, da hat 32:28.300 --> 32:31.440 er auch schon Grad B, das heißt diese Aufspaltung setzt sich immer 32:31.440 --> 32:32.180 weiter fort. 32:33.480 --> 32:35.940 Naja, aber im Allgemeinen wird das irgendwann aufhören. 32:36.060 --> 32:40.520 Also ich finde jetzt ein x kleiner B, da habe ich dann am Ende x plus 32:40.520 --> 32:45.780 1, also die Aufspaltung hat sich bis hier fortgesetzt und dann stoppt 32:45.780 --> 32:48.560 das Ganze und meine Datenstruktur ist wieder repariert. 32:49.300 --> 32:50.960 Das ist die Grundidee. 32:52.940 --> 32:58.340 Nun könnte es sein, dass die Position, wo es stoppt, es gar nicht 32:58.340 --> 33:01.400 gibt, das ist dann der Fall, wenn selbst die Wurzel Grad B hat. 33:02.480 --> 33:05.860 Dann spalte ich die Wurzel auf, jetzt habe ich plötzlich zwei Bäume. 33:08.660 --> 33:10.280 Dann mache ich einfach eine neue Wurzel. 33:12.420 --> 33:17.420 Das heißt, an der Stelle inkrementiere ich dann die Höhe des Baums und 33:17.420 --> 33:19.020 ich kriege eine neue Wurzel mit Grad 2. 33:19.860 --> 33:22.660 Und jetzt sehen wir auch, wieso wir die Invariante bei der Wurzel so 33:22.660 --> 33:25.320 haben müssen, dass da Grad 2 reicht. 33:25.320 --> 33:30.040 In dem Moment, wo ich da unten aufspalte, habe ich gar nicht genug 33:30.040 --> 33:33.220 Knoten, um den oberen Grad A zu geben. 33:37.200 --> 33:41.940 Alles größer Grad 2 könnte ich für allgemeine Parameter gar nicht 33:41.940 --> 33:42.320 erreichen. 33:43.540 --> 33:46.180 Ein Beispiel, damit das ein bisschen konkreter wird. 33:47.880 --> 33:53.960 Wir wollen die 4 einfügen, suchen hier runter, finden die 5, fügen das 33:53.960 --> 34:01.280 hier ein und jetzt füge ich eben in den Vorgängerknoten einen Zeiger 34:01.280 --> 34:04.580 auf dieses List-Item und den dazugehörigen Schlüssel einfach ein. 34:05.320 --> 34:08.860 Und in dem Fall ist das jetzt wieder ein 2-4-Baum, ist die 34:08.860 --> 34:11.200 Gradbedingung nicht verletzt, ich bin fertig. 34:12.120 --> 34:18.100 Oder ein anderes Beispiel, wir fügen hier die 15 ein, wir suchen hier 34:18.100 --> 34:22.480 runter, finden die 17, fügen das hier ein und jetzt habe ich das mal 34:22.480 --> 34:26.240 konzeptionell so hingeschrieben, als würde ich hier temporär einen 34:26.240 --> 34:28.800 inneren Knoten mit 5 Nachfolgern bauen. 34:29.760 --> 34:33.720 Das darf ich aber nicht, weil ich gesagt habe, 4 ist die obere Grenze. 34:35.440 --> 34:36.360 Was mache ich dann? 34:36.420 --> 34:44.400 Ich spalte das Ding auf, 5 halber aufgerundet sind 3 links, ich mache 34:44.400 --> 34:46.520 2 links und 3 rechts hier. 34:48.960 --> 34:53.840 Also konzeptionell ist das so, ich nehme die Hälfte, ich schneide das 34:53.840 --> 34:57.660 Ding einfach mit dem Messer hier durch, aber dann bleibt dieser 34:57.660 --> 34:59.760 Splitter 11 sozusagen übrig. 35:01.320 --> 35:05.240 Den rechten Splitter brauche ich ja gar nicht, ich weiß ja alles, was 35:05.240 --> 35:09.640 größer ist als 7, landet halt hier. 35:10.640 --> 35:14.020 Aber das ist gerade der Schlüssel, den ich dann da oben wieder 35:14.020 --> 35:14.680 einfüge. 35:14.680 --> 35:17.260 Da gehe ich einen nach oben, 35:25.460 --> 35:30.480 und dann füge ich den hier ein und in dem Fall ist die Wurzel nicht 35:30.480 --> 35:31.980 überfüllt und ich bin fertig. 35:32.740 --> 35:33.480 Fragen dazu? 35:36.740 --> 35:38.480 Okay, noch ein weiteres Beispiel. 35:42.480 --> 35:49.400 Ich will die 3 einfügen, in diesem kleinen Baum hier. 35:53.140 --> 35:54.960 Nein, die 12. 35:58.560 --> 36:00.740 Oder gehe ich jemandem nach rechts? 36:00.940 --> 36:02.940 Aha, hier einfügen, fein. 36:04.900 --> 36:08.760 Jetzt kriege ich einen inneren Knoten mit 5 Nachfolgern, an der 36:08.760 --> 36:14.160 Wurzel, den spalte ich auf in 2, 3 und 5, 12 und endlich. 36:16.740 --> 36:23.280 Das hier ist die alte Wurzel, das ist sozusagen ein neuer Schlüssel, 36:23.520 --> 36:26.120 also jetzt den mittleren Schlüssel 3 nehme ich jetzt als Spalter, der 36:26.120 --> 36:30.280 nach oben propagiert wird und den zeige auf das Ding und diese 36:30.280 --> 36:36.140 Information, diesen Schlüssel und dieses T brauche ich jetzt, um ganz 36:36.140 --> 36:38.600 oben nochmal eine neue Wurzel zu bauen. 36:39.580 --> 36:42.460 Und dann kommt halt das hier raus, dann hat sich die Höhe um 1 36:42.460 --> 36:43.060 vergrößert. 36:43.560 --> 36:44.360 Gibt es dazu Fragen? 36:47.700 --> 36:48.260 So, 36:52.520 --> 36:55.600 jetzt müssen wir uns überlegen, funktioniert das denn immer? 36:55.840 --> 37:03.260 Also wir haben den inneren Knoten vom Grad b, machen daraus 37:03.260 --> 37:09.600 konzeptionell einen mit Grad b plus 1, spalten den dann auf und jetzt 37:09.600 --> 37:13.760 müssen ja beide Kinderknoten Grad mindestens a haben. 37:14.900 --> 37:18.680 Das heißt insbesondere der kleinere, der Grad b plus 1 halber 37:18.680 --> 37:22.020 abgerundet hat, muss ein Grad größer gleich a haben. 37:24.500 --> 37:27.760 Daraus folgt eine ganz einfache Bedingung, nämlich dass b größer 37:27.760 --> 37:29.980 gleich 2a minus 1 sein muss. 37:30.380 --> 37:33.540 Ich habe gesagt, wir werden b größer gleich 2a wählen aus anderen 37:33.540 --> 37:37.240 Gründen, aber 2a minus 1 würde im Prinzip reichen. 37:41.340 --> 37:45.600 Und das kann man jetzt, warum gilt das hier, warum ist diese 37:45.600 --> 37:47.480 Äquivalenz, können Sie einfach mal nachrechnen. 37:48.220 --> 37:54.320 Im Wesentlichen setzen Sie jetzt mal diesen Extremwert hier ein für b, 37:54.740 --> 38:00.800 2a minus 1 plus 1 halber gibt gerade genau a. 38:02.120 --> 38:08.160 Man kann sich jetzt leicht überlegen, wenn ich da ein kleineres b als 38:08.160 --> 38:11.120 2a minus 1 einsetze, dass das dann nicht mehr aufgeht, dass dann 38:11.120 --> 38:12.880 irgendwas kleiner a rauskommen würde. 38:13.340 --> 38:16.660 Während es klar ist, wenn ich das b noch größer wähle, dass das dann 38:16.660 --> 38:18.820 kein Problem sein kann. 38:22.940 --> 38:25.740 Also vielleicht noch mal zu konkreten Parameterwahlen. 38:26.320 --> 38:30.060 Sie können tatsächlich 2-3 Bäume bauen, das sind sozusagen die aller 38:30.060 --> 38:32.520 abgespecktesten abe-Bäume. 38:32.520 --> 38:36.260 Aber wie gesagt, meistens verwendet man eher 2-4 Bäume oder eben 38:36.260 --> 38:41.680 wirklich größere Parameter, so dass vielleicht das innere Knoten 38:41.680 --> 38:45.180 gerade noch in den Cache-Block passt, würde man vielleicht im Internal 38:45.180 --> 38:51.080 -Memory verwenden oder in eine Virtual-Memory-Page, dass das dann 38:51.080 --> 38:55.980 irgendwie 4 oder 8 Kilobyte sind, könnte man für Sekundärspeicher 38:55.980 --> 38:57.740 -Datenstrukturen verwenden, Fragen 39:01.030 --> 39:03.470 dazu? 39:07.610 --> 39:14.170 So, jetzt habe ich das aber erstmal so allgemein von der Idee her 39:14.170 --> 39:15.890 erklärt, jetzt gehen wir mal ein bisschen mehr in die 39:15.890 --> 39:17.250 Implementierungsdetails. 39:19.090 --> 39:24.090 Ein Problem, das ich habe, ist, dieses Aufspalten setzt sich von unten 39:24.090 --> 39:24.590 fort. 39:26.610 --> 39:30.050 Meine Datenstruktur speichert aber nur Zeiger, die von oben nach unten 39:30.050 --> 39:33.950 gehen. 39:34.070 --> 39:37.230 Ich kann also nicht sowas machen, wirklich erstmal ein Locate, ein 39:37.230 --> 39:40.590 ganz normales Locate, und dann habe ich nur diese Information, an 39:40.590 --> 39:43.110 welchem Blatt ich bin, von da komme ich nie wieder nach oben. 39:46.290 --> 39:51.270 Deshalb bauen wir sozusagen das Suchen und das Einfügen in eine 39:51.270 --> 39:55.130 Funktion zusammen und der Rekursionsstapel sorgt dann im Prinzip 39:55.130 --> 39:58.590 dafür, dass die zusätzliche Hilfsinformation, die ich brauche, 39:58.670 --> 39:59.510 gespeichert wird. 40:08.170 --> 40:12.030 Dann hat man eine Implementierungsentscheidung vor sich, wie diese 40:12.030 --> 40:14.630 Item -Datentypen aussehen. 40:14.750 --> 40:18.370 Das sind ja sozusagen Arrays variabler Größe zwischen A und B. 40:19.910 --> 40:24.770 Einträgen, dann ist vermutlich in den meisten Fällen das Beste, da ein 40:24.770 --> 40:26.930 statisches Array der Größe B bzw. 40:27.030 --> 40:29.270 B-1 für die Splitter zu allocieren. 40:32.170 --> 40:36.510 In C++ zumindest kann man das dann problemlos in einen Speicherbereich 40:36.510 --> 40:36.870 packen. 40:36.970 --> 40:42.010 Das Splitter-Array, das Kinder-Array und davor noch dieses D, die 40:42.010 --> 40:44.970 Größe, und das ist dann in einem kompakten Stück Speicher drin. 40:47.250 --> 40:50.230 Das immer die gleiche Größe hat und man kann damit eine relativ 40:50.230 --> 40:53.050 effiziente Speicherverwaltung machen, zum Beispiel wieder mit 40:53.050 --> 40:54.530 Freilisten oder was auch immer. 40:56.050 --> 41:02.650 Und natürlich sollten wir nie explizit diese temporären Knoten mit B 41:02.650 --> 41:04.410 -plus -1-Nachfolgern bauen. 41:04.970 --> 41:10.090 Ich werde das im Pseudocode so hinschreiben, aber in einer effizienten 41:10.090 --> 41:14.150 Implementierung würde man dann eher eine geeignete Fallunterscheidung 41:14.150 --> 41:14.390 machen. 41:17.570 --> 41:21.710 Die dann halt dieses neue Item alloziert und dann einzelne Elemente 41:21.710 --> 41:25.410 rüberkopiert in dieses neue Item, und zwar so, dass dann am Ende neues 41:25.410 --> 41:27.770 und altes Item da sind, wo sie hingehören. 41:28.570 --> 41:32.490 Und man nicht Sachen in temporäre Datenstrukturen rüberkopiert und 41:32.490 --> 41:36.450 dann nochmal rüberkopiert, das führt dann zu konstanten Faktoren der 41:36.450 --> 41:38.090 Laufzeit, die man sich sparen möchte. 41:39.150 --> 41:42.170 Das werde ich aber eben nicht in den Folien vorführen, weil das dann 41:42.170 --> 41:44.350 zu ziemlich länglichem, hässlichem Kot führt. 41:44.970 --> 41:48.730 Den man jetzt so frontal auch nicht mehr so leicht verstehen kann. 41:51.860 --> 41:54.360 So, dann gucken wir uns jetzt mal einigermaßen detaillierten 41:54.360 --> 41:55.400 Pseudocode an. 42:05.760 --> 42:09.020 Also hier ist das eigentliche Top-Level-Insert. 42:09.920 --> 42:14.500 Das ruft auf, wie bei dem Locate, auch ein rekursives Insert auf der 42:14.500 --> 42:14.900 Wurzel. 42:16.580 --> 42:19.360 Dem übergibt es wie beim Locate auch die Höhe. 42:19.360 --> 42:22.540 Ich übergebe dem aber jetzt auch nochmal die Liste. 42:22.960 --> 42:28.400 Also diese doppeltverkettete Liste ist ja abgespeichert an dem 42:28.400 --> 42:32.020 Baumobjekt, aber die Items haben darauf keinen direkten Zugriff, 42:33.140 --> 42:34.960 deshalb wird das hier als Parameter übergeben. 42:35.780 --> 42:39.400 Das ist ein kleines Detail, damit das in unsere Pseudocode-Sprache 42:39.400 --> 42:42.620 geht und ich denke in C oder Java hatten Sie ähnliche Probleme. 42:43.280 --> 42:48.640 So, und jetzt der Rückgabewert von diesem rekursiven Ding ist relativ 42:48.640 --> 42:49.320 kompliziert. 42:50.580 --> 42:55.820 Der gibt Ihnen einen Schlüssel und einen Zeiger oder einen Händel von 42:55.820 --> 42:56.400 einem Arbetri. 42:56.840 --> 43:00.420 Und die Bedeutung ist die folgende, es kann sein, dass das Einfügen 43:00.420 --> 43:01.700 einfach funktioniert hat. 43:02.200 --> 43:04.460 Dann ist das eigentlich egal, was da drin steht, dann ist die 43:04.460 --> 43:08.600 Vereinbarung, dass dann dieser Zeiger ein Nullzeiger ist, der mir 43:08.600 --> 43:13.560 ansagt, aha, da ist nichts Schlimmes passiert, aber es könnte halt 43:13.560 --> 43:20.880 sein, dass ich die Aufspaltoperation bis zur Wurzel fortgepflanzt 43:20.880 --> 43:28.600 habe, und in dem Fall kriege ich einen Zeiger auf sozusagen den einen 43:28.600 --> 43:33.680 Teil von dem Baum, der andere steht weiter in R, und den neuen 43:33.680 --> 43:35.040 Spaltschlüssel, den ich brauche. 43:36.060 --> 43:42.140 Das heißt, in dem Fall muss ich eine neue Wurzel vom Grad 2 bauen, die 43:42.140 --> 43:47.380 auf R und T als Nachfolger verweist und dieses K als Spaltschlüssel 43:47.380 --> 43:47.660 hat. 43:48.580 --> 43:51.780 Und in dem Fall muss ich auch die Höhe des Baums inkrementieren. 43:52.380 --> 43:55.620 Also auf dem Top-Level relativ einfach, aber ein etwas hässliches 43:55.620 --> 43:58.660 Interface für das rekursive Insert. 43:59.140 --> 44:01.480 Und jetzt gucken wir uns das rekursive Insert an, das ist 44:01.480 --> 44:05.100 wahrscheinlich auch der hässlichste Pseudocode, den wir bisher auf der 44:05.100 --> 44:08.640 Folie hatten, kann ich aber nichts gegen machen, das ist halt bei 44:08.640 --> 44:11.020 Arbetris ein bisschen unschöner. 44:11.300 --> 44:14.580 Wenn ich Ihnen Binärbäume hier vorgeführt hätte, dann würde das so 44:14.580 --> 44:21.660 sein, da hat man dann irgendwie Rebalanzierungsprozeduren, die auch 44:21.660 --> 44:24.820 über mehrere Folien gehen, mit zwölf Fallunterscheidungen und so einem 44:24.820 --> 44:25.280 Quatsch. 44:25.780 --> 44:29.340 Also bei den sortierten Folgen müssen sie irgendeinen Tod sterben 44:29.340 --> 44:29.680 leider. 44:29.680 --> 44:33.820 Da gibt es keine wirklich eleganten Lösungen, die sind alle ein 44:33.820 --> 44:34.740 bisschen hässlich leider. 44:38.900 --> 44:44.280 Also eine rekursive Prozedur auf dem Arbetris-Item, das Element ist 44:44.280 --> 44:48.520 klar, die verbleibende Höhe, die Liste und ich gebe zurück einen 44:48.520 --> 44:49.640 Schlüssel und einen Handle. 44:50.440 --> 44:53.360 Ich mache wieder ein Locate Locally, das ist genau wie beim normalen 44:53.360 --> 44:56.760 Locate, das sagt mir, wo in dem Baum muss ich eigentlich weitersuchen. 44:56.760 --> 45:04.140 Wenn die Höhe gleich eins ist, bin ich unten angelangt, dann mache ich 45:04.140 --> 45:09.880 das Insert auf der Liste und dann muss ich mir überlegen, was hier 45:09.880 --> 45:16.680 sozusagen die Aufspaltinformation ist. 45:16.780 --> 45:19.760 Das ist jetzt das neue Listen-Element und die dazugehörige... 45:19.760 --> 45:27.980 also der Handle von dem neuen Listen-Element und der Schlüssel, der da 45:27.980 --> 45:29.760 eingefügt wurde. 45:32.840 --> 45:38.460 Sonst, rekursiver Aufruf, mache ich einen rekursiven Aufruf auf CI, 45:38.620 --> 45:42.420 die Höhe dekrementiert sich, das E und das L wird so übergeben, wie 45:42.420 --> 45:46.000 ich es gekriegt habe und wie gesagt, ich kriege jetzt so ein K und T 45:46.000 --> 45:46.460 zurück. 45:50.160 --> 45:57.620 Und dann hatten wir ja dieses, falls da nichts zu tun war, also wenn 45:57.620 --> 46:03.660 das in dem rekursiven Aufruf alles schon schön balanciert war, die 46:03.660 --> 46:07.980 Invariante gilt, kriege ich ja einen Nullwert im T zurück und dann 46:07.980 --> 46:10.700 muss ich nach oben auch nichts weiter zurückgeben, dann gebe ich 46:10.700 --> 46:14.420 einfach auch das Null und irgendwas Undefiniertes zurück. 46:16.300 --> 46:25.240 Was übrig bleibt, ist der Fall, wo ich tatsächlich was tun muss in dem 46:25.240 --> 46:27.240 momentanen Arbitrary Item. 46:28.340 --> 46:31.120 Und jetzt mache ich das, wo ich gesagt habe, eine reale 46:31.120 --> 46:35.460 Implementierung sollte das nicht tun, ich erzeuge so temporäre 46:35.460 --> 46:44.400 Splitter und Timzeiger, die halt dieses vergrößerte Arbitrary Item 46:44.400 --> 46:48.120 haben, das also auch B plus 1 Elemente enthalten darf, da muss ich 46:48.120 --> 46:53.600 also einfach nach der Stelle I minus 1 mein K und T einfügen und alles 46:53.600 --> 46:56.060 andere wird halt um eine Position nach rechts geschoben. 46:56.840 --> 46:57.480 So, 47:02.290 --> 47:08.350 wenn jetzt der Grad vorher kleiner b war, dann ist er jetzt kleiner 47:08.350 --> 47:16.050 gleich b, dann kann ich einfach diese temporären Arrays in meinen S 47:16.050 --> 47:20.470 und C reinkopieren, das D wird um 1 vergrößert und ich kann 47:20.470 --> 47:24.910 zurückkehren und hier diesen Nullzeiger zurückgeben als Darstellung, 47:24.910 --> 47:27.970 jetzt bin ich fertig, ich musste hier in dem Arbitrary Item was 47:27.970 --> 47:30.570 ändern, aber nach oben pflanzt es sich nicht fort. 47:30.770 --> 47:35.450 Das wird damit gesagt und wie gesagt, in Wirklichkeit sollte man 47:35.450 --> 47:41.270 natürlich in diesem Fall hier oben schon abtesten, dann Elemente von 47:41.270 --> 47:45.230 den S und C nach rechts verschieben, jenseits der Stelle I und dann 47:45.230 --> 47:47.270 meine Elemente da einfügen und dann bin ich fertig. 47:47.270 --> 47:50.550 Oder aber, wenn ich gemerkt habe, es ist nicht balanciert, was anderes 47:50.550 --> 47:50.890 tun. 47:52.070 --> 47:55.110 Jedenfalls, ich mache es hier, damit es auf eine Folie passt, mit 47:55.110 --> 47:56.390 diesen temporären Arrays. 47:57.010 --> 48:01.190 So, also der Fall d kleiner b war relativ einfach. 48:02.790 --> 48:10.110 So, jetzt der Fall d gleich b, jetzt erzeuge ich zwei neue Listen 48:10.110 --> 48:21.190 Items, das neue d hier selber wird b plus 1 halber abgerundet sein und 48:21.190 --> 48:29.010 dieser Arbitrary-Knoten übernimmt sozusagen die rechte Hälfte. 48:29.010 --> 48:37.690 Deshalb kopiere ich von b plus 2 minus d bis b die Splitter rein und 48:37.690 --> 48:45.770 von b plus 2 minus d bis b plus 1 die Kinderknoten Und jetzt erzeuge 48:45.770 --> 48:50.970 ich einen neuen Arbitrie, in dem ich die Positionen 1 bis b-d bzw. 48:51.270 --> 48:56.450 1 bis b plus 1-d aus s-strich und c-strich reinkopiere. 49:01.190 --> 49:04.770 Und wenn Sie aufgepasst haben, da bleibt dann ein Element von dem 49:04.770 --> 49:08.310 Splitter -Array über, das wird jetzt zurückgegeben. 49:10.370 --> 49:15.250 Und jetzt verstehen Sie vielleicht auch diese komische Notation in 49:15.250 --> 49:15.970 diesem Beispiel. 49:17.070 --> 49:22.670 Das ist sozusagen mein T, das dann nach oben zurückgegeben wird. 49:27.450 --> 49:29.030 Gibt es dazu Fragen? 49:30.870 --> 49:34.050 Also mir ist klar, dass das jetzt relativ verwickelter Pseudocode ist. 49:37.010 --> 49:40.370 Und ich denke, wenn ich Sie jetzt in den Raum setzen würde und sagen, 49:40.570 --> 49:45.590 okay, hier ist ein Computer, kein Internetzugang, Sie haben eine Woche 49:45.590 --> 49:49.290 Zeit, das zu programmieren, dann würden das die meisten von Ihnen 49:49.290 --> 49:52.950 hinkriegen, aber ich glaube kaum jemand auf Anhieb. 49:53.070 --> 49:57.450 Also man macht da mindestens einen Plus-Minus-Eins-Fehler, wenn man 49:57.450 --> 49:58.310 sowas implementiert. 49:58.410 --> 50:00.670 Wahrscheinlich vier oder fünf, die man dann irgendwie langsam 50:00.670 --> 50:02.690 rausfizzeln muss. 50:03.550 --> 50:05.650 Das ist leider bei solchen Sachen so. 50:07.470 --> 50:10.830 Aber ich hoffe, dass zumindest dieser Pseudocode inzwischen korrekt 50:10.830 --> 50:11.130 ist. 50:11.930 --> 50:14.730 Wenn Sie da noch einen Fehler finden, weisen Sie mich darauf hin. 50:16.870 --> 50:22.670 Aber ich hoffe, was Sie sich merken, ist wirklich, das hier ist diese 50:22.670 --> 50:29.070 Algorithmen -Skizze und das da sind wir nur die Implementierung davon. 50:32.110 --> 50:36.330 Okay, das war das noch ein bisschen Sacken. 50:36.750 --> 50:38.230 Und jetzt kommt Entfernen. 50:38.970 --> 50:40.430 Das geht analog weiter. 50:41.670 --> 50:43.030 Ich erkläre es schon. 50:49.330 --> 50:53.170 Also vor allem, da ist jetzt auch noch eine oder eigentlich zwei 50:53.170 --> 50:54.430 algorithmische Ideen drin. 50:54.430 --> 51:02.230 Also für das Einfügen war halt der kreative Teil, was mache ich, wenn 51:02.230 --> 51:05.310 die Invariante verletzt wird? 51:05.370 --> 51:09.250 Aha, ich spalte die zu groß gewordenen Knoten in zwei auf und das 51:09.250 --> 51:10.970 verlangt sich nach oben fort. 51:12.090 --> 51:16.110 Und genau so hier beim Entfernen ist im Prinzip klar, was zu tun ist. 51:16.490 --> 51:18.890 Nur an irgendeiner Stelle verletzten Sie die Invariante. 51:19.070 --> 51:21.690 Ein Knoten wird zu klein und man muss sich überlegen, was macht man 51:21.690 --> 51:21.910 dann? 51:21.910 --> 51:25.150 Und das ist tatsächlich noch mal ein bisschen komplizierter als beim 51:25.150 --> 51:30.390 Einfügen -Fall, weil wir da zwei Reparaturmöglichkeiten verwenden 51:30.390 --> 51:34.930 müssen, weil nicht in jedem Fall eine der beiden anwendbar ist. 51:35.170 --> 51:39.270 Also die beiden zusammen sind immer anwendbar, aber eine alleine 51:39.270 --> 51:39.910 reicht nicht. 51:42.690 --> 51:48.010 Also es geht los wie immer, wir suchen den Pfad von der Wurzel, in dem 51:48.010 --> 51:50.230 Fall zu dem Element, das wir löschen wollen, selber. 51:50.230 --> 51:53.270 Wenn es das Element nicht gibt, sind wir fertig, das ist egal. 51:55.330 --> 51:59.050 Dann, wie eben auch, das Löschen in der doppeltverketteten Liste 51:59.050 --> 52:02.170 selber ist trivial, da machen wir einfach einen Remove. 52:04.050 --> 52:06.350 Und jetzt ist im Prinzip auch klar, was wir tun wollen. 52:06.430 --> 52:13.030 Wir müssen jetzt den Schlüssel, der dazu gehört, in dem Vorgänger U 52:13.030 --> 52:13.930 auch entfernen. 52:13.930 --> 52:17.470 Also wir haben hier ein Element in der doppeltverketteten Liste und 52:17.470 --> 52:21.870 darüber gibt es irgendwie einen inneren Knoten, der direkt darauf 52:21.870 --> 52:22.570 verweist. 52:23.690 --> 52:26.630 Und diesen Verweis und den dazugehörigen Schlüssel müssen wir 52:26.630 --> 52:28.930 entfernen, alles nach links schieben und dann sind wir eigentlich 52:28.930 --> 52:29.450 fertig. 52:30.410 --> 52:35.430 Außer, wenn danach, und das steht hier, nur es könnte jetzt sein, dass 52:35.430 --> 52:41.770 danach in diesem Vorgänger von dem Item der Grat unter die Schranke A 52:41.770 --> 52:44.850 -A fällt, also dann ist er genau A-1. 52:45.890 --> 52:47.970 Und jetzt müssen wir gucken, wie wir das reparieren. 52:48.870 --> 52:50.950 Aufspalten nützt nichts, dann wird es nur noch kleiner. 52:51.830 --> 52:52.550 Was mache ich denn da? 52:55.410 --> 52:58.810 Der Trick ist jetzt der folgende, ich suche mir irgendeinen Nachbarn. 53:01.870 --> 53:05.050 Das könnte einer zu rechten oder einer zu linken sein, aber da alle 53:05.050 --> 53:06.050 Knoten... 53:06.710 --> 53:10.630 Also ich muss mir den Vorgänger von U angucken und der hat grad 53:10.630 --> 53:11.490 mindestens zwei. 53:12.670 --> 53:15.210 Das heißt, es gibt entweder einen linken Nachbarn oder einen rechten 53:15.210 --> 53:17.070 Nachbarn, da suche ich mir einen von. 53:20.270 --> 53:21.450 Den nenne ich U-Strich. 53:24.150 --> 53:27.170 So, und jetzt kommt es darauf an, wie sieht der aus. 53:31.830 --> 53:39.250 Wenn der Grad von U-Strich plus der Grad von U, das war A-1, wenn der 53:39.250 --> 53:41.190 kleiner gleich B ist, 53:44.490 --> 53:47.130 dann fusioniere ich die beiden Knoten. 53:47.690 --> 53:49.950 Da mache ich aus zwei Nachbarn einen Knoten. 53:52.410 --> 53:55.970 Das führt dann wieder dazu, dass sich dieses Fusionieren, das pflanzt 53:55.970 --> 54:00.190 sich nach oben fort, das führt dazu, dass ich in dem Vorgänger von U 54:00.190 --> 54:04.150 dann auch ein Element löschen muss, einen Spalter und einen Verweis, 54:05.250 --> 54:07.670 und da könnte dann auch wieder die Invariante verletzt sein, dann 54:07.670 --> 54:09.810 mache ich irgendwas und das pflanzt sich nach oben fort 54:09.810 --> 54:10.630 möglicherweise. 54:12.210 --> 54:18.410 Das könnte sich auch so weit gehen, dass ich die aus der Wurzel was 54:18.410 --> 54:19.070 entferne. 54:22.330 --> 54:26.770 Die darf Grad kleiner A haben, aber die darf nicht Grad kleiner 2 54:26.770 --> 54:27.170 haben. 54:28.210 --> 54:30.950 Also wenn ich irgendwie eine Wurzel produzieren würde, die dann nur 54:30.950 --> 54:34.190 noch Grad 1 hat, dann schmeiße ich die einfach weg und der 54:34.190 --> 54:37.610 verbleibende, überlebende Nachfolger der Wurzel wird dann die neue 54:37.610 --> 54:37.950 Wurzel. 54:38.730 --> 54:42.530 Also das ist jetzt die Stelle, an der die Höhe des AB-Baums sich 54:42.530 --> 54:43.990 verringern kann. 54:47.610 --> 54:50.690 Jetzt kann es aber sein, dass dieses Fusionieren hier nicht 54:50.690 --> 54:56.810 funktioniert, weil das mag ja sein, dass der Grad von U klein ist, A 54:56.810 --> 54:57.390 -1. 54:57.870 --> 55:02.790 Es könnte ja sein, dass der Grad von U' groß ist, B sogar im 55:02.790 --> 55:03.490 Extremfall. 55:04.320 --> 55:11.930 Und B plus A-1 ist sicherlich größer als B, dann kann ich nicht 55:11.930 --> 55:12.490 fusionieren. 55:13.730 --> 55:16.010 Ist das eine gute oder eine schlechte Nachricht? 55:16.830 --> 55:19.970 In gewisser Weise ist es eine gute Nachricht, weil dann mache ich eine 55:19.970 --> 55:21.810 andere Operation, ich balanciere. 55:22.850 --> 55:34.180 Ich klaue im Prinzip Nachfolger von dem U' und habe dann beide Sachen 55:34.180 --> 55:34.840 ausgeglichen. 55:41.910 --> 55:45.590 Und da müssen wir uns natürlich überlegen, ich habe jetzt behauptet, 55:45.630 --> 55:48.750 wir können immer entweder Fuse oder Balance machen, daraus folgen dann 55:48.750 --> 55:51.810 Bedingungen an A und B, die wir uns gleich noch angucken müssen. 55:52.350 --> 55:55.310 Aber wenn die dann erfüllt sind, kann man immer entweder Fuse oder 55:55.310 --> 55:56.090 Balance machen. 56:01.670 --> 56:04.430 Wenn Sie so wollen, also balancieren kann man auch wieder auf 56:04.430 --> 56:05.890 verschiedene Arten und Weisen machen. 56:05.990 --> 56:09.430 Es gibt dann auch die realen Implementierungen, die gucken sich dann 56:09.430 --> 56:13.110 sowohl den linken als auch den rechten Nachbarn an und gucken, sollte 56:13.110 --> 56:16.970 ich die zum Beispiel alle zusammen irgendwie neu balancieren oder 56:16.970 --> 56:18.050 welchen nehme ich lieber. 56:18.650 --> 56:21.550 Aber die Performanceunterschiede davon sind nicht so riesig. 56:23.570 --> 56:25.810 Deshalb habe ich hier gesagt, ich nehme irgendeinen und das ist gut. 56:28.470 --> 56:31.830 Was man auch machen könnte, wäre dem Nachbarn wirklich nur einen 56:31.830 --> 56:33.490 einzigen Nachfolger stehlen. 56:34.570 --> 56:36.070 Das ist eine Möglichkeit. 56:36.250 --> 56:38.510 Wir haben es hier jetzt so hingeschrieben, dass wir eigentlich gesagt 56:38.510 --> 56:43.630 haben, aha, ich mache dann sogar konzeptionell dieses Fuse und danach 56:43.630 --> 56:45.270 wird es aber gleich wieder aufgespalten. 56:46.670 --> 56:48.230 Und zwar dann zu gleichen Teilen. 56:48.310 --> 56:50.950 Das scheint mir irgendwie so zu sein, dass man dann seltener was 56:50.950 --> 56:51.510 machen muss. 56:52.110 --> 56:56.850 Ich habe das aber nicht im Detail mir angeschaut. 56:57.510 --> 56:59.330 Jetzt gucken wir uns vielleicht noch die Bilder dazu an. 57:02.150 --> 57:05.210 Also wir haben hier jetzt, das ist wieder ein 2-4-Baum, jetzt haben 57:05.210 --> 57:08.430 wir hier zum 57:12.200 --> 57:20.260 Beispiel hier einen Knoten vom Grad 2, wir haben hier 57:23.450 --> 57:28.630 einen Knoten vom Grad 1, hier einen Knoten vom Grad 2, also das ist ja 57:28.630 --> 57:31.870 ein 2-4-Baum, der ist zu klein, der ist gerade noch groß genug. 57:33.030 --> 57:35.250 Zusammen gibt es einen Knoten vom Grad 3. 57:37.230 --> 57:38.770 Und dann sind die hier zusammengefügt. 57:39.150 --> 57:45.030 Oder beim Balance, da habe ich jetzt den Fall, ich habe einen Knoten 57:45.030 --> 57:48.090 vom Grad 1 und einen vom Grad 3. 57:53.430 --> 57:55.290 Daraus mache ich zwei vom Grad 2. 57:55.290 --> 58:00.290 Und die Dinger bleiben in ihrer relativen Antwort gleich. 58:00.410 --> 58:02.790 Ich muss die halt nur hin und her schieben zwischen diesen beiden 58:02.790 --> 58:03.310 Knoten. 58:03.730 --> 58:06.290 Gucken wir uns auch nochmal ein konkretes Beispiel an. 58:12.850 --> 58:13.990 Was wird gelöscht? 58:14.030 --> 58:15.930 Die 5, das ist mein K. 58:18.650 --> 58:19.890 Lösche ich aus der Liste? 58:20.110 --> 58:21.050 Klar, kein Problem. 58:21.690 --> 58:25.070 Jetzt muss ich das aus diesem Knoten rauslöschen, dann hat der nur 58:25.070 --> 58:28.150 noch einen Nachfolger, in dem Fall ist das dieses Dummy-Element, aber 58:28.150 --> 58:29.610 das macht keinen großen Unterschied. 58:30.710 --> 58:34.010 Der sucht sich einen Nachbarn, wir sehen einen rechten Nachbarn, kann 58:34.010 --> 58:37.250 ich nicht garantieren, aber in dem Fall gibt es einen linken, oder 58:37.250 --> 58:37.970 umgekehrt. 58:38.450 --> 58:39.550 Dann ist das der Nachbar. 58:43.730 --> 58:49.590 Der hat Grad 2, plus 1 ist 3, dann kriege ich das Ding. 58:50.370 --> 58:52.610 Jetzt war das so, die Wurzel hatte Grad 2 nur. 58:56.430 --> 58:59.890 Dadurch, dass ich die beiden zusammengefügt habe, fliegt hier ein 58:59.890 --> 59:04.250 Nachbar raus aus der Wurzel, der kriegt Grad 1, dann lösche ich die 59:04.250 --> 59:05.890 Wurzel und das wird meine neue Wurzel. 59:06.350 --> 59:10.470 Also ist der Baum geschrumpft von etwas Höhe 2 auf Höhe 1. 59:11.730 --> 59:16.730 Ein anderes Beispiel, wir wollen die 19 hier löschen. 59:21.570 --> 59:25.250 Dann kriegt der hier Grad 1, einen rechten Nachbarn gibt es nicht, 59:25.310 --> 59:26.390 einen linken. 59:27.570 --> 59:31.270 Den kann ich nicht fusen, weil der hat schon Grad 4, also muss ich 59:31.270 --> 59:32.010 balancieren. 59:34.070 --> 59:36.370 Das ist jetzt wieder der Zustand von da oben. 59:37.510 --> 59:40.070 Das Listen-Element hatte ich schon gelöscht, hier auch. 59:41.110 --> 59:49.190 Jetzt balanciere ich die, indem ich aus 4 plus 1 mache ich 3 plus 2. 59:53.910 --> 59:57.230 Und was dann noch passiert ist, dass man dann damit die Invariante 59:57.230 --> 01:00:02.470 wieder stimmt, diese Splitter-Elemente und Zeiger auch geeignet hin- 01:00:02.470 --> 01:00:04.830 und herschiebt, damit dann am Ende alles wieder stimmt. 01:00:09.710 --> 01:00:13.210 Warum geht das immer, dieses Entfernen? 01:00:14.190 --> 01:00:17.030 Dafür muss man zusätzliche Bedingungen erfüllen. 01:00:17.210 --> 01:00:21.290 Nach Fuse müssen zulässige Items entstehen. 01:00:21.290 --> 01:00:26.770 Das bedeutet, wenn ich einen Knoten vom Grad A mit einem Knoten vom 01:00:26.770 --> 01:00:37.290 Grad A-1 vereinige, darf höchstens Grad B da sein. 01:00:37.390 --> 01:00:41.050 Das heißt, B ist größer gleich 2A-1, das ist eine Bedingung, die wir 01:00:41.050 --> 01:00:42.050 schon hatten. 01:00:49.410 --> 01:00:54.210 Hier könnte es natürlich auch sein, dass ich irgendwas größer als A 01:00:54.210 --> 01:00:58.470 hier stehen habe, aber das führt nur zu weniger harten Bedingungen an 01:00:58.470 --> 01:00:59.210 B. 01:01:05.970 --> 01:01:06.470 Laufzeit. 01:01:08.610 --> 01:01:13.030 O von B mal Höhe, wie beim Locate auch. 01:01:14.390 --> 01:01:17.970 Die Höhe haben wir gezeigt, ist log zur Basis A von N asymptotisch. 01:01:19.850 --> 01:01:24.330 Und wenn A und B konstanten sind, ist das einfach O von log N. 01:01:26.870 --> 01:01:30.470 Man kann hier nicht so ohne weiteres, wenn man asymptotisch effizient 01:01:30.470 --> 01:01:33.410 sein will, ein nicht konstantes B wählen. 01:01:35.490 --> 01:01:40.430 Jetzt ist es auch so, wir hatten da diese Übungsaufgabe für das 01:01:40.430 --> 01:01:47.610 Locate, da habe ich gesagt, wie kann man in Zeit O von log B das 01:01:47.610 --> 01:01:50.670 Locate locally machen. 01:01:50.670 --> 01:01:54.410 Und dann können Sie sehen, dass die Laufzeit für das Locate, da ist es 01:01:54.410 --> 01:01:56.150 eigentlich egal, wie groß das B ist. 01:01:56.670 --> 01:01:59.350 Sie können auch B gleich unendlich machen, dann haben Sie ein 01:01:59.350 --> 01:02:00.110 sortiertes Array. 01:02:00.410 --> 01:02:03.710 Und Sie können trotzdem dann mit binärer Suche, jetzt habe ich es 01:02:03.710 --> 01:02:07.450 verraten, in logarithmischer Zeit das Locate locally und damit auch 01:02:07.450 --> 01:02:08.310 das Locate machen. 01:02:09.150 --> 01:02:12.130 Hier haben Sie ein bisschen ein Problem, also im schlechtesten Fall 01:02:12.130 --> 01:02:17.450 müssen Sie auf jeder Ebene des Suchbaums tatsächlich ein neues 01:02:17.450 --> 01:02:23.570 Arbetrie -Item anlegen oder O von B Arbeit beim Umkopieren von Sachen 01:02:23.570 --> 01:02:25.570 durchführen oder sowas. 01:02:25.670 --> 01:02:31.530 Und das braucht Zeit Theta von B, auch wenn Sie das Locate-Teil in log 01:02:31.530 --> 01:02:32.150 B können. 01:02:33.250 --> 01:02:35.810 Das heißt, da kommen Sie dann nicht um das hier drum herum. 01:02:37.550 --> 01:02:41.910 Das ist allerdings so, das machen wir in der Vorlesung nicht, aber man 01:02:41.910 --> 01:02:48.270 kann zeigen, dass wenn B größer gleich 2A ist, amortisiert wir nur 01:02:48.270 --> 01:02:53.110 konstant viele von diesen Split- und Fuse-Operationen machen. 01:02:56.470 --> 01:03:03.110 Und dann könnte man möglicherweise ein B gleich Log N verkraften. 01:03:03.830 --> 01:03:06.990 Aber dann muss man auch gucken, was da oben noch passiert. 01:03:06.990 --> 01:03:10.650 Ich glaube, man könnte dann zeigen, dass man B gleich Log N machen 01:03:10.650 --> 01:03:11.110 darf. 01:03:11.550 --> 01:03:17.230 Aber nicht so wichtig, eigentlich für die Asymptotik hier A und B sind 01:03:17.230 --> 01:03:17.730 konstant. 01:03:22.100 --> 01:03:27.420 Jetzt hatte ich bei dem Einfügen das ganze Jahr gemacht, erst die 01:03:27.420 --> 01:03:34.000 Algorithmen -Idee und dann im Detail den Pseudocode vorgeführt. 01:03:36.380 --> 01:03:39.380 Können Sie bei den A-B-Bäumen auch haben, nur weil wird der Pseudocode 01:03:39.380 --> 01:03:39.860 noch länger? 01:03:40.000 --> 01:03:43.060 Ich habe den hier in klein mal abgedruckt, so ein bisschen als 01:03:43.060 --> 01:03:45.720 Zeichen, dass ich da gar nicht im Detail drauf eingehen will. 01:03:46.520 --> 01:03:51.400 Ich will nur ein bisschen noch was dazu sagen, was man da konkret 01:03:51.400 --> 01:03:52.360 macht. 01:03:54.120 --> 01:03:57.460 Insgesamt sind die Details etwas kompliziert, wie merkt man die sich 01:03:57.460 --> 01:03:58.520 eigentlich gar nicht. 01:03:58.520 --> 01:04:02.400 Sondern was man sich merkt, sind die Invarianten von A-B-Trees, Höhe, 01:04:02.480 --> 01:04:06.080 Knotengerade, was das bedeutet, diese Splitterschlüssel. 01:04:06.600 --> 01:04:11.020 Und dann die Grundideen für die Updates, nämlich Spalten, Balancieren 01:04:11.020 --> 01:04:13.740 und Vereinigen von internen Knoten. 01:04:14.100 --> 01:04:16.540 Und den Rest leitet man sich dann bei Bedarf neu her. 01:04:18.100 --> 01:04:21.260 Jetzt will ich trotzdem mal ein bisschen über den Pseudocode hier 01:04:21.260 --> 01:04:21.660 sagen. 01:04:22.340 --> 01:04:25.760 Er ist auch nicht so viel komplizierter, wenn man genau hinguckt. 01:04:25.760 --> 01:04:32.640 Also wir haben einen A-B-Tree-Remove, das ruft wieder nur ein 01:04:32.640 --> 01:04:33.980 rekursives Remove auf. 01:04:34.500 --> 01:04:37.660 Und dann gibt es halt den Fall, dass die Wurzel gerade eins kriegt. 01:04:41.960 --> 01:04:44.940 Dann wird im Wesentlichen die Wurzel weggeschmissen. 01:04:45.280 --> 01:04:49.200 Und dann gibt es hier noch den Fall, dass der, das ist sogar erlaubt, 01:04:49.260 --> 01:04:51.900 wenn die Höhe auch nur eins ist. 01:04:51.900 --> 01:04:55.260 Weil dann habe ich die leere Liste und da darf ich das, sonst nicht. 01:04:57.020 --> 01:04:58.320 Also das ist relativ einfach. 01:04:58.400 --> 01:05:01.140 Jetzt habe ich wieder das Remove-Rekursive. 01:05:02.420 --> 01:05:07.140 Das kriegt einen Schlüssel, die Liste und die verbleibende Höhe. 01:05:07.720 --> 01:05:10.420 Ich mache wieder ein Locate-Locally, wie beim Locate, das ist ganz 01:05:10.420 --> 01:05:11.040 einfach. 01:05:11.460 --> 01:05:13.760 Wenn Höhe gleich eins ist, der Basisfall. 01:05:16.160 --> 01:05:21.740 Wenn der gefundene Schlüssel gleich dem gesuchten Schlüssel ist, muss 01:05:21.740 --> 01:05:24.400 ich was tun, sonst bin ich fertig, weil es gibt nichts zu löschen. 01:05:25.440 --> 01:05:29.860 Ich lösche das Ding aus der Liste und mache den Remove-Locally. 01:05:30.480 --> 01:05:32.940 Das Remove-Locally habe ich hier ganz high-level hingeschrieben. 01:05:33.340 --> 01:05:38.700 Ich entferne die entsprechenden Sachen aus dem Erase-C&S und 01:05:38.700 --> 01:05:39.860 dekrementiere den Grad. 01:05:40.900 --> 01:05:44.080 Der schwierige Fall ist der Rekursive-Fall natürlich. 01:05:44.960 --> 01:05:47.820 Da mache ich erstmal ein Rekursives-Remove. 01:05:49.220 --> 01:05:53.800 Wenn dadurch mein Grad unter A gefallen ist, muss ich was tun, sonst 01:05:53.800 --> 01:05:54.540 bin ich fertig. 01:05:56.280 --> 01:05:59.820 Jetzt mache ich wieder das, wo man in der realen Implementierung das 01:05:59.820 --> 01:06:00.600 vermeiden würde. 01:06:12.260 --> 01:06:14.920 Ich konkretiniere, was da ist. 01:06:14.920 --> 01:06:16.660 Das kann ich gar nicht lesen, das ist so klein. 01:06:23.810 --> 01:06:29.730 Ich suche mir meinen rechten Nachbarn. 01:06:35.810 --> 01:06:41.190 Ich tue so, als würde ich ein Fuse machen, so eine Art virtuelles 01:06:41.190 --> 01:06:41.570 Fuse. 01:06:42.490 --> 01:06:45.950 Warum kann ich da immer den rechten Nachbarn nehmen, das weiß ich im 01:06:45.950 --> 01:06:46.770 Moment auch nicht. 01:06:52.720 --> 01:06:56.900 Wenn das kleiner B ist, mache ich ein Fuse und sonst mache ich einen 01:06:56.900 --> 01:06:57.580 Balance. 01:07:01.420 --> 01:07:03.800 Ich weiß es im Moment auch nicht so genau, tut mir leid. 01:07:04.240 --> 01:07:06.200 Wie gesagt, das müssen Sie so im Detail nicht wissen. 01:07:07.680 --> 01:07:10.140 Deshalb frage ich jetzt auch nicht, ob es da Fragen zu gibt, das wäre 01:07:10.140 --> 01:07:11.940 nicht so sinnvoll. 01:07:13.240 --> 01:07:18.280 Ich hoffe, Sie haben die Grundideen hinter Insert und Remove von 01:07:18.280 --> 01:07:19.380 Arbetris verstanden. 01:07:21.180 --> 01:07:25.980 Jetzt haben wir noch Zeit, uns weitere Informationen anzuschauen. 01:07:27.500 --> 01:07:30.700 Minimum, das ist ganz einfach, ich wandle einfach den Baum immer nach 01:07:30.700 --> 01:07:31.020 links. 01:07:31.700 --> 01:07:33.280 Maximum, ich wandle immer nach rechts. 01:07:36.760 --> 01:07:39.580 Oder ich könnte sogar die Elemente in dieser Liste verwenden. 01:07:39.740 --> 01:07:42.860 Da habe ich ja den Dummy, der linke Nachfolger des Dummies ist das 01:07:42.860 --> 01:07:46.420 größte Element, der rechte Nachfolger ist das kleinste Element. 01:07:48.640 --> 01:07:50.620 Bereichsuche haben wir auch schon erklärt im Prinzip. 01:07:50.620 --> 01:07:54.800 Man macht ein Locate und durchläuft dann auch wieder nur die Liste. 01:07:57.940 --> 01:07:58.340 Build. 01:07:58.340 --> 01:08:03.440 Wir kriegen eine sortierte Liste und müssen nur noch die 01:08:03.440 --> 01:08:04.800 Navigationsdatenstruktur aufbauen. 01:08:05.260 --> 01:08:07.180 Das ist eine Übung, das können Sie sich überlegen. 01:08:07.620 --> 01:08:10.580 Da kann man zum Beispiel Bottom-up durch diese Liste durchlaufen, man 01:08:10.580 --> 01:08:19.160 kann immer innere Knoten maximalen Graz aufbauen, die dann wieder zu 01:08:19.160 --> 01:08:22.120 mehr inneren Knoten zusammenfassen und so weiter. 01:08:23.840 --> 01:08:29.360 Das ist ziemlich einfach zu sehen, dass das in linearer Zeit geht, 01:08:29.560 --> 01:08:33.760 weil Sie haben zwar logarithmisch viele Durchläufe, aber die Größe der 01:08:33.760 --> 01:08:35.800 verbleibenden Liste schrumpft geometrisch. 01:08:36.060 --> 01:08:37.480 Deshalb wird das lineare Zeit. 01:08:37.480 --> 01:08:42.820 Was nicht so einfach ist, ist dieses Konkatenieren und Aufspalten. 01:08:44.180 --> 01:08:47.580 Da steht dann im Buch, wie das im Detail in logarithmischer Zeit geht. 01:08:47.980 --> 01:08:51.280 Die Idee ist, dass ich da ganze Teilbäume umhängen kann. 01:08:51.820 --> 01:08:55.480 Und es ist auch relativ simpel, das in Log-N-Zeit zu machen. 01:08:56.740 --> 01:09:00.420 Nur einzusehen, dass das auch in Log-N geht, da muss man ein bisschen 01:09:00.420 --> 01:09:01.460 genauer hinschauen. 01:09:01.460 --> 01:09:07.240 Aber das ist keine so häufig benutzte Operation, deshalb ist das für 01:09:07.240 --> 01:09:09.500 Algorithmen 1 vielleicht ein bisschen Overkill. 01:09:10.040 --> 01:09:13.300 Aber ich finde, Sie sollen wissen, dass es das gibt, falls man es mal 01:09:13.300 --> 01:09:13.640 braucht. 01:09:16.420 --> 01:09:18.900 Das gleiche gilt für eine Merge-Operation. 01:09:20.240 --> 01:09:24.680 Wenn ich jetzt zwei sortierte Folgen habe, kann ich sozusagen die 01:09:24.680 --> 01:09:30.720 Information in der Navigationsdatenstruktur nutzen, um die zu einer 01:09:30.720 --> 01:09:33.340 großen Suchbaumdatenstruktur umzubauen. 01:09:33.860 --> 01:09:40.300 Sei jetzt zum Beispiel die linke Liste, die kleinere, mit n kleiner 01:09:40.300 --> 01:09:42.340 gleich m Elementen. 01:09:43.200 --> 01:09:44.320 Dann geht das in Zeit... 01:09:44.320 --> 01:09:47.800 Also es ist klar, Sie können einfach die Navigationsdatenstrukturen 01:09:47.800 --> 01:09:52.220 wegwerfen, das normale Merge aufrufen, das ist halt Laufzeit o von n 01:09:52.220 --> 01:09:56.920 plus m, und dann die Navigationsdatenstruktur neu draufbauen. 01:09:58.640 --> 01:10:02.380 Das geht in linearer Zeit auch o von n plus m, aber es geht schneller, 01:10:03.060 --> 01:10:06.140 und das ist dann wichtig, wenn die Listen sehr ungleiche Größe haben. 01:10:06.340 --> 01:10:11.500 Also wenn n klein gegen m ist, kann es durchaus sinnvoll sein, was 01:10:11.500 --> 01:10:14.720 Geschickteres zu machen in n mal log m durch n Zeit. 01:10:18.860 --> 01:10:23.180 Die Details sind aber auch ein bisschen komplizierter und hängen dann 01:10:23.180 --> 01:10:25.340 auch wieder mit dieser Idee der Fingersuche zusammen. 01:10:25.340 --> 01:10:30.860 Wenn Sie irgendwie schon was darüber wissen, wo das nächste Element in 01:10:30.860 --> 01:10:33.300 Ihrer Datenstruktur sein könnte, können Sie das ein bisschen schneller 01:10:33.300 --> 01:10:33.700 finden. 01:10:34.900 --> 01:10:39.940 Die Details wären jetzt nicht so einfach, vor allem nicht im Kontext 01:10:39.940 --> 01:10:43.720 der konkreten Repräsentation, die wir hier gewählt haben, deshalb 01:10:43.720 --> 01:10:44.840 verzichte ich darauf. 01:10:47.900 --> 01:10:52.840 Eine andere Sache, die wir nicht machen, das ist sozusagen wieder die 01:10:52.840 --> 01:10:54.020 Teilkapitel des Buchs. 01:10:54.020 --> 01:10:58.000 Also die Zusatzoperationen werden im Buch im Detail erklärt, hier 01:10:58.000 --> 01:11:02.240 weise ich nur darauf hin, wie es geht und was die Ideen dahinter sind, 01:11:02.320 --> 01:11:03.820 so ein bisschen Blick über den Tellerrand. 01:11:05.280 --> 01:11:08.040 Genauso amortisierte Analyse von Insert und Remove. 01:11:08.820 --> 01:11:13.300 Also grob gesagt kann man sowas zeigen, dass wir nur konstant viel 01:11:13.300 --> 01:11:19.780 Arbeit aufwenden, abgesehen von diesem rekursiven Abstieg bei der 01:11:19.780 --> 01:11:23.760 Suche nach den passenden Positionen in der Liste, machen wir nur 01:11:23.760 --> 01:11:26.420 konstant viel Arbeit, insbesondere auch nur konstant viele 01:11:26.420 --> 01:11:30.340 Speicherverwaltungsoperationen, was irgendwie wichtig dafür ist, zu 01:11:30.340 --> 01:11:33.920 verstehen, wie effizient oder nicht effizient diese realen 01:11:33.920 --> 01:11:35.200 Implementierungen sind. 01:11:37.540 --> 01:11:41.860 Und es gibt auch Varianten der Datenstruktur, wo man weitere 01:11:41.860 --> 01:11:46.620 Operationen hat, zum Beispiel hier ist ein Element der Liste, ich habe 01:11:46.620 --> 01:11:48.900 sowieso schon einen Zeiger darauf, löscht das mal. 01:11:50.100 --> 01:11:54.220 Dann können wir sowas in amortisiert konstanter Zeit implementieren, 01:11:54.520 --> 01:11:57.840 wenn die Datenstruktur ein bisschen anders implementiert ist, 01:11:58.040 --> 01:11:59.060 repräsentiert ist. 01:11:59.340 --> 01:12:03.560 Und da will ich jetzt darauf eingehen, nämlich wir können diese 01:12:03.560 --> 01:12:07.160 Suchbaumdatenstrukturen mit ein bisschen mehr Informationen 01:12:07.160 --> 01:12:11.340 ausstatten, die uns die effiziente Implementierung weiterer 01:12:11.340 --> 01:12:12.620 Operationen ermöglicht. 01:12:12.620 --> 01:12:16.700 Eben unter anderem dieses insert and remove in konstanter Zeit 01:12:16.700 --> 01:12:18.640 amortisiert in dem Fall. 01:12:22.320 --> 01:12:26.760 Aber erstmal ganz allgemein, die Idee ist, zusätzliche Informationen 01:12:26.760 --> 01:12:30.400 verwalten, daraus kriegt man mehr Operationen, die schneller 01:12:30.400 --> 01:12:36.580 implementiert werden, als wenn ich diese Augmentierung nicht 01:12:36.580 --> 01:12:37.400 durchgeführt hätte. 01:12:38.000 --> 01:12:41.620 Nachteil, wenn ich die zusätzlichen Operationen gar nicht brauche, 01:12:42.500 --> 01:12:45.540 verschwende ich Zeit und Platz für die Operationen, die ich benutze 01:12:45.540 --> 01:12:48.660 und die diese Informationen gar nicht brauchen, weil ich muss die halt 01:12:48.660 --> 01:12:49.760 immer aktualisieren. 01:12:53.500 --> 01:12:56.960 Im Softwareengineering nennt man das Goldplating, also Sie entwerfen 01:12:56.960 --> 01:13:00.820 Software und sagen, ich hätte aber gern noch die Operation, es könnte 01:13:00.820 --> 01:13:02.280 ja sein, dass ich mal das machen will. 01:13:02.280 --> 01:13:05.540 Und am Ende brauchen Sie es gar nicht oder nur ganz selten und dann 01:13:05.540 --> 01:13:08.500 lohnt sich das gar nicht, was Sie da in Aufwand getrieben haben. 01:13:09.160 --> 01:13:15.280 Und das zeigt leider auch, dass der Entwurf von Datenstrukturen, da 01:13:15.280 --> 01:13:18.600 können Sie nicht die absolute Lösung angeben, die Sie dann einmal in 01:13:18.600 --> 01:13:22.220 der Library implementieren und danach wird die immer benutzt von allen 01:13:22.220 --> 01:13:22.640 Leuten. 01:13:23.740 --> 01:13:27.360 Das wird nie funktionieren, weil entweder haben Sie das Goldplating 01:13:27.360 --> 01:13:31.180 gemacht, dann ist das Ding aber zu langsam für einfachere Benutzungen 01:13:31.180 --> 01:13:34.700 oder Sie haben das halt nicht gemacht, aber dann gibt es immer 01:13:34.700 --> 01:13:39.040 Anwendungen, die halt eigentlich diese Augmentierung brauchen in einer 01:13:39.040 --> 01:13:39.880 bestimmten Richtung. 01:13:40.520 --> 01:13:43.180 Und das rechtfertigt für mich auch ein bisschen, warum wir das hier 01:13:43.180 --> 01:13:43.760 überhaupt machen. 01:13:44.460 --> 01:13:48.380 Also jeder Informatiker sollte für diese grundlegenden Datenstrukturen 01:13:48.380 --> 01:13:52.800 wissen, wie die grob funktionieren und was so Augmentierungstechniken 01:13:52.800 --> 01:13:57.600 sind, weil es nicht unwahrscheinlich ist, dass Sie in der Praxis dann 01:13:57.600 --> 01:14:01.540 in der Zukunft mal auf Anwendungen stoßen, wo ein Performance 01:14:01.540 --> 01:14:04.820 -Bottleneck auftritt und Sie dann sehen, aha, da liegt in dieser 01:14:04.820 --> 01:14:08.780 Datenstruktur und ich kann aber vielleicht diese Datenstruktur für 01:14:08.780 --> 01:14:12.080 meine Anwendung so umbauen, dass ich dieses Performance-Bottleneck 01:14:12.080 --> 01:14:14.020 überwinden kann. 01:14:16.180 --> 01:14:19.560 Und da möchte ich jetzt ein paar Beispiele für Augmentierung deshalb 01:14:19.560 --> 01:14:20.160 vorführen. 01:14:21.540 --> 01:14:26.320 Eine ganz einfache Geschichte sind Elternzeiger, dass ich Verweise 01:14:26.320 --> 01:14:29.100 habe, nicht nur auf meine Nachfolger, sondern auch auf meine Vorgänger 01:14:29.100 --> 01:14:36.580 und dann kann man, wie gesagt, zum Beispiel so einen Remove machen, wo 01:14:36.580 --> 01:14:38.480 ich sage, hier ist dieses Ding, lösch das mal. 01:14:40.460 --> 01:14:42.580 Oder zum Beispiel das da, lösch das mal. 01:14:43.640 --> 01:14:47.100 Man muss natürlich jetzt wissen, dass sich das auf den da auswirkt und 01:14:47.100 --> 01:14:49.540 vielleicht sogar zu Fuse-Operationen führt usw. 01:14:53.740 --> 01:14:57.060 Und man kann auch sowas wie Insert Before oder Insert After dann 01:14:57.060 --> 01:15:04.420 machen und man spart sich die Suche von oben runter. 01:15:04.420 --> 01:15:09.980 Und dann wäre jetzt eine nette Übungsfrage, was ist denn der 01:15:09.980 --> 01:15:11.900 Vorgängerzeiger bei A-B-Bäumen? 01:15:13.400 --> 01:15:20.240 Hat da jemand eine Idee, ist das einfach ein Zeiger auf dieses A-B 01:15:20.240 --> 01:15:22.440 -Tree -Item oder ein bisschen mehr? 01:15:29.000 --> 01:15:32.400 Ich habe jetzt hier so suggestiv immer Zeiger da drauf gemacht. 01:15:32.400 --> 01:15:36.500 Also eigentlich wäre es praktisch, wenn da nicht nur ein Zeiger auf 01:15:36.500 --> 01:15:39.680 das A-B-Tree-Item steht, sondern auch die Position innerhalb dieses 01:15:39.680 --> 01:15:42.660 Splitter -Arrays, dass ich das nicht nochmal wieder suchen muss. 01:15:44.640 --> 01:15:49.080 Man kann sich dann auch überlegen, das sollte dann eigentlich immer in 01:15:49.080 --> 01:15:52.680 einen wirklichen Zeiger reinpassen, wenn man die Least Significant 01:15:52.680 --> 01:15:54.460 Bits für diesen Index verwendet und so. 01:15:54.780 --> 01:15:57.720 Kann man diverse Hacking-Tricks machen, um das wirklich effizient zu 01:15:57.720 --> 01:15:57.940 machen. 01:16:00.820 --> 01:16:04.140 Auf die Details will ich hier nicht eingehen, die können auch wieder 01:16:04.140 --> 01:16:04.860 hässlich sein. 01:16:05.420 --> 01:16:07.960 Zum Beispiel fällt mir gerade auf, wenn ich das hier löschen will, 01:16:08.760 --> 01:16:11.980 dann brauche ich für das Fuse ja einen Geschwisterknoten, den habe ich 01:16:11.980 --> 01:16:13.620 da gar nicht so ohne weiteres. 01:16:14.300 --> 01:16:17.140 Das führt dann dazu, dass ich entweder noch weiter hoch muss, bis ich 01:16:17.140 --> 01:16:21.080 meinen Geschwisterknoten gefunden habe, oder ich brauche zusätzlich so 01:16:21.080 --> 01:16:22.040 Geschwisterzeiger. 01:16:23.500 --> 01:16:27.180 Also da gibt es wieder ganz viele Möglichkeiten, auf die wir hier 01:16:27.180 --> 01:16:28.580 nicht im Detail eingehen wollen. 01:16:29.560 --> 01:16:32.680 Eine andere Möglichkeit, die ich ein bisschen ausführlicher vorstellen 01:16:32.680 --> 01:16:37.360 will, ist Abspeichern von Teilbaumgrößen in inneren Knoten. 01:16:41.080 --> 01:16:47.360 Da schlage ich hier eine etwas andere Variante vor als im Buch, und 01:16:47.360 --> 01:16:48.820 nur für die Binärbäume. 01:16:49.020 --> 01:16:52.040 Bei BNAB-Bäumen geht das dann wieder analog, aber eben ein bisschen 01:16:52.040 --> 01:16:52.800 komplizierter. 01:16:53.620 --> 01:16:57.300 Wir speichern in den inneren Knoten eines Binärbaums ab, wie viele 01:16:57.300 --> 01:17:01.180 Blätter von links aus erreichbar sind, von dem linken Zeiger. 01:17:01.720 --> 01:17:04.180 Wir werden später sehen, warum das genau das ist, was wir brauchen. 01:17:06.120 --> 01:17:11.220 Zum Beispiel, wenn ich jetzt das Karteelement in dieser sortierten 01:17:11.220 --> 01:17:15.500 Liste haben will, das ist gerade wieder unsere Select-Operation, die 01:17:15.500 --> 01:17:20.600 wir schon vom Quick-Select-Algorithmus kannten, dann funktioniert das 01:17:20.600 --> 01:17:20.920 so. 01:17:21.720 --> 01:17:27.080 Also ich habe eine rekursive Funktion, die kriegt die Wurzel von dem 01:17:27.080 --> 01:17:33.040 Teilbaum, in dem ich gerade suche, und ist K, und wenn von links 01:17:33.040 --> 01:17:38.920 größer K-Elemente erreichbar sind, eigentlich müsste da größer gleich 01:17:38.920 --> 01:17:43.260 K stehen, glaube ich, dann mache ich einfach einen rekursiven Aufruf 01:17:43.260 --> 01:17:43.980 nach links, 01:17:49.480 --> 01:17:52.280 weil hier dieses L nicht die Liste sein soll, sondern der linke 01:17:52.280 --> 01:17:52.880 Nachfolger. 01:17:55.960 --> 01:18:03.380 Sonst mache ich einen rekursiven Aufruf auf den rechten Nachfolger, 01:18:03.500 --> 01:18:05.480 und dann aber mit K minus Left Size. 01:18:06.500 --> 01:18:09.680 Eigentlich der gleiche Trick wie beim Quick-Select, nur dass ich jetzt 01:18:09.680 --> 01:18:13.660 in dieser Datenstruktur suche, und wir haben jetzt eine Datenstruktur 01:18:13.660 --> 01:18:18.040 mit, zumindest wenn ich den balanciere, logarithmischer Tiefe, und ich 01:18:18.040 --> 01:18:20.980 kann also mein Select in logarithmischer Zeit implementieren, während 01:18:20.980 --> 01:18:28.260 Quick -Select, weil es eine unsortierte Liste hatte, in linearer Zeit 01:18:28.260 --> 01:18:29.100 gearbeitet hat. 01:18:32.360 --> 01:18:35.800 Genau, da ergeben sich jetzt schöne Übungsaufgaben, wenn Sie das 01:18:35.800 --> 01:18:40.440 haben, könnten Sie sich überlegen, wie verallgemeinere ich das auf AB 01:18:40.440 --> 01:18:44.340 -Bäume, eine andere Operation, die man in logarithmischer Zeit relativ 01:18:44.340 --> 01:18:49.900 leicht kann, ist den Rang eines Elements zu bestimmen, also welche 01:18:49.900 --> 01:18:54.080 Position hat der in dieser Liste, da das eine verkettete Liste ist, 01:18:54.080 --> 01:18:58.380 ist das erstmal nicht einfach, aber mit diesen Left Size-Informationen 01:18:58.380 --> 01:19:04.200 können Sie das auch in logarithmischer Zeit, oder eine Variante der 01:19:04.200 --> 01:19:08.740 Bereichssuche, wo Sie sagen, gib mir nicht alle Elemente in dem 01:19:08.740 --> 01:19:11.100 Bereich A bis B, sondern zähle die nur. 01:19:15.040 --> 01:19:18.320 Und das geht auch in logarithmischer Zeit und relativ einfach. 01:19:18.700 --> 01:19:23.200 Schöne Übungsaufgabe, vielleicht auch Klausuraufgabe, weiß ich nicht. 01:19:23.940 --> 01:19:26.900 Jetzt will ich mal das Select an einem Beispiel vorführen. 01:19:26.900 --> 01:19:33.500 Also wir haben diesen binären Suchbaum und das Blaue, was ich da dran 01:19:33.500 --> 01:19:36.200 geflanscht habe, ist die augmentierte Information. 01:19:39.200 --> 01:19:44.700 Also gucken wir nochmal, Suchbaumwurzel, sieben Elemente nach links 01:19:44.700 --> 01:19:48.620 erreichbar, eins, zwei, drei, vier, fünf, sechs, sieben, stimmt. 01:19:50.720 --> 01:19:56.440 Ich suche das sechste Element, sieben ist größer gleich sechs, also 01:19:56.440 --> 01:19:57.680 kann ich links weitersuchen. 01:20:00.220 --> 01:20:03.540 Hier sind nach links vier erreichbar, eins, zwei, drei, vier. 01:20:10.520 --> 01:20:12.500 Sechs ist größer vier. 01:20:17.100 --> 01:20:24.920 Also mache ich einen rekursiven Aufruf nach rechts und suche hier aber 01:20:24.920 --> 01:20:26.540 eben das zweite Element. 01:20:31.280 --> 01:20:34.340 Die vier kann ich abziehen, also das zweite hier. 01:20:35.660 --> 01:20:39.160 Und jetzt steht hier, da sind zwei im linken Teilbaum, also kann ich 01:20:39.160 --> 01:20:40.320 nach links absteigen. 01:20:41.480 --> 01:20:44.860 Da ist nur einer im rechten Teilbaum, also steige ich nach rechts ab 01:20:44.860 --> 01:20:48.280 und habe meine 13 gefunden und tatsächlich eins, zwei, drei, vier, 01:20:48.440 --> 01:20:49.980 fünf, sechs, passt. 01:20:50.620 --> 01:20:51.380 Fragen dazu? 01:21:00.960 --> 01:21:03.760 Und das können Sie halt ohne diese Augmentierung durch die 01:21:03.760 --> 01:21:06.700 Teilbaumgrößen, wüsste ich nicht, wie man das hinkriegen soll. 01:21:08.340 --> 01:21:15.040 Es gibt übrigens auch Varianten von AB-Bäumen, wo man die Invariante 01:21:15.040 --> 01:21:18.640 gar nicht über die Gerade festlegt, sondern über die Größe von 01:21:18.640 --> 01:21:21.120 Teilbaum, das nennt man Weight-Balanced B-Trees. 01:21:21.900 --> 01:21:25.040 Die haben auch schöne Vorteile und unterstützen dann nebenbei noch 01:21:25.040 --> 01:21:28.380 diese Eigenschaft, haben aber auch leider Nachteile, deshalb stelle 01:21:28.380 --> 01:21:29.440 ich das so hier nicht vor. 01:21:30.900 --> 01:21:32.500 So, fassen wir das mal zusammen. 01:21:34.200 --> 01:21:38.180 Suchbäume erlauben viele effiziente Operationen auf sortierten Folgen. 01:21:39.180 --> 01:21:41.840 Die Ausführungszeit für viele dieser Operationen ist einfach nur 01:21:41.840 --> 01:21:46.780 logarithmisch und der schwierige Teil dabei ist, diese logarithmische 01:21:46.780 --> 01:21:47.810 Höhe wirklich zu erzwingen. 01:21:49.120 --> 01:21:50.500 Das kriegen Sie nicht umsonst. 01:21:52.180 --> 01:21:57.080 Und wir haben diese Augmentierungen, die uns weitere Operationen 01:21:57.080 --> 01:21:58.100 effizient erlauben. 01:21:58.100 --> 01:21:58.640 Ja, 01:22:03.290 --> 01:22:10.350 es gibt ein paar Dinge, die wir nicht hier gemacht haben, obwohl sie 01:22:10.350 --> 01:22:11.030 schön wären. 01:22:11.210 --> 01:22:13.990 Zum Beispiel hatte ich am Anfang dieses Bild vom Karteikasten. 01:22:18.320 --> 01:22:20.820 Eine Baumdatenstruktur ist etwas komplett anderes als ein 01:22:20.820 --> 01:22:21.720 Karteikasten. 01:22:23.580 --> 01:22:27.940 Da kann man sich fragen, wir haben jetzt ganz oft den Fall gehabt, zum 01:22:27.940 --> 01:22:33.940 Beispiel beim Radexort, dass diese Analogrechner-Implementierungen 01:22:33.940 --> 01:22:38.400 dann am Ende wieder digitale Gegenstücke haben, die auch nützlich 01:22:38.400 --> 01:22:38.840 sind. 01:22:40.100 --> 01:22:44.940 Und tatsächlich gibt es eine Datenstruktur, die kann man am besten als 01:22:44.940 --> 01:22:47.000 sortiertes Array mit Löchern bezeichnen. 01:22:47.340 --> 01:22:50.760 Also Sie haben ein sortiertes Array, in dem stehen Ihre Elemente, aber 01:22:50.760 --> 01:22:53.400 das Array ist ein bisschen größer, einen konstanten Faktor, sagen wir 01:22:53.400 --> 01:22:57.540 mal zweimal so groß versuchen Sie, oder Sie versuchen sicherzustellen, 01:22:57.600 --> 01:23:01.020 dass das zwischen zwei und viermal so groß ist wie die Anzahl Elemente 01:23:01.020 --> 01:23:01.620 von mir aus. 01:23:02.700 --> 01:23:05.320 Und da, wo kein Element gespeichert ist, ist ein Loch. 01:23:06.260 --> 01:23:09.820 Dieses Loch hat aber auch einen Schlüssel, der zu dieser Invariante 01:23:09.820 --> 01:23:14.220 passt, dass das Ganze bezüglich dieser Schlüssel sortiert ist. 01:23:15.000 --> 01:23:17.760 Dann können Sie nämlich auf diesem Array weiter binäre Suche machen. 01:23:19.240 --> 01:23:23.440 Das heißt, suchen ist ganz schnell, löschen ist auch ganz schnell, Sie 01:23:23.440 --> 01:23:28.420 machen binäre Suche und sagen, okay, dieses Element markiere ich jetzt 01:23:28.420 --> 01:23:31.220 als gelöscht, der Schlüssel bleibt stehen, aber es ist jetzt ein Loch. 01:23:32.720 --> 01:23:39.060 Einfügen ist auch relativ einfach, Sie suchen die richtige Position 01:23:39.060 --> 01:23:43.720 und jetzt schieben Sie lokal die Elemente hin und her, damit ein Loch 01:23:43.720 --> 01:23:46.160 entsteht und fügen da Ihr Element ein. 01:23:47.860 --> 01:23:52.280 Wenn Sie das so naiv machen, dann kann es halt passieren, dass wenn 01:23:52.280 --> 01:23:55.040 Sie ganz viel an der gleichen Stelle einfügen, dass Sie dann immer 01:23:55.040 --> 01:23:56.800 wieder ganz viel schieben müssen. 01:23:57.460 --> 01:24:01.180 Und dann gibt es halt Techniken, wie man dann das Ganze balanciert. 01:24:01.340 --> 01:24:05.860 Man macht dann ab und zu mal ein bisschen mehr Arbeit, verteilt die 01:24:05.860 --> 01:24:08.880 Löcher etwas gleichmäßiger über das Array und dann kriegt man wieder 01:24:08.880 --> 01:24:10.180 eine effiziente Datenstruktur. 01:24:11.060 --> 01:24:14.400 Und das finde ich klasse, weil das genau das ist, was Sie beim 01:24:14.400 --> 01:24:15.360 Karteikasten machen. 01:24:15.360 --> 01:24:20.000 Sie suchen da in dem Karteikasten, schieben da eine neue Karteikarte 01:24:20.000 --> 01:24:24.160 rein und klopfen dann so ein bisschen, dass sich das nach hinten 01:24:24.160 --> 01:24:24.560 verschiebt. 01:24:24.640 --> 01:24:27.440 Und manchmal ist das aber so eng, dass Sie dann ein bisschen 01:24:27.440 --> 01:24:30.900 rumkruscheln müssen, bis das wieder passt. 01:24:33.200 --> 01:24:36.000 Und das ist genau dieses Array mit Löcher und Datenstruktur 01:24:36.000 --> 01:24:36.520 eigentlich. 01:24:37.940 --> 01:24:41.300 Also der Karteikasten, wenn Sie den voller Karteikasten stopfen, dass 01:24:41.300 --> 01:24:43.660 er so richtig voll ist, können Sie den gar nicht mehr benutzen. 01:24:44.220 --> 01:24:46.420 Das ist die Analogie auch. 01:24:53.050 --> 01:24:54.590 Anderer Blick über den Tellerrand. 01:24:54.970 --> 01:24:59.070 Wie gesagt, A-B-Bäume sind eine wichtige externe Datenstruktur. 01:24:59.590 --> 01:25:01.650 Also wenn das Ganze nicht mehr in den Hauptspeicher passt. 01:25:03.530 --> 01:25:06.710 Oder wahrscheinlich ist das auch auf dem Smartphone relevant, weil da 01:25:06.710 --> 01:25:09.510 haben Sie auch nur begrenzten Hauptspeicher und ganz viel Flash 01:25:09.510 --> 01:25:09.930 -Memory. 01:25:10.610 --> 01:25:14.750 Und dann sind halt Ihre natürlichen Seitengrößen eine Seite von diesem 01:25:14.750 --> 01:25:19.430 Flash -Memory, das den Massenspeicher des Smartphones zum Beispiel 01:25:19.430 --> 01:25:20.010 darstellt. 01:25:22.310 --> 01:25:26.550 Was noch ganz spannend ist, wir hatten das beim Sortieren ja auch, 01:25:26.610 --> 01:25:29.530 wenn Sie ganzzahlige Schlüssel haben, geht es schneller. 01:25:30.950 --> 01:25:34.630 Und tatsächlich gibt es eine Suchbaum-Datenstruktur mit Lock-Lock-U 01:25:34.630 --> 01:25:37.950 -Zugriffszeit, wenn U der maximale Schlüssel ist. 01:25:39.930 --> 01:25:42.910 Nennt sich Van Emde Boas Suchbaum-Datenstruktur. 01:25:44.190 --> 01:25:47.310 Und dann gibt es Verallgemeinerungen für Zeichenketten oder 01:25:47.310 --> 01:25:51.770 mehrdimensionale Daten, also zum Beispiel Punkte in zwei- oder 01:25:51.770 --> 01:25:53.750 dreidimensionalen eukalyptischen Räumen. 01:25:54.690 --> 01:25:56.350 Und alle möglichen schönen Dinge. 01:25:57.930 --> 01:25:59.550 Also eigentlich ist das hier erst der Anfang. 01:25:59.710 --> 01:26:02.710 Sie können über so Suchbaum-Datenstrukturen in der Algorithmusstudie 01:26:02.710 --> 01:26:05.070 noch ganz viel lernen, da gibt es noch ganz viele Anwendungen. 01:26:07.090 --> 01:26:11.030 Mal ein paar Zahlen, Implementierungen. 01:26:15.390 --> 01:26:20.770 Wir haben hier fünf verschiedene Suchbaum-Datenstrukturen für 01:26:20.770 --> 01:26:22.490 zufällige 32-Bit-Zahlen. 01:26:23.410 --> 01:26:28.730 Der x-Achse ist die Anzahl Elemente. 01:26:30.030 --> 01:26:34.590 Und zwar sind das einfach zufällige Elemente, zwischen 1 und 1 01:26:34.590 --> 01:26:35.570 Milliarde glaube ich. 01:26:36.590 --> 01:26:40.610 Und dann ziehen wir auch zufällige Schlüssel und machen ein Locate. 01:26:41.490 --> 01:26:45.590 Das Ganze wiederholen wir ganz oft und messen die Zeit für ein Locate 01:26:45.590 --> 01:26:46.730 in Nanosekunden. 01:26:48.150 --> 01:26:52.190 Das ist auch schon wieder zehn Jahre alt, das Papier, aber ich glaube, 01:26:52.270 --> 01:26:53.730 so viel hat sich da nicht geändert. 01:26:54.710 --> 01:26:59.650 Und wir haben hier in der Mitte zwei vergleichsbasierte 01:26:59.650 --> 01:26:59.890 Datenstrukturen. 01:27:00.610 --> 01:27:06.010 Das eine ist die STL-Map, das ist ein binärer Suchbaum, von dem Sie 01:27:06.010 --> 01:27:09.130 aber lernen werden, und zwar das nennt sich ein Red-Black-Tree. 01:27:10.090 --> 01:27:13.410 Der hat eine Invariante, dass die Höhe des Baumes höchstens zweimal 01:27:13.410 --> 01:27:14.190 log n ist. 01:27:15.350 --> 01:27:18.550 Und der in gewisser Weise isomorph zu 2-4 Bäumen ist. 01:27:20.710 --> 01:27:26.730 Und wir haben eine AB-Baum-Implementierung aus Leda, das ist Library 01:27:26.730 --> 01:27:30.210 of Efficient Data Types and Algorithms, und zwar mit einer etwas 01:27:30.210 --> 01:27:32.890 extremen Variante, das sind 2-16 Bäume. 01:27:33.870 --> 01:27:38.790 Das ist ein bisschen effizienter als 8-16 Bäume für den Operationen 01:27:38.790 --> 01:27:40.930 -Mix, den wir hier probiert haben. 01:27:42.750 --> 01:27:49.470 Und das ist ganz instruktiv, was da passiert, dieser 2-4 Baum aus der 01:27:49.470 --> 01:27:52.610 Standard Template Library, der ist für kleine Eingaben ein bisschen 01:27:52.610 --> 01:28:00.130 schneller und für große ein bisschen langsamer als die 2-16 Bäume. 01:28:02.490 --> 01:28:06.470 Der bricht einen früher ab, das heißt diese 2-16 Bäume brauchen auch 01:28:06.470 --> 01:28:07.630 ein bisschen mehr Platz leider. 01:28:08.430 --> 01:28:11.390 Also man könnte sagen, okay, verschiedene vergleichsbasierte 01:28:11.390 --> 01:28:15.310 Datenstrukturen sind so ein bisschen relativ nah beieinander, 01:28:15.550 --> 01:28:18.830 allerdings bei großen Datenstrukturen sind tatsächlich die AB-Bäume 01:28:18.830 --> 01:28:20.810 cache -effizienter, erheblich. 01:28:21.410 --> 01:28:26.290 Und das ist, was ich demonstrieren wollte, was vielleicht auch ein 01:28:26.290 --> 01:28:28.990 bisschen noch mal rechtfertigt, warum wir hier die AB-Bäume gemacht 01:28:28.990 --> 01:28:29.330 haben. 01:28:29.830 --> 01:28:33.150 Und dann gibt es diese Datenstrukturen mit log log u, das war 01:28:33.150 --> 01:28:35.310 tatsächlich die Forschungsfrage, die wir damals hatten. 01:28:35.310 --> 01:28:39.490 Und dann gab es noch mal 10 Jahre älteres Papier und unsere eigene 01:28:39.490 --> 01:28:44.050 Implementierung, die gesagt hat, schöne Theorie geht nicht in der 01:28:44.050 --> 01:28:45.410 Praxis, ist viel zu langsam. 01:28:46.510 --> 01:28:49.070 Und dann haben wir gesagt, das glauben wir nicht, wir machen jetzt 01:28:49.070 --> 01:28:52.310 Algorithm Engineering mit einer ganzen Menge Implementierungstricks, 01:28:53.970 --> 01:28:55.750 spezialisiert für 32-Bit-Schlüssel. 01:28:56.750 --> 01:28:59.830 Was genau wir gemacht haben, lernen Sie in der Vorlesung Algorithm 01:28:59.830 --> 01:29:00.310 Engineering. 01:29:00.310 --> 01:29:03.330 Und dann waren wir tatsächlich deutlich schneller, sogar 01:29:03.330 --> 01:29:05.350 überraschenderweise über den ganzen Schlüsselbereich. 01:29:08.230 --> 01:29:11.890 Also Theorie funktioniert, wenn man sie sehr gut implementiert, das 01:29:11.890 --> 01:29:13.550 ist so ein bisschen die Lehre, die man daraus schließt. 01:29:14.310 --> 01:29:20.570 Und man sollte keine voreiligen Schlüsse aus schlechten 01:29:20.570 --> 01:29:21.630 Implementierungen schließen. 01:29:22.610 --> 01:29:24.510 Also es hat sich genau umgedreht. 01:29:24.750 --> 01:29:28.410 Vorher waren wir viel langsamer als vergleichsbasierte Datenstrukturen 01:29:28.410 --> 01:29:29.910 und nachher deutlich schneller. 01:29:33.450 --> 01:29:36.490 So, ja, damit sind wir fertig mit dem Kapitel. 01:29:36.590 --> 01:29:36.930 Vielen Dank!