WEBVTT 00:00.000 --> 00:01.300 So, schönen Tag. 00:01.520 --> 00:05.060 Ich begrüße Sie zur Fortsetzung der Vorlesung Effiziente Algorithmen. 00:05.740 --> 00:09.740 Zu Beginn wollte ich kurz eine Sache nochmal ansprechen. 00:09.900 --> 00:15.380 Ich habe bis heute die Auswertung der Vorlesungsbefragung nicht 00:15.380 --> 00:15.920 bekommen. 00:16.900 --> 00:18.940 Das heißt, irgendwas muss da schief gelaufen sein. 00:20.400 --> 00:24.740 Da müsste mal nachgehakt werden, was da passiert. 00:24.940 --> 00:25.740 Der Vogel macht das. 00:27.420 --> 00:27.980 Gut. 00:28.720 --> 00:34.060 Wir sind letztes Mal beschäftigt gewesen nach wie vor mit Suchen und 00:34.060 --> 00:34.740 Sortieren. 00:35.000 --> 00:36.940 Haben uns dort einiges angeschaut. 00:37.040 --> 00:40.240 Nicht mehr die einfachen Sortierverfahren, sondern wir hatten uns die 00:40.240 --> 00:42.280 ein bisschen fortgeschritteneren angeschaut. 00:42.400 --> 00:46.140 Wir waren ja bei dem Parallel Merge gewesen. 00:46.420 --> 00:51.500 Hatten uns angeguckt das mal davor. 00:51.500 --> 00:57.880 Die Mergesort haben uns letztes Mal nachdem wir noch mal das 00:57.880 --> 01:04.660 Vergleichernetz angeschaut hatten uns dann bei Tonicsort beschäftigt. 01:04.680 --> 01:09.040 Ich habe Ihnen gezeigt, die betonischen Folgen, die auf- und absteigen 01:09.040 --> 01:09.260 bzw. 01:09.960 --> 01:12.260 Verschiebungen auf- und absteigende Folgen sind. 01:13.020 --> 01:17.380 Wie man die sortieren kann und wie man das nutzen kann, um dann 01:17.380 --> 01:20.940 einfach Also erstmal, wie man dort den Beweis machen kann, dass das 01:20.940 --> 01:21.660 korrekt ist. 01:21.840 --> 01:24.980 Und dann hatten wir gesehen, wie man das einsetzen kann, um 01:24.980 --> 01:30.000 tatsächlich eine Merge, also ein Verschmelzen zu machen von 01:30.000 --> 01:34.300 vorsortierten Folgen, weil im Prinzip durch Spiegeln der einen Folge 01:34.300 --> 01:37.100 daraus eine betonische Folge wird. 01:37.160 --> 01:39.840 Und das ist halt einfach mit dem Vergleichernetz, was hier dargestellt 01:39.840 --> 01:41.460 ist, einfach zu realisieren. 01:42.080 --> 01:44.160 Und dadurch kamen wir dann auf das Botonic Merge Sort. 01:44.160 --> 01:47.200 Wir haben uns anschließend das zweidimensionale Sortieren angeschaut. 01:47.700 --> 01:58.280 Ich habe Ihnen gezeigt, wie man wie man wie man wie man hier diese 01:59.980 --> 02:01.820 Sortierordnungen definieren kann. 02:02.760 --> 02:10.180 Und ich habe dann weiterhin Ihnen das Verfahren LSU3 Sort vorgestellt, 02:10.380 --> 02:12.280 dass er in drei einfachen Schritten funktioniert. 02:12.500 --> 02:15.880 Im Wesentlichen so ein Vierfach-Merge von Schlangen wie in 02:15.880 --> 02:21.940 vorsortierten Quadranten, wobei man einfach zweimal OETS macht, einmal 02:21.940 --> 02:27.060 auf den Spalten, einmal auf der ganzen Schlange auf dem ganzen Feld 02:27.060 --> 02:32.200 und jeweils nur zweimal Zeilenlänge viele Schritte ausführt und dann 02:32.200 --> 02:34.680 schon fertig ist, was zunächst erstaunlich ist. 02:34.760 --> 02:40.960 Aber wenn man sich das überlegt mit den entsprechenden Überlegungen 02:40.960 --> 02:44.700 für 01 folgen, sieht man eben, dass das tatsächlich ausreicht, diese 02:44.700 --> 02:49.640 zwei Endschritte am Ende zu machen, weil man halt die Anteile der 02:49.640 --> 02:53.220 vorsortierten Quadranten gleichmäßig verteilt auf diese Doppelspalten 02:53.220 --> 02:56.540 und dadurch eine gleichartige Situation hat in all diesen 02:56.540 --> 03:01.620 Doppelspalten und dadurch zwei unsortierte Zeilen durchbleiben können. 03:01.740 --> 03:06.100 Wir hatten dann uns angeschaut, eine untere Schranke für das 03:06.100 --> 03:06.840 Sortieren. 03:07.020 --> 03:11.820 Dafür habe ich Ihnen vorgestellt, dieses Prinzip der Joker-Zone, dass 03:11.820 --> 03:15.360 man also einen Bereich hat, in dem man im Prinzip schlechte Fälle 03:15.360 --> 03:19.180 konstruieren kann, dafür sorgen kann, dass egal welcher Algorithmus da 03:19.180 --> 03:24.140 verwendet wird, der immer mindestens eine gewisse Zeit braucht. 03:24.240 --> 03:28.140 Diese gewisse Zeit war da gerade für ein quadratisches Feld mit 03:28.140 --> 03:32.680 Zeilenlänge n, gerade 3n Schritte. 03:33.300 --> 03:35.200 Das war das, was wir hier gesehen hatten. 03:35.620 --> 03:37.120 Da stand die untere Schranke. 03:37.620 --> 03:39.880 3n minus irgendwas Kleines. 03:40.580 --> 03:43.260 Und das Interessante ist, dass man eben genau diese Schranke auch 03:43.260 --> 03:44.000 erreichen kann. 03:44.540 --> 03:48.980 Das heißt, die ist wirklich scharf und das ist ja nicht so oft, dass 03:48.980 --> 03:52.400 wir scharfe Schranken angeben können für die Komplexität eines 03:52.400 --> 03:53.180 Problems. 03:53.580 --> 03:57.420 Ich hatte Ihnen dann noch das Mesh-of-Tree-Sortieren gezeigt, als so 03:57.420 --> 04:02.020 ein Beispiel für eine andere Struktur, bei der man im Wesentlichen die 04:02.020 --> 04:06.340 Probleme des concurrent read, concurrent write auf zweidimensionalen 04:06.340 --> 04:10.580 oder auf vielen parallel arbeitenden Prozessoren vermeidet und diese 04:10.580 --> 04:12.820 Baumstrukturen, die man flexibel einsetzen kann. 04:13.600 --> 04:18.860 Wir hatten danach uns noch kurz angeschaut, die untere Schranke für 04:18.860 --> 04:23.440 Sortieren, n log n und wir waren dann nochmal auf ein spezielles 04:23.440 --> 04:25.860 Sortierverfahren gegangen, hatten gesehen, dass man eben, wenn man 04:25.860 --> 04:29.780 mehr Informationen hat, über die zu sortierenden Elemente durchaus in 04:29.780 --> 04:32.900 linierer Zeit sortieren kann, auch im schlechtesten Fall, sogar ohne 04:32.900 --> 04:35.080 jeden Vergleich, nur durch Anschauende Elemente. 04:36.640 --> 04:39.860 Danach kamen wir zu den Selektionsverfahren, haben dort zunächst mal 04:39.860 --> 04:42.880 geguckt, worum es da eigentlich geht, dass man eben das k-größte 04:42.880 --> 04:49.700 Element oder im Extremfall den Median haben möchte und sind dann auf 04:49.700 --> 04:56.540 den naiven Ansatz für Selektion ist dann einfach, dass ich mir 04:56.540 --> 05:01.840 überlege, ich möchte gerne das k-größte Element haben, naja, dann kann 05:01.840 --> 05:05.480 ich natürlich sagen, ich nehme einfach zunächst mal das größte, ja, 05:05.640 --> 05:09.320 dann gucke ich in der Restfolge, die dann dann auch übrig bleibt, 05:09.700 --> 05:12.520 suche ich einfach wieder nach dem größten, das ist dann das 05:12.520 --> 05:15.960 zweitgrößte Element, das drittgrößte und so weiter und so weiter. 05:16.460 --> 05:20.560 Ich nehme also immer gerade hier jeweils aus der Restfolge, das ist 05:20.560 --> 05:25.220 auch immer das gleiche, hier steht S minus, ach so, 1 bis S bis k-1 05:25.220 --> 05:25.560 von S. 05:25.760 --> 05:28.860 Klar, ich habe also hier jeweils eine größere Menge rausgenommen, 05:29.020 --> 05:32.980 immer das maximale Element ziehe ich raus und dann habe ich natürlich 05:33.860 --> 05:35.960 dann das k-größte Element. 05:36.960 --> 05:40.840 Wenn ich ein Element haben will, also das 05:43.940 --> 05:49.420 kleiner ist als der Median, dann würde ich halt erst das kleinste, das 05:49.420 --> 05:52.380 zweitkleinste, drittkleinste und so weiter suchen, das wäre dann diese 05:52.380 --> 05:53.000 Reihenfolge. 05:53.860 --> 05:58.340 Der Aufwand ist natürlich hoch, wenn das k eine Konstante ist, ist das 05:58.340 --> 06:03.760 kein Problem, wenn das halt diese Konstante mal n, also k mal lineare 06:03.760 --> 06:10.740 Aufwand, aber wenn wir halt das Allgemeines anschauen, dann ist 06:10.740 --> 06:15.860 natürlich im schlechtesten Fall für, also k beliebig, dann haben wir 06:15.860 --> 06:19.200 im schlechtesten Fall den Median zu bestimmen und dann ist halt der 06:19.200 --> 06:24.340 Aufwand quadratisch, weil wir dann ein halbes Mal n brechen müssen und 06:24.340 --> 06:31.740 auch wenn wir ein Quartier haben wollen, ein Viertel oder irgend 06:31.740 --> 06:35.600 sowas, dann brauchen wir einfach entsprechend quadratische Zahl von 06:35.600 --> 06:36.520 Operationen. 06:36.700 --> 06:39.800 Und es ist völlig klar, dass das natürlich zu viel ist, denn mit 06:39.800 --> 06:42.580 einfach überlegen kann man natürlich sagen, ich sortiere einfach 06:42.580 --> 06:46.900 zunächst mal, das geht in ZnLn und dann habe ich ja alle 06:46.900 --> 06:48.640 Rangpositionen einfach zur Verfügung. 06:49.440 --> 06:55.920 Also n² braucht man eigentlich niemals, sondern ich sortiere in ZnLn 06:55.920 --> 06:56.860 und dann bin ich ja fertig. 06:57.240 --> 06:59.360 Also Selektion mit ZnLn. 07:00.260 --> 07:03.040 Aber eigentlich will ich ja nur das k größte haben. 07:03.160 --> 07:05.080 Ich will ja gar nicht alle Rangpositionen haben, das ist ja viel zu 07:05.080 --> 07:05.400 viel. 07:05.400 --> 07:07.720 Deswegen muss man sich überlegen, geht das nicht doch besser? 07:09.440 --> 07:13.260 Und dazu kann man sich einfach mal immer noch mal angucken, unseren 07:13.260 --> 07:15.340 QuickSort -Algorithmus. 07:15.780 --> 07:18.820 Den nennen wir jetzt um von QuickSort in QuickSelect. 07:19.580 --> 07:21.400 Mit dem völlig gleichen Prinzip. 07:23.120 --> 07:24.540 Und wir gucken uns an, was dann passiert. 07:24.720 --> 07:28.020 Also wir wollen modifiziertes QuickSort machen. 07:28.460 --> 07:29.980 Wir teilen unsere Folge hier auf. 07:30.720 --> 07:32.140 Wir haben also unsere Ausgangsfolge. 07:32.140 --> 07:34.060 Wir wählen wieder ein beliebiges Element. 07:36.540 --> 07:38.480 Zerteilen die Folge in zwei Teilfolgen. 07:38.900 --> 07:40.760 Dann haben wir hier wieder unsere zwei Teilfolgen. 07:40.880 --> 07:44.980 Diejenigen, die in dem Fall größer gleich diesem Element sind, das 07:44.980 --> 07:45.600 sind die vorne. 07:46.020 --> 07:47.360 Und dann hier die kleiner als C. 07:47.740 --> 07:50.140 Das ist unsere absteigende Aufteilung. 07:51.260 --> 07:56.920 Und wenn ich jetzt das so aufgeteilt habe und dieses S-Strich hier hat 07:56.920 --> 08:03.200 genau die Größe K, dann ist natürlich das Element C hier das K-größte. 08:04.180 --> 08:05.620 Weil es genau K-Elemente sind. 08:06.080 --> 08:09.300 Das ist das K-größte. 08:09.400 --> 08:10.220 Dann bin ich fertig. 08:11.940 --> 08:14.420 Das ist schon mal deutlich einfacher als QuickSort. 08:14.580 --> 08:16.960 Ich bin schon nach einem Schritt, nach einer Partition eventuell 08:16.960 --> 08:17.360 fertig. 08:19.080 --> 08:21.900 Dann kann es natürlich sein, dass ich dort mehr Elemente drin habe in 08:21.900 --> 08:22.460 dem S-Strich. 08:23.120 --> 08:26.280 Dann weiß ich aber, das K-größte Element liegt garantiert in der Menge 08:26.280 --> 08:26.840 S -Strich. 08:28.980 --> 08:32.780 Dann brauche ich nur in der Menge S-Strich nach dem K-größten zu 08:32.780 --> 08:33.040 suchen. 08:34.160 --> 08:39.780 Und wenn das kleiner als K ist, also weniger Elemente als K drin sind, 08:41.180 --> 08:44.820 dann weiß ich aber, dass dann das K-größte irgendwo in diesem Bereich 08:44.820 --> 08:45.480 hier liegen muss. 08:45.560 --> 08:46.140 In dem Bereich. 08:46.680 --> 08:47.660 In S2-Strich. 08:50.420 --> 08:56.720 Und ich berechne dann, wenn das, also noch mal hier, was ich natürlich 08:56.720 --> 09:00.640 mache ist, das war noch nicht ganz so einfach, wenn S-Strich größer K 09:00.640 --> 09:06.140 ist, sage ich jetzt hier, berechne S3-Strich gleich S-Strich minus C. 09:06.220 --> 09:07.300 Warum muss ich das überhaupt machen? 09:09.400 --> 09:13.880 Das könnte ja sein, dass ich nicht völlig verschiedene Elemente habe, 09:14.460 --> 09:16.460 sondern dass ich mehrere gleiche Elemente habe. 09:17.280 --> 09:19.240 Wir hatten immer angenommen, die sind alle verschieden. 09:19.240 --> 09:21.880 Wenn sie nicht alle verschieden sind, hatten wir gesagt, können wir 09:21.880 --> 09:25.240 annehmen, dass wir die einfach nach ihrer Position anordnen. 09:25.920 --> 09:29.180 Nehmen wir mal an, wir haben diese letzte Annahme nicht. 09:29.800 --> 09:31.060 Dann nehme ich einfach das C raus. 09:31.160 --> 09:35.400 Und wenn jetzt mehrfach hier ein C steht, dann ist natürlich dieses S3 09:35.400 --> 09:41.620 -Strich, das hat dann weniger Elemente, eventuell als K, wenn das C 09:41.620 --> 09:42.540 mehrfach auftaucht. 09:43.280 --> 09:48.360 Und dann wäre also dieses Element C das K-größte Element. 09:49.160 --> 09:51.920 Dann weiß ich auch, dass ich fertig bin. 09:53.700 --> 09:58.080 Wenn also das S3-Strich auch noch größer als K ist, wenn also von dem 09:58.080 --> 10:02.400 S -Strich das C abgezogen, mehr als K-Elemente sind, dann stelle ich 10:02.400 --> 10:03.760 KICKSELECT auf S3-Strich. 10:04.280 --> 10:09.160 Und wenn das weniger als K-Elemente sind, dann muss ich einfach auf S2 10:09.160 --> 10:11.740 -Strich das Verfahren anwenden. 10:11.820 --> 10:13.640 Aber jetzt suche ich nicht mehr nach dem K-größten. 10:14.260 --> 10:15.560 Sondern jetzt habe ich ja 10:18.580 --> 10:20.760 diese Elemente S-Strich alle rausgenommen. 10:21.020 --> 10:26.460 Und ich weiß, die sind alle größer als die Elemente in S2-Strich. 10:26.920 --> 10:30.220 Das heißt, ich muss jetzt nicht mehr nach dem K-größten suchen, 10:30.360 --> 10:33.540 sondern ich muss von dem K die Anzahl der Elemente in S-Strich 10:33.540 --> 10:34.000 abziehen. 10:35.280 --> 10:38.520 Dann nach dem entsprechenden Rang in S2-Strich suchen. 10:39.380 --> 10:44.260 Was ich aber auf jeden Fall sehe, ist, dass ich nicht mehr eine 10:45.880 --> 10:48.700 Rekursion habe, bei der ich in zwei Teilfolgen suchen muss, sondern 10:48.700 --> 10:50.240 ich muss nur noch in einer Teilfolge suchen. 10:51.480 --> 10:52.580 Das ist natürlich schon mal toll. 10:53.480 --> 10:57.640 Hilft uns aber für den schlechtesten Fall leider nicht. 10:57.780 --> 11:00.740 Also die Anzahl der Vergleiche ist klar. 11:00.920 --> 11:04.160 Das ist also die Anzahl der Vergleiche von KICKSELECT auf LISTENELÄNGE 11:04.160 --> 11:04.400 N. 11:05.780 --> 11:09.900 Und das ist dann das Maximum für alle K aus N. 11:10.960 --> 11:15.200 Für alle möglichen Positionen, die ich vergleiche, die ich auf 11:15.200 --> 11:17.200 irgendeiner solchen Teilfolge habe. 11:17.300 --> 11:21.520 Und das Problem ist natürlich, wenn ich Pech habe, dann ist das S 11:21.520 --> 11:24.080 -Strich immer gerade oder besteht immer nur aus einem Element. 11:24.780 --> 11:27.020 Oder aus N-1 Elementen. 11:27.560 --> 11:31.220 Und dann habe ich genau in dem schlechten Fall wieder KICKSELECT. 11:31.480 --> 11:34.960 Das heißt, ich bin im schlechtesten Fall immer noch quadratisch. 11:35.860 --> 11:41.860 Aber Sie können sich schon denken, im besten Fall, wenn ich also immer 11:41.860 --> 11:43.460 nur auf die Hälfte noch weiter... 11:43.460 --> 11:47.240 und der beste Fall wäre ja der, dass ich sofort fertig bin. 11:47.620 --> 11:50.480 Dann bin ich ja sowieso mit Zeit N fertig. 11:51.280 --> 11:55.920 Aber auch wenn ich mir das mittlere Verhalten anschaue, dadurch, dass 11:55.920 --> 12:01.320 ich nur in einer Folge nachschauen muss, läuft das mittlere Verhalten 12:01.320 --> 12:03.740 darauf hinaus, dass ich lineare Zeit bekomme. 12:04.560 --> 12:10.940 Das heißt, ich habe jetzt bei KICKSELECT nicht mehr NlogN, sondern ich 12:10.940 --> 12:13.580 habe lineare Zeit sogar für das mittlere Verhalten. 12:13.900 --> 12:16.400 Das heißt, KICKSELECT ist gar nicht so schlecht. 12:17.380 --> 12:18.720 Mit Mittel lineare Zeit. 12:19.580 --> 12:23.660 Die Frage ist, kann ich auch den schlechtesten Fall runterdrücken von 12:23.660 --> 12:25.720 NlogN, also von dem N² natürlich. 12:25.860 --> 12:29.760 Wir wissen, dass das mit einfachem Sortieren mit NlogN immer in der 12:29.760 --> 12:31.020 Zeit NlogN zu machen ist. 12:31.460 --> 12:37.640 Aber kann ich den schlechtesten Fall auch runterdrücken auf N? 12:39.120 --> 12:42.800 Dann müssen wir uns überlegen, woran liegt das eigentlich, dass wir im 12:42.800 --> 12:46.780 schlechtesten Fall dieses dumme Verhalten haben hier von N²? 12:47.600 --> 12:51.640 Der Grund ist doch, dass wir im schlechtesten Fall immer nur ein 12:51.640 --> 12:53.760 Element hier abzwacken können. 12:54.760 --> 13:00.260 Wenn wir erreichen könnten, dass die Anzahl der Elemente hier, wenn 13:00.260 --> 13:07.460 das irgendein N durch C wäre, irgendein konstanter Bruchteil, ich kann 13:07.460 --> 13:11.980 das garantieren, für jeden Rekursionsschritt, dass ich immer einen 13:11.980 --> 13:17.000 konstanten Bruchteil mindestens abziehe von der Folge, die ich noch 13:17.000 --> 13:17.860 betrachten muss. 13:19.740 --> 13:23.340 Dann habe ich den schlechtesten Fall ausgegeben. 13:24.720 --> 13:27.400 Das war ja auch bei Quicksort so, dass wir gesagt haben, wenn wir 13:27.400 --> 13:31.780 garantieren können, dass wir immer zwar nicht die Hälfte, aber 13:31.780 --> 13:34.600 irgendwie eine Aufteilung machen, sodass ich immer einen konstanten 13:34.600 --> 13:38.020 Bruchteil dort jeweils mit drin habe, dann kamen wir dort bei 13:38.020 --> 13:39.680 Quicksort auch auf NlogN. 13:41.020 --> 13:45.160 Wenn wir jetzt hier nur in einer Folge weiter runterlaufen müssen, und 13:45.160 --> 13:49.280 wir können dafür sorgen, dass wir immer nur in einem Bruchteil der 13:49.280 --> 13:52.760 ursprünglichen Folge weiter suchen müssen, dann kriegen wir auch das 13:52.760 --> 13:53.620 schlechteste Verhalten. 13:55.520 --> 13:58.160 Genau das wird in dem nächsten Verfahren gemacht. 13:58.980 --> 14:00.540 Selektion in innerer Zeit. 14:00.700 --> 14:03.440 Das ist die Idee, die ich Ihnen jetzt hier vorstelle. 14:04.540 --> 14:10.620 Wir wollen erreichen, dass wir nur auf die Rekursion auf die Folge, 14:10.640 --> 14:15.320 die sich bezieht, die ein Bruchteil der Länge ist, und der 14:15.320 --> 14:16.840 Ausgangsfolge. 14:17.500 --> 14:19.440 Dann auf lineare Zeit runterkommen. 14:20.620 --> 14:25.060 Zunächst mal gucken wir uns an, wie groß eigentlich die Folge ist. 14:25.200 --> 14:29.740 Wenn die nicht zu groß ist, wenn kleiner gleich 100, können wir 14:29.740 --> 14:30.620 irgendeine Zahl nehmen. 14:31.360 --> 14:34.420 Irgendeine vernünftige Zahl, dann machen wir das direkt. 14:34.920 --> 14:36.020 Mit irgendeinem Verfahren. 14:38.800 --> 14:39.720 Das sind nur Konstante. 14:41.300 --> 14:44.040 Wenn das größer ist, dann machen wir was anderes. 14:44.680 --> 14:51.460 Dann teilen wir unsere Folge auf in Teillisten, T1 bis Tn5 mit jeweils 14:51.460 --> 14:52.300 5 Elementen. 14:52.480 --> 14:53.260 Das sehen Sie hier. 14:55.500 --> 15:00.380 Das ist jeweils so eine Teilfolge mit 5 Elementen. 15:01.480 --> 15:02.900 Was bringt uns das? 15:03.720 --> 15:07.020 Jetzt bestimmen wir die mediale md der T. 15:08.380 --> 15:13.340 M1 bis Mn5 sind die Mediane dieser Teilfolgen. 15:14.160 --> 15:18.640 Und jetzt sei die Anordnung so, dass wir annehmen, wir haben oben die 15:18.640 --> 15:23.680 kleinen, unten die großen, und links die großen und rechts die 15:23.680 --> 15:23.940 kleinen. 15:24.020 --> 15:28.200 Wir nehmen einfach mal eine gewisse Visualisierung an, weil das ist 15:28.200 --> 15:30.060 für die Argumentation gleich einfacher. 15:31.440 --> 15:35.280 Das kann ich obda so annehmen, dass das so ist für die Argumentation, 15:35.440 --> 15:36.560 die ich gleich brauche. 15:38.020 --> 15:43.580 Ich habe also meine Teilfolgen und ich nehme mal an, wir sind so 15:43.580 --> 15:51.280 gruppiert, zunächst mal innerhalb, das ist keine Voraussetzung für das 15:51.280 --> 15:54.400 Verfahren, dass das so angeordnet ist, nur für die Darstellung ist das 15:54.400 --> 15:54.660 so. 15:55.940 --> 15:58.520 Ich habe also jetzt jeweils die Mediane, die habe ich hier so in der 15:58.520 --> 16:02.660 Mitte dargestellt, der N5-Teilfolgen. 16:03.820 --> 16:11.800 Jetzt habe ich also N5-Elemente und jetzt bestimme ich den Median 16:12.740 --> 16:18.470 dieser Menge, dieser Menge von Medianen. 16:20.550 --> 16:26.530 Das ist ein Aufruf dieser Select-Operation auf eine Teilfolge der 16:26.530 --> 16:27.270 Größe N5. 16:28.050 --> 16:30.530 Nur ein Bruchteil der ursprünglichen Folge. 16:31.030 --> 16:32.350 Das ist kein Problem. 16:33.510 --> 16:36.810 Dieser Median, das sind hier die großen, das heißt, wenn wir davon 16:36.810 --> 16:40.330 ausgehen, dass das eine gerade Zahl, also dass das alles schön teilbar 16:40.330 --> 16:45.230 ist, wenn das eine gerade Zahl ist, N5, dann wäre das dieses Element, 16:46.510 --> 16:49.870 wäre der Median der Mediane, wenn wir annehmen, dass es so hier mal 16:49.870 --> 16:50.670 visualisiert. 16:52.910 --> 16:56.630 Jetzt mache ich eigentlich nur Quick-Select. 16:57.450 --> 17:00.150 Aber Quick-Select bezogen auf dieses M. 17:03.160 --> 17:07.960 So, Quick-Select bezogen auf dieses M heißt, ich teile meine Folge so 17:07.960 --> 17:12.380 auf in S-Strich und S2-Strich und irgendwo liegt dieses M. 17:13.660 --> 17:16.420 Hier ist mein S-Strich, da ist mein S2-Strich. 17:19.940 --> 17:20.340 So. 17:21.680 --> 17:23.280 Das ist S-Strich und S2-Strich. 17:24.620 --> 17:27.740 Wenn das S-Strich gleich K ist, so ist M gleich K von S, das ist genau 17:27.740 --> 17:28.960 das gleiche wie bei Quick-Select. 17:30.000 --> 17:33.000 Wenn die Anzahl immer eine Größe als K ist, mache ich einfach direkt 17:33.000 --> 17:37.820 darauf das S-Strich, K und andernfalls mache ich S2-Strich, K von S. 17:37.980 --> 17:39.080 Das ist einfach Quick-Select. 17:39.520 --> 17:43.400 Wobei ich hier den Punkt rausgelassen habe, dass sich noch alle, die 17:43.400 --> 17:46.080 gleich M sind, auch noch rausschmeißen. 17:47.240 --> 17:48.360 Könnte ich auch noch machen. 17:48.920 --> 17:49.920 Habe ich aber hier gar nicht gemacht. 17:50.500 --> 17:54.060 Also dieser Teil hier ist einfach nur Quick-Select. 17:54.660 --> 17:57.840 Und das hier oben ist einfach, wie bestimme ich dieses Pivot-Element. 17:59.060 --> 18:00.920 Das ist die Bestimmung von dem M. 18:02.180 --> 18:06.800 Und jetzt habe ich hier so zwei Teilmengen, Teilbereiche A und B. 18:08.300 --> 18:19.080 Wenn ich mir angucke, alle Elemente, die kleiner gleich dem M sind. 18:20.240 --> 18:22.140 Ich sage hier kleiner als M. 18:22.500 --> 18:23.620 S ist kleiner als M. 18:24.260 --> 18:25.040 In S2-Strich. 18:26.180 --> 18:31.260 Die Elemente, die kleiner sind, die liegen in diesem Bereich, die 18:31.260 --> 18:32.540 kleineren als M. 18:32.540 --> 18:33.800 Diese hier, 18:37.660 --> 18:41.880 die Elemente, die hier liegen, hier unten drin, die sind alle größer. 18:41.940 --> 18:45.860 M1 bis Mn10, die sind alle größer als dieses M. 18:46.960 --> 18:52.280 Und die Elemente, die hier unten liegen, in dem A, die sind alle 18:52.280 --> 18:53.980 größer als das M. 18:54.740 --> 18:55.940 Oder größer gleich diesem M. 18:57.020 --> 19:06.080 Das heißt, in dem S2-Strich, das hier S2-Strich, dieses gestrichelte 19:06.080 --> 19:09.900 oder straffierte, liegt das A garantiert nicht drin. 19:11.980 --> 19:17.660 Dieses A hier unten, was ich hier einfach nur so dargestellt habe, die 19:17.660 --> 19:24.160 Elemente, die größer sind als dieser Median der Mediane, das sind doch 19:24.160 --> 19:26.700 aber mindestens, wie viele Elemente? 19:27.320 --> 19:30.420 Ich habe M1 bis Mn5 solche Mediane. 19:31.300 --> 19:36.160 Das heißt, ich habe hier M1 bis also ich habe hier ein Zehntel oder N 19:36.160 --> 19:39.160 -Zehntel -Teilfolgen. 19:39.560 --> 19:45.320 Und in jeder Teilfolge habe ich mindestens drei Elemente, die größer 19:45.320 --> 19:49.600 sind als dieser oder größer gleich diesem Median. 19:50.480 --> 19:55.660 Das heißt, ich habe drei Zehntel-N-Elemente, die größer sind oder 19:55.660 --> 19:59.760 größer gleich dem Median sind, die nicht hier drin sind in der Menge 19:59.760 --> 20:01.140 S2 -Strich. 20:02.980 --> 20:09.420 Das heißt also sofort, das Betrag von S2-Strich kleiner gleich 7 20:09.420 --> 20:10.300 Zehntel -N. 20:13.260 --> 20:15.240 Da haben wir genau das, was wir haben wollen. 20:16.200 --> 20:20.180 Wenn wir den Median so wählen, wie wir das hier gemacht haben, 20:20.180 --> 20:23.360 Quatsch, wenn wir das Pivot-Element von QuickSelect so wählen, wie das 20:23.360 --> 20:29.880 hier passiert, dann haben wir garantiert, dass wir nur in Folgen 20:29.880 --> 20:36.480 weitersuchen, die eine kleinere Größe haben. 20:37.340 --> 20:41.600 Also nur einen Bruchteil der Größe haben, der ursprünglichen Folgen. 20:42.580 --> 20:44.700 Natürlich müssen wir noch hier nachschauen. 20:45.700 --> 20:51.580 Bestimme den Median der Mediale. 20:52.440 --> 20:54.500 Ich habe N fünftel Mediale. 20:56.220 --> 20:58.500 Da muss ich ja wieder so ein Select machen. 21:00.220 --> 21:03.120 Das sind 1 fünftel N. 21:04.140 --> 21:12.860 Wenn Sie 1 fünftel zu 7 Zehntel dazurechnen, sind Sie bei 9 Zehntel. 21:15.260 --> 21:21.400 Insgesamt führen Sie QuickSelect auf Folgen aus, die insgesamt eine 21:21.400 --> 21:24.400 kleinere Länge haben, als die Ausgangsfolgen. 21:26.200 --> 21:32.400 Sie haben einmal höchstens 7 Zehntel, das andere Mal höchstens 2 21:32.400 --> 21:32.900 Zehntel. 21:33.000 --> 21:38.580 Also insgesamt haben Sie nur auf Folgen mit insgesamt Länge 9 Zehntel 21:38.580 --> 21:39.120 etwas gemacht. 21:39.240 --> 21:44.560 Das riecht danach, dass die asymptotische Zeit besser ist. 21:44.860 --> 21:47.060 Das wird auf der nächsten Folie dargestellt. 21:50.120 --> 21:53.440 Die wesentliche Idee ist, wir vermeiden die schlechten Fälle von 21:53.440 --> 21:56.800 QuickSelect durch garantierte Reduktion der zu bearbeitenden Restliste 21:56.800 --> 21:58.620 um einen festen Bruchteil von N. 21:58.860 --> 22:02.780 Das ist einfach nur geschicktes Wählen dieses Pivot-Element von 22:02.780 --> 22:06.680 QuickSelect und dann entsprechend QuickSelect anbinden. 22:07.720 --> 22:09.220 Das ist hier nochmal eine Analyse. 22:09.300 --> 22:16.020 In dem S2-Strich ist garantiert das A nicht drin. 22:17.180 --> 22:20.520 Symmetrisch dazu ist in dem S-Strich garantiert das B nicht drin. 22:21.380 --> 22:24.740 Die Größe von A und B ist jeweils 3 Zehntel N. 22:26.460 --> 22:28.880 Weil wir jeweils 3 Elemente dort haben. 22:31.660 --> 22:36.780 Und dadurch haben wir sofort die Aussage, dass S-Strich und S2-Strich 22:36.780 --> 22:39.180 maximal 7 Zehntel N Elemente haben. 22:39.800 --> 22:42.540 Wenn das ein ganzes Vielfaches von 10 ist. 22:43.920 --> 22:47.600 Wenn es das nicht ist, dann müssen wir ein bisschen anders abschätzen. 22:47.940 --> 22:53.780 Dann haben wir aber immer noch hier 3 Elftel N und 3 als Mindestgröße 22:53.780 --> 22:54.800 von dem A und dem B. 22:55.320 --> 23:02.420 Und dann sind wir bei S-Strich und S2-Strich bei 8 Elftel N. 23:02.860 --> 23:04.180 Das reicht immer noch aus. 23:04.780 --> 23:08.860 Die Gesamtfolge, die wir dann kriegen, ist immer noch kleiner als N. 23:10.380 --> 23:13.480 Das heißt, in jedem Reduktionsschritt wird die Liste um einen festen 23:13.480 --> 23:14.720 Bruchteil ihrer Länge kürzer. 23:15.180 --> 23:18.580 Wir müssen eben nur aufpassen, dass dieser Aufwand für das Bestimmen 23:18.580 --> 23:22.060 dieses Medians der Mediane unseren S-Strich durch die Rechnung macht. 23:23.740 --> 23:27.060 Also wesentlich die Rekursion sehr vereinfacht. 23:27.620 --> 23:28.800 Sieht so aus wie hier. 23:29.500 --> 23:32.580 Wir arbeiten ja auf einer Folge bei dem T-Select. 23:33.220 --> 23:36.780 Insgesamt ist das etwas, was kleiner ist als N. 23:37.220 --> 23:38.980 Und danach haben wir noch linearen Aufwand. 23:39.740 --> 23:41.860 Das ist aber kein Problem. 23:42.040 --> 23:46.180 Wenn wir solch eine Abschätzung haben, wissen wir nach unseren 23:46.180 --> 23:47.340 Rekursionsgleichungen. 23:47.340 --> 23:52.640 Dann haben wir sofort T-Select im linearen Bereich. 23:54.340 --> 23:56.080 Hier ist das A kleiner als 1. 23:56.240 --> 24:00.060 Das heißt, durch unsere Abschätzung, die wir gemacht haben mit dem 24:00.060 --> 24:03.920 allgemeinen Überlegung der Rekursionsgleichung, sieht man dann sofort, 24:04.060 --> 24:04.920 dass das linear ist. 24:05.940 --> 24:07.580 Das ist nicht hundertprozentig richtig. 24:07.780 --> 24:13.280 Ganz genau ist es so, dass wir hier für die einzelnen Schritte, für 24:13.280 --> 24:18.960 den Schritt 1 irgendeinen Aufwand kriegen für das Suchen in einer 24:18.960 --> 24:21.460 Folge Länge 100 oder maximal 100. 24:22.020 --> 24:25.580 Für Schritt 2 also das ist ein konstanter Aufwand. 24:25.680 --> 24:28.840 Für Schritt 2, das Aufteilen in Listende Teile der Länge 5. 24:29.180 --> 24:30.180 Das ist kein Aufwand. 24:31.460 --> 24:34.940 Wir wollen ja dann nur auf jeweils diesen Teilabschnitten ein Median 24:34.940 --> 24:35.400 bestimmen. 24:36.040 --> 24:40.460 Das ist so, dass Sie ein Median auf einer Folge Länge 5, können Sie 24:40.460 --> 24:43.280 ein Median mit maximal 9 Vergleichen hinbekommen. 24:43.420 --> 24:44.620 Können Sie überlegen, wie man das macht. 24:46.580 --> 24:53.180 Und da wir das für N5 solcher Teilfolgen machen müssen, haben wir N5 24:53.180 --> 24:56.420 mal 9, das sind weniger als 2 N-Vergleiche. 24:57.520 --> 24:58.900 Dann kommt der Schritt 4. 24:59.040 --> 25:03.900 Das war das rekursive Suchen des Medians der Mediane. 25:05.680 --> 25:10.520 Und das steckt an dieser Stelle drin. 25:11.060 --> 25:16.560 Das ist dieses 4V-Select von N5. 25:20.100 --> 25:23.920 Das ist diese 21N hat was damit zu tun, dass ich hier wenn das nicht 25:23.920 --> 25:26.280 richtig teilbar ist, das abschätzen muss. 25:27.280 --> 25:30.480 Und Schritt 5 ist der Schritt für die Partitionierung. 25:30.640 --> 25:31.680 Das ist wieder Quick-Select. 25:32.200 --> 25:34.720 Da wissen wir, dass Partitionierung Nplus1 Vergleiche braucht. 25:34.720 --> 25:37.080 Dann mache ich den rekursiven Aufruf. 25:37.180 --> 25:40.340 Das ist ein Aufruf auf einer Folge, die maximal die Länge 8N-Hälfte 25:40.340 --> 25:40.660 hat. 25:41.180 --> 25:42.800 Das ist der Aufruf. 25:42.920 --> 25:45.740 Und damit habe ich insgesamt hier meine Rekursionsgleichen für die 25:45.740 --> 25:46.780 Anzahl der Vergleiche. 25:47.380 --> 25:51.720 Und wenn Sie sich das hier anschauen, das können Sie genau sich 25:51.720 --> 25:52.220 angucken. 25:52.820 --> 25:58.000 Diese Rekursion können Sie auflösen, sodass Sie insgesamt ein lineares 25:58.000 --> 25:58.680 Verhalten kriegen. 25:59.080 --> 26:06.280 Allerdings ist die Konstante, die Sie da vorkriegen, nicht allzu toll. 26:06.900 --> 26:10.200 Also im schlechtesten Fall haben Sie hier eine relativ große 26:10.200 --> 26:10.760 Konstante. 26:12.000 --> 26:14.160 Wenn Sie Glück haben, sind Sie wesentlich besser. 26:15.060 --> 26:16.280 Und dann ist die Konstante klein. 26:16.360 --> 26:18.540 Das ist eben nur die Abschätzung für den schlechtesten Fall. 26:21.200 --> 26:25.180 Aber im Prinzip ist das hier ein sehr schönes Verfahren, weil Sie ja 26:25.180 --> 26:30.220 nur den Aufwand reinstecken müssen, um zunächst mal den Median der 26:30.220 --> 26:32.680 Mediane von folgender Länge 5 zu bekommen. 26:33.600 --> 26:35.180 Und das geht eigentlich recht schnell. 26:36.020 --> 26:40.160 Da müssen Sie nur noch mal anschließend Ihre Rekursion nach unten 26:40.160 --> 26:41.460 machen, das QuickSelect anwenden. 26:42.180 --> 26:47.860 Also der erwartete Aufwand ist sowieso linear und ist hierdurch also 26:47.860 --> 26:52.160 noch wieder besser als das, was wir bei dem einfachen QuickSelect 26:52.160 --> 26:52.480 haben. 26:53.320 --> 26:57.060 Also nochmal, das Wesentliche ist hier eine Verbesserung von 26:57.060 --> 27:00.600 QuickSelect, dadurch, dass wir das Pivot-Element zur Aufteilung 27:00.600 --> 27:04.780 geeignet wählen und dafür sorgen können, dass das immer zu einer 27:04.780 --> 27:06.220 vernünftigen Aufteilung führt. 27:06.700 --> 27:09.380 Und dadurch haben wir auch im schlechtesten Fall lineare Zahlen. 27:10.780 --> 27:13.580 Die Konstante im schlechtesten Fall ist relativ groß. 27:14.360 --> 27:15.520 Also wirklich recht groß. 27:15.740 --> 27:19.280 Man bringt das für praktische Anwendungen normalerweise relativ wenig. 27:19.900 --> 27:22.720 Da macht man bei praktischen Anwendungen häufig einfach QuickSelect. 27:22.720 --> 27:25.600 Wäre eine nette Aufgabe, zu vergleichen für irgendwelche 27:25.600 --> 27:28.740 Beispielfolgen, wie groß ist der Aufwand, wenn Sie einfach QuickSelect 27:28.740 --> 27:34.280 anwenden oder wenn Sie dieses Verfahren anwenden, für irgendwelche 27:34.280 --> 27:35.900 Folgen, die man Ihnen vorgibt. 27:39.100 --> 27:43.480 Das gibt Ihnen dann einen Erfahrungswert, wie weit sich das eine lohnt 27:43.480 --> 27:44.040 oder das andere. 27:45.280 --> 27:48.480 Das Interessante ist aber, ich kann dieses Verfahren für die 27:48.480 --> 27:53.700 Medienbestimmung sehr schön parallelisieren. 27:53.900 --> 27:54.760 Habe ich das nicht nochmal drauf? 27:54.780 --> 27:55.260 Habe ich nicht. 27:56.300 --> 28:01.660 Also, jetzt wollte ich hier nochmal kurz zurück, dieses Bild nochmal 28:01.660 --> 28:02.340 anschauen. 28:04.580 --> 28:08.580 Ich muss hier parallel, ich kann hier diesen Schritt, Bestimmung der 28:08.580 --> 28:14.000 Mediane der Teilfolgen, das kann ich ja alles parallel machen. 28:15.160 --> 28:19.540 Und ich kann es auch so machen, dass ich sage, wenn ich meinetwegen k 28:19.540 --> 28:28.600 Prozessoren habe oder p Prozessoren, dann teile ich einfach auf in p 28:28.600 --> 28:31.360 Teilfolgen der Länge n durch p. 28:33.980 --> 28:40.420 Und mache jetzt in jedem Prozessor zunächst mal eine Mediansuche. 28:41.320 --> 28:42.680 Parallel für alle. 28:42.680 --> 28:49.460 Und dann muss ich nur noch auf diesen p Medianen diesen Rest 28:49.460 --> 28:49.880 ausführen. 28:49.940 --> 28:53.620 Wenn das p konstant ist, kann ich hier sofort, also wenn das relativ 28:53.620 --> 28:55.700 klein ist, kann ich das mit direktem Verfahren machen. 28:56.180 --> 28:59.440 Das heißt, für Parallelisierung ist das ein idealer Ansatz. 29:00.200 --> 29:03.720 Dieses zweistufige Verfahren, Median der Median, erst die Mediane 29:03.720 --> 29:12.080 bestimmen, dann entsprechend habe ich diese Teilfolge noch einmal 29:12.080 --> 29:14.360 ausführen auf den Rest. 29:15.000 --> 29:16.280 Das geht dann wirklich sehr schnell. 29:18.260 --> 29:24.140 Also das ist ein sehr schönes Verfahren für parallele Ausführung. 29:25.140 --> 29:30.600 Und da kriegt man daraus ein schönes paralleles Verfahren für das 29:30.600 --> 29:35.180 Suchen des Kartgrößen oder auch für die Bestimmung des Medians. 29:36.660 --> 29:38.620 Gut, damit ist das erstmal abgeschlossen. 29:39.100 --> 29:40.260 Suchen und Selektieren. 29:40.400 --> 29:41.520 Und jetzt kommen wir zu Suchverfahren. 29:41.940 --> 29:44.860 Suchverfahren sind auch Standardansatz. 29:45.280 --> 29:48.720 Jetzt geht es nicht um Suche im Internet, Suchmaschinen, sondern es 29:48.720 --> 29:49.640 geht um anderes Suchen. 29:50.060 --> 29:52.900 Ich habe irgendeine Folge von Elementen. 29:53.160 --> 29:56.720 Ich nehme an, dass sie alle verschieden sind. 29:57.260 --> 29:58.920 Kann sein, dass sie nicht verschieden sind. 29:59.060 --> 30:01.660 Dann unterscheide ich sie nach Position oder so. 30:03.480 --> 30:06.440 Und jetzt möchte ich gerne folgende Operation ausführen. 30:06.580 --> 30:11.340 Ich möchte wissen, ist ein Element A in meiner Menge S drin? 30:12.120 --> 30:13.420 Kann sein, dass ich das suchen möchte. 30:15.220 --> 30:18.140 Kann sein, dass ich was einfügen will oder löschen will. 30:18.260 --> 30:20.660 Das waren alles hier unsere Lexikon-Operationen. 30:22.260 --> 30:22.960 Also das sind hier 30:27.000 --> 30:27.960 Lexikon -Operationen. 30:30.100 --> 30:32.280 Und die möchte ich natürlich möglichst alles schnell machen können. 30:32.400 --> 30:36.180 Ich brauche also eine geeignete Datenstruktur und geeignete Verfahren, 30:36.360 --> 30:37.120 um das schnell zu machen. 30:40.480 --> 30:42.840 Und jetzt gucken wir uns an, wie man das machen kann. 30:42.980 --> 30:45.460 Hier steht nochmal, Standard Lexikon-Operationen hatte ich Ihnen schon 30:45.460 --> 30:45.840 erzählt. 30:46.780 --> 30:49.960 Manchmal guckt man sich auch die Operationen an Xmin und Near. 30:50.580 --> 30:53.620 Das heißt, ich möchte immer das kleinste Element oder immer das größte 30:53.620 --> 30:56.360 Element raussuchen und entfernen aus der Menge. 30:56.860 --> 31:00.300 Das ist so für Priority Heaps oder Prioritätswarteschlangen. 31:00.680 --> 31:02.460 Das ist die Operation, die ich brauche. 31:03.060 --> 31:05.240 Und wenn ich sage, ich möchte ein Element, das in der Nähe eines 31:05.240 --> 31:08.000 bestimmten Elements A ist, muss ich erstmal wissen, kann ich den 31:08.000 --> 31:10.460 Abstand von Elementen überhaupt bestimmen? 31:11.340 --> 31:13.460 So eine Operation brauche ich bei den anderen nicht. 31:13.900 --> 31:15.340 Da vergleiche ich direkt mit Elementen. 31:15.440 --> 31:19.280 Wenn ich Near machen will, dann muss ich einen Abstand zwischen 31:19.280 --> 31:21.120 verschiedenen Elementen berechnen. 31:22.560 --> 31:26.140 Wir nehmen jetzt an, dass wir nicht Near machen wollen, sondern nur 31:26.140 --> 31:27.840 die direkte Suche. 31:28.360 --> 31:31.120 Und jetzt kann man sich überlegen, wie geht das am einfachsten? 31:31.240 --> 31:32.120 Lineare Suche. 31:32.580 --> 31:36.800 Ich habe hier meine Folge S und da sind meine ganzen Elemente drin. 31:37.000 --> 31:40.240 Und ich gehe jetzt der Reihe nach hier einfach durch, bis ich das 31:40.240 --> 31:41.480 Element A gefunden habe. 31:42.380 --> 31:44.220 Das ist klar, dass das lange dauert. 31:44.380 --> 31:46.200 Das ist halt lineare Zeit. 31:46.800 --> 31:48.680 Dann kann ich binäre Suche machen. 31:49.040 --> 31:51.060 Also, wie mache ich binäre Suche? 31:51.500 --> 31:54.780 Wenn ich hier meine Folge habe, dann gucke ich mir das mittlere 31:54.780 --> 31:55.540 Element an. 31:56.280 --> 32:00.580 Und wenn das hier irgendein Element X ist, gucke ich nach, ob das A 32:00.580 --> 32:02.760 kleiner als X ist. 32:03.120 --> 32:06.120 Wenn das A kleiner als X ist, dann muss ich halt hier entsprechend da 32:06.120 --> 32:07.340 reingehen. 32:07.440 --> 32:10.280 Wir machen, dass es aufsteigend sortiert ist, das Ganze. 32:10.940 --> 32:14.700 Wenn das größer als X ist, dann muss ich halt hier weiter schauen. 32:15.140 --> 32:21.080 Dann habe ich halt so eine Struktur, bei der ich logarithmisch viele 32:21.080 --> 32:22.580 Aufrufe machen muss. 32:22.760 --> 32:28.280 Sie wissen, binäre Suche braucht auf folgende Länge N, die sortiert 32:28.280 --> 32:28.520 sind. 32:28.660 --> 32:29.820 Gerade logarithmische Zeit. 32:30.360 --> 32:31.900 Das ist alles einfach. 32:32.120 --> 32:33.080 Entopulierende Suche. 32:33.420 --> 32:36.380 Ist auch einfach, wenn ich etwas mehr weiß über die Elemente. 32:36.980 --> 32:42.380 Dann gehe ich in die Nähe des zu suchenden Elementes und weiß halt ein 32:42.380 --> 32:46.840 großes Element, das liegt eher im rechten Bereich, ein kleines Element 32:46.840 --> 32:47.960 eher im linken Bereich. 32:48.360 --> 32:51.380 Und dann kann ich also interpolierend suchen. 32:51.500 --> 32:54.000 Da mache ich nicht nur die einfache binäre Aufteilung, sondern mache 32:54.000 --> 32:56.380 eben eine größenorientierte Aufteilung. 32:58.080 --> 32:59.240 Das ist aber nicht alles. 33:00.340 --> 33:03.000 Das Problem ist nämlich, wenn wir hier zum Beispiel binäre Suche 33:03.000 --> 33:07.300 machen, dann brauche ich eine aufsteigend sortierte Folge. 33:09.580 --> 33:11.240 Nur fürs Suchen ist das fein. 33:11.620 --> 33:12.640 Immer logarithmische Zeit. 33:13.840 --> 33:17.220 Wenn ich aber jetzt auch noch Elemente einfügen und löschen oder sowas 33:17.220 --> 33:22.120 will, wenn ich also nicht nur suchen möchte, dann muss ich ja meine 33:22.120 --> 33:23.480 Folge ständig neu sortieren. 33:23.760 --> 33:27.300 Ich will Element einfügen, das heißt, wenn ich da jetzt irgendwo ein 33:27.300 --> 33:30.620 Element einfüge, muss ich den ganzen Teil hier nach rechts schieben. 33:31.800 --> 33:32.600 Das ist Aufwand. 33:32.660 --> 33:34.380 Das geht nur in linearer Zeit. 33:34.380 --> 33:37.640 Ich habe also sofort fürs Einfügen lineare Zeit, wenn ich binäre Suche 33:37.640 --> 33:40.480 nehme auf einer einfach sortierten Folge. 33:41.160 --> 33:42.080 Das ist schlecht. 33:43.060 --> 33:45.060 Also muss ich was anderes machen. 33:45.480 --> 33:49.520 Dann gehe ich zum Beispiel auf sogenannte AVL-Bäume. 33:50.480 --> 33:53.080 Hat jemand von Ihnen den Begriff AVL-Bäume schon mal gehört? 33:54.120 --> 33:54.880 Noch nicht. 33:55.600 --> 33:58.560 Eigentlich ist das Standardthema von... 33:59.380 --> 34:02.600 müsste ein Standardthema sein von Grundlagen in Format 1. 34:02.600 --> 34:03.320 Das ist es aber nicht. 34:05.340 --> 34:08.020 Jetzt gucken wir uns ganz kurz das einmal an. 34:08.780 --> 34:10.060 Was ist ein AVL-Baum? 34:11.200 --> 34:12.840 Hier sehen wir ein AVL-Baum. 34:14.300 --> 34:17.520 Das Wesentliche beim AVL-Baum steht für Erdels, Dersky und Landes. 34:17.720 --> 34:19.260 Das sind drei Russen, die... 34:21.240 --> 34:24.960 das hört sich gerade nicht so an, wie russische Namen oder 34:24.960 --> 34:25.720 südrussische Namen. 34:26.120 --> 34:29.600 Die haben also diese Bäume entworfen. 34:30.310 --> 34:38.040 Und das Wesentliche ist, dass das in diesem Fall höhenbalancierte 34:38.040 --> 34:38.940 Bäume sind. 34:39.000 --> 34:40.320 Was heißt höhenbalanciert? 34:40.880 --> 34:44.380 Das heißt, wenn ich mir irgendeinen Knoten anschaue, zum Beispiel hier 34:44.380 --> 34:48.020 die Wurzel des Baumes, oder auch irgendeinen anderen, dann 34:48.020 --> 34:55.760 unterscheiden sich die Höhen der linken und rechten Teilbäume maximal 34:55.760 --> 34:56.340 um 1. 34:56.920 --> 34:58.180 Egal, wo Sie hier hinschauen. 34:59.760 --> 35:03.220 Die Höhenunterschiede, also wenn Sie hier hinschauen, 59, auf der 35:03.220 --> 35:11.020 einen Seite haben Sie die Höhe 1, 2, 3, und hier haben Sie die Höhe 1, 35:11.120 --> 35:11.640 2, 3. 35:11.740 --> 35:12.260 Gleiche Höhe. 35:12.360 --> 35:15.140 Wenn Sie sich den anschauen, da haben Sie 2 und hier haben Sie 1. 35:16.680 --> 35:17.620 Ein höhenbalancierter Baum. 35:18.920 --> 35:20.260 Höhenbalanciert, warum will man das haben? 35:20.980 --> 35:24.040 Sie wissen, wenn ich einen vollständigen Baum habe, mit N-Elementen, 35:24.340 --> 35:27.480 mit N-Knoten, dann ist die maximale Pfadlänge log N. 35:30.180 --> 35:31.360 Log N-1. 35:31.940 --> 35:33.180 Jeden Knoten-Elemente. 35:34.280 --> 35:37.880 Und das heißt, die längsten Suchpfade haben die Länge log N. 35:38.420 --> 35:43.380 Wenn ich was einfügen möchte, brauche ich Zeit log N, um an den Platz 35:43.380 --> 35:46.500 zu kommen, muss dann noch ein bisschen umbauen, wenn ich das geeignet 35:46.500 --> 35:50.060 hinkriegen kann, Zeit log N, habe ich auch Einfügen log N. 35:50.440 --> 35:52.760 Das sind also solche, diese AVL-Bäume erlauben das. 35:53.140 --> 35:54.480 Lassen Sie mal sehen, was hier passiert. 35:54.760 --> 35:59.640 Man kann also hier raufklicken, und da wird einfach irgendein Element 35:59.640 --> 36:00.260 eingefügt. 36:02.580 --> 36:04.280 Wie wird das jetzt eingefügt? 36:04.980 --> 36:06.300 Das Hopf hüpft hier so schön rum. 36:06.520 --> 36:07.820 Das war eine sehr schöne Operation. 36:08.960 --> 36:09.760 Was haben Sie gesehen? 36:10.440 --> 36:12.760 Machen wir das nochmal hier zurück. 36:16.720 --> 36:18.080 Das war also unsere... 36:18.080 --> 36:19.840 Jetzt fügen wir das gleiche... 36:19.840 --> 36:21.240 Wir können ja mal ein anderes Element einfügen. 36:21.380 --> 36:24.340 Wir wollen jetzt meinetwegen das Element... 36:24.800 --> 36:26.840 Fügen wir mal 17 ein. 36:29.360 --> 36:30.680 11 ist auch gut. 36:31.840 --> 36:32.820 Ich sage Insert. 36:33.320 --> 36:35.940 Dann sehen Sie, das läuft runter, immer nach links, weil ich immer 36:35.940 --> 36:36.760 dorthin laufe. 36:36.760 --> 36:39.500 Nach links sind immer die kleineren Elemente. 36:40.400 --> 36:42.160 Und Sie sehen, das müsste umgebaut werden. 36:42.280 --> 36:42.480 Warum? 36:43.160 --> 36:50.100 Weil vorher, da war eben die 22 oben, und wenn ich die 11, da muss ich 36:50.100 --> 36:53.860 nach links laufen, und dann von der 4 aus hätte ich nach rechts laufen 36:53.860 --> 36:57.160 müssen, dann hätte ich auf einmal hier diese Höhenbalancierung 36:57.160 --> 36:57.960 verletzt gehabt. 36:59.260 --> 37:02.860 Und diese Höhenbalancierung, in jedem Knoten kann ich ja die Höhe mir 37:02.860 --> 37:03.260 merken. 37:03.820 --> 37:06.100 Ich stelle fest, die Höhenbalancierung passt nicht mehr. 37:06.160 --> 37:07.260 Ich muss jetzt umbauen. 37:07.600 --> 37:11.360 Und dann wird halt entsprechend ein Element nach oben gezogen. 37:11.460 --> 37:13.060 Und es wird so umgebaut. 37:13.220 --> 37:16.540 So können wir also hier beliebig uns Elemente einbauen lassen. 37:16.680 --> 37:18.480 Da wird jetzt ein großes Element, da wird also immer zufällig eins 37:18.480 --> 37:18.880 gezogen. 37:18.960 --> 37:20.260 Sie können auch eins explizit wählen. 37:20.700 --> 37:23.660 Und Sie sehen, auch hier musste wieder umgebaut werden, weil wir hier 37:23.660 --> 37:27.140 auf einmal in diesem Teilbaum rechts Höhendifferenz 2 hatten. 37:28.460 --> 37:30.760 Ja, das war also nur für den Baum hier gezogen. 37:30.940 --> 37:32.360 So können Sie damit weiter rumspielen. 37:32.780 --> 37:34.700 Der Link ist auf den Folien angegeben. 37:35.300 --> 37:39.300 Das ist also ein ganz nettes Werkzeug, um zu sehen, was passiert 37:39.300 --> 37:39.660 eigentlich. 37:39.740 --> 37:43.480 Und es wird jeweils hier unten angegeben, welche Vergleiche gemacht 37:43.480 --> 37:43.760 wurden. 37:43.880 --> 37:47.280 Da ist diese Zeile, wird genau protokolliert, welche Operationen 37:47.280 --> 37:48.120 ausgeführt werden. 37:48.540 --> 37:51.660 Und man kann also feststellen, alle Operationen, die ich hier mache, 37:51.740 --> 37:55.660 beim Einfügen, auch beim Löschen und ähnlichen, also wenn ich jetzt 37:55.660 --> 38:05.940 hier meinetwegen sage, ich möchte gerne die 59 löschen, dann wird da 38:05.940 --> 38:08.820 ein bisschen ungeordnet, wird ein kleines Element nach oben gerufen. 38:10.340 --> 38:13.120 Und so können Sie damit also rumspielen und sehen, was da eigentlich 38:13.120 --> 38:13.560 passiert. 38:14.440 --> 38:16.100 Okay, gehen wir zurück zu unserer Präsentation. 38:17.740 --> 38:19.080 Das sind also die AVL-Bäume. 38:20.120 --> 38:22.320 Auf die gehe ich nicht im Einzelnen weiter ein. 38:22.320 --> 38:23.960 Zum Rumspielen sind sie ganz nett. 38:24.600 --> 38:28.000 Das Wesentliche ist, Höhendifferenz rechts minus links ist immer 38:28.000 --> 38:28.840 kleiner gleich eins. 38:31.860 --> 38:33.900 Also natürlich Betrag davon. 38:34.260 --> 38:37.140 Ist klar, dass ich hier nicht auf den Betrag beziehe. 38:42.530 --> 38:43.370 Also Betrag... 38:45.410 --> 38:49.270 Höhendifferenz rechts links Betrag der Höhendifferenz rechte Höhe, 38:49.330 --> 38:51.110 linke Höhe, ist kleiner gleich eins. 38:52.550 --> 38:54.730 Das nächste sind B-Bäume. 38:55.270 --> 38:56.270 Was sind B-Bäume? 38:56.430 --> 38:57.590 B steht für Bayer. 38:58.270 --> 39:02.350 Das ist der Name eines Wissenschaftlers, der in München gearbeitet 39:02.350 --> 39:02.690 hat. 39:03.270 --> 39:05.010 Der hat diese B-Bäume entworfen. 39:06.170 --> 39:10.550 B-Bäume, die werden also insbesondere für Datenbankanwendungen 39:10.550 --> 39:11.210 verwendet. 39:12.550 --> 39:18.610 Und ich zeige Ihnen jetzt eine eingeschränkte Variante. 39:18.610 --> 39:21.610 Bei den B-Bäumen, nur um das nochmal kurz anzudeuten. 39:22.330 --> 39:28.190 Bei den B-Bäumen, da haben sie im Prinzip jeweils Bäume, die haben 39:28.190 --> 39:29.430 ziemlich viele Nachfolger. 39:30.110 --> 39:35.750 Und die Anzahl der Elemente, die hier drin sind wenn das hier, ich 39:35.750 --> 39:43.290 nenne das mal die Anzahl der Schlüssel in irgendeinem Knoten das ist 39:43.290 --> 39:51.790 immer kleiner gleich B und B ist die Blockgröße des 39:51.790 --> 39:52.770 Hintergrundspeichers. 39:56.260 --> 39:58.060 Warum macht man sowas? 39:59.220 --> 40:00.840 Blockgröße des Hintergrundspeichers. 40:00.920 --> 40:05.000 Das heißt, wenn ich hier irgendwelche neuen Elemente brauche die im 40:05.000 --> 40:09.760 Hintergrundspeicher liegen wenn ich also Elemente nicht finde, dann 40:09.760 --> 40:11.700 muss ich immer einen ganzen Block sowieso holen vom 40:11.700 --> 40:12.460 Hintergrundspeicher. 40:13.080 --> 40:16.460 Und ich kann also den ganzen Block dann in sinnvoller Art und Weise 40:16.460 --> 40:17.880 hier drin einbauen. 40:18.140 --> 40:20.660 Können Sie so kurz eigentlich gar nicht richtig verstehen. 40:21.840 --> 40:26.020 Aber eine eingeschränkte Variante sind die sogenannten 2-3-4-Bäume. 40:26.480 --> 40:34.420 Bei den 2-3-4-Bäumen da ist das B gerade gleich 4. 40:36.160 --> 40:43.200 Das sind einfache B-Bäume, bei denen ich die Anzahl der Elemente in 40:43.200 --> 40:44.580 den einzelnen bzw. 40:44.860 --> 40:45.400 in dem Fall 40:48.760 --> 40:56.320 die Anzahl der Nachfolger ist maximal 4. 40:56.860 --> 40:59.180 3 Elemente im Knotenhaber kriege ich 4 Nachfolger. 40:59.260 --> 41:00.480 Das werden Sie gleich sehen, woran das liegt. 41:01.340 --> 41:05.040 Und die Red-Black-Trees, die Rot-Schwarz-Bäume, sind eine effiziente 41:05.040 --> 41:07.400 Implementierung der 2-3-4-Bäume. 41:08.200 --> 41:12.220 Das ist eigentlich die effizienteste Suchstruktur, die wir haben. 41:12.280 --> 41:15.560 Man kann noch gewisse Varianten, man kann noch Splash-Trees bauen und 41:15.560 --> 41:16.140 ähnliche Dinge. 41:16.260 --> 41:19.660 Da hat man auch ein bisschen Annahmen über die zufällige Verteilung 41:19.660 --> 41:20.820 von Suchschlüsseln. 41:21.240 --> 41:25.000 Aber so für die humanistische Suche sind die Rot-Schwarz-Bäume 41:25.000 --> 41:26.220 eigentlich die effizienteste Suchstruktur. 41:27.700 --> 41:29.980 Auch dazu gibt es ein Applet. 41:31.920 --> 41:34.720 Können wir auch kurz reinschauen. 41:35.940 --> 41:38.980 Ups, das wollte ich gar nicht raus. 41:39.880 --> 41:41.640 Ich muss das mal wieder zurück. 41:42.580 --> 41:44.840 Da habe ich das verkehrte getippt. 41:48.180 --> 41:49.320 Wo bin ich denn jetzt gelandet? 41:49.360 --> 41:50.100 Ach doch, da bin ich ja. 41:51.280 --> 41:52.820 Da will ich jetzt rein. 41:54.660 --> 41:56.100 Und hier sehen Sie noch das. 41:56.200 --> 41:58.080 Also ein etwas allgemeineres Applet. 42:00.860 --> 42:02.580 Ich akzeptiere das Risiko. 42:02.580 --> 42:03.920 Führe aus. 42:05.700 --> 42:10.720 Das ist das allgemeinere Applet für binäre Suchbäume. 42:11.540 --> 42:13.500 Da haben Sie auch hier so ein Splash-Trees. 42:13.620 --> 42:16.340 Sie haben Rot-Schwarz-Bäume, AVL-Bäume. 42:16.940 --> 42:20.540 Das sind Balanceierungsfaktoren, die man zeigen kann. 42:21.100 --> 42:24.660 Hier kann man ein Rotieren der Bäume manuell machen und so weiter. 42:25.140 --> 42:26.740 Hier finden Sie noch irgendwelche Sachen. 42:26.740 --> 42:30.360 Da können Sie die Aufsteigung absteigend machen. 42:30.520 --> 42:34.460 Da können Sie eine so genannte Ford-Control machen, was immer das ist. 42:35.160 --> 42:41.140 Hier können Sie die Geschwindigkeit oder die Größe des Baumes 42:41.140 --> 42:42.060 verändern. 42:42.620 --> 42:45.940 Also das ist hier in dem Fall ein AVL-Baum. 42:49.280 --> 42:53.220 Und wenn ich hier auf Rot-Schwarz-Baum gehe, ist es der gleiche Baum 42:53.220 --> 42:54.820 als Rot-Schwarz-Baum. 42:55.240 --> 42:59.420 Sie sehen beim Rot-Schwarz-Baum da haben Sie rote Knoten und schwarze 42:59.420 --> 42:59.940 Knoten. 43:00.700 --> 43:05.960 Wenn Sie jetzt zählen, die Anzahl der schwarzen Knoten auf einem Weg 43:05.960 --> 43:11.600 von der Wurzel zu den Blättern, stellen Sie fest, dass auf jedem Pfad 43:11.600 --> 43:14.300 genau gleich viele schwarze Knoten sind. 43:15.880 --> 43:21.620 1, 2, 3 1, 2, 3 1, 2, 3 und so weiter. 43:22.800 --> 43:25.560 Fügen wir mal ein, jetzt eine... 43:25.560 --> 43:27.420 können wir hier mal eine 100 einfügen. 43:30.740 --> 43:31.780 100 einfügen. 43:31.860 --> 43:33.060 Das muss ja nun ganz nach rechts laufen. 43:33.380 --> 43:35.880 Hat er gar nicht gemacht. 43:35.960 --> 43:37.480 Aha, der nimmt nur zweistellige Wege. 43:37.760 --> 43:39.440 Fügen wir eine 99 ein. 43:45.000 --> 43:46.440 Jetzt muss die hier ganz nach rechts. 43:47.760 --> 43:50.720 Sie sehen, das wird auch ein roter Knoten. 43:51.660 --> 43:56.280 An der Anzahl der schwarzen Knoten auf dem Pfad lässt sich nichts 43:56.280 --> 43:56.700 verändern. 43:57.140 --> 44:00.300 Fügen wir mal eine 97 an. 44:02.140 --> 44:03.420 Der nimmt sich im Ärger. 44:04.620 --> 44:08.300 97 Der muss jetzt noch da unten mit rein. 44:09.100 --> 44:10.500 Und jetzt sehen Sie, jetzt wird ja was umgebaut. 44:13.200 --> 44:15.460 Und wir haben 97 da unten. 44:16.240 --> 44:19.300 Und auf jedem Pfad immer noch drei schwarze Knoten. 44:20.360 --> 44:22.240 Das heißt, das ist hier das Wesentliche. 44:22.340 --> 44:25.120 Die Anzahl der schwarzen Knoten, das muss man sich hier merken. 44:25.760 --> 44:30.180 Die Anzahl der schwarzen Knoten auf dem Weg von der Wurzel zu den 44:30.180 --> 44:33.060 Blättern ist auf jedem Pfad bedächtig. 44:33.900 --> 44:37.780 Die Frage ist, wie wählt man dann aus, was schwarz und was rote Knoten 44:37.780 --> 44:37.900 sind. 44:38.620 --> 44:42.580 Und das schauen wir uns genauer an, dadurch, dass wir zunächst mal die 44:42.580 --> 44:44.040 2 -3-4-Bäume betrachten. 44:45.020 --> 44:48.400 Wenn Sie die verstanden haben, 2-3-4-Bäume, wissen Sie, was da bei den 44:48.400 --> 44:49.280 roten und schwarzen Knoten ist. 44:50.640 --> 44:52.440 Also, zunächst mal gehen wir zurück. 44:53.300 --> 44:54.720 Was ist überhaupt ein binärer Baum? 44:55.520 --> 45:02.040 Ein binärer Baum ist ein Baum, bei dem jeder Knoten also, wir haben 45:02.040 --> 45:07.740 hier irgendwelche Knoten der hat entweder zwei Nachfolger 45:11.550 --> 45:13.310 oder er hat keinen Nachfolger. 45:13.710 --> 45:16.010 Ich habe hier einen, der hat zwei Nachfolger, die anderen unten haben 45:16.010 --> 45:16.910 keinen Nachfolger. 45:18.170 --> 45:23.090 Üblicherweise werden die Blattknoten so anders gekennzeichnet. 45:23.910 --> 45:24.850 Solche Kästchen. 45:25.770 --> 45:29.150 Kann man auch anders beliebig andeuten. 45:29.630 --> 45:31.690 Wir können auch darauf verzichten, die aufzumalen. 45:31.870 --> 45:35.270 Aber in der Regel deuten wir an, da unten sind solche Kästchen, das 45:35.270 --> 45:35.730 sind die Blätter. 45:38.940 --> 45:40.160 So, was wäre ein binärer Baum? 45:42.200 --> 45:47.700 Die Knoten ohne Vater oder Mutter heißen Wurzel, also das hier wäre 45:47.700 --> 45:48.360 unsere Wurzel. 45:50.100 --> 45:53.240 Und ein Knoten, der kein Blatt ist, ist ein innerer Knoten. 45:53.700 --> 45:55.420 Das ist alles bekannt, denke ich. 45:55.480 --> 45:56.400 Binärer Suchbaum. 45:57.340 --> 46:04.220 Das ist jetzt ein binärer Baum, bei dem ich eine gewisse Belegung der 46:04.220 --> 46:06.440 Knoten habe mit Werten. 46:07.040 --> 46:08.760 Jeder Knoten enthält einen Schlüssel. 46:08.760 --> 46:12.820 Also zum Beispiel könnte hier eine 7 stehen. 46:14.620 --> 46:18.980 Und alle Schlüssel im linken Unterbaum eines inneren Knotens sind 46:18.980 --> 46:19.500 kleiner. 46:19.740 --> 46:21.500 Alle im rechten Unterbaum sind größer. 46:22.120 --> 46:26.460 Also hier könnte eine 3 stehen, da könnte eine 10 stehen. 46:27.340 --> 46:29.380 Das wäre also ein binärer Suchbaum. 46:29.460 --> 46:30.760 Ich habe eine Ordnungsrelation. 46:31.600 --> 46:35.420 Wenn ich einen vollständigen Suchbaum habe, so schön balanciert, dann 46:35.420 --> 46:38.760 ist das genau die Suchstruktur, die ich habe, wenn ich eine binäre 46:38.760 --> 46:39.320 Suche mache. 46:39.920 --> 46:43.980 Das mittlere Element und dann gucke ich das entsprechend links wieder 46:43.980 --> 46:45.460 das mittlere Element an und so weiter. 46:46.200 --> 46:47.600 Deswegen binärer Suchbaum. 46:47.640 --> 46:52.240 Wenn ich da durchlaufe, mache ich genau die Vergleiche, die ich bei 46:52.240 --> 46:54.360 einer binären Suche in einer linearen Liste mache. 46:56.220 --> 46:57.880 Das ist also ein binärer Suchbaum. 46:58.280 --> 47:02.320 Und ein idealer binärer Suchbaum ist halt so ein vollständiger binärer 47:02.320 --> 47:05.640 Baum, wo ich für egal, was ich suche, log n Vergleiche habe. 47:06.840 --> 47:08.620 Jetzt baue ich einen binären Suchbaum. 47:09.860 --> 47:15.340 Ich habe da keine Anforderungen gemacht, welche Gestalt die jeweiligen 47:15.340 --> 47:16.200 Teilbäume haben. 47:16.340 --> 47:19.020 Es könnte sein, dass ich einen solchen Baum nehme. 47:19.120 --> 47:20.980 Der ist genauso ein binärer Suchbaum. 47:21.080 --> 47:23.580 Man nimmt immer an, dass a kleiner b kleiner c kleiner d ist. 47:24.520 --> 47:26.800 Dann ist das natürlich genauso ein binärer Suchbaum. 47:27.340 --> 47:30.920 Es sind in der einen Richtung nie irgendwelche Elemente drin. 47:32.360 --> 47:34.460 Nur der hat natürlich nicht die schöne Struktur, die wir haben 47:34.460 --> 47:34.800 wollten. 47:35.440 --> 47:38.300 Hier hätte ich lineare Zeit im schlechtesten Falle zu suchen. 47:38.380 --> 47:39.580 Das ist im Prinzip eine lineare Liste. 47:40.860 --> 47:44.820 Das heißt, worum es geht ist, dafür zu sorgen, dass die Pfade zu den 47:44.820 --> 47:48.380 einzelnen Elementen, die ich suchen möchte, alle einigermaßen gleich 47:48.380 --> 47:52.120 lang sind und möglichst maximal die Länge, Größenordnung log n haben. 47:53.260 --> 47:56.300 Also das ist die typische binäre Suchbäume. 47:56.300 --> 47:59.000 Die müssten Sie eigentlich aus Grundlage der Informatik 1 noch kennen. 48:00.860 --> 48:02.740 Wenn ich jetzt... 48:02.740 --> 48:04.200 Also Ausweg woraus? 48:04.400 --> 48:06.260 Ausweg aus diesem Problem. 48:07.360 --> 48:10.640 Häufiges Einfügen oder Löschen binärer Suchbäume kann entartete 48:10.640 --> 48:11.440 Suchbäume erzeugen. 48:12.100 --> 48:13.300 Mit linearem Suchaufwand. 48:13.400 --> 48:16.140 Es sei denn, ich rotiere die wieder geeignet hin und her. 48:16.980 --> 48:18.200 Das ist jetzt der Ausweg. 48:18.320 --> 48:22.100 Ich habe die höhenbalancierten Bäume, bei denen sich die Höhe der 48:22.100 --> 48:24.220 beiden Unterbäume höchstens um 1 unterscheidet. 48:24.220 --> 48:25.880 Das sind zum Beispiel die AFL-Bäume. 48:25.940 --> 48:28.500 Habe ich Ihnen gerade kurz vorgestellt. 48:28.740 --> 48:31.020 Mit dem Applet können Sie sich auch genauer anschauen. 48:31.500 --> 48:34.840 Da kann ich Einfügen und Löschen über Rebalancierung machen. 48:34.940 --> 48:36.300 Auch dafür haben Sie gerade ein Beispiel gesehen. 48:36.480 --> 48:40.280 Dieser Aufwand für das Rebalancieren, also nur aufrechterhalten, der 48:40.280 --> 48:47.060 Tatsache, dass ich links und rechts Bäume habe, deren Höhe sich 48:47.060 --> 48:48.200 höchstens um 1 unterscheidet. 48:48.840 --> 48:49.780 Das ist also kein Problem. 48:49.780 --> 48:53.460 Da kann aber Folgendes passieren, dass ich hier irgendeinen Baum habe 48:53.460 --> 48:59.860 und auf einmal habe ich hier einen Knoten, der hat nur einen 48:59.860 --> 49:00.840 Nachfolger. 49:01.280 --> 49:03.020 Also solche Dinge können ja auch auftauchen. 49:03.580 --> 49:06.960 Aber das ist alles nicht so entscheidend. 49:08.460 --> 49:10.800 Das sind die einfachen höhenbalancierten Bäume. 49:10.920 --> 49:11.960 Darauf wollte ich immer nicht weiter eingehen. 49:12.040 --> 49:13.340 Jetzt kommen hier die 2-3-4-Bäume. 49:14.220 --> 49:18.960 Bei den 2-3-4-Bäumen gilt dieses 2-3-4 dafür, dass ich nicht mehr nur 49:18.960 --> 49:25.100 binäre Bäume betrachte, sondern Bäume, die haben die Knoten bis zu 4 49:25.100 --> 49:25.760 Nachfolger. 49:26.920 --> 49:29.220 Allgemeiner kann ich auch von A-B-Bäumen reden. 49:30.040 --> 49:35.320 Das heißt, minimale Anzahl der Nachfolger ist A, maximale Anzahl der 49:35.320 --> 49:36.280 Nachfolger ist B. 49:36.720 --> 49:37.780 Dann habe ich A-B-Bäume. 49:38.760 --> 49:44.120 Bei den Groß-B-Bäumen, die ich Ihnen vorhin kurz angedeutet habe, wäre 49:44.120 --> 49:49.440 das Klein-B gerade die Blockgröße, also diese große Zahl, 1000 49:49.440 --> 49:50.300 Elemente oder irgendwas. 49:50.960 --> 49:53.100 Oder 500 oder so, das ist die typische Größe. 49:54.580 --> 49:59.080 Bei den 2-3-4-Bäumen enthält jeder Knoten 0 bis 3 Schlüssel. 50:00.180 --> 50:04.420 Wenn er keine Schlüssel enthält, ist es ein Blatt, keine Nachfolger. 50:04.420 --> 50:08.240 Wenn ich einen Schlüssel drin habe, also ein Element, dann kann ich 50:08.240 --> 50:10.320 entscheiden, kleiner oder größer. 50:10.640 --> 50:11.900 Dann habe ich 2 Nachfolger. 50:12.360 --> 50:14.640 Das wäre also diese übliche Anordnung. 50:15.100 --> 50:20.760 Wenn ich dort 2 Elemente habe, A und B, dann würde ich also 3 50:20.760 --> 50:21.780 Nachfolger bekommen. 50:22.760 --> 50:26.580 Diejenigen, die kleiner als A sind, die größer gleich A sind und 50:26.580 --> 50:30.360 kleiner als B und diejenigen, die größer als B oder größer gleich B 50:30.360 --> 50:30.640 sind. 50:31.880 --> 50:34.060 Dann hätte ich 3 Nachfolger. 50:34.720 --> 50:37.620 Wenn ich 3 Knoten drin habe, hätte ich entsprechend 4 Nachfolger. 50:37.840 --> 50:41.680 Allgemein kann ich sagen, ich habe hier K-Elemente drin in einem 50:41.680 --> 50:42.160 Knoten. 50:42.480 --> 50:44.200 Das ist genau das, was ich gerade angedeutet habe. 50:45.000 --> 50:51.160 Ich habe hier jeweils die Schlüssel innerhalb der Knoten S1 bis SK. 50:51.440 --> 50:55.880 Sind sortiert angeordnet, aufsteigend sortiert. 50:55.880 --> 51:04.280 Und für die Unterbäume gilt gerade, dass der linkeste, dieser T1, die 51:04.280 --> 51:06.820 Schlüssel, die da drin sind, sind kleiner als S1. 51:07.140 --> 51:10.320 Die kommen alle ganz nach links hier rüber. 51:11.740 --> 51:17.880 Und dann in den anderen Unterbäumen sind alle Schlüssel größer gleich 51:17.880 --> 51:20.160 SI -1 und kleiner als SI. 51:21.120 --> 51:25.300 Und alles in TK plus 1 ist größer gleich SK. 51:26.300 --> 51:30.180 Und alle Unterbäume haben die gleiche Höhe. 51:31.300 --> 51:32.620 Das ist ja interessant. 51:33.240 --> 51:37.280 Wir hatten vorher bei den höhenbalancierten Bäumen gesagt, 51:37.680 --> 51:39.560 Höhenunterschied maximal 1. 51:40.320 --> 51:45.740 Hier sagen wir, alle Pfade in diesen Bäumen sind gleich lang. 51:46.280 --> 51:48.980 Alle Unterbäume haben die gleiche Höhe. 51:48.980 --> 51:53.660 Das heißt, man steckt hier die Höhendifferenzen im Prinzip in die 51:53.660 --> 51:54.260 Knoten ran. 51:56.200 --> 51:57.880 Macht einfach dickere Knoten. 51:58.860 --> 52:02.800 Dann habe ich zwei dickere Knoten, aber die Pfade sind alle gleich 52:02.800 --> 52:03.060 lang. 52:04.560 --> 52:10.340 Damit weiß ich, egal wo ich durchlaufe, die Anzahl der Kanten ist 52:10.340 --> 52:10.840 immer gleich. 52:10.980 --> 52:14.420 Ich habe also überall fast den gleichen Suchaufwand. 52:15.240 --> 52:18.920 Der ist nicht genau gleich, weil natürlich, wenn ich jetzt auf einem 52:18.920 --> 52:26.700 Pfad von der Wurzel runter zu den eigentlichen Elementen, die ich ja 52:26.700 --> 52:31.080 tatsächlich nachher haben möchte, wenn ich hier jeweils viele Elemente 52:31.080 --> 52:35.540 drin habe, muss ich ja jeweils erstmal den entsprechenden Nachfolger 52:35.540 --> 52:35.860 finden. 52:37.040 --> 52:39.420 Das ist jeweils logarithmisch in der Größe der... 52:39.420 --> 52:41.780 Das mache ich mit binärer Suchuhr, ich habe da selbst wieder einen 52:41.780 --> 52:42.400 Suchbaum drin. 52:43.000 --> 52:46.360 Das dauert, wie der Lock der Anzahl der Schlüssel da drin ist. 52:47.000 --> 52:49.720 Wenn ich eine konstante Anzahl von Schlüsseln habe, ist das konstant, 52:50.540 --> 52:54.580 aber insgesamt ist der Suchaufwand auf jeden Fall kleiner gleich 52:54.580 --> 52:54.960 Locken. 52:56.040 --> 53:00.600 Ich habe es ein bisschen verkürzt, aber diese Verkürzung bezahle ich 53:00.600 --> 53:04.300 durch ein bisschen mehr Aufwand, um die Nachfolger feststellen zu 53:04.300 --> 53:04.540 können. 53:05.340 --> 53:07.560 Also um die Verzweigung durchführen zu können. 53:07.560 --> 53:13.240 Also insofern auf jeden Fall Locken, also maximal Locken, das ist aber 53:13.240 --> 53:15.180 etwas beschlossen. 53:15.940 --> 53:16.960 Die Struktur ist ja einfach. 53:17.840 --> 53:19.620 Schauen wir mal an, wie solche Bäume entstehen. 53:19.720 --> 53:22.960 Wir haben einen ganz einfachen Baum, der hat ein Element, mit dem das 53:22.960 --> 53:23.940 a kleiner gleich b ist. 53:23.960 --> 53:27.640 Wir wollen a einfügen, dann machen wir einfach aus so einer Wurzel, 53:28.060 --> 53:31.080 oder aus einem einfachen Baum mit einem Element, einfach einen Baum 53:31.080 --> 53:35.520 mit zwei Elementen, beziehungsweise einen Knoten mit zwei Elementen, 53:35.880 --> 53:36.600 der hat drei Blätter. 53:36.760 --> 53:37.780 Das ist ja ganz einfach. 53:38.680 --> 53:42.020 Dann haben wir einen Knoten, der hat zwei Elemente, wir fügen ein 53:42.020 --> 53:47.560 drittes dazu und haben dann einen Knoten, in den wir nichts weiteres 53:47.560 --> 53:48.500 mehr reinschreiben können. 53:48.580 --> 53:49.100 Der ist voll. 53:51.820 --> 53:56.580 Jetzt wollen wir etwas einfügen, wenn wir etwas einfügen wollen, in 53:56.580 --> 53:57.140 einen Baum. 53:58.080 --> 54:01.660 Dann laufen wir ja in, sagen wir hier so einen größeren Baum, da haben 54:01.660 --> 54:04.500 wir oben immer irgendeinen Knoten, dann verzweigt sich das hier 54:04.500 --> 54:04.900 irgendwie. 54:05.620 --> 54:08.640 Und irgendwie laufen wir hier runter, wenn wir etwas einfügen wollen, 54:08.720 --> 54:11.820 bis zu einem Blatt, wo wir das Element nicht gefunden haben. 54:12.660 --> 54:13.800 Das heißt, wir müssen es einfügen. 54:14.460 --> 54:17.880 Und wir sind genau an der Position, wo wir es einfügen müssen, weil 54:17.880 --> 54:23.740 alle Elemente auf der einen Seite kleiner gleichen, auf der anderen 54:23.740 --> 54:25.180 Seite größer sind. 54:26.320 --> 54:32.300 Jetzt sind wir also zum Beispiel hier angelangt und wollen etwas 54:32.300 --> 54:36.460 einfügen in diesen Knoten. 54:36.500 --> 54:39.400 Wir sind hier unten irgendwo gelandet, stellen fest, wir sind kleiner 54:39.400 --> 54:42.460 als B und müssen da etwas einfügen. 54:43.100 --> 54:45.280 Das passt aber, das A passt da nicht rein. 54:45.520 --> 54:48.680 Wenn das hier nur zwei Elemente gewesen wären oder nur ein Element, 54:48.740 --> 54:49.820 hätte ich es da reinschreiben können. 54:50.280 --> 54:51.180 Jetzt geht das aber nicht. 54:51.260 --> 54:53.820 Das A ist größer gleich X, deswegen sind wir hier gelandet. 54:54.500 --> 54:55.540 Es ist kleiner gleich B. 54:56.660 --> 55:01.900 Jetzt mache ich das einfach so, dass ich so tue, als könnte ich einen 55:01.900 --> 55:06.520 solchen Knoten bauen mit A, B, C, D. 55:08.020 --> 55:10.820 Und ich schiebe einfach den Media nach oben. 55:11.980 --> 55:13.660 Das ist aufsteigend sortiert. 55:14.340 --> 55:15.900 Der Median ist das Element C. 55:18.380 --> 55:21.420 C nach oben schieben, also aus diesem Knoten hier, der hätte ja 55:21.420 --> 55:24.080 eigentlich fünf Nachfolger, das darf ich hier nicht. 55:24.840 --> 55:29.700 Ich schiebe das C nach oben, dann bleibt der Knoten A, B übrig, der 55:29.700 --> 55:30.800 hat drei Nachfolger. 55:31.180 --> 55:34.540 Das C ist nach oben gewandert und hier bleibt das D noch übrig, der 55:34.540 --> 55:35.280 hat zwei Nachfolger. 55:36.300 --> 55:43.020 Also ich baue fiktiv einen Knoten mit vier Schlüsseln und schiebe den 55:43.020 --> 55:48.140 Median dieses Knotens einfach nach oben. 55:49.600 --> 55:52.440 Und da muss natürlich das C da oben reinpassen. 55:53.960 --> 55:59.260 Wenn der schon zu groß ist, dann baue ich den halt um, schiebe den 55:59.260 --> 56:00.960 nach oben und so weiter. 56:01.980 --> 56:03.320 Wie oft muss ich umbauen? 56:04.820 --> 56:08.120 Maximal Log N mal, weil die Fahrtlänge ja Log N ist. 56:09.220 --> 56:11.980 Und der Aufwand zum Umbauen, der ist ja nicht sehr groß. 56:12.680 --> 56:16.420 Die anderen Fälle sind entsprechend identisch. 56:16.960 --> 56:18.500 Ich sagte, ich schiebe den Median nach oben. 56:18.880 --> 56:22.380 Wenn das A, also das ist natürlich kleiner als A, und in dem Fall 56:22.380 --> 56:24.980 nehmen wir an, dass A wäre größer als D, wenn das das größte Element 56:24.980 --> 56:29.280 ist, dann ist D der Median, das ist im Prinzip immer noch das gleiche. 56:29.280 --> 56:33.960 Oder wenn ich an der Wurzel bin, das ist ein kleiner Baum, ich bin 56:33.960 --> 56:35.700 also an der Wurzel angelangt mit dem Einfügen. 56:36.920 --> 56:43.600 Und dann entsteht eben eine neue Wurzel mit dem Median dieser vier 56:43.600 --> 56:44.280 Elemente. 56:45.460 --> 56:48.400 Und unten drunter sind zwei weitere Knoten. 56:48.640 --> 56:50.840 Einer sind drei Knoten, einer sind zwei Knoten. 56:52.480 --> 56:57.860 Und das heißt, wenn ich mir anschaue, wie diese Bäume sich verändern, 56:58.620 --> 57:05.580 wenn ich also einen Baum habe, in den ich hier oben etwas einfüge, ich 57:05.580 --> 57:08.560 habe hier das A, das muss eingefügt werden, wenn das hier nicht 57:08.560 --> 57:11.280 reinpasst, dann kann das sein, dass ich hier sukzessive immer nach 57:11.280 --> 57:14.180 oben laufe und irgendwann an der Wurzel ankomme. 57:15.280 --> 57:18.920 Und da wird jetzt eventuell ein neuer Knoten nach oben geschoben. 57:19.660 --> 57:24.400 Dann habe ich die Höhe meines Baumes um 1 erhöht. 57:24.580 --> 57:27.600 Das ist hier die Erhöhung der Höhe des Baumes um 1. 57:28.440 --> 57:31.600 Die anderen Operationen haben ja an der Höhe meines Baumes nichts 57:31.600 --> 57:35.000 verändert, weil ich ja nur etwas in die nächste Ebene reingeschoben 57:35.000 --> 57:35.360 habe. 57:36.680 --> 57:37.740 Das verändert die Höhe nicht. 57:38.340 --> 57:39.820 Die Höhe wird nur am Ende verändert. 57:39.980 --> 57:43.740 Und da ich nur eine neue Wurzel dazu baue, sind natürlich alle Pfade 57:43.740 --> 57:47.080 von der Wurzel zu den Blättern jetzt um 1 erhöht. 57:47.080 --> 57:53.480 Die Eigenschaft, die ich brauchte, dass alle Knoten maximal 3 57:53.480 --> 57:58.260 Schlüssel enthalten und dass alle Pfade die gleiche Länge haben, die 57:58.260 --> 58:00.660 ist mit dieser Operation eindeutig einzuhalten. 58:01.780 --> 58:07.520 Ich mache also immer diese Operation media nach oben und habe dann den 58:07.520 --> 58:08.720 Effekt, den ich brauchte. 58:08.720 --> 58:12.960 Ich habe logarithmischen Aufwand, um etwas zu suchen. 58:14.100 --> 58:16.460 Die Pfadlänge ist immer kleiner gleich log n. 58:17.280 --> 58:22.040 Wenn ich etwas einfüge, maximaler Aufwand ebenfalls log n. 58:22.100 --> 58:24.380 Ich habe ein bisschen zu tun, ich muss erstmal den Platz hier unten 58:24.380 --> 58:24.800 finden. 58:25.460 --> 58:28.940 Dann muss ich nach oben laufen, bis ich einen Knoten finde, der 58:28.940 --> 58:30.520 genügend Platz hat. 58:30.580 --> 58:32.800 Und wenn die alle nicht genügend Platz haben, muss ich eben eventuell 58:32.800 --> 58:33.860 noch einen neuen dazufügen. 58:33.860 --> 58:36.140 Das ist eben auch nochmal Aufwand log n. 58:36.280 --> 58:41.220 Das heißt, ich habe hier 2 mal eine Konstante mal log n da drin. 58:41.920 --> 58:44.180 Und das heißt, es ist schon ein bisschen kompliziert. 58:47.580 --> 58:51.260 Diese Situation 3 und 4 hier, dass ich also etwas nach oben schieben 58:51.260 --> 58:58.440 möchte, die fügen führen halt zu extra Aufwand, wenn der Vorgänger, wo 58:58.440 --> 59:02.560 hier das x eingemalt ist, bereits ein 4 Knoten ist, der bereits voll 59:02.560 --> 59:02.840 ist. 59:04.060 --> 59:05.280 Jetzt gibt es eine Idee. 59:06.200 --> 59:12.660 Ich sorge einfach dafür, dass bei einem Einfügen die Knoten, die oben 59:12.660 --> 59:14.740 drüber liegen, immer Platz haben. 59:16.300 --> 59:17.800 Wie kann man das machen? 59:20.600 --> 59:26.560 Beim Suchen des Einfügeortes teile ich einfach... also ich bin dabei, 59:26.640 --> 59:27.700 ich möchte etwas einfügen. 59:28.200 --> 59:30.240 Ich komme zu einem solchen Knoten. 59:31.180 --> 59:32.040 Da gehe ich rein. 59:32.100 --> 59:33.160 Ich stelle fest, der ist voll. 59:34.620 --> 59:36.840 Mein Element, das ich suche, ist nicht hier drin. 59:36.940 --> 59:38.480 Ich weiß, ich muss da unten runter laufen. 59:38.560 --> 59:41.180 Es könnte sein, dass ich später mal wieder hier zurückkomme. 59:42.460 --> 59:46.140 Das möchte ich dafür sorgen, dass auf jeden Fall dort Platz ist. 59:46.900 --> 59:52.220 Das heißt, ich baue einfach einen solchen vollen Knoten um, in drei 59:52.220 --> 59:58.980 neue Knoten, A, B und C, die jeweils zwei Knoten sind. 59:59.980 --> 01:00:01.780 Bei denen ist auf jeden Fall Platz. 01:00:02.080 --> 01:00:03.760 Und ich suche dann entsprechend unten weiter. 01:00:03.860 --> 01:00:05.120 Zum Beispiel hier bei T2. 01:00:06.100 --> 01:00:08.380 Und wenn da schon ein Blatt war, dann weiß ich, wenn ich hier was 01:00:08.380 --> 01:00:10.460 einfügen musste, oben drüber ist ja Platz. 01:00:11.220 --> 01:00:14.260 Entsprechend macht man das einfach, dass man beim Suchen ein bisschen 01:00:14.260 --> 01:00:14.880 mehr macht. 01:00:15.120 --> 01:00:21.460 Dass man einfach jeden vollen Knoten aufteilt in solche drei Knoten. 01:00:22.880 --> 01:00:25.440 Beziehungsweise ich mache das bei dem ersten, wenn die Wurzel voll 01:00:25.440 --> 01:00:26.300 ist, mache ich das. 01:00:28.500 --> 01:00:34.960 Und dann weiß ich hier oben drüber, ist garantiert ein Zweiknoten über 01:00:34.960 --> 01:00:35.660 dem T2. 01:00:36.340 --> 01:00:42.260 Wenn das T2 als Wurzel einen vollen Knoten hat, dann teile ich den auf 01:00:42.260 --> 01:00:45.520 und die Wurzel da draußen, die wandert ja einfach dahin. 01:00:45.740 --> 01:00:47.040 Das ist dann relativ einfach. 01:00:47.180 --> 01:00:48.300 Das ist hier nochmal angedeutet. 01:00:49.560 --> 01:00:51.860 Zweite Situation, wenn ich nicht an der Wurzel bin, sondern irgendwo 01:00:51.860 --> 01:00:52.180 drin. 01:00:52.560 --> 01:00:54.040 Ich treffe auf das A, B, C. 01:00:54.800 --> 01:00:57.960 Ich teile es einfach auf, schiebe das B nach oben. 01:00:58.320 --> 01:01:00.900 Und ich weiß ja, oben drüber ist Platz, weil ich alles oben drüber 01:01:00.900 --> 01:01:01.880 bereits aufgeteilt habe. 01:01:03.180 --> 01:01:06.300 Das heißt, wenn ich jetzt ganz nach unten gekommen bin, habe ich auf 01:01:06.300 --> 01:01:08.940 jeden Fall oben drüber Platz, ich kann sofort einführen. 01:01:09.180 --> 01:01:13.300 Ich mache jetzt eben den Aufwand, stecke ich jetzt rein bei dem 01:01:13.300 --> 01:01:14.920 Runterlaufen in den Zugbaum. 01:01:16.380 --> 01:01:19.400 Das ist nochmal die gleiche Situation, im Prinzip nur anders. 01:01:19.740 --> 01:01:21.020 Einmal links, einmal rechts. 01:01:21.840 --> 01:01:23.280 Und hier nochmal irgendwas in der Mitte. 01:01:24.020 --> 01:01:26.140 Jeweils die gleiche Überlegung. 01:01:26.260 --> 01:01:28.560 Ich habe oben drüber jeweils Platz, das ist das Wesentliche. 01:01:32.960 --> 01:01:38.940 Und die Eigenschaften sind halt, dass ich hier jeweils zwei neue 01:01:38.940 --> 01:01:39.440 Knoten... 01:01:39.440 --> 01:01:43.140 Wenn ich also aufteile, jetzt stehen zwei neue Knoten und höchstens 01:01:43.140 --> 01:01:44.360 ein neuer Vierknoten. 01:01:44.980 --> 01:01:49.860 Und die Suche endet in einem neuen Zweiknoten oder in einem alten Zwei 01:01:49.860 --> 01:01:50.900 - oder Dreiknoten. 01:01:51.300 --> 01:01:52.400 Das heißt, da ist auf jeden Fall Platz. 01:01:52.940 --> 01:01:54.040 Ich muss dann nicht mehr aufteilen. 01:01:54.040 --> 01:02:01.420 Dieses 2-3-4-Bäume mit Top-Down-Teilen ist deutlich effizienter als 01:02:01.420 --> 01:02:07.300 das einfache Einfügen in einen 2-3-4-Baum. 01:02:07.700 --> 01:02:12.800 Wenn ich jetzt die Buchstaben in dieser Folge von Buchstaben einfüge 01:02:12.800 --> 01:02:14.500 in einen 2-3-4-Baum... 01:02:14.500 --> 01:02:17.960 Hier sehen Sie, ich habe gleiche Elemente, also das E taucht mehrfach 01:02:17.960 --> 01:02:19.560 auf, das I taucht mehrfach auf. 01:02:19.900 --> 01:02:21.740 Dann entsteht ein Baum, der sieht so aus. 01:02:23.300 --> 01:02:25.660 Können Sie sich einfach überlegen, wenn Sie hier etwas einfügen, nach 01:02:25.660 --> 01:02:28.800 den Regeln, die ich gerade genannt habe, dann entsteht genau solch ein 01:02:28.800 --> 01:02:28.980 Baum. 01:02:29.440 --> 01:02:32.560 Das heißt, hier haben Sie hier unten einmal einen vollen Knoten, da 01:02:32.560 --> 01:02:33.720 haben Sie auch einen vollen Knoten. 01:02:34.060 --> 01:02:36.620 Die anderen sind alle gar nicht voll, das sind alles Dreiknoten, das 01:02:36.620 --> 01:02:38.120 sind die einzigen beiden Vierknoten. 01:02:39.160 --> 01:02:42.780 Wenn Sie das gleiche in einen Binärbaum einfügen, einen binären 01:02:42.780 --> 01:02:45.260 Suchbaum, dann würden Sie diese Struktur bekommen. 01:02:45.260 --> 01:02:48.820 Wenn Sie einfach immer nur links und rechts einfügen, je nachdem, ob 01:02:48.820 --> 01:02:52.340 der Buchstabe da eingefügt werden muss, kleiner oder größer als der 01:02:52.340 --> 01:02:58.040 Wert an dem Knoten ist, dann bekommen Sie also eine andere Struktur. 01:02:58.200 --> 01:03:03.740 Und Sie sehen, die Pfadlänge hier ist 1-2-3-4-5. 01:03:04.620 --> 01:03:09.000 Und hier habe ich gerade 1-2 als Höhe dieses Baumes. 01:03:10.700 --> 01:03:15.320 Natürlich habe ich hier drin dann noch drei Elemente, die ich mir noch 01:03:15.320 --> 01:03:15.940 angucken muss. 01:03:16.600 --> 01:03:19.420 Und das steckt hier halt in der Pfadlänge drin, aber dieser hier oben 01:03:19.420 --> 01:03:20.080 ist auf jeden Fall balanciert. 01:03:20.880 --> 01:03:22.220 Der hier unten ist halt nicht balanciert. 01:03:22.520 --> 01:03:25.060 Da habe ich eine Länge 2, E, C, B. 01:03:25.580 --> 01:03:27.960 Und hier habe ich halt diese lange Folge gehabt. 01:03:29.460 --> 01:03:35.940 Also das ist 2-3-4 Bäume, mit denen erreiche ich eine Balancierung der 01:03:35.940 --> 01:03:41.040 Höhen, damit einen Ausgleich des Aufwandes zwischen den Suchen, 01:03:41.660 --> 01:03:43.380 Einfügen, Löschen. 01:03:44.300 --> 01:03:45.600 Das ist noch ein bisschen eine andere Operation. 01:03:46.020 --> 01:03:47.420 Kann man ähnlich machen. 01:03:47.980 --> 01:03:49.880 Das schauen wir uns nachher gleich noch an. 01:03:50.740 --> 01:03:53.840 Also hier haben halt alle Pfade von der Wurzelsilbe dann die gleiche 01:03:53.840 --> 01:03:54.120 Länge. 01:03:54.560 --> 01:03:55.400 Habe ich schon gesagt. 01:03:56.240 --> 01:04:02.400 Beim Einfügen habe ich also maximal Lock-N-4-Knoten aufgeteilt. 01:04:03.120 --> 01:04:08.340 Wenn ich stets Top-Down-Teilen anwende, dann liegt auf jedem Pfad von 01:04:08.340 --> 01:04:12.880 der Wurzel zu einem Blatt maximal ein solcher voller Knoten. 01:04:13.420 --> 01:04:15.380 Weil ich volle Knoten immer aufteile. 01:04:16.260 --> 01:04:18.840 Wenn ich also da immer durchgelaufen bin, füge ich ja maximal an einer 01:04:18.840 --> 01:04:20.760 Stelle einen neuen Knoten ein. 01:04:22.140 --> 01:04:24.620 Und das nächste Mal, wenn ich da durchlaufe, wird das schon wieder 01:04:24.620 --> 01:04:25.220 aufgeteilt. 01:04:25.220 --> 01:04:34.400 Also insofern, ich habe hier den Aufwand für das Aufteilen reduziert. 01:04:34.560 --> 01:04:37.640 Allerdings wird die Größe der Knoten dadurch auch ein bisschen 01:04:37.640 --> 01:04:38.100 kleiner. 01:04:38.840 --> 01:04:42.900 Und die Pfade wird etwas länger, aber immer noch alle gleiche Länge. 01:04:43.400 --> 01:04:45.800 Das Löschen kann ich mir natürlich auch angucken. 01:04:45.940 --> 01:04:49.640 Da gibt es, ich muss überlegen, was mache ich denn da beim Löschen. 01:04:50.740 --> 01:04:52.460 Also ich habe hier meinen Baum. 01:04:55.680 --> 01:04:58.380 Das ist auf der nächsten Folie, aber das wird gleich noch genauer 01:04:58.380 --> 01:04:59.000 erläutert. 01:04:59.120 --> 01:05:00.160 Brauche ich hier nicht aufzumalen. 01:05:02.380 --> 01:05:06.320 Ich möchte das A rauslöschen, also das erste A aus dem 2-3-4-Baum 01:05:06.320 --> 01:05:06.920 rauslöschen. 01:05:07.380 --> 01:05:10.960 Wenn das A gar nicht drin ist, brauche ich gar nichts zu machen. 01:05:11.200 --> 01:05:12.880 Dann muss ich nur einmal durchsuchen und ich bin fertig. 01:05:13.380 --> 01:05:18.900 Das Interessante ist der Fall, dass das A drin ist und ich muss es 01:05:18.900 --> 01:05:19.220 löschen. 01:05:19.220 --> 01:05:22.580 Das A ist irgendwo mitten in einem inneren Knoten drin. 01:05:23.400 --> 01:05:24.780 Jetzt will ich das A löschen. 01:05:25.740 --> 01:05:30.460 Und die Frage ist, was mache ich mit dem Rest des Baumes? 01:05:33.560 --> 01:05:40.140 Ich möchte das A ersetzen durch das nächstgrößere Element im Baum. 01:05:40.900 --> 01:05:43.220 Was ist das nächstgrößere Element im Baum? 01:05:45.220 --> 01:05:49.500 Das ist ein Element, das nach rechts gewandert ist, an dem A vorbei. 01:05:50.940 --> 01:05:53.120 Aber nicht weiter nach rechts. 01:05:53.840 --> 01:05:56.320 Es ist an keinem anderen Element vorbeigelaufen. 01:05:57.560 --> 01:06:01.420 Das heißt, wenn es an keinem anderen Element vorbeiläuft, weiter nach 01:06:01.420 --> 01:06:04.340 rechts, kann es also einmal nach rechts laufen und dann immer nach 01:06:04.340 --> 01:06:04.660 links. 01:06:05.500 --> 01:06:11.060 Dann habe ich hier ganz unten, also den linkesten Schlüssel, rechts 01:06:11.060 --> 01:06:11.600 von A. 01:06:12.180 --> 01:06:15.780 Und der ist ganz unten, direkt über den Blätter. 01:06:16.280 --> 01:06:17.060 Da sitzt der. 01:06:17.940 --> 01:06:21.540 Und den muss ich jetzt irgendwie da oben hin bewegen. 01:06:24.920 --> 01:06:27.520 Das kann man auf geeignete Art und Weise machen. 01:06:28.160 --> 01:06:33.040 Symmetrisch kann man auch sagen, ich nehme das nächstkleinere Element. 01:06:33.760 --> 01:06:35.920 Dann würde ich das Element, das hier ist, wählen. 01:06:36.240 --> 01:06:38.100 Das ist also symmetrisch, können Sie machen, wie Sie wollen. 01:06:40.120 --> 01:06:42.400 Hier sehen Sie, wie man das im Prinzip machen könnte. 01:06:42.400 --> 01:06:46.960 Ich will also das A durch das nächstgrößere Element im Baum ersetzen. 01:06:47.520 --> 01:06:50.020 Das heißt, ich schiebe das B nach oben, dann sind wir das B raus. 01:06:50.820 --> 01:06:54.020 Wenn das hier ein Drei- oder Vierknoten ist, ist es kein Problem. 01:06:54.760 --> 01:06:56.920 Dann nehme ich einfach das B raus und der Rest ist immer noch ein 01:06:56.920 --> 01:06:57.740 vernünftiger Knoten. 01:06:58.500 --> 01:06:59.300 Dann ist es damit fertig. 01:07:00.180 --> 01:07:04.520 Wenn aber das B in einem Zweiknoten liegt, wenn das ein einzelner 01:07:04.520 --> 01:07:07.260 Knoten ist mit zwei Blättern dran, darf ich den nicht einfach 01:07:07.260 --> 01:07:11.120 rauslöschen, dann hätte ich auf einmal hier eine kürzere Pfadlänge. 01:07:11.240 --> 01:07:11.860 Das geht nicht. 01:07:12.640 --> 01:07:16.700 Dann muss ich also dafür sorgen, dass ich das C runterziehe, hier oben 01:07:16.700 --> 01:07:20.180 drüber mit dem nächsten Knoten zusammenfüge. 01:07:20.260 --> 01:07:21.660 Dann habe ich hier C, D und E. 01:07:22.200 --> 01:07:23.940 Das mittlere geht nach oben und ich bin fertig. 01:07:25.060 --> 01:07:29.100 Und entsprechend, weil das C jetzt hier oben rausgelaufen ist, kann es 01:07:29.100 --> 01:07:32.460 sein, dass da noch weitere Folgeprobleme auftauchen. 01:07:32.460 --> 01:07:34.000 Und die muss ich auch geeignet bearbeiten. 01:07:34.260 --> 01:07:35.880 Das möchte ich jetzt aber nicht im Einzelnen ausfügen. 01:07:37.300 --> 01:07:38.480 Hier also noch ein Fall. 01:07:39.280 --> 01:07:41.380 Da wird entsprechend was rausgelöscht. 01:07:43.700 --> 01:07:46.280 Das geht entsprechend weiter auf den nächsten Ebenen. 01:07:46.320 --> 01:07:48.660 Ähnlich wie beim Einfügen muss ich also auch hier weiter nach oben 01:07:48.660 --> 01:07:48.980 gucken. 01:07:50.240 --> 01:07:54.320 Und das kann eben sein, dass ich jetzt auf einmal, wenn ja oben drüber 01:07:54.320 --> 01:07:57.060 immer solche Zweiknoten liegen, kriege ich immer wieder Probleme und 01:07:57.060 --> 01:07:58.060 muss dann etwas löschen. 01:07:58.060 --> 01:08:03.640 Und am Ende bin ich dann bis zur Wurzel gekommen und muss dann 01:08:03.640 --> 01:08:08.740 tatsächlich, wenn das Ersetzen in der Wurzel endet, dann wird einfach 01:08:08.740 --> 01:08:13.420 die Wurzel rausgelöscht und ich habe die Höhe des Baumes um 1 01:08:13.420 --> 01:08:13.900 verringert. 01:08:14.600 --> 01:08:15.300 Dann wird das rausgelöscht. 01:08:15.620 --> 01:08:16.820 Also auch das kann passieren. 01:08:17.400 --> 01:08:19.600 Das ist einfach ein Iterieren dieser Überlegungen. 01:08:20.100 --> 01:08:23.160 Ich möchte das gar nicht weiter im Einzelnen machen. 01:08:23.660 --> 01:08:26.180 Das können Sie sich auch selbst leicht überlegen, wie das 01:08:26.180 --> 01:08:26.720 funktioniert. 01:08:27.220 --> 01:08:29.100 Ich sage das einfach so leicht überlegen. 01:08:29.200 --> 01:08:31.100 Das ist ein bisschen kompliziert, also würde ich es mit wenigen 01:08:31.100 --> 01:08:31.920 Vorrednern erklären. 01:08:32.440 --> 01:08:34.120 Aber es ist nicht wirklich schwierig. 01:08:36.020 --> 01:08:41.420 Und jetzt haben wir also den Aufwand für das Delete in logarithmischer 01:08:41.420 --> 01:08:42.700 Zahl insgesamt. 01:08:44.060 --> 01:08:45.020 Logarithmische Pfadlänge. 01:08:45.120 --> 01:08:48.720 Pro Pfad ist es kein, also pro Knoten konstanter Aufwand. 01:08:48.860 --> 01:08:51.280 Das heißt, wir müssen eventuell nochmal nach oben laufen. 01:08:51.880 --> 01:08:54.120 Das ist also auch wieder logarithmischer Aufwand. 01:08:54.120 --> 01:09:00.920 Und wir sind damit schon soweit, dass wir dann eben alle diese 01:09:00.920 --> 01:09:02.100 Operation angeguckt haben. 01:09:02.560 --> 01:09:05.240 Jetzt die Frage, wie implementiert man diese 2-3-4-Bomben? 01:09:06.840 --> 01:09:09.260 Natürlich können Sie so einen Baum... 01:09:09.260 --> 01:09:12.180 Sie haben einen Knoten, das war so ein Baum. 01:09:12.280 --> 01:09:14.800 Da haben Sie jetzt hier S1 bis irgendwie SK. 01:09:15.500 --> 01:09:19.860 Sie haben hier entsprechend die ganzen Teilbäume unten drunter. 01:09:21.680 --> 01:09:23.540 Das heißt, Sie brauchen dort eine Struktur. 01:09:26.200 --> 01:09:29.160 Der Knoten hat immer eine unterschiedliche Anzahl von Elementen. 01:09:29.800 --> 01:09:31.620 Sie müssen sich merken, wie viele Elemente das sind. 01:09:32.480 --> 01:09:34.440 Diese Struktur wird ein bisschen aufwendig. 01:09:35.480 --> 01:09:36.420 Und Sie müssen dann umbauen. 01:09:37.460 --> 01:09:40.980 Wenn Sie sagen, das ist ein 2-Knoten, 3-Knoten oder 4-Knoten. 01:09:41.380 --> 01:09:44.480 Wenn Sie den jetzt umbauen, müssen Sie den dann zu einem 01:09:44.480 --> 01:09:46.720 entsprechenden anderen Knoten machen. 01:09:46.720 --> 01:09:48.960 Das heißt, der Aufwand ist relativ hoch. 01:09:49.960 --> 01:09:51.600 Sie haben drei unterschiedliche Knotentypen. 01:09:52.480 --> 01:09:53.920 Ein Teil der Knoten ist aufwendig. 01:09:56.360 --> 01:10:00.700 Und dieser Vorteil der 2-3-4-Bäume, der geht ein bisschen verloren. 01:10:01.240 --> 01:10:03.700 Also der Vorteil, gleiche Fahrtlänge usw. 01:10:04.520 --> 01:10:08.580 Weil die Datenstrukturen, um solche 2-, 3- und 4-Knoten zu 01:10:08.580 --> 01:10:11.040 repräsentieren, halt etwas aufwendiger sind. 01:10:11.120 --> 01:10:12.980 Die Operationen darauf sind ein bisschen aufwendiger. 01:10:13.180 --> 01:10:15.480 Konstanter Aufwand zwar, trotzdem braucht das Zeit. 01:10:15.480 --> 01:10:18.280 Und deswegen versucht man, das besser zu machen. 01:10:19.700 --> 01:10:23.760 Die Idee ist jetzt da, im Prinzip jetzt die Rot-Schwarz-Bäume 01:10:23.760 --> 01:10:24.460 einzusetzen. 01:10:25.380 --> 01:10:27.200 Das ist jetzt die Idee. 01:10:27.720 --> 01:10:35.040 Ich stelle einfach meine 2-3-4-Bäume durch binäre Bäume dar, mit roten 01:10:35.040 --> 01:10:37.180 und schwarzen Kanten. 01:10:38.660 --> 01:10:40.400 Da kommen wir gleich drauf. 01:10:40.540 --> 01:10:42.800 Sie hatten in dem Beispiel gesehen, da waren das rote und schwarze 01:10:42.800 --> 01:10:43.340 Knoten. 01:10:45.440 --> 01:10:47.840 Ich sage zunächst mal, rote und schwarze Kante. 01:10:49.060 --> 01:10:53.600 Wenn ich also einen solchen einfachen Knoten habe, einen 2-Knoten, der 01:10:53.600 --> 01:10:55.940 ist ja ein binärer Knoten, da brauche ich nichts zu ändern. 01:10:56.880 --> 01:11:03.260 Wenn ich einen 3-Knoten habe, mit 3 Nachfolgern, dann baue ich den 01:11:03.260 --> 01:11:03.920 einfach um. 01:11:04.940 --> 01:11:07.700 Das ist hier mein Knoten, der hat 2 Elemente. 01:11:07.700 --> 01:11:12.660 Und jetzt verbinde ich einfach die beiden Elemente durch eine rote 01:11:12.660 --> 01:11:13.060 Kante. 01:11:15.990 --> 01:11:19.890 Das, was ich jetzt hier rot eingerahmt habe, ist ja nach wie vor mein 01:11:19.890 --> 01:11:21.240 3 -Knoten, mit den 3 Nachfolgern. 01:11:22.110 --> 01:11:24.930 Ich habe einfach nur da eine rote Kante dazwischen gemalt. 01:11:25.010 --> 01:11:26.650 Jetzt ist die Frage, wie ordne ich das an? 01:11:26.750 --> 01:11:29.990 Wo hänge ich die eingehende schwarze Kante ran? 01:11:30.310 --> 01:11:33.610 Hänge ich die an A oder hänge ich die an B? 01:11:35.070 --> 01:11:36.310 Das ist beliebig. 01:11:37.110 --> 01:11:40.150 Das hat nur Auswirkungen für die anschließenden Operationen. 01:11:40.210 --> 01:11:44.870 Das sind beides mögliche Darstellungen eines 3-Knotens. 01:11:45.430 --> 01:11:47.310 Jetzt können Sie sich schon nicht denken, wenn man so einen 4-Knoten 01:11:47.310 --> 01:11:48.290 hat, das ist ja ganz einfach. 01:11:50.270 --> 01:11:53.430 Den stelle ich einfach da durch einen kleinen Baum. 01:11:54.790 --> 01:11:57.210 Ich habe hier 2 rote Kanten. 01:11:58.550 --> 01:12:00.330 Die sind praktisch nicht sichtbar. 01:12:02.170 --> 01:12:05.590 Und ich habe dadurch A, B und C hier drin. 01:12:06.990 --> 01:12:11.830 Und das Interessante ist, jetzt brauche ich mir im Prinzip in jedem 01:12:11.830 --> 01:12:16.710 Knoten meiner Datenstruktur nur zu merken, kommt dort eine rote Kante 01:12:16.710 --> 01:12:18.630 rein oder kommt dort eine schwarze Kante rein? 01:12:20.910 --> 01:12:25.050 Wenn in einen Knoten eine rote Kante reinkommt, kann ich auch sagen, 01:12:25.130 --> 01:12:25.950 der Knoten ist rot. 01:12:27.090 --> 01:12:30.510 Das war die Darstellung in dem Applet mit den roten und schwarzen 01:12:30.510 --> 01:12:31.030 Knoten. 01:12:31.910 --> 01:12:34.510 Also roter Knoten heißt, es geht eine rote Kante rein. 01:12:35.050 --> 01:12:38.670 Das heißt, im Prinzip habe ich hier eine nicht sichtbare Kante. 01:12:40.110 --> 01:12:41.690 Und ich zähle nur die schwarzen Kanten. 01:12:42.310 --> 01:12:45.110 Wenn ich schwarze Kanten zähle, zähle ich im Prinzip die schwarzen 01:12:45.110 --> 01:12:46.190 Knoten in dem Applet. 01:12:46.890 --> 01:12:49.090 Da hat man gesehen, es waren immer eine gleiche Anzahl von schwarzen 01:12:49.090 --> 01:12:51.410 Knoten auf dem Faden von der Wurzel zu den Blättern. 01:12:52.050 --> 01:12:55.270 Das sind genau diese gleiche Anzahl von Knoten eines 2-3-4-Baums. 01:12:57.690 --> 01:13:03.230 Das heißt, so kann man einfach 2-3-4 Knoten darstellen. 01:13:04.410 --> 01:13:11.450 Und wenn ich jetzt aus einem 4-Knoten, also wenn ich diese Applet aus 01:13:11.450 --> 01:13:16.470 einem 4-Knoten, beziehungsweise wenn ich das nach oben schiebe, mache 01:13:16.470 --> 01:13:20.550 ich aus einem 4-Knoten jetzt diese Struktur, Sie erinnern sich, wir 01:13:20.550 --> 01:13:25.530 hatten diese Struktur gehabt, aus so einem Knoten mit 4 Nachfolgern, 01:13:26.450 --> 01:13:29.050 der wurde überführt in dieses Aufteilen. 01:13:32.120 --> 01:13:34.060 Das Aufteilen ist ja ganz einfach. 01:13:35.200 --> 01:13:39.820 Diese Operation besteht nur darin, dass ich bei dieser Baumstruktur 01:13:39.820 --> 01:13:46.820 aus den beiden roten Kanten, schwarze Kanten mache, muss nur 2 Bits 01:13:46.820 --> 01:13:47.200 ändern. 01:13:48.200 --> 01:13:54.600 Um diese Operation hier, Aufteilung eines 4-Knotens, in so einen Baum 01:13:54.600 --> 01:14:00.220 aus 3 2-Knoten zu machen, das war bei den Top-Down-Teilen zum 01:14:00.220 --> 01:14:06.200 Beispiel, das entspricht hier bei dem Rot-Schwarz-Baum einfach nur dem 01:14:06.200 --> 01:14:11.760 Umbenennen dieser, wenn ich also weiß, hier sind bei einem ein B hat 2 01:14:11.760 --> 01:14:18.980 rote Nachfolger, dann würde ich einfach bei den Nachfolgern jeweils 01:14:18.980 --> 01:14:22.060 das Bit auf schwarz setzen von rot. 01:14:22.520 --> 01:14:24.600 Und ich habe genau diese Operation hier oben. 01:14:25.400 --> 01:14:26.500 Ganz einfach. 01:14:27.540 --> 01:14:30.000 Das ist also die Effizienz dieser Datenstruktur. 01:14:31.420 --> 01:14:34.560 Alle Blätter haben die gleiche schwarze Tiefe, niemals 2 rote Kanten 01:14:34.560 --> 01:14:38.160 nacheinander, kann ja nicht sein, weil ich ja von solchen Bäumen, von 01:14:38.160 --> 01:14:40.440 diesen Strukturen hier ausgehe. 01:14:40.440 --> 01:14:43.820 Da laufen immer schwarze Kanten rein und schwarze Kanten raus. 01:14:45.080 --> 01:14:48.860 Und ein Bit pro Knoten reicht, um ihn als rot oder schwarz zu 01:14:48.860 --> 01:14:49.480 kennzeichnen. 01:14:49.560 --> 01:14:52.160 Abhängig von der Farbe der Kante zum Vorgänger. 01:14:53.080 --> 01:14:57.540 Also ob ich jetzt die Kante mit dem Bit versehe oder den Knoten, ist 01:14:57.540 --> 01:15:00.160 im Prinzip nicht relevant. 01:15:01.320 --> 01:15:03.280 Damit habe ich also diese einfache Darstellung. 01:15:04.060 --> 01:15:06.880 Und jetzt kann ich Operationen auf Rot-Schwarz-Bäumen machen. 01:15:08.620 --> 01:15:12.700 Ich kann suchen, natürlich in Zeit kleiner gleich 2 log n. 01:15:13.320 --> 01:15:22.160 Ich habe im schlechtesten Fall, habe ich jeweils eine Folge von roten 01:15:22.160 --> 01:15:24.500 und schwarzen Knoten oder roten und schwarzen Kanten. 01:15:25.080 --> 01:15:26.640 Ich zähle nur die schwarzen Kanten. 01:15:27.080 --> 01:15:30.960 Das heißt maximal habe ich da 2 log n Fahrtlängen. 01:15:31.480 --> 01:15:32.800 Wenn ich rot und schwarz zähle. 01:15:34.720 --> 01:15:38.040 Und ich habe also hier bei dem Einfügen, hatte ich schon gesagt, das 01:15:38.040 --> 01:15:39.600 ist ganz einfach das Aufteilen. 01:15:41.620 --> 01:15:43.680 Und einfach durch diesen Farbwechsel. 01:15:45.740 --> 01:15:49.120 Wenn also oben drüber, also hier, wenn Sie sich angucken, diesen 01:15:49.120 --> 01:15:54.520 Farbwechsel, dann hatte ich erst hier einen 4 Knoten und darüber 2 01:15:54.520 --> 01:15:55.080 Knoten. 01:15:56.700 --> 01:16:01.520 Und jetzt schiebe ich einen Knoten nach oben. 01:16:02.960 --> 01:16:04.900 Und die anderen teile ich auf. 01:16:05.500 --> 01:16:08.580 Dann habe ich aus dem, das war jetzt hier ein 2 Knoten, das wird jetzt 01:16:08.580 --> 01:16:09.500 ein 3 Knoten. 01:16:10.320 --> 01:16:11.400 Auf die Art und Weise. 01:16:12.800 --> 01:16:16.600 Da habe ich einfach hier oben drüber einen, daraus einen roten Knoten 01:16:16.600 --> 01:16:19.240 gemacht und unten drunter, das sind jeweils schwarze Knoten geworden. 01:16:20.980 --> 01:16:22.220 Und schon bin ich damit fertig. 01:16:22.780 --> 01:16:25.400 Also das ist eine ganz einfache Operation. 01:16:26.360 --> 01:16:29.100 Ich habe noch Sonderfälle dabei zu betrachten, die ich jetzt hier 01:16:29.100 --> 01:16:29.760 nicht betrachte. 01:16:29.760 --> 01:16:33.360 Beim Löschen werden auch ähnliche Operationen gemacht. 01:16:34.000 --> 01:16:38.580 Der Aufwand insgesamt für Einfügen, Löschen und Suchen ist jeweils 01:16:38.580 --> 01:16:38.760 höher. 01:16:41.000 --> 01:16:43.320 Und damit habe ich eine sehr schöne, einfache Struktur. 01:16:43.500 --> 01:16:45.260 Ich kann die einzelnen Operationen einfach machen. 01:16:45.400 --> 01:16:47.620 Ich habe eine schöne, ausgeglichene Fahrtlänge. 01:16:48.120 --> 01:16:50.640 Das heißt, das ist eine sehr schöne Suchstruktur, ist also eine sehr 01:16:50.640 --> 01:16:55.820 effiziente Suchstruktur, die man in solchen größeren Datenmengen sehr 01:16:55.820 --> 01:16:56.720 schön einsetzen kann. 01:16:56.720 --> 01:16:59.720 Und damit bin ich am Ende dieses Abschnitts. 01:17:02.120 --> 01:17:04.820 Und ich hatte es gar nicht gedacht, dass ich heute tatsächlich so 01:17:04.820 --> 01:17:05.680 schnell hier durchkomme. 01:17:06.440 --> 01:17:07.600 Deswegen bin ich für heute fertig. 01:17:08.120 --> 01:17:12.320 Das Nächste ist, wäre ich bin, also ich habe jetzt ein Zeichen, kein 01:17:12.320 --> 01:17:12.800 weiteres Problem mehr. 01:17:12.840 --> 01:17:16.400 Das Nächste, was noch kommt, also im nächsten Kapitel, das wären dann, 01:17:16.640 --> 01:17:18.460 wenn ich mich richtig erinnere, die Graph-Algorithmen. 01:17:19.180 --> 01:17:23.520 Und danach kommt dann die algorithmische Geometrie bzw. 01:17:24.040 --> 01:17:27.180 ich habe noch ein Kapitel da drin, das sind verteilte Algorithmen. 01:17:27.940 --> 01:17:28.660 Die kommen auch noch. 01:17:29.620 --> 01:17:32.220 Und das machen wir dann in der nächsten Woche. 01:17:32.520 --> 01:17:34.620 Für heute können wir dann vor Schluss machen. 01:17:34.720 --> 01:17:36.380 Oder Sie dürfen gerne noch Fragen stellen, wenn Sie irgendwelche 01:17:36.380 --> 01:17:36.980 Fragen haben. 01:17:38.860 --> 01:17:40.740 Keine Fragen, dann war es das für heute. 01:17:40.900 --> 01:17:41.220 Vielen Dank.