WEBVTT 00:02.290 --> 00:05.630 Schönen guten Tag, ich begrüße Sie zu einer weiteren Fortsetzung der 00:05.630 --> 00:07.130 Vorlesung Effiziente Algorithmen. 00:07.830 --> 00:10.750 Zum Glück haben wir die letzten Tage Feiertage gehabt und mussten hier 00:10.750 --> 00:16.050 nicht die heißesten Tage im Hörsaal verbringen, obwohl mir das hier 00:16.050 --> 00:17.050 jetzt genauso vorkommt. 00:17.950 --> 00:22.610 Wahrscheinlich bin ich zu schnell die Treppe rauf gelaufen, aber es 00:22.610 --> 00:25.390 ist schon ein sehr heißer Tag. 00:25.470 --> 00:30.310 Ich mache jetzt eine heiße Vorlesung, also hoffen wir mal, oder was 00:30.310 --> 00:30.510 immer. 00:31.050 --> 00:37.030 Also, Vorlesung geht über unsere Sortierverfahren heute nochmal. 00:37.590 --> 00:39.970 Gar nicht mehr, heute sind wir damit eigentlich durch. 00:40.110 --> 00:43.730 Wir hatten eine wesentliche Sache kennengelernt, das 01-Prinzip, 00:43.890 --> 00:47.410 hatten das parallelen Algorithmen fürs Sortieren, wir hatten das 00:47.410 --> 00:51.990 angewandt hier bei dem odd even merge sort, beim betonischen 00:51.990 --> 00:54.670 Sortieren, hatten gesehen, wie schön man damit Beweise führen kann. 00:55.250 --> 00:58.010 Wir hatten dann das zweidimensionale Sortieren angeschaut, ich habe 00:58.010 --> 01:02.030 Ihnen das Verfahren LSO3-Sort vorgeführt, wir haben auch da gesehen, 01:02.150 --> 01:07.210 wie man dort die Korrektheit mit dem 01-Prinzip nachweisen kann, Sie 01:07.210 --> 01:09.070 dürfen sich damit auch in den Übungen rumschlagen. 01:10.570 --> 01:14.850 Und dann hatten wir nochmal eine untere Schranke uns betrachtet, ich 01:14.850 --> 01:18.610 hatte Ihnen das Prinzip der Joker-Zone vorgeführt, eine Möglichkeit, 01:18.850 --> 01:22.690 wie man also einfach schlechte Fälle konstruieren kann in solchen 01:22.690 --> 01:27.150 Situationen, geht also sehr generell, kann man generell einsetzen, 01:27.310 --> 01:29.470 kann man Ideen kriegen dafür, wie man überhaupt schlechte Fälle 01:29.470 --> 01:31.970 konstruiert, wenn man sowas machen möchte. 01:32.850 --> 01:36.470 Und dann haben wir uns nochmal kurz mit der unteren Schranke 01:36.470 --> 01:41.370 beschäftigt für das Sortieren generell, das kam auch noch irgendwann, 01:41.650 --> 01:44.510 wir hatten das Sortieren auf dem Mesh of Trees betrachtet, genau, wir 01:44.510 --> 01:49.210 hatten, das war hier die Folie zu der Anzahl Vergleiche beim Sortieren 01:49.210 --> 01:52.390 generell, da hatte ich nochmal darauf hingewiesen, dass wir eben da 01:52.390 --> 01:56.370 durch die Endfakultät verschiedene Permutationen der Folge als 01:56.370 --> 02:00.330 sortierte Folge bekommen können, je nachdem, welche Eingabe wir 02:00.330 --> 02:04.650 kriegen, ist es im Prinzip ein Baum mit Endfakultätblättern, der halt, 02:05.330 --> 02:09.130 wenn man da eine untere Schranke für den schlechtesten Fall machen 02:09.130 --> 02:11.950 möchte oder auch eine untere Schranke für den mittleren Fall, bekommt 02:11.950 --> 02:16.610 man eben so einen ausgeglichenen Baum, der dann eine Fahrtlänge hat 02:16.610 --> 02:20.310 von etwa Log Endfakultät, was man abschätzen kann durch Endlog End. 02:21.010 --> 02:23.610 Dann hat man das spezielle Sortierverfahren angeschaut, gesehen, dass 02:23.610 --> 02:26.970 man speziell auch ohne jeden Vergleich arbeiten kann, wenn man weiß, 02:27.070 --> 02:30.590 welche Elemente zu sortieren sind und wenn das eben relativ wenige 02:30.590 --> 02:34.770 Elemente sind, was durchaus in der Praxis häufiger mal vorkommen kann. 02:35.210 --> 02:39.810 Das Ganze kann auch in Richtung Radixort gehen, wenn man also 02:39.810 --> 02:46.870 stückweise jeweils einzelne Stellen sortiert und dann kamen wir zu dem 02:46.870 --> 02:49.190 neuen Abschnitt über Selektionsverfahren. 02:49.370 --> 02:53.290 Ich habe Ihnen kurz gesagt, wie man hier das so und so vierte Element 02:53.290 --> 02:59.730 in einer Folge herausfinden wollen und dann kommt hier die erste neue 02:59.730 --> 03:00.370 Folie. 03:00.670 --> 03:03.870 Das ist diese, wo wir uns einfach mal angucken, wie man jetzt einfach 03:03.870 --> 03:05.210 selektieren könnte. 03:05.450 --> 03:08.290 Wir wollen also irgendein Element haben, das K-größte Element. 03:09.610 --> 03:11.970 Das Einfachste wäre halt natürlich, dass ich zunächst mal das 03:11.970 --> 03:17.110 kleinste, also wenn das K kleiner gleich N halb N ist, dann besuche 03:17.110 --> 03:20.670 ich erst mal das größte, dann das zweitgrößte, das drittgrößte und so 03:20.670 --> 03:20.910 weiter. 03:21.130 --> 03:27.010 Das heißt, ich nehme immer gerade das, hier müsste eigentlich stehen, 03:28.250 --> 03:32.870 1S bis K-1S natürlich. 03:33.070 --> 03:36.230 Also immer gerade diejenigen, die ich rausgenommen habe, die nehme ich 03:36.230 --> 03:37.430 jeweils raus. 03:37.550 --> 03:40.850 Dann habe ich erst das größte, zweitgrößte, drittgrößte und so weiter 03:40.850 --> 03:42.650 bis zu dem K-größten gekommen bin. 03:44.410 --> 03:48.490 Oder wenn ich eben einen Wert habe, der größer als N halber ist, dann 03:48.490 --> 03:50.970 würde ich immer das Minimum bestimmen und hätte auf die Art und Weise 03:50.970 --> 03:54.990 N halber mal im schlechtesten Fall einen linearen Aufwand. 03:55.050 --> 03:56.970 Was aber ein quadratischer Aufwand ist, ist natürlich schlecht. 03:57.290 --> 03:58.310 Wir wissen, dass es besser geht. 03:58.550 --> 04:01.970 Wenn ich nur das Fünfgrößte haben möchte, mag das ein guter Ansatz 04:01.970 --> 04:06.030 sein, weil ich dann fünfmal N haben habe im Prinzip. 04:07.150 --> 04:10.430 Und wenn ich es eben allgemeiner haben möchte, wenn ich also in die 04:10.430 --> 04:14.330 Gegend des, also das, was hier Aufwand N² ist, ist klar. 04:14.730 --> 04:22.230 Wenn ich in die Gegend kommen möchte oder komme, wo das K-linear ist 04:22.230 --> 04:28.230 schon in der Länge der Folge, also keine Konstante mehr, dann ist eine 04:28.230 --> 04:30.750 Verbesserung zu sagen, ich sortiere zunächst mal, dann habe ich 04:30.750 --> 04:35.050 Aufwand N log N und dann nehme ich dort das entsprechende Element an 04:35.050 --> 04:36.990 der Kartenposition raus und ich bin fertig. 04:37.470 --> 04:41.210 Das heißt, der Aufwand ist N log N im schlechtesten Fall. 04:41.290 --> 04:43.850 Das können wir immer erreichen, dass wir nie schlechter als N log N 04:43.850 --> 04:44.190 werden. 04:44.810 --> 04:47.810 Wenn das keine Konstante ist, im Berlinianen Fall, wenn das keine 04:47.810 --> 04:52.730 Konstante mehr ist, dann geht es auf jeden Fall mit N log N und damit 04:52.730 --> 04:55.210 haben wir also das eigentlich gelöst. 04:55.430 --> 04:58.210 Aber selektieren ist ja eigentlich einfacher als sortieren. 04:58.330 --> 05:01.050 Warum soll ich alle Rangpositionen bestimmen, wenn ich nur eine 05:01.050 --> 05:02.290 Rangposition haben möchte? 05:02.930 --> 05:05.850 Dann ist eben die Frage, kann ich das auch besser machen als mit N log 05:05.850 --> 05:06.090 N. 05:08.090 --> 05:14.030 Und dazu schauen wir uns einfach mal verschiedene Ansätze an und ein 05:14.030 --> 05:16.670 Ansatz, den wir von vorher schon kannten, war das Quick Sort. 05:16.970 --> 05:19.290 Das machen wir jetzt einfach nicht Quick Sort, sondern Quick Select. 05:19.810 --> 05:22.570 Im Prinzip genau die Idee, die wir vorher hatten bei Quick Sort, 05:22.990 --> 05:26.390 verwenden wir, um ein Selektionsverfahren zu machen. 05:27.390 --> 05:29.230 Was heißt das also, was machen wir? 05:29.970 --> 05:34.730 Wir haben, ich habe das hier auch wieder aufgemalt, wir haben unsere 05:34.730 --> 05:40.290 Folge S, wir wählen ein beliebiges Element, OBDA, das Pivot-Element, 05:40.430 --> 05:44.050 das erste Element, zerteilen die Folge, wie vorher auch, in zwei 05:44.050 --> 05:46.410 Teilfolgen, das sind hier die beiden Teilfolgen. 05:46.790 --> 05:49.570 Auf der einen Seite haben wir hier alle, die größer gleich sind als 05:49.570 --> 05:52.410 dieses Pivot-Element und da rechts daneben alle, die kleiner sind. 05:52.410 --> 05:53.990 Jetzt muss man sehen, was muss ich denn machen? 05:54.050 --> 05:55.570 Ich will das K-größte Element haben. 05:56.490 --> 05:58.050 Wo ist das K-größte Element? 05:58.990 --> 06:01.550 Ich muss mir nur anschauen, in welcher Position ist das C? 06:02.510 --> 06:07.030 Alle, die größer sind, größer gleich sind, sind links davon, also in 06:07.030 --> 06:07.990 der Folge S'. 06:08.550 --> 06:11.730 Alle, die kleiner sind, sind in der Folge S2'. 06:11.730 --> 06:17.950 Wenn jetzt diese Folge, also wenn dieses S' hier genau gleich K ist, 06:19.050 --> 06:22.030 wenn ich also genau K-Elemente dort habe, dann heißt das, ich habe mit 06:22.030 --> 06:23.590 dem C genau das K-größte Element. 06:24.250 --> 06:32.610 Dann ist dieses C hier gerade das K-größte Element, weil ich ja hier 06:32.610 --> 06:34.150 genau K-Elemente drin habe. 06:34.790 --> 06:38.050 Also dieses hier sind genau K-Elemente, also ist das hier, das sind 06:38.050 --> 06:41.810 alle großen, da sind die kleineren als C, ist das hier das K-größte 06:41.810 --> 06:42.110 Element. 06:42.250 --> 06:42.670 Fertig. 06:43.430 --> 06:45.410 Eine Partitionierung reicht in dem Fall aus. 06:45.770 --> 06:47.970 Nun wäre das ein Glücksfall, dass wir genau dorthin kommen. 06:48.430 --> 06:49.730 Da gibt es natürlich die anderen Fälle. 06:50.710 --> 06:55.870 Wenn das S' mehr als K-Elemente enthält, dann kann ich im Prinzip das 06:55.870 --> 07:01.270 S2' vergessen, weil ich ja weiß, das K-größte Element liegt auf jeden 07:01.270 --> 07:02.150 Fall in S'. 07:03.930 --> 07:09.770 Also dann brauche ich nur S'-C erstmal rauszunehmen, das C ist ja hier 07:09.770 --> 07:10.290 mein Element. 07:10.290 --> 07:13.570 Wir hatten immer angenommen, dass C ist, oder alle Elemente sind 07:13.570 --> 07:14.630 verschieden. 07:14.970 --> 07:17.350 Jetzt nehmen wir mal an, es könnte ja auch sein, dass da mehrere 07:17.350 --> 07:19.530 gleiche Elemente sind, das hatten wir bei den Selektionen immer 07:19.530 --> 07:20.750 gemacht, bei den Beispielen. 07:20.810 --> 07:25.070 Also nehmen wir mal an, das C könnte öfter auftreten. 07:25.550 --> 07:29.050 Dann ziehe ich einfach das Element C aus dieser Menge ab. 07:30.070 --> 07:38.090 Das heißt, wenn also jetzt dieses S', mehr als K-Elemente drin, jetzt 07:38.090 --> 07:45.450 nehme ich ein Element C raus, wenn dadurch die Restmenge weniger als K 07:45.450 --> 07:50.450 -Elemente enthält, heißt das, das C kam nochmal vor, in der Restmenge, 07:50.490 --> 07:54.730 hier waren also noch ein paar mehr C's, die Restmenge, das ist also 07:54.730 --> 08:02.110 jetzt hier mein S3', in dem Fall, hat weniger als K-Elemente, also ist 08:02.110 --> 08:05.190 das C immer noch mein K-größtes Element. 08:07.430 --> 08:10.690 Denn ich habe zwar jetzt nicht die Position, an der das ist unbedingt, 08:10.950 --> 08:15.970 aber ich weiß, das C ist das K-größte Element, weil weniger als K 08:15.970 --> 08:29.570 -Elemente größer sind, und es waren hier vorher eben weniger als N-K 08:29.570 --> 08:32.510 -Elemente tatsächlich kleiner als das C. 08:33.190 --> 08:42.090 Und wenn das S3' immer noch größer gleich K ist, das wäre der andere 08:42.090 --> 08:46.490 Fall, dass ich also hier, ich habe das C rausgenommen, das ist immer 08:46.490 --> 08:52.270 noch mehr als oder mindestens K-Elemente drin, dann wende ich 08:52.270 --> 08:55.250 QuickSelect auf dieses S3' an. 08:56.330 --> 08:59.010 So, dann bin ich ja noch nicht fertig. 08:59.450 --> 09:02.050 Das heißt, das S2' brauche ich dann nicht zu betrachten. 09:02.050 --> 09:06.330 Der andere Fall ist, dass ich hier in dem S' weniger als K-Elemente 09:06.330 --> 09:06.610 habe. 09:07.250 --> 09:11.390 Wenn dort weniger als K-Elemente sind, dann muss das K-größte Element 09:11.390 --> 09:12.850 irgendwo in diesem Bereich sein. 09:13.730 --> 09:14.650 In S2'. 09:14.650 --> 09:19.030 Aber wenn ich jetzt in S2' suche, dann kann ich ja nicht nach dem K 09:19.030 --> 09:22.010 -größten Element suchen, sondern dann muss ich natürlich gucken, in 09:22.010 --> 09:26.850 der Restmenge hier, muss ich entsprechend diese Elemente von S' ja 09:26.850 --> 09:28.830 abziehen, da sind alle, die größer sind. 09:29.690 --> 09:35.050 Und das heißt, ich muss von dem K die Anzahl der Elemente in, oder die 09:35.050 --> 09:38.070 Größe von S' abziehen. 09:38.510 --> 09:46.170 Das heißt, ich suche in S2', das in dieser Menge, nach dem K-Betrag 09:46.170 --> 09:48.470 von S' Element. 09:50.010 --> 09:53.730 Aber auf jeden Fall habe ich eben eine wichtige Erkenntnis gewonnen, 09:54.750 --> 10:00.270 meine Anzahl der Vergleiche, die ich machen muss, um das K-größte 10:00.270 --> 10:09.810 Element zu finden, die ist das Maximum von diesem Wert hier. 10:09.810 --> 10:17.970 Das habe ich da, genau, das ist also QuickSelect von K-Elementen. 10:19.410 --> 10:23.850 QuickSelect, das K-größte Element bei N-Elementen, ist definiert als 10:23.850 --> 10:27.810 die Anzahl der Vergleiche von QuickSelect auf Listende Länge N. 10:29.490 --> 10:36.130 Und dieses QuickSelect-Stern definiere ich als das Maximum über alle 10:36.130 --> 10:41.070 möglichen Folgenlängen, die ich habe, K aus N, es kann ja jede 10:41.070 --> 10:44.850 beliebige Folgenlänge dort auftauchen, von 1 bis N. 10:45.970 --> 10:49.490 Aber ich brauche eben nur, die jeweils einmal anzuschauen. 10:50.090 --> 10:55.350 Bei QuickSort hatten wir zweimal, in zwei Folgen nachzuschauen. 10:55.450 --> 10:59.570 Da war es immer die Summe von den Vergleichen in jeweils den beiden 10:59.570 --> 11:00.230 Teilfolgen. 11:01.390 --> 11:07.890 Das heißt aber auch, im schlechtesten Fall habe ich natürlich jeweils 11:07.890 --> 11:10.990 in einer Folge nachzuschauen, die nur um 1 kleiner ist, als das, was 11:10.990 --> 11:11.970 ich bisher gehabt habe. 11:12.270 --> 11:15.370 Der schlechteste Fall von QuickSelect ist der gleiche wie bei 11:15.370 --> 11:16.010 QuickSort. 11:17.030 --> 11:22.150 Es kann sein, dass ich eben wirklich hier im quadratischen Bereich 11:22.150 --> 11:22.710 lande. 11:23.310 --> 11:26.250 Also wenn ich dieses N-halbte Element haben will und ich gehe 11:26.250 --> 11:30.250 sukzessive immer nur um 1 weiter runter, dann habe ich halt genau 11:30.250 --> 11:32.450 dieses N-Quadrat als schlechtesten Fall. 11:33.430 --> 11:37.590 Das mittlere Verhalten ist hier aber linear. 11:38.990 --> 11:44.890 Denn, das kann man zeigen, das können Sie in den Übungen gerne machen, 11:45.190 --> 11:50.410 bester Fall sowieso linear, bester Fall, da hätte ich ja im besten 11:50.410 --> 11:57.410 Fall, wäre das gerade, oder bester Fall wäre sogar noch besser, bester 11:57.410 --> 12:00.250 Fall wäre, dass ich hier in einem Schritt schon fertig bin. 12:01.890 --> 12:05.370 Ein Schritt heißt aber, ich muss einmal durchgehen, also auch linear. 12:06.050 --> 12:08.150 Ich habe nur einmal die Partitionierung zu machen. 12:08.150 --> 12:23.490 Und wenn ich diese Aufteilung mache, die Zeit von QuickSelect auf 12:23.490 --> 12:28.250 Folgen der Länge N, ist ja dann im besten Fall, oder ein guter Fall 12:28.250 --> 12:32.370 auf jeden Fall, wenn ich hier eine Folgenlänge der Größe N halber 12:32.370 --> 12:38.230 habe, plus O von N, das ist insgesamt immer noch ein O von N. 12:41.590 --> 12:45.870 Bei QuickSort hatten wir hier zweimal TQS von N halber, im besten 12:45.870 --> 12:49.570 Fall, die haben wir nur einmal, und reduzieren aber auf die halbe 12:49.570 --> 12:52.970 Folgengröße, und damit haben wir im besten Fall auf jeden Fall 12:52.970 --> 12:54.010 lineares Verhalten. 12:54.550 --> 12:58.250 Man kann eben zeigen, dass das mittlere Verhalten auch in O von N 12:58.250 --> 12:59.510 liegt, auch linear ist. 12:59.510 --> 13:04.290 Deswegen ist QuickSelect ein ganz einfacher Ansatz, um so mit 13:04.290 --> 13:09.990 Erwartungswert lineare Zeit den Median zu bestimmen, zum Beispiel, 13:10.170 --> 13:12.910 oder ein beliebiges Rangelement in der Folge. 13:13.630 --> 13:17.370 Also das ist schon mal ein Fortschritt, dass wir zumindest im 13:17.370 --> 13:21.630 mittleren Fall auf linear runterkriegen können. 13:21.630 --> 13:29.890 Und jetzt zeige ich als nächstes, dass wir das sogar im schlechtesten 13:29.890 --> 13:32.710 Fall in linearer Zeit hinbekommen können. 13:33.650 --> 13:37.730 Da muss man sich angucken, woran liegt es, dass wir bei QuickSort und 13:37.730 --> 13:42.450 bei QuickSelect im schlechtesten Fall quadratische Zeit brauchen. 13:43.690 --> 13:49.930 Das liegt daran, dass wir jedes Mal, wenn das unsere Folge ist, in der 13:49.930 --> 13:54.450 wir suchen, der schlechteste Fall sieht so aus, dass wir eben hier ein 13:54.450 --> 13:58.950 Element rausgenommen haben, ein Pivot-Element, und das transformieren, 13:59.170 --> 14:02.090 und es kommt im Prinzip genau wieder so etwas raus. 14:02.730 --> 14:06.950 Wir müssen hier weitersuchen in dieser Folge S2'. 14:07.630 --> 14:10.630 Wir haben nur ein Element rausgenommen, das war der schlechteste Fall. 14:11.730 --> 14:16.970 Wenn ich erreichen könnte, dass ich jedes Mal, wenn ich partitioniere, 14:16.970 --> 14:24.470 hier nicht ganz vorne lande, sondern wenn ich erreichen könnte, dass 14:24.470 --> 14:32.570 ich hier ein Teil abschneiden kann, der in Omega von N liegt, also 14:32.570 --> 14:38.170 einen Bruchteil von N abziehen kann, einen festen Anteil abziehen 14:38.170 --> 14:41.750 kann, dann habe ich jedes Mal eine deutliche Reduktion. 14:42.950 --> 14:45.610 Und dann habe ich so etwas Ähnliches, wie ich gerade auf der vorigen 14:45.610 --> 14:52.330 Seite gezeigt habe, dafür den besten Fall, da war es ein Halbe, aber 14:52.330 --> 14:54.730 ich muss ja immer nur diese eine Folge weiter anschauen. 14:55.370 --> 14:59.030 Und wenn ich die jeweils um einen festen Bruchteil runterkriege und 14:59.030 --> 15:03.290 nicht nur konstant viele Elemente abziehe, dann habe ich eine Chance, 15:03.410 --> 15:04.610 dass das Ganze linear wird. 15:05.410 --> 15:08.750 Und das ist die ganze Idee bei dem Verfahren für Selektion in linearer 15:08.750 --> 15:10.070 Zeit, was ich Ihnen jetzt zeige. 15:10.990 --> 15:14.650 Wir wollen einfach erreichen, dass wir den schlechtesten Fall 15:14.650 --> 15:19.770 vermeiden können, von Quick Select. 15:21.550 --> 15:26.750 Im Prinzip zeige ich Ihnen nochmal Quick Select, aber jetzt so, dass 15:26.750 --> 15:33.910 wir immer einen festen, oder mindestens einen guten Bruchteil von N 15:33.910 --> 15:34.770 abziehen. 15:36.210 --> 15:40.410 Das ist nicht die halbe Menge der Elemente, aber etwas, Sie werden 15:40.410 --> 15:43.370 sehen, das ist also fast ein Viertel, wie wir hier schon angedeutet 15:43.370 --> 15:43.730 bekommen. 15:43.810 --> 15:45.650 Wie ist die Idee von dem Verfahren? 15:46.250 --> 15:50.290 Wir nehmen also an, wir haben N Elemente in der Folge, und wenn die 15:50.290 --> 15:52.010 Folge nicht zu lang ist, machen wir das direkt. 15:53.090 --> 15:55.970 Dann können wir irgendwie das grad größte Element bestimmen. 15:57.670 --> 16:04.010 Und jetzt suchen wir das grad größte Element und fangen einfach mal 16:04.010 --> 16:09.210 an, dass wir unsere Folge aufteilen in Teillisten mit jeweils fünf 16:09.210 --> 16:10.350 Elementen. 16:10.970 --> 16:12.410 Die sind hier angedeutet. 16:13.430 --> 16:17.290 Jeweils so angedeutet, und ich nehme mal an, dass ich hier die jeweils 16:17.290 --> 16:22.330 so angeordnet habe, für dieses Bild, dass dort kleine Elemente oben 16:22.330 --> 16:23.410 sind, große Elemente unten. 16:23.550 --> 16:26.790 Ich nehme mal an, die werden sortiert, aufsteigend sortiert, was in 16:26.790 --> 16:29.050 der Realität gar nicht sein muss, auch bei dem Verfahren ist es nicht 16:29.050 --> 16:29.770 erforderlich. 16:29.770 --> 16:32.690 Aber für die Abschätzung nachher, was wir wirklich rausschmeißen 16:32.690 --> 16:33.930 können, ist das wichtig. 16:35.430 --> 16:37.110 Also wir nehmen mal an, die sind so angeordnet. 16:37.390 --> 16:43.630 In jeder dieser Teilfolgen, fünf Elemente, ich habe natürlich N 16:43.630 --> 16:49.030 Fünftel solche Teilfolgen, bestimme ich jeweils den Median. 16:50.850 --> 16:55.650 Das ist der Median der ersten Folge, dann habe ich hier den Median der 16:55.650 --> 16:56.990 zweiten Folge und so weiter. 16:56.990 --> 16:59.450 Und jetzt nehme ich einfach mal an, dass ich die angeordnet habe, 17:00.350 --> 17:06.090 sodass der größte dieser Mediane ganz links steht, und der kleinste 17:06.090 --> 17:06.590 ganz rechts. 17:06.690 --> 17:08.750 Also wir seien einfach mal sortiert hier angeordnet. 17:09.910 --> 17:14.290 Also nur etwas, was ich jetzt für die Abschätzung brauche, um 17:14.290 --> 17:18.370 festzustellen, wie viel kann ich nachher rauswerfen. 17:19.790 --> 17:23.310 Und diese Mediane zu bestimmen, das ist ja nicht viel Aufwand. 17:23.310 --> 17:27.070 In einer Folge von fünf Elementen, das mittlere Element zu bestimmen, 17:27.490 --> 17:29.410 das ist eine konstante Anzahl von Vergleichen. 17:29.810 --> 17:31.910 Egal, wie schlecht Sie das machen, auf jeden Fall eine konstante 17:31.910 --> 17:35.970 Anzahl von Vergleichen, oder wie gut Sie das machen, das ist etwas, 17:36.090 --> 17:38.610 was ich in kurzer Zeit hinbekomme. 17:38.990 --> 17:42.330 Unabhängig von der Größe meiner Folge, die ich machen muss. 17:43.310 --> 17:46.810 Natürlich muss ich das für jede Folge machen, aber für jede einzelne 17:46.810 --> 17:48.150 Folge ist der Aufwand klein. 17:49.070 --> 17:52.750 Und jetzt schaue ich mir diese hier alle an. 17:54.330 --> 18:01.270 Und ich bestimme den Median dieser Mediane der Teilfolge. 18:02.490 --> 18:05.250 Und mache das einfach durch einen Aufruf von Select. 18:05.850 --> 18:09.890 Und jetzt nicht Select K, nicht das K-größte Element bestimmen, 18:09.950 --> 18:13.470 sondern ich möchte den Median dieser N-fünftel Elemente haben. 18:14.390 --> 18:20.770 Das ist ein Aufruf auf einer relativ kleinen Teilfolge, das sind nur N 18:20.770 --> 18:22.630 -fünftel Elemente. 18:23.490 --> 18:24.950 Vorher hatte ich N-Elemente. 18:27.530 --> 18:30.530 Das kann ich also hier machen, rekursiv. 18:31.010 --> 18:32.730 Dann bekomme ich irgendeinen Median raus. 18:32.810 --> 18:36.810 Und ich nehme mal an, der Median steht hier halt gerade in der Mitte. 18:38.030 --> 18:38.770 Das wäre der. 18:41.290 --> 18:45.690 Ja, das ist dieses Element M in Zehntel. 18:48.550 --> 18:54.490 So, und jetzt schaue ich mir an, das mache ich im Prinzip einfach nur 18:54.490 --> 18:55.450 Quick Select. 18:57.050 --> 18:59.030 Ich habe jetzt ein Pivot-Element gefunden. 18:59.170 --> 19:00.430 Das ist der ganze Witz dahinter. 19:00.830 --> 19:02.470 Ich habe ein Pivot-Element gefunden. 19:03.190 --> 19:05.370 Das ist dieser Median der Mediane. 19:06.110 --> 19:10.870 Jetzt schaue ich mir an, das, was ich haben wollte, war ja, wie groß 19:10.870 --> 19:14.910 sind diese beiden Teilmengen hier, S-strich und S2-strich. 19:15.790 --> 19:18.910 Ich habe jetzt hier diesen Median, der Median, das ist jetzt mein M. 19:22.810 --> 19:29.110 So, genau wie vorher, S-strich ist die Menge aller Elemente, die 19:29.110 --> 19:36.350 größer gleich M sind, S2-strich die Menge aller Elemente, die kleiner 19:36.350 --> 19:37.090 als M sind. 19:37.750 --> 19:38.790 Genau Quick Select. 19:40.250 --> 19:43.610 Und jetzt schaue ich mir an, das andere ist auch das gleiche, falls S 19:43.610 --> 19:45.910 -strich gleich K ist, so ist M gleich K von S. 19:46.410 --> 19:49.970 Falls S-strich größer als K ist, führe ich Select S-strich K aus. 19:50.990 --> 19:54.410 Andernfalls nehme ich also hier Select S2-strich K-S-strich. 19:56.250 --> 19:58.990 Ich habe jetzt hier diesen Fall, dass ich da gleiche Elemente drin 19:58.990 --> 20:01.350 habe, habe ich jetzt hier rausgelassen, das könnte man auch noch mit 20:01.350 --> 20:01.810 einbauen. 20:02.370 --> 20:03.590 Das ist jetzt irrelevant. 20:07.370 --> 20:09.490 So, das ist also einfach Quick Select. 20:10.070 --> 20:13.520 Jetzt schaue ich mir an, wie groß sind denn diese Restmengen? 20:13.890 --> 20:18.630 Wenn ich hier auf S-strich das K-größte Element suche, oder auf S2 20:18.630 --> 20:25.090 -strich das K-Anzahl Elemente von S-strich größte, wie groß sind diese 20:25.090 --> 20:26.370 Teilfolgen, die übrig bleiben? 20:28.170 --> 20:33.430 Also, wenn ich alle anschaue, die kleiner gleich diesem M sind. 20:35.590 --> 20:37.510 Kleiner gleich als das Element. 20:37.670 --> 20:43.110 Das sind doch alle hier, diese ganzen, das wäre also diese Folge S2 20:43.110 --> 20:44.990 -strich, oder kleiner als M. 20:45.490 --> 20:49.930 Diese Mediane auf der rechten Seite hier, sind alle kleiner als der 20:49.930 --> 20:50.950 Median der Mediane. 20:52.410 --> 20:59.410 Die Elemente hier oben drüber, sind alle jeweils kleiner als der 20:59.410 --> 21:01.490 Median der jeweiligen Teilfolgen. 21:01.490 --> 21:04.950 Das heißt, das, was ich jetzt hier eingerahmt habe, Menge B, 21:08.980 --> 21:11.740 das ist eine... 21:11.740 --> 21:13.420 Ich muss jetzt andersherum argumentieren. 21:14.860 --> 21:17.880 S2-strich sind alle Elemente, die kleiner als M sind. 21:18.460 --> 21:20.140 Welche sind also alle nicht da drin? 21:21.320 --> 21:25.100 Nicht da drin sind alle die, Entschuldigung, oder das, was ich hier 21:25.100 --> 21:28.700 gesagt habe, ich kann auch hier mit dem B weitermachen, in dem B waren 21:28.700 --> 21:35.180 jetzt alle drin, die sind kleiner als M, das sind mindestens diese 21:35.180 --> 21:38.940 Elemente, das ist mindestens so etwa, sieht so aus wie etwa ein 21:38.940 --> 21:39.960 Viertel der Elemente. 21:41.380 --> 21:43.140 Das heißt, in dem S-strich 21:46.220 --> 21:51.920 sind maximal so viele Elemente, also diese Menge, also maximal die 21:51.920 --> 21:54.560 Elemente drin, die nicht in B liegen. 21:55.480 --> 21:58.000 Es könnten alle drin sein, die nicht in B sind. 21:59.100 --> 22:02.700 Das sind aber nur drei Viertel der Folge, im schlechtesten Fall. 22:02.700 --> 22:07.900 Und symmetrisch dazu der andere Fall, wie viele Elemente sind maximal 22:07.900 --> 22:09.840 in S2-strich drin? 22:10.880 --> 22:16.960 Es sind alle nicht drin, die größer gleich M sind, und größer gleich M 22:16.960 --> 22:23.040 sind diese Mediane, und alle Elemente, die größer gleich diesen 22:23.040 --> 22:24.160 Medianen jeweils sind. 22:25.240 --> 22:28.720 Das heißt, die sind auch nicht in S2-strich drin. 22:29.520 --> 22:34.680 Damit habe ich also etwa gleiche Abschätzung. 22:34.800 --> 22:41.160 Ich kann sagen, sowohl bei S2-strich als auch bei S-strich weiß ich, 22:41.540 --> 22:47.700 ich habe einen festen Bruchteil der Folgenlänge rausschmeißen können. 22:47.940 --> 22:52.660 Mein Pivot-Element ist so bestimmt worden, dass ich hier einen 22:52.660 --> 22:54.120 günstigen Fall bekomme. 22:55.200 --> 23:03.500 Das heißt, man kann erwarten, da ich jeweils die Folge richtig kleiner 23:03.500 --> 23:10.220 mache, habe ich vermutlich ein lineares Laufzeitverhalten, was man 23:10.220 --> 23:11.400 tatsächlich auch zeigen kann. 23:11.820 --> 23:13.160 Da kommen wir gleich noch genauer drauf. 23:14.160 --> 23:20.640 Also das ist hier dieses Verfahren im Prinzip, die ganze Idee ist, ich 23:20.640 --> 23:24.880 vermeide die schlechten Fälle von Quickselect, durch garantierte 23:24.880 --> 23:28.180 Reduktion der zu bearbeitenden Restliste, um einen festen Bruchteil 23:28.180 --> 23:28.580 von N. 23:29.880 --> 23:32.080 Das ist der wesentliche Schritt. 23:32.520 --> 23:34.260 Muss natürlich gucken, was kostet mich das. 23:35.320 --> 23:40.120 Ich muss ja jetzt diese Mediane der kleinen Teilfolgen bestimmen, und 23:40.120 --> 23:43.200 ich muss den Median der Mediane bestimmen. 23:44.700 --> 23:45.860 Da muss ich natürlich aufpassen. 23:47.480 --> 23:52.840 Wenn ich jetzt in den Bereich komme, wie wir das vorher bei Quicksort 23:52.840 --> 23:59.140 hatten, dass wir in zwei Folgen rekursiv etwas machen müssen, und das 23:59.140 --> 24:04.080 ist insgesamt gleiche Größe wie vorher, dann haben wir genau dieses 2 24:04.080 --> 24:08.260 mal T von N durch 2 oder was ähnliches. 24:09.140 --> 24:11.820 Dann kommen wir wieder in den Bereich N log N, das wollten wir ja 24:11.820 --> 24:12.040 nicht. 24:12.780 --> 24:16.120 Also wir müssen dafür sorgen, dass das, was wir als rekursiven Aufwand 24:16.120 --> 24:20.680 haben, wirklich auf einer kürzeren Folge passiert, dass wir wirklich 24:20.680 --> 24:23.220 einen festen Bruchteil abschneiden können. 24:24.480 --> 24:28.180 Insgesamt, auch wenn wir diesen rekursiven Aufruf zur Bestimmung des 24:28.180 --> 24:29.400 Medians drin haben. 24:30.040 --> 24:32.040 Das habe ich Ihnen gerade alles erklärt hier. 24:32.300 --> 24:37.140 Also das A-geschnittene S2-strich ist garantiert leer, und B 24:37.140 --> 24:38.800 -geschnittene S-strich ist auch leer. 24:39.580 --> 24:43.880 Das kann jeweils sagen, diese Elemente sind auf keinen Fall in S2 24:43.880 --> 24:44.940 -strich oder S-strich. 24:45.960 --> 24:48.560 Nun schaut man sich an, wie groß sind diese Mengen denn. 24:49.420 --> 24:56.500 Naja, das hier sind jeweils, also in dem A, das sind jeweils drei 24:56.500 --> 24:57.940 Elemente aus jeder Folge. 25:00.520 --> 25:06.620 Das heißt, ich habe hier, das sind N-Zehntel, die dort drin liegen, 25:06.740 --> 25:10.140 also drei Zehntel N, die dort drin liegen. 25:11.700 --> 25:17.080 Ich habe N-Fünftel Teilfolgen, N-Zehntel also in dieser oberen Hälfte. 25:17.080 --> 25:22.340 Das heißt, ich habe hier drei Zehntel N, und bei B gilt das Gleiche. 25:22.920 --> 25:30.080 Drei Zehntel N als Anzahl der Elemente, die in A und in B drin liegen. 25:30.720 --> 25:35.780 Und dann weiß ich, dass in den Folgen S-Strich und S2-Strich maximal 25:35.780 --> 25:42.540 sieben Zehntel N drin liegen können, weil ich mindestens drei Zehntel 25:42.540 --> 25:43.280 N rauswerfe. 25:47.080 --> 25:50.520 Wenn das ein ganzes Vielfaches von zehn ist, ansonsten muss ich da 25:50.520 --> 25:54.060 kleinere Abschätzungen machen. 25:54.300 --> 25:57.080 Ich kann das dann, wenn das kein Vielfaches ist von zehn, kann ich 25:57.080 --> 25:59.800 hier auf drei Elftel gehen, das ist aber Kleinkram. 26:02.040 --> 26:05.420 Dann habe ich aber eben immer noch S-Strich und S2-Strich, dann haben 26:05.420 --> 26:08.420 wir maximal acht Elftel N Elemente drin. 26:09.420 --> 26:10.220 So. 26:12.220 --> 26:23.540 Jetzt ist der Aufruf, dieser Median hat ja N fünftel Elemente, dieser 26:23.540 --> 26:24.360 eine Aufruf. 26:24.460 --> 26:32.200 Hier habe ich eine Folge, die hat maximal acht Elftel N Elemente. 26:33.040 --> 26:37.040 Und das heißt, ich habe insgesamt, auf jeden Fall habe ich hier die 26:37.040 --> 26:40.800 Liste um einen festen Bruchteil kürzer gemacht. 26:40.920 --> 26:45.780 Also was ich erwarte ist, dass ich hier irgend so ein T-Select von A 26:45.780 --> 26:48.020 mal N habe. 26:49.380 --> 26:53.580 Also ein Fünftel N sind ja zwei Zehntel, nochmal kurz zurück, das sind 26:53.580 --> 26:55.460 zwei Zehntel N. 26:56.420 --> 27:00.280 Und sieben Zehntel plus zwei Zehntel wären neun Zehntel. 27:01.020 --> 27:04.740 Das heißt, ich bin unterhalb, ich habe also ein Zehntel N auf jeden 27:04.740 --> 27:08.360 Fall bei der Summe der beiden rekursiven Aufrufe. 27:08.740 --> 27:10.840 Die Folgenlängen sind also insgesamt kleiner. 27:11.580 --> 27:14.720 Das ist so eine intuitive Begründung, warum wir hier lineares 27:14.720 --> 27:15.780 Verhalten erwarten können. 27:16.900 --> 27:20.280 Also im Prinzip sieht das so aus, dass ich hier das T-Select aufrufe, 27:21.100 --> 27:25.260 in zwei parallel laufenden Schritten, auf einer Folgenlänge, die 27:25.260 --> 27:30.700 kleiner als N ist, um einen festen Faktor a kleiner mindestens. 27:31.300 --> 27:34.000 Und dann habe ich noch linearen Aufwand dazu zu treiben. 27:34.520 --> 27:40.220 Der lineare Aufwand dazu, das war die Bestimmung der Mediane dieser 27:40.220 --> 27:41.940 Folgen der Länge 5 jeweils. 27:44.620 --> 27:47.560 Und dann bekomme ich also diese Folge. 27:47.640 --> 27:51.980 Wenn ich das genauer mache, dann habe ich hier, das ist ganz genau 27:51.980 --> 27:57.560 hinzuschreiben, ich habe zunächst mal irgendeinen Aufwand für Folgen 27:57.560 --> 28:04.860 der Größe kleiner als 100. 28:06.400 --> 28:10.160 Dieses Aufteilen in die Teilfolge der Länge 5 ist gar kein Aufwand. 28:10.160 --> 28:13.240 Das sind nur abzählende Elemente. 28:14.120 --> 28:18.080 Dann ist die Frage, wie viele Vergleiche brauche ich, um ein Median 28:18.080 --> 28:20.460 einer Folge von fünf Elementen zu bestimmen. 28:20.860 --> 28:23.080 Sie können das mit neun Vergleichen hinbekommen. 28:25.220 --> 28:31.040 Neun Vergleiche pro Median, neun mal N fünftel, sind kleiner als zwei 28:31.040 --> 28:32.120 N Vergleiche. 28:35.480 --> 28:39.320 Schritt 5, Schritt 4 war der rekursive Aufruf. 28:39.800 --> 28:44.780 Median bestimmen dieser N fünftel Mediane. 28:45.960 --> 28:48.900 Und dann habe ich die Partitionierung zu machen. 28:49.260 --> 28:52.340 Partitionierung ist N plus 1 Schritte, das wissen wir maximal. 28:53.200 --> 28:55.420 Ne, genau N plus 1 Schritte, da haben wir die Partitionierung 28:55.420 --> 28:55.900 hinbekommen. 28:56.520 --> 28:58.940 Das ist der Partitionierungsschritt von Quicksort. 29:01.600 --> 29:04.020 Der sechste Schritt, was war der sechste Schritt? 29:05.320 --> 29:06.400 Mal kurz zurück. 29:08.020 --> 29:12.980 Der sechste Schritt, der sechste Schritt. 29:13.220 --> 29:17.500 Achso, das war einfach nur, wenn ich genau K Elemente habe, dann bin 29:17.500 --> 29:18.060 ich fertig. 29:18.880 --> 29:20.040 Das kostet keine Zeit. 29:20.780 --> 29:27.140 Und der siebte Schritt ist dann wieder rekursiver Aufruf auf einer 29:27.140 --> 29:30.540 Folge, die maximal die Größe 8 N elftel hat. 29:31.360 --> 29:36.340 Und dann bekomme ich insgesamt auf diese Rekursion, jetzt kann ich 29:36.340 --> 29:37.460 versuchen, die aufzulösen. 29:38.220 --> 29:44.860 Wenn man das macht, findet man raus, ich habe insgesamt ein lineares 29:44.860 --> 29:45.300 Verhalten. 29:46.040 --> 29:48.940 Die Konstante, die man dabei rauskriegt, ist relativ groß. 29:49.880 --> 29:51.760 Aber es ist asymptotisch linear. 29:52.800 --> 29:55.600 Also es lohnt sich wirklich nur für sehr große Folgen. 29:56.940 --> 29:59.940 Insbesondere, wenn ich den Median bestimmen will oder etwas, was 29:59.940 --> 30:06.960 Größenordnung, eine Rangposition, die linear in der Folgenlänge ist. 30:07.960 --> 30:12.700 Aber ich habe dann ein Selektionsverfahren, das in linearer Zeit 30:12.700 --> 30:13.020 läuft. 30:13.200 --> 30:16.600 Also ich habe nicht nur den mittleren Fall runterdrücken können, auf 30:16.600 --> 30:20.080 linear wie bei QuickSelect, sondern auch noch die schlechtesten Fälle 30:20.080 --> 30:24.060 und eben einfach dadurch, dass ich die schlechten Fälle im Prinzip 30:24.060 --> 30:29.340 ausschließe, weil ich immer ausreichend viele Elemente rauswerfen 30:29.340 --> 30:29.740 kann. 30:31.240 --> 30:36.020 Große Konstante macht das für die Praxis etwas irrelevant. 30:36.260 --> 30:42.720 Das Interessante ist aber, ich kann diesen Ansatz sehr gut 30:42.720 --> 30:44.060 parallelisieren. 30:44.060 --> 30:49.080 Das heißt, diesen Ansatz, dass ich eine Folge habe, in der ich den 30:49.080 --> 30:55.400 Median bestimmen möchte oder ein kartengrößeres Element und ich teile 30:55.400 --> 31:00.580 das jetzt einfach auf in eine Reihe von Teilfolgen, in denen ich 31:00.580 --> 31:02.200 jeweils den Median bestimme. 31:03.920 --> 31:05.620 Das kann ich parallel machen. 31:06.920 --> 31:13.060 Und wenn ich P Prozessoren habe, mache ich das gerade auf P solchen 31:13.060 --> 31:13.720 Teilfolgen. 31:13.960 --> 31:15.160 Hier können das alle parallel. 31:16.540 --> 31:19.340 Dann habe ich jeweils den Aufwand, um in dieser Teilfolge den Median 31:19.340 --> 31:26.340 zu bestimmen und dann mache ich entsprechend anschließend die weiteren 31:26.340 --> 31:29.440 Schritte, ähnlich wie bei dem sequentiellen Verfahren. 31:29.440 --> 31:37.000 Also diese Idee aus dem linearen Verfahren für die Selektion, lineares 31:37.000 --> 31:40.880 Verfahren für die Medianbestimmung, daraus bekommt man genau einen 31:40.880 --> 31:46.520 sehr schönen und auch skalierbaren Ansatz für die Parallelisierung. 31:47.700 --> 31:56.440 Und dann habe ich in N durch P, wenn P der Parallelitätsgrad ist, kann 31:56.440 --> 31:58.160 ich den Median bestimmen. 31:58.160 --> 32:02.000 Das ist also ein sehr gut skalierbares Verfahren, auf das ich aber 32:02.000 --> 32:03.200 auch nicht weiter eingehen möchte. 32:03.600 --> 32:08.160 Wenn Sie da genaueres erfahren wollen, schauen Sie dem Buch von Selim 32:08.160 --> 32:08.820 Akel nach. 32:08.880 --> 32:11.780 Der hat das in seinem Buch über parallele Algorithmen sehr schön 32:11.780 --> 32:12.320 dargestellt. 32:13.920 --> 32:19.620 Das sei jetzt in dem Fall genug, was Parallelität oder was Sortieren 32:19.620 --> 32:21.580 und Selektieren angeht. 32:21.580 --> 32:25.600 Und ich möchte dann zum nächsten Thema kommen, was bei vielen 32:25.600 --> 32:31.560 Vorlesungen über effiziente Algorithmen mit zu Anfang auftaucht. 32:33.500 --> 32:33.980 Suchverfahren. 32:33.980 --> 32:39.140 Eine Operation, die sehr weit verbreitet ist. 32:39.240 --> 32:42.020 Mittlerweile reden wir, wenn wir suchen, häufig von Suchen in 32:42.020 --> 32:45.580 irgendwelchen Datenbanken. 32:46.320 --> 32:47.980 Dann machen wir Suchen im World Wide Web. 32:48.160 --> 32:50.140 Da sind noch ganz andere Verfahren dahinter, als das, was ich Ihnen 32:50.140 --> 32:50.700 jetzt vorstelle. 32:50.700 --> 32:53.420 Aber ich habe eben einfach das Problem, ich möchte aus einer großen 32:53.420 --> 32:55.420 Datenmenge ein Element raussuchen. 32:55.580 --> 32:59.160 Und die Frage ist, wie hoch ist da der Aufwand, welche Operation habe 32:59.160 --> 32:59.440 ich? 32:59.500 --> 33:05.080 Ich habe die üblichen Annahmen, ich habe eine Menge von Elementen, in 33:05.080 --> 33:06.100 denen ich etwas suchen möchte. 33:06.780 --> 33:09.500 Ich nehme an, dass die alle verschieden sind, wie üblich. 33:10.800 --> 33:15.160 Ich könnte natürlich ein Element auch mehrfach drin haben, das ist 33:15.160 --> 33:18.640 aber dann eigentlich eher einfacher. 33:19.420 --> 33:24.360 Obwohl, wenn ich ein Element löschen möchte, ich möchte vielleicht ein 33:24.360 --> 33:27.900 Element suchen und dann anschließend löschen, wenn ein Element 33:27.900 --> 33:31.340 mehrfach auftreten könnte, dann müsste ich natürlich jedes Auftauchen 33:31.340 --> 33:33.040 dieses Elementes rauslöschen. 33:33.980 --> 33:36.960 Also, welche Operationen habe ich überhaupt, die mich interessieren? 33:37.120 --> 33:38.480 Die hatten wir alle schon mal angeschaut. 33:39.200 --> 33:43.760 Das eine ist Member, das heißt, ist das Element A, nach dem ich suche, 33:44.300 --> 33:46.760 in meiner Folge oder in meiner Menge S drin? 33:46.760 --> 33:49.260 Das ist nicht notwendigerweise eine Folge, sondern eine Menge. 33:49.900 --> 33:52.600 Wenn ich eine Menge habe, ist es sowieso, dann habe ich nur 33:52.600 --> 33:53.680 verschiedene Elemente drin. 33:55.840 --> 33:59.580 Wenn ich aber eben eine Menge als irgendwelche Folge darstelle, kann 33:59.580 --> 34:01.660 es sein, dass da einige Elemente mehrfach drin stehen. 34:02.820 --> 34:07.260 Suchen heißt, ich möchte tatsächlich das Element rausholen. 34:08.080 --> 34:09.780 Warum möchte ich das Element rausholen? 34:09.780 --> 34:14.480 Es kann natürlich sein, dass ich suche nur nach irgendeinem Element, 34:14.880 --> 34:18.820 also ich suche nach dem Schlüssel, nach einem Schlüssel A, aber das, 34:18.940 --> 34:21.900 was mich interessiert, ist eigentlich das Element, das da hinten 34:21.900 --> 34:22.560 dranhängt. 34:23.500 --> 34:27.120 Ich suche in einem Lexikon nach einem Eintrag und will gerne die 34:27.120 --> 34:29.180 Erklärung eines Begriffs dann rausholen. 34:29.900 --> 34:34.880 Deswegen ist Suchen eine interessante Operation. 34:35.480 --> 34:37.240 Und dann natürlich Einfügen und Löschen. 34:38.320 --> 34:42.220 Ich möchte irgendwas Neues reinschreiben oder etwas rauslöschen. 34:42.760 --> 34:43.620 Auch das ist wichtig. 34:44.340 --> 34:46.280 Muss Google auch lernen, wie man etwas löscht. 34:48.360 --> 34:49.520 Sie bieten es an. 34:50.160 --> 34:53.980 Es wäre interessant zu sehen, ob Sie wirklich jedes Vorkommen eines 34:53.980 --> 34:55.700 Eintrags damit löschen können. 34:55.860 --> 34:59.440 Oder ob Sie, das glaube ich nicht, dass Sie tatsächlich dafür sorgen 34:59.440 --> 35:00.220 können, dass... 35:00.220 --> 35:02.660 Sie werden auch weniger die Sachen löschen, sondern wir dafür sorgen, 35:03.100 --> 35:05.220 dass die Elemente nicht angezeigt werden. 35:05.220 --> 35:08.420 Weil Sie werden nicht wirklich die Elemente löschen können, weil die 35:08.420 --> 35:10.940 in allen möglichen Backup-Systemen drin sind. 35:11.080 --> 35:12.260 Aber das ist ein ganz anderes Thema. 35:13.100 --> 35:17.880 Wir machen hier den einfachen Fall, wir wollen etwas tun auf einer 35:17.880 --> 35:19.820 einfachen Menge. 35:20.220 --> 35:23.600 Und in dem Fall ist das halt wie so ein Lexikon oder Dictionary. 35:24.140 --> 35:27.640 Da müssen wir gucken, wie viel Zeit wir brauchen für die Operation. 35:28.720 --> 35:31.700 Und das hängt ganz davon ab, welche Datenstrukturen wir haben. 35:32.140 --> 35:33.980 Es gibt manchmal noch ein paar andere Operationen. 35:33.980 --> 35:36.580 Xmin, ich möchte das Minimum rausnehmen, oder, das hatte ich auch 35:36.580 --> 35:38.060 schon mal gesagt, ist NearAS. 35:38.280 --> 35:42.020 Ich möchte die nächsten Elemente zu einem bestimmten Suchterm haben, 35:42.120 --> 35:44.080 die in meinem Lexikon drin sind. 35:44.560 --> 35:45.620 Auch die kann man anschauen. 35:46.040 --> 35:51.340 Wir werden im Wesentlichen suchen, einfügen und löschen betrachten. 35:52.860 --> 35:53.340 Einfachste? 35:53.480 --> 35:53.640 Ja. 35:55.660 --> 35:56.020 Gerne. 35:59.880 --> 36:03.700 Also, U könnte zum Beispiel sein, alle ganzen Zahlen. 36:06.320 --> 36:07.580 Das Universum. 36:08.540 --> 36:10.660 Kann auch sein, alle deutschen Namen. 36:12.060 --> 36:15.600 Und hier in diesem Raum sitzen aber weniger als alle deutschen Namen 36:15.600 --> 36:16.100 vertreten. 36:16.800 --> 36:21.060 Also irgendwelche, irgendein Universum und das Einfachste, wir nehmen 36:21.060 --> 36:23.300 normalerweise an, das sind einfach nur ganze Zahlen. 36:23.820 --> 36:25.820 Oder meistens nur natürliche Zahlen. 36:29.240 --> 36:30.280 Muss nicht. 36:31.320 --> 36:33.640 Da muss keine Ordnung drauf sein. 36:34.320 --> 36:35.560 Es kann eine drauf sein. 36:35.620 --> 36:37.620 Bei den ganzen Zahlen oder bei den natürlichen Zahlen habe ich eine 36:37.620 --> 36:38.740 Ordnung drauf definiert. 36:39.100 --> 36:40.200 Das kann ich ausnutzen. 36:40.920 --> 36:43.340 Wenn ich keine Ordnung drauf habe, dann wird es schwierig. 36:44.640 --> 36:47.020 Wenn ich keine Ordnung habe, und das ist das, was auf der nächsten 36:47.020 --> 36:49.060 Folie als erstes kommt, lineare Suche. 36:49.060 --> 36:53.280 Dann habe ich irgendwie meine Folge dargestellt, irgendwie. 36:54.300 --> 36:58.940 Und das muss ich hier der Reihe nach durchlaufen und durchsehen, ob 36:58.940 --> 37:00.200 das Element da drin ist. 37:00.340 --> 37:03.360 Wenn ich keine Ordnungsrelation habe da drauf, kann ich nichts weiter 37:03.360 --> 37:03.660 machen. 37:04.960 --> 37:10.640 Wenn ich eine Ordnungsrelation habe, wenn ich davon ausgehen kann, 37:11.080 --> 37:16.140 meine Elemente sind aufsteigend sortiert, dann kann ich natürlich 37:16.140 --> 37:20.640 schön binäre Suche machen, indem ich erstmal in der Mitte schaue, ob 37:20.640 --> 37:24.460 mein Element kleiner oder größer als das mittlere Element ist. 37:24.940 --> 37:27.620 Wenn es sortiert ist, kann ich direkt darauf zugreifen, auf die Mitte. 37:28.120 --> 37:32.080 Und wenn es kleiner ist, dann würde ich halt hier wieder in der Mitte 37:32.080 --> 37:32.460 schauen. 37:32.560 --> 37:34.720 Wenn es größer ist, würde ich da wieder in der Mitte schauen usw. 37:34.920 --> 37:39.440 Wir wissen, dass das mit logarithmisch vielen Zugriffen auf die Folge 37:39.440 --> 37:42.080 maximal erledigt ist. 37:42.080 --> 37:45.620 Bei binärer Suche, wenn ich also eine sortierte Reihenfolge habe, dann 37:45.620 --> 37:51.360 kann ich sehr schön in Zeit Log N maximal mein Element finden oder es 37:51.360 --> 37:52.000 war halt nicht drin. 37:53.460 --> 37:56.420 Das heißt, festzustellen, dass es nicht drin ist, braucht dann genau 37:56.420 --> 37:57.140 Log N-Schritte. 37:58.380 --> 38:04.720 Binäre Suchbäume, das ist im Prinzip genau das, was ich logisch mache, 38:05.080 --> 38:10.060 mit der binären Suche auf einer linear angeordneten Liste, einfach nur 38:10.060 --> 38:11.440 als Baum aufgemalt. 38:11.440 --> 38:15.500 Dann hätte ich also hier, das wäre meine Wurzel, die beiden Elemente, 38:15.560 --> 38:18.080 die da sind, wären dann die nächsten Elemente usw. 38:19.340 --> 38:25.000 Da baue ich im Prinzip den Entscheidungsbaum, der der binären Suche 38:25.000 --> 38:27.220 zugrunde liegt, liefert genau einen binären Suchbaum. 38:27.320 --> 38:29.660 Wir werden gleich noch sehen, wie man das dann macht. 38:30.560 --> 38:34.560 Interpolierende Suche ist auch interessant, wenn Sie noch mehr wissen. 38:34.680 --> 38:36.980 Sie wissen nicht nur diesen angeordnet, sondern Sie haben auch eine 38:36.980 --> 38:38.200 Größenabschätzung. 38:39.240 --> 38:43.300 Sie wissen, das ist aufsteigend sortiert und Sie kennen das größte und 38:43.300 --> 38:47.540 das kleinste Element, aufsteigend sortiert, und Sie haben einen großen 38:47.540 --> 38:49.840 Wert, nach dem Sie suchen, der in der Nähe von, nehmen wir mal an, 38:49.860 --> 38:51.820 hier steht irgendein K, liegt. 38:52.260 --> 38:55.120 Dann würden Sie wahrscheinlich nicht in der Mitte suchen als Nächstes, 38:55.200 --> 39:00.240 sondern Sie würden irgendwo im oberen Bereich suchen, um dadurch die 39:00.240 --> 39:02.240 Anzahl der Vergleiche schon mal zu reduzieren. 39:02.320 --> 39:05.500 Das wird durch interpolierende Suche, Sie wissen etwas über die 39:05.500 --> 39:09.260 Größenordnung und suchen einfach entsprechend der Größe Ihres 39:09.260 --> 39:13.320 Elements, nach dem Sie suchen, bestimmen Sie eine Position, wo es sein 39:13.320 --> 39:17.040 könnte und können dann entsprechend weitermachen, reduzieren dadurch 39:17.040 --> 39:18.220 die Anzahl der Vergleiche. 39:19.300 --> 39:23.140 Und dann gibt es etwas, was eben nicht interpolierend läuft, sondern 39:23.140 --> 39:26.520 Sie haben einfach balancierte Bäume, das sind spezielle Suchbäume. 39:27.380 --> 39:31.420 Und da gibt es die AVL-Bäume, es gibt die B-Bäume. 39:31.500 --> 39:35.180 Jetzt habe ich hier, glaube ich, ein Problem, wenn ich hier draufgehe. 39:35.180 --> 39:42.200 Ich dachte, ich hätte das eigentlich erledigt, aber Herr Braun, ich 39:42.200 --> 39:44.780 glaube, wenn ich jetzt hier raufgehe, dann kommt gleich, ich habe das 39:44.780 --> 39:47.960 gestern versucht, er konnte gar keinen Internet-Server oder Proxy 39:47.960 --> 39:48.460 finden. 39:48.720 --> 39:51.340 Okay, ich gehe da, will das auch gar nicht jetzt machen. 39:52.820 --> 39:54.400 Ich habe jetzt keine Verbindung zum Netz. 39:58.650 --> 40:06.050 Jetzt will er irgendwas, das muss ich doch erstmal kurz hier in... 40:07.470 --> 40:13.510 Jetzt wollte ich einmal kurz die Verbindung zum Netz herstellen. 40:21.130 --> 40:25.810 Ich stelle fest, ich habe mich gar nicht mit dem Stromkabel verbunden. 40:31.280 --> 40:38.360 Ein anderes Netz, der ist anscheinend verbunden und dann schaue ich 40:38.360 --> 40:38.740 hier nochmal. 40:44.220 --> 40:46.840 Dann kommt er, glaube ich, gleich mit einer Fehlermeldung. 40:48.140 --> 40:49.840 Ach nee, er ist da, perfekt. 40:50.480 --> 40:53.580 Aber ich hatte eine andere Darstellung nachher bei den Rot-Schwarz 40:53.580 --> 40:57.680 -Bäumen, da wollte ich was angucken und das Ding wollte er nicht. 40:58.360 --> 40:59.340 Zumindest gestern nicht. 41:00.080 --> 41:05.280 Also, hier sehen Sie eine Darstellung von verschiedenen... 41:05.280 --> 41:08.600 Das ist hier einfach jetzt ein AVL-Baum. 41:09.320 --> 41:11.280 Wer von Ihnen weiß, was ein AVL-Baum ist? 41:12.320 --> 41:13.360 Keiner von Ihnen. 41:14.260 --> 41:17.480 AVL steht für Adelsen, Welski und Landes. 41:17.680 --> 41:22.060 Das sind drei Russen, die diese Idee hatten mit dem Suchbaum. 41:22.060 --> 41:32.460 Und hier ist die Idee, dass für jeden Knoten die beiden nachfolgenden 41:32.460 --> 41:39.360 Knoten oder die Höhen der nachfolgenden beiden Knoten sich um maximal 41:39.360 --> 41:40.420 eins unterscheiden. 41:42.580 --> 41:50.600 Das heißt, ich habe hier Höhe 2, da habe ich Höhe 1 und so weiter. 41:50.600 --> 42:00.860 Jetzt könnte ich ja mal hier zum Beispiel eine 46 eintragen. 42:01.840 --> 42:02.600 Was macht er dann? 42:03.240 --> 42:04.640 Die müsste jetzt daneben kommen. 42:06.240 --> 42:09.320 So, wir sehen, jetzt habe ich aber hier einen größeren Unterschied. 42:10.640 --> 42:14.360 Er hat also ein bisschen umgeordnet, damit wir nicht rechts daneben 42:14.360 --> 42:18.900 einen noch längeren Pfad bekommen. 42:19.540 --> 42:21.180 Ich könnte jetzt noch was einbauen. 42:21.360 --> 42:25.680 Ich könnte meinetwegen 47 nehmen als nächstes. 42:26.760 --> 42:30.020 Ich könnte auch 44 nehmen, das ist kein Problem, das ist klar, wo das 42:30.020 --> 42:30.780 hinlaufen wird. 42:31.360 --> 42:33.420 Das läuft natürlich gerade links von der 45. 42:34.440 --> 42:37.460 Und wenn ich jetzt...haben wir hier einen vollständigen Baum, da passt 42:37.460 --> 42:38.220 nichts mehr rein. 42:39.200 --> 42:46.500 Und wenn ich jetzt hier die 47 nehme und die einfüge, können Sie sich 42:46.500 --> 42:47.400 vorstellen, was passiert? 42:47.400 --> 42:52.500 Dann muss er dafür sorgen, dass die Wurzel etwas oben rüber geschoben 42:52.500 --> 42:52.820 wird. 42:53.160 --> 42:54.560 Hier ist der Unterschied zu groß. 42:55.440 --> 42:56.340 Das reicht auch noch nicht. 42:56.540 --> 42:58.120 Sie sehen, er schiebt es jetzt ganz oben rum. 42:58.880 --> 43:01.380 Das heißt, dieses Hin- und Herschieben kann sich bis an die Wurzel 43:01.380 --> 43:04.660 fortsetzen und anschließend ist der Baum wieder ausbalanciert. 43:05.200 --> 43:09.960 Das heißt, das sind höhenbalancierte Bäume und ich sorge dafür, das 43:09.960 --> 43:14.460 sind also binäre Bäume, wobei wir hier den Fall haben, dass da eben 43:14.460 --> 43:16.360 nur ein Nachfolger ist, der andere ist hier nicht gefüllt. 43:16.360 --> 43:24.240 Aber es sind binäre Bäume, die Höhen der Teilbäume sind jeweils 43:24.240 --> 43:26.040 maximal um eins unterschiedlich. 43:26.140 --> 43:30.900 Das gilt für jeden Knoten dort drin und in dem Sinne höhenbalanciert. 43:31.320 --> 43:34.000 Sie sehen übrigens hier genau die einzelnen Vergleiche, die er alle 43:34.000 --> 43:34.260 macht. 43:34.380 --> 43:36.020 Das ist ja alles schön dokumentiert. 43:36.240 --> 43:37.120 Eine sehr schöne Animation. 43:39.880 --> 43:42.720 So, kann man also beliebig mit rumspielen. 43:43.660 --> 43:47.160 Wenn ich jetzt hier, meinetwegen sage ich möchte jetzt 61, mal sehen, 43:47.340 --> 43:48.180 was er dann macht. 43:48.260 --> 43:53.880 Wenn ich 61 löschen möchte, dann geht er da hin, nimmt das Ding raus 43:53.880 --> 43:57.080 und Sie sehen, das war ganz einfach. 43:59.260 --> 44:03.360 Also, kann man mit rumspielen, kann man ein bisschen so ein Gefühl 44:03.360 --> 44:08.140 dafür bekommen, was eigentlich mit diesen AVL-Bäumen passiert. 44:08.140 --> 44:12.600 Und Sie können hier auch noch andere, ich meine, das sind jetzt hier 44:12.600 --> 44:16.180 nur AVL-Bäume, es gibt aber andere Animationen, wo Sie sich noch 44:16.180 --> 44:23.100 verschiedenste solche Suchbäume anschauen können. 44:23.500 --> 44:27.080 So, das war also jetzt die Idee zu den AVL-Bäumen. 44:27.080 --> 44:30.380 Man kann, habe ich die auch animiert? 44:30.740 --> 44:34.100 Die habe ich nicht animiert. 44:35.760 --> 44:40.320 Also B-Bäume, B-Bäume könnten Sie kennen eventuell. 44:40.860 --> 44:47.380 B-Bäume, B für Bayer, derjenige, der sich die überlegt hat. 44:47.380 --> 44:54.960 Das sind Bäume, die man in Datenbanken benutzt, um den Zugriff auf 44:54.960 --> 44:58.000 große Datenmengen zu verbessern. 44:58.800 --> 45:03.680 Und zwar, da komme ich gleich drauf, also B-Bäume, da hat man im 45:03.680 --> 45:11.640 Prinzip die Idee, ich betrachte zwar einen binären Baum, aber dieser 45:11.640 --> 45:13.960 binäre Baum sieht ein bisschen anders aus. 45:15.100 --> 45:20.980 Ich habe sehr große, das können also mehrere sein hier, ich habe sehr 45:20.980 --> 45:26.020 große Knoten und jeder Knoten hat etwa so viele Elemente, wie in einem 45:26.020 --> 45:28.320 Block im Hintergrundspeicher drin liegen. 45:29.860 --> 45:33.840 Das heißt, mit jedem Zugriff, wenn ich also hier etwas suche und ich 45:33.840 --> 45:37.000 finde mein Element hier, danach suche ich, das finde ich hier nicht, 45:37.820 --> 45:41.180 dann suche ich irgendwo anders, ich gehe in einen entsprechenden 45:41.180 --> 45:44.480 Teilknoten rein, ich weiß, wo ich ihn suchen muss, ich habe eine ganze 45:44.480 --> 45:45.340 Reihe von Möglichkeiten. 45:46.160 --> 45:49.220 Ich suche mir den nächsten Block, wo das Element drin liegen könnte 45:49.220 --> 45:53.320 und ich sorge dafür, dass ich hier einen ganzen Block gleich 45:53.320 --> 45:56.540 rauskriege und hoffe, dass das Element dann da drin ist. 45:56.640 --> 46:00.220 Auf die Art und Weise reduziere ich die Anzahl der Zugriffe auf 46:00.220 --> 46:03.500 Hintergrundspeicher, weil ich mit jedem Zugriff gleich einen ganzen 46:03.500 --> 46:04.800 Block runterhole. 46:04.800 --> 46:09.560 Das sind also die B-Bäume, ganz wichtig für Beschleunigung der 46:09.560 --> 46:12.160 Zugriffe auf Daten in Datenbankanwendungen. 46:12.900 --> 46:16.940 Wir machen das jetzt ein bisschen einfacher und ich werde Ihnen etwas 46:16.940 --> 46:20.560 erzählen über 2-3-4-Bäume und über Rot-Schwarz-Bäume. 46:21.620 --> 46:27.300 2-3-4-Bäume sind im Prinzip Spezialfälle von diesen B-Bäumen, heißen 46:27.300 --> 46:28.460 aber 2-3-4-Bäume. 46:30.080 --> 46:31.440 Warum, werden Sie gleich sehen. 46:31.440 --> 46:33.040 Dazu gibt es auch ein Applet. 46:33.280 --> 46:34.480 Mal gucken, ob das funktioniert. 46:34.560 --> 46:38.760 Da hatte ich gestern Schwierigkeiten, sagte ich ja schon. 46:41.160 --> 46:42.840 Mal sehen, ob es jetzt funktioniert. 46:43.380 --> 46:45.820 Sehen Sie, da will Herr Braun. 46:46.960 --> 46:51.640 Da habe ich jetzt hier, da will er irgendein Plugin haben. 46:52.780 --> 46:57.900 Und der will hier das Ausführen von Java Plattform SE 7u. 46:59.680 --> 47:04.020 Und ich sage Erlauben und Erscheidung. 47:04.480 --> 47:05.040 Merken. 47:06.420 --> 47:08.840 Anwendung durch Sicherheitseinstellung blockiert. 47:08.920 --> 47:11.140 Wir machen ja sichere Systeme, deshalb muss ich froh sein, dass er 47:11.140 --> 47:14.580 mich warnt vor irgendwelchen unsicheren Dingen. 47:14.940 --> 47:17.600 Meine Sicherheitseinstellungen haben die Ausführung einer nicht 47:17.600 --> 47:19.160 vertrauenswürdigen Anwendung blockiert. 47:20.180 --> 47:23.620 Recht so, offensichtlich habe ich hier gesagt, oder in den 47:23.620 --> 47:26.040 Standardeinstellungen, dieses Applet nicht mit drin. 47:26.560 --> 47:29.600 Und da sollte ich mich auch gar nicht nur beschweren, sondern dann ist 47:29.600 --> 47:31.260 das auch irgendeinem Grund da drin. 47:32.000 --> 47:35.240 Und ich muss mal sehen, wie man das dann umgehen kann, weil wir ja 47:35.240 --> 47:37.080 solche Sicherheitsrichtlinien gar nicht mögen. 47:37.140 --> 47:40.640 Wir wollen ja eigentlich auf alles zugreifen können und uns nicht 47:40.640 --> 47:44.660 durch solche Sicherheitshinweise abschrecken lassen. 47:44.820 --> 47:48.280 Was ich natürlich nicht ernst gemeint habe, sondern das ist ganz 47:48.280 --> 47:55.400 wichtig, dass wir solche Sicherheitsmaßnahmen in unseren Systemen drin 47:55.400 --> 47:55.680 haben. 47:56.740 --> 48:00.540 Also, auch das ist ein Applet, schauen Sie sich an, es gibt 48:00.540 --> 48:02.060 Möglichkeiten, wie Sie darauf zugreifen können. 48:02.180 --> 48:05.640 Das hat keine Probleme, dieses Applet, man kann darauf zugreifen, das 48:05.640 --> 48:08.580 fügt Ihrem Rechner keinen Schaden zu. 48:09.140 --> 48:12.500 Es geht einfach darum, dass Sie hier Code ausführen auf Ihrem Rechner, 48:12.560 --> 48:14.120 der von einem anderen Rechner kommt. 48:14.120 --> 48:18.700 Und da gibt es die üblichen Probleme, dass Sie dann signierte Applets 48:18.700 --> 48:20.420 eigentlich nur verwenden sollten und so weiter. 48:22.360 --> 48:25.560 Wir werden später noch wieder auf die 2, 3, 4 Bäume zurückkommen, ich 48:25.560 --> 48:29.420 werde aber zunächst mal Ihnen vorstellen, was ein binärer Suchbaum 48:29.420 --> 48:31.420 ist, nochmal allgemein definiert. 48:32.100 --> 48:33.820 Habe ich eigentlich schon aufgemalt. 48:34.780 --> 48:47.340 Ein binärer Baum, ganz einfach, jeder Knoten hat zwei Nachfolger, also 48:47.340 --> 48:50.300 entweder zwei Nachfolger oder er hat keine. 48:50.360 --> 48:54.160 Wenn er keine hat, male ich das normalerweise so als Kasten da unten 48:54.160 --> 48:54.400 hin. 48:54.840 --> 48:55.480 Das sind die Blätter. 48:55.880 --> 48:59.540 Knoten ohne Nachfolger heißen Blatt, Knoten ohne Vater oder Mutter 48:59.540 --> 49:03.720 heißen Wurzel, oder ohne Vorfahr kann man auch sagen, oder Vorfahrin 49:03.720 --> 49:05.120 heißen Wurzel. 49:05.420 --> 49:10.300 Also Bäume haben ein großes Gender-Problem, da muss man immer gucken, 49:10.400 --> 49:17.560 dass man genderkonform von den Kindern redet, und nicht von Söhnen, 49:17.740 --> 49:19.980 sondern von Kindern und ähnlichen Dingen. 49:22.880 --> 49:27.500 Also Knoten ohne Vater oder Mutter heißen Wurzel, Knoten, der kein 49:27.500 --> 49:29.440 Blatt ist, heißt innerer Knoten. 49:29.440 --> 49:31.060 Ist klar, das kennen Sie alles. 49:31.480 --> 49:34.900 Und dann habe ich einen binären Suchbaum, und beim binären Suchbaum 49:34.900 --> 49:36.540 habe ich eben weitere Eigenschaften. 49:36.860 --> 49:41.900 Das ist zunächst mal ein binärer Baum, und jeder Knoten, alle inneren 49:41.900 --> 49:43.460 Knoten, enthalten einen Schlüssel. 49:44.080 --> 49:45.020 Da gibt es Unterschiede. 49:45.220 --> 49:49.180 Manchmal sagt man, die Elemente, nach denen ich suche, sind nur in den 49:49.180 --> 49:49.540 Blättern. 49:51.000 --> 49:54.480 Und manchmal sage ich, alle Elemente, nach denen ich suche, sind in 49:54.480 --> 49:55.660 den inneren Knoten. 49:56.700 --> 49:59.380 Das ist also Geschmackssache, führt ein bisschen zu unterschiedlichen 49:59.380 --> 50:03.000 Verfahren, aber ich gehe mal davon aus, dass die Elemente in den 50:03.000 --> 50:06.260 Knoten gespeichert sind, in den inneren Knoten, und nicht in den 50:06.260 --> 50:06.560 Blättern. 50:06.660 --> 50:07.380 Die Blätter sind leer. 50:09.460 --> 50:17.100 Und jetzt hat also jeder Knoten einen Schlüssel, ein Datum, das ich 50:17.100 --> 50:24.300 suchen könnte, und alle Schlüssel im linken Unterbaum hier sind 50:24.300 --> 50:30.740 kleiner, alle im rechten Unterbaum sind größer, gleich dem Schlüssel 50:30.740 --> 50:31.380 im Knoten. 50:32.140 --> 50:34.580 Das heißt, ich brauche nur das Element hier in einem Knoten 50:34.580 --> 50:36.900 anzuschauen, ich kann mich entscheiden, gehe ich nach links oder gehe 50:36.900 --> 50:37.480 ich nach rechts. 50:37.780 --> 50:39.620 Das ist genau das, was wir bei der binären Suche machen. 50:39.760 --> 50:43.720 Ich sagte, so kann man problemlos einen binären Suchbaum erzeugen, 50:43.720 --> 50:48.500 indem man diese Folge von Elementen, die man anschaut, genauso dort 50:48.500 --> 50:49.840 als Baum aufmalt. 50:51.060 --> 50:53.240 Also das ist ein einfacher binärer Suchbaum. 50:53.840 --> 50:54.800 Jetzt schauen wir uns das mal an. 50:55.000 --> 50:57.840 Ideal habe ich einen vollständigen binären Baum. 50:58.860 --> 51:02.940 Und wenn ich jetzt nach irgendeinem Element suche, dann komme ich im 51:02.940 --> 51:07.800 schlechtesten Fall halt hier immer mit einem Pfad, in dem Fall Länge 51:07.800 --> 51:09.300 3, bis zu einem Blatt. 51:09.300 --> 51:12.040 Wenn ich bei einem Blatt gelandet bin, heißt das, das Element war 51:12.040 --> 51:13.240 nicht in der Folge drin. 51:13.860 --> 51:15.340 Ansonsten habe ich es vorher schon gefunden. 51:17.720 --> 51:21.160 Und wenn ich nach 15 suche, bin ich halt nach zwei Vergleichen dort. 51:22.940 --> 51:27.740 Und das Dumme ist, wenn ich mir jetzt anschaue, eine dynamisch 51:27.740 --> 51:32.020 veränderliche Menge, und ich baue mir dafür Suchbäume auf, binären 51:32.020 --> 51:38.260 Suchbäume, und ich fange an mit einem Element A und füge jetzt ein 51:38.260 --> 51:39.200 Element B dazu. 51:39.860 --> 51:41.460 Dann wird das rechts angeordnet. 51:41.560 --> 51:44.360 Ich füge das Element C hinzu, das ist rechts davon angeordnet, ich 51:44.360 --> 51:47.300 füge das Element D hinzu, und ich habe das wieder rechts davon 51:47.300 --> 51:48.020 angeordnet. 51:48.740 --> 51:52.720 Ich müsste eigentlich, damit das ein schöner, vollständiger, binärer 51:52.720 --> 51:55.180 Suchbaum bleibt, müsste ich das alles umordnen. 51:55.560 --> 52:00.400 Aber wenn ich einfach nur sage, das ist ein binärer Baum, bei dem die 52:00.400 --> 52:03.820 Elemente im linken Teilbaum jeweils kleiner und die im rechten 52:03.820 --> 52:10.240 Teilbaum größer gleich dem Element an der jeweiligen Knoten sind, dann 52:10.240 --> 52:12.780 bekomme ich auf einmal so einen entarteten Suchbaum. 52:13.880 --> 52:17.360 Das ist auch ein binärer Suchbaum, aber der hat das Problem, dass ich 52:17.360 --> 52:21.180 hier auf einmal linearen Suchaufwand habe und keinen logarithmischen 52:21.180 --> 52:21.800 Suchaufwand. 52:23.360 --> 52:27.840 Und nicht nur linearen Suchaufwand, sondern auch linearen Aufwand, um 52:27.840 --> 52:30.640 dann entsprechend was einzufügen oder zu löschen. 52:31.420 --> 52:33.360 Also das ist etwas, was ich vermeiden möchte. 52:34.020 --> 52:37.680 Das heißt, ich muss beim Einfügen darauf achten, dass ich die Struktur 52:37.680 --> 52:42.620 immer erhalte, dass ich etwas erhalte, was in die Richtung geht eines 52:42.620 --> 52:44.580 binären Baumes. 52:45.040 --> 52:47.860 Wenn ich immer erreichen möchte, dass ich stets einen vollständigen 52:47.860 --> 52:51.120 binären Baum habe, dann wird es aufwendig. 52:51.940 --> 52:57.220 Deswegen gibt es diese Varianten, das waren diese höhenbalancierten 52:57.220 --> 52:58.020 binären Bäume. 52:59.060 --> 53:03.660 Für jeden Knoten unterscheiden sich die Höhen der beiden Unterbäume 53:03.660 --> 53:04.520 höchstens um eins. 53:07.840 --> 53:13.080 Und dann ist das also nicht notwendigerweise ein bestmöglicher 53:13.080 --> 53:16.680 vollständiger binärer Baum, den ich dort habe, aber ich habe eben auf 53:16.680 --> 53:23.860 jeden Fall gewährleistet, dass ich als schlechtester Fall Lock-in 53:23.860 --> 53:24.780 -Fahrtlänge habe. 53:25.640 --> 53:28.980 Also ich kann eine Rebalancierung machen müssen, das haben wir gesehen 53:28.980 --> 53:30.000 an dem Applet. 53:30.940 --> 53:35.340 Der Aufwand dafür sollte möglichst logarithmisch bleiben. 53:35.440 --> 53:37.340 Der ist tatsächlich, man kann das so hinbekommen. 53:38.000 --> 53:39.020 Muss man genau überlegen. 53:39.100 --> 53:41.980 Wir hatten ja gesehen, wenn man Pech hat, läuft man erstmal ganz 53:41.980 --> 53:44.960 runter und dann baut man da unten etwas um, dann baut man auf der 53:44.960 --> 53:47.480 nächsten Stufe etwas um und dann baut man auf der nächsten Stufe oben 53:47.480 --> 53:48.520 drüber wieder etwas um. 53:49.240 --> 53:52.920 Und dieses, also wenn wir hier irgendwo runtergelaufen waren und wir 53:52.920 --> 53:56.960 müssen auf jeder Ebene etwas umordnen mit unserer Struktur, und da 53:56.960 --> 54:01.800 oben auch nochmal, könnte es ja sein, dass ich alle Knoten anfassen 54:01.800 --> 54:03.520 musste, die in diesem Teilbaum lagen. 54:03.600 --> 54:06.640 Das sind aber linear viele, das wäre ganz schlecht. 54:07.960 --> 54:10.840 Es müsste also so sein, dass ich nur mich hier in so einem engen 54:10.840 --> 54:14.640 Bereich um den Pfad von der Wurzel bis zu der Position, wo ich jetzt 54:14.640 --> 54:17.580 gerade hingekommen bin, dass ich nur die in einem engen Bereich 54:17.580 --> 54:21.340 modifizieren muss, sodass ich diese Eigenschaft Höhenbalanzierung 54:21.340 --> 54:22.780 wieder gewährleisten kann. 54:23.480 --> 54:24.760 Und das kann man eben so hinbekommen. 54:25.400 --> 54:27.440 Bei den AVL-Bäumen ist das der Fall. 54:28.340 --> 54:32.080 Sollte eigentlich, ist aber nicht in der Grundlagenvorlesung drin 54:32.080 --> 54:32.440 sein. 54:33.020 --> 54:34.420 Ich gehe auf das nicht weiter ein. 54:34.540 --> 54:40.260 Ich mache andere schön balancierte Bäume, die aber eben auch keine 54:40.260 --> 54:41.840 vollständigen binären Bäume sind. 54:43.220 --> 54:47.480 Das ist jetzt der zweite Ausweg, den ich genauer betrachten möchte. 54:47.700 --> 54:52.800 Die 2-3-4-Bäume, das ist mittlerweile die Suchstruktur für Mengen, die 54:52.800 --> 54:55.060 sich am besten durchgesetzt hat. 54:55.740 --> 55:00.440 Allerdings nicht in der Variante 2-3-4-Bäume, sondern mit der Variante 55:00.440 --> 55:01.860 Rot -Schwarz-Bäume. 55:03.080 --> 55:05.880 Das werden wir gleich noch später sehen, was die miteinander zu tun 55:05.880 --> 55:06.140 haben. 55:07.720 --> 55:09.460 Also was sind 2-3-4-Bäume? 55:09.460 --> 55:15.140 Das sind Bäume, bei denen ich allgemeiner A-B-Bäume habe. 55:16.120 --> 55:20.860 Und das A und B bezieht sich auf den Verzweigungsgrad meiner Knoten. 55:22.820 --> 55:27.260 Also jeder Knoten in dem Fall enthält 0 bis 3 Schlüssel. 55:27.440 --> 55:29.280 Die Blätter enthalten überhaupt keinen Schlüssel. 55:32.420 --> 55:39.220 Wenn ich dort einen Schlüssel drin habe, bei einem Schlüssel, wenn ich 55:39.220 --> 55:43.720 hier eine 5 in einem Knoten drin habe, dann kann ich mich entscheiden, 55:44.180 --> 55:47.020 ob ich nach links oder nach rechts gehe, Elemente, die kleiner sind 55:47.020 --> 55:47.900 oder größer sind. 55:49.620 --> 55:59.340 Wenn ich mehr habe, zwei Elemente, 5 und 17, dann könnte ich hier, ich 55:59.340 --> 56:06.060 mal das nochmal neu, das war nicht schön, das ist hier der Fall 56:06.060 --> 56:06.460 gewesen. 56:06.560 --> 56:08.060 Ich habe ein Element dort drin. 56:09.640 --> 56:13.940 Jetzt nehmen wir den Fall, wir haben hier zwei Elemente drin, da wären 56:13.940 --> 56:15.880 8 und 16 drin. 56:16.180 --> 56:19.060 Dann könnte ich halt Elemente haben, die liegen zwischen 5 und 8, 56:19.220 --> 56:22.480 Elemente, die liegen zwischen 8 und 16 und Elemente, die sind größer 56:22.480 --> 56:23.040 als 16. 56:23.380 --> 56:28.240 Oder allgemein, wenn ich K-Elemente dort drin habe, habe ich K plus 1 56:28.240 --> 56:31.760 Teilbäume, in denen ich weiter suchen müsste. 56:31.760 --> 56:35.240 Das ist genau die Idee, die ich vorhin kurz angedeutet habe bei den B 56:35.240 --> 56:35.580 -Bäumen. 56:36.680 --> 56:42.500 Also B-Bäume sind solche A, B-Bäume, wobei da das A gerade die halbe 56:42.500 --> 56:46.200 Blockgröße ist im Hintergrundspeicher und das B ist halt entsprechend 56:46.200 --> 56:49.900 die gesamte Blockgröße. 56:50.900 --> 56:51.460 So. 56:52.600 --> 57:04.060 Und 2-3-4-Baum heißt also, ich habe hier 2, 3 oder 4 Nachfolger. 57:05.180 --> 57:09.740 Also 1, 2 oder 3 Elemente drin, das sind 2-3-4-Bäume. 57:10.320 --> 57:17.540 Zwischen 2 und 4 ist der Verzweigungsgrad meiner Knoten, also der 57:17.540 --> 57:18.280 inneren Knoten. 57:19.060 --> 57:24.260 Und es ist klar, dass dann hier jeweils die, wenn ich also in dem 57:24.260 --> 57:30.140 Knoten K Schlüssel S1 bis Sk habe, hier sind sie angedeutet, da meine 57:30.140 --> 57:34.520 Schlüssel S1 bis Sk, dann seien die hier aufsteigend sortiert in dem 57:34.520 --> 57:37.040 Knoten. 57:37.040 --> 57:43.820 Und für die Unterbäume gilt dann entsprechend, dass Ti gerade Elemente 57:43.820 --> 57:50.860 enthält, die kleiner sind als Si und größer gleich Si-1. 57:53.060 --> 57:55.020 Also das ist genau das, was hier steht. 57:55.740 --> 58:01.380 Und die ganz außen sind halt größer gleich dem maximalen Schlüssel in 58:01.380 --> 58:02.000 dem Knoten. 58:03.660 --> 58:09.260 Und alle Unterbäume haben die gleiche Höhe, vollständig balanciert, 58:09.900 --> 58:10.920 alle die gleiche Höhe. 58:11.460 --> 58:15.380 Das heißt, ich habe hier so etwas wie hier angedeutet, es kann sein, 58:15.480 --> 58:21.580 dass ich hier durchaus irgendwie A, B, C, 3 Elemente drin habe und 58:21.580 --> 58:24.620 dann hier entsprechend 1, 2, 3, 4 Nachfolger. 58:25.660 --> 58:32.500 Aber dann habe ich hier auch jeweils Knoten, das geht jetzt hier in 58:32.500 --> 58:35.180 das Ding über, das sollte es aber nicht, und hier müsste ich auch 58:35.180 --> 58:42.240 entsprechend Knoten haben, die auch zu Pfaden führen, die genau die 58:42.240 --> 58:43.140 gleiche Länge haben. 58:43.220 --> 58:48.160 Das heißt, die Ungleichheit in dieser unvollständigen Pfade, wenn ich 58:48.160 --> 58:53.120 einen nicht vollständigen Baum habe, die äußert sich hier nicht in den 58:53.120 --> 58:56.920 unterschiedlichen Pfadlängen, sondern in den unterschiedlichen Größen 58:56.920 --> 58:58.440 der Knoten. 58:58.440 --> 59:01.160 Zwischen 1 und 3 Elemente. 59:02.800 --> 59:05.780 Und wenn ich also überall die gleiche Pfadlänge habe, dann weiß ich 59:05.780 --> 59:09.960 halt, ich muss maximal diese Pfadlänge durchlaufen, bis ich den Knoten 59:09.960 --> 59:13.140 gefunden habe oder den Schlüssel gefunden habe oder weiß, dass er gar 59:13.140 --> 59:13.700 nicht drin ist. 59:13.700 --> 59:16.360 Das sieht dann schon relativ balanciert aus. 59:17.080 --> 59:20.140 Und wie gesagt, dieses, was noch übrig bleibt an Unbalanciertheit, das 59:20.140 --> 59:21.860 stecke ich in die Knoten rein. 59:22.880 --> 59:24.460 Das ist halt die Frage, ob das immer so geht. 59:24.880 --> 59:28.500 Der Suchaufwand ist ein kleiner gleich Log N. 59:29.060 --> 59:30.760 Warum eigentlich Log N? 59:30.880 --> 59:35.160 Ich muss ja in den einzelnen Knoten auch noch suchen. 59:36.360 --> 59:39.880 Da muss ich ja jeweils rausfinden, an welcher Stelle darf ich 59:39.880 --> 59:40.460 weiterlaufen. 59:40.460 --> 59:48.380 Der Aufwand ist aber konstant in der Größe, das sind ja nur 1, 2, 3 59:48.380 --> 59:54.280 Elemente drin, den Aufwand kann ich, das ist ein konstanter Faktor, 59:54.440 --> 01:00:00.640 das heißt ich habe insgesamt konstant mal Log Verzweigungsgrad drin, 01:00:00.980 --> 01:00:03.380 kann man abschätzen durch Log N. 01:00:03.380 --> 01:00:07.100 Also genau wie in einem binären Baum. 01:00:10.360 --> 01:00:13.680 Und insofern habe ich dann hier das erreicht, was ich gerne möchte, 01:00:13.800 --> 01:00:21.160 sofern ich in der Lage bin, beim Einfügen und beim Löschen genau diese 01:00:21.160 --> 01:00:22.620 Struktur immer aufrecht zu erhalten. 01:00:23.380 --> 01:00:24.680 Und das ist das, was wir anschauen müssen. 01:00:24.760 --> 01:00:28.460 Wenn wir einen solchen 2-drauf-4-Baum haben, ist der Suchaufwand 01:00:28.460 --> 01:00:29.940 kleiner gleich Log N. 01:00:30.400 --> 01:00:33.100 Jetzt müssen wir uns überlegen, was passiert, wenn wir etwas einfügen. 01:00:33.420 --> 01:00:35.060 Wie bauen wir so einen Baum auf? 01:00:36.620 --> 01:00:40.640 Also zunächst mal, wenn ich einen einfachen Baum habe, nehmen wir an, 01:00:40.700 --> 01:00:45.420 dass schon ein Element drin ist, ich habe eine Wurzel oder ein Element 01:00:45.420 --> 01:00:49.300 unten, es kann ja auch sein, dass ich hier meinen großen Baum habe und 01:00:49.300 --> 01:00:52.620 ich bin hier an einem Knoten angelangt, da angelangt, da sind jetzt 01:00:52.620 --> 01:00:55.680 hier meine beiden Elemente und da möchte ich etwas einfügen. 01:00:55.680 --> 01:01:00.460 Also dieses B hier, das ist halt ein innerer Knoten an der untersten 01:01:00.460 --> 01:01:00.760 Schicht. 01:01:00.820 --> 01:01:03.420 Ich füge hier nur etwas ein, wenn es noch nicht drin war. 01:01:03.980 --> 01:01:06.880 Das heißt, ich bin auf jeden Fall ganz runtergelaufen bis zu der 01:01:06.880 --> 01:01:08.300 Position, wo das A hin soll. 01:01:09.400 --> 01:01:11.520 Das ist jetzt kleiner gleich B. 01:01:13.180 --> 01:01:16.560 Naja, das kann ich ja einfach reinschreiben in meinen Knoten. 01:01:16.600 --> 01:01:20.580 Dann habe ich da zwei Elemente drin und entsprechend drei Blätter 01:01:20.580 --> 01:01:21.180 unten drunter. 01:01:21.780 --> 01:01:24.500 Ich darf ja bis zu drei Elemente drin haben, also das ist gar kein 01:01:24.500 --> 01:01:24.840 Problem. 01:01:25.320 --> 01:01:29.240 Wenn ich zwei Elemente drin habe, dann baue ich das entsprechend hier 01:01:29.240 --> 01:01:35.600 mit ein und dann habe ich hier dann A, B, C oder irgendwie, wenn das A 01:01:35.600 --> 01:01:38.960 kleiner als C ist oder größer als B, entsprechend eine andere 01:01:38.960 --> 01:01:40.220 Reihenfolge, das ist alles trivial. 01:01:41.100 --> 01:01:45.500 Also solange das ein Knoten oder zwei Knoten ist, ist das gar kein 01:01:45.500 --> 01:01:48.160 Problem, die kann ich einfach einbauen, ich muss das entsprechend in 01:01:48.160 --> 01:01:49.740 der richtigen Position dort reinschreiben. 01:01:50.980 --> 01:01:58.980 Jetzt ist das Problem, ich habe ein Element, das A möchte ich einfügen 01:01:58.980 --> 01:02:03.280 und ich bin gelandet bei einem Knoten, der hat bereits drei Elemente 01:02:03.280 --> 01:02:03.460 drin. 01:02:05.800 --> 01:02:10.620 Dann darf ich diesen Knoten nicht größer machen und ich muss 01:02:10.620 --> 01:02:11.800 entsprechend umordnen. 01:02:12.700 --> 01:02:13.720 Wie mache ich das? 01:02:14.840 --> 01:02:16.100 Die Idee ist ganz einfach. 01:02:16.100 --> 01:02:24.000 Ich habe hier mein A verglichen mit dem Element X aus dem Knoten oben 01:02:24.000 --> 01:02:24.340 drüber. 01:02:24.900 --> 01:02:26.720 Deswegen bin ich überhaupt nur hier reingekommen. 01:02:28.260 --> 01:02:30.840 Und ich weiß, das A muss irgendwo hier mit rein. 01:02:31.740 --> 01:02:34.500 Ich darf nicht eine neue Ebene aufmachen. 01:02:35.820 --> 01:02:39.220 Ich darf das A, wenn das kleiner als B ist, jetzt nicht einfach, ich 01:02:39.220 --> 01:02:44.180 schreibe das einfach hier unten rein und habe dann hier nochmal zwei 01:02:44.180 --> 01:02:44.480 Blätter. 01:02:44.480 --> 01:02:47.660 Das geht nicht, das wäre eine neue Ebene, die darf ich nicht 01:02:47.660 --> 01:02:48.100 aufmachen. 01:02:48.860 --> 01:02:49.780 Also das geht nicht. 01:02:51.340 --> 01:02:55.340 Das heißt, ich baue im Prinzip das A mit dazu, dann habe ich A, B, C, 01:02:55.460 --> 01:02:55.560 D. 01:02:56.320 --> 01:03:03.640 Und das mittlere Element, das C, das ist der Median dieser Folge A, B, 01:03:03.720 --> 01:03:06.540 C, D, das schiebe ich einfach nach oben. 01:03:08.480 --> 01:03:09.880 Ich baue das da oben mit ein. 01:03:10.060 --> 01:03:11.340 Nehmen wir mal an, da oben ist Platz. 01:03:13.340 --> 01:03:17.300 Das ist also ein Knoten, der noch nicht drei Elemente enthält. 01:03:18.400 --> 01:03:22.320 Das heißt, ich schiebe einfach, ich mache einfach hier die Folge A, B, 01:03:22.400 --> 01:03:27.200 C, D auf, schiebe das C nach oben und habe dann das C, darunter diesen 01:03:27.200 --> 01:03:30.660 Zweiknoten und den Einsknoten und oben drüber das C. 01:03:32.820 --> 01:03:38.420 Das geht natürlich nur, wenn ich da oben auch Platz habe. 01:03:40.400 --> 01:03:43.560 So, das kann ich natürlich beliebig machen, wenn das A irgendwo 01:03:43.560 --> 01:03:44.340 dazwischen liegt. 01:03:44.740 --> 01:03:54.520 Ich schiebe immer den Median, also Median nach oben. 01:03:54.820 --> 01:03:56.580 Das sieht man nach. 01:03:59.820 --> 01:04:02.620 Das ist also etwas vereinfacht ausgedrückt, das, was ich da mache. 01:04:05.220 --> 01:04:08.760 Und dann kann es natürlich sein, dass ich an der Wurzel angelangt bin. 01:04:10.080 --> 01:04:12.380 Also warum, wie komme ich an die Wurzel? 01:04:12.540 --> 01:04:16.000 Es könnte ja sein, wenn ich jetzt hier ein Element da reingeschoben 01:04:16.000 --> 01:04:20.720 habe, hier das C oder da das D, dann kann da das gleiche Problem 01:04:20.720 --> 01:04:21.360 auftauchen. 01:04:21.560 --> 01:04:24.120 Wenn der Knoten schon voll ist, muss ich entsprechend das weiter nach 01:04:24.120 --> 01:04:24.640 oben schieben. 01:04:25.440 --> 01:04:30.020 Und irgendwann, wenn ich also überall solche vollen Knoten gehabt 01:04:30.020 --> 01:04:33.800 habe, bin ich an der Wurzel angelangt, das ist also unten irgendwas 01:04:33.800 --> 01:04:34.240 drunter. 01:04:35.540 --> 01:04:40.780 Und dann schiebe ich auch den Median nach oben. 01:04:40.860 --> 01:04:46.480 Das heißt, wenn ich an der Wurzel mehr einfügen muss, dann erzeuge ich 01:04:46.480 --> 01:04:50.760 einfach eine neue Wurzel und unten drunter sind die beiden Knoten, die 01:04:50.760 --> 01:04:51.800 hier zu sehen sind. 01:04:52.740 --> 01:04:58.200 Und wenn das also hier, diese hier angedeutet vier Blätter, können 01:04:58.200 --> 01:05:02.960 natürlich auch einfach vier Teilbäume sein. 01:05:04.240 --> 01:05:08.760 T1, T2, T3, T4 und die wären ja hier nach wie vor. 01:05:10.920 --> 01:05:19.940 Nein, die sind, Entschuldigung, das sind meine vier Teile und jetzt 01:05:19.940 --> 01:05:20.920 werden die irgendwie aufgeteilt. 01:05:22.220 --> 01:05:26.160 In dem Fall schiebe ich also, genau, das eine nach oben, dann hätte 01:05:26.160 --> 01:05:26.800 ich... 01:05:32.850 --> 01:05:34.290 Was habe ich denn jetzt hier? 01:05:40.120 --> 01:05:43.160 Ich schiebe das Element nach oben, 01:05:51.220 --> 01:05:54.700 vier Teilbäume, schiebe da eins nach oben. 01:06:01.780 --> 01:06:03.980 Jetzt bin ich irritiert, warum bin ich hier irritiert? 01:06:03.980 --> 01:06:04.720 T1. 01:06:17.300 --> 01:06:17.800 Ja... 01:06:26.370 --> 01:06:27.370 Ich bin... 01:06:33.230 --> 01:06:33.730 Ja... 01:06:37.850 --> 01:06:38.350 Richtig. 01:06:39.790 --> 01:06:43.670 Genau, das ist hier, das ist im Prinzip, das ist der Teil hier, diese 01:06:43.670 --> 01:06:47.850 beiden hier, das ist im Prinzip, da wird's aufgeteilt, dass hier die 01:06:47.850 --> 01:06:57.530 beiden zusammen waren im Prinzip die T1 und das ist hier T2, T3, T4. 01:06:58.450 --> 01:06:58.890 Danke. 01:07:00.190 --> 01:07:03.210 Auf jeden Fall kann man das auf die Art und Weise machen, ich schiebe 01:07:03.210 --> 01:07:05.650 den Median immer nach oben, das steht hier sogar schon drauf auf der 01:07:05.650 --> 01:07:10.230 Folie und auf die Art und Weise kann ich also dafür sorgen, dass ich 01:07:10.230 --> 01:07:14.350 nur an der Wurzel, wenn ich da angelangt bin, eine neue Ebene erzeuge 01:07:14.350 --> 01:07:18.290 und der ganze Rest, der bleibt also dann gleich. 01:07:18.290 --> 01:07:22.550 Die Situation 3 und 4 sind natürlich problematisch, wenn die Vorgänger 01:07:22.550 --> 01:07:27.670 auch 4 Knoten sind, dann muss man entsprechend das aufbauen. 01:07:27.770 --> 01:07:29.630 Wir haben gesehen, das ist etwas umständlich. 01:07:29.730 --> 01:07:33.810 Wir haben ja gesehen hier, da hatte ich gerade eben gestockt, ich muss 01:07:33.810 --> 01:07:35.270 dann hier ein bisschen mehr umbauen. 01:07:35.770 --> 01:07:36.910 Das möchte ich eigentlich vermeiden. 01:07:38.070 --> 01:07:42.490 Das ist die Frage, wie kann ich vermeiden, dass der Knoten, der oben 01:07:42.490 --> 01:07:45.950 drüber ist, kein voller Knoten ist. 01:07:46.610 --> 01:07:55.190 Das mache ich einfach so, dass ich einen vollen Knoten, sobald ich den 01:07:55.190 --> 01:07:58.730 beim Runterlaufen, beim Suchen nach der Einfügeposition für ein 01:07:58.730 --> 01:08:02.390 Element, einfach aufteile. 01:08:02.650 --> 01:08:07.090 Wenn ich einen vollen Knoten habe, mache ich daraus zwei Knoten. 01:08:07.190 --> 01:08:09.970 Das heißt, wenn ich einen solchen Knoten gefunden habe, hier einen 01:08:09.970 --> 01:08:16.210 vollen Knoten, der hier vier Nachfolgebäume hat, dann wandle ich den 01:08:16.210 --> 01:08:16.930 einfach um. 01:08:18.230 --> 01:08:21.910 Das ist ja im Prinzip logisch, immer noch ein solch großer Knoten, 01:08:22.390 --> 01:08:26.390 aber ich habe ihn aufgeteilt in drei 1-Knoten. 01:08:27.610 --> 01:08:34.150 Und wenn ich jetzt von irgendeinem dieser Teilbäume T1, T2, T3 oder T4 01:08:34.150 --> 01:08:37.370 nach oben laufe, habe ich auf jeden Fall Platz, um ein Element 01:08:37.370 --> 01:08:38.030 einzufügen. 01:08:40.190 --> 01:08:44.990 Ja, es könnte sein, dass dann hier unten drunter irgendwelche Knoten 01:08:44.990 --> 01:08:46.690 sind, die noch nicht ganz voll sind, das ist aber egal. 01:08:46.830 --> 01:08:50.830 Auf jeden Fall weiß ich, oben drüber ist kein voller Knoten. 01:08:51.890 --> 01:08:55.390 Und entsprechend, wenn ich hier irgendwo mittendrin bin, ich bin 01:08:55.390 --> 01:08:59.710 runtergelaufen, hier ist jetzt wieder so ein, könnte ja das T4 genauso 01:08:59.710 --> 01:09:03.730 eine Situation sein, dass ich wieder einen vollen Knoten habe, dann 01:09:03.730 --> 01:09:06.010 würde ich auch wieder einfach das mittlere Element nach oben schieben. 01:09:06.010 --> 01:09:10.150 Oben drüber ist jetzt da ein Knoten, der genügend Platz hat. 01:09:11.690 --> 01:09:16.730 Und auf die Art und Weise weiß ich, auf dem Pfad nachher von einem 01:09:16.730 --> 01:09:24.830 Blatt bis hoch zur Wurzel, habe ich maximal Knoten, die zwei Schlüssel 01:09:24.830 --> 01:09:25.350 enthalten. 01:09:25.490 --> 01:09:28.970 Es ist kein Knoten da auf diesem Pfad, der drei Schlüssel enthält. 01:09:30.030 --> 01:09:34.530 Und damit weiß ich, mein Einfügen endet sehr schnell. 01:09:35.450 --> 01:09:39.610 Ich kann das also im Prinzip direkt unten dann machen. 01:09:41.210 --> 01:09:46.130 Also entsprechend hier wird jeweils das dann nach oben geschoben, das 01:09:46.130 --> 01:09:48.010 mittlere Element jeweils nach oben, das sind nur die verschiedenen 01:09:48.010 --> 01:09:52.250 Situationen, je nachdem, wo ich gelandet bin, dann habe ich eben 01:09:52.250 --> 01:09:55.310 entsprechend hier Elemente drin. 01:09:55.510 --> 01:10:00.770 Also es kann eben sein, kann natürlich passieren, wenn ich hier 01:10:00.770 --> 01:10:04.810 runtergelaufen bin, ich habe hier oben ein Zweiknoten gehabt und unten 01:10:04.810 --> 01:10:10.010 drunter ist ein voller Knoten, dann schiebe ich hier ein Element nach 01:10:10.010 --> 01:10:15.130 oben und dann habe ich jetzt auf einmal hier einen vollen Knoten. 01:10:16.290 --> 01:10:21.530 Aber unten drunter sind welche, die haben maximal ein Element drin. 01:10:21.990 --> 01:10:28.110 Das heißt, ich kann garantieren, dass ich dieses Problem, das wir 01:10:28.110 --> 01:10:31.690 vorgesehen hatten, ich muss eventuell immer wieder oben drüber etwas 01:10:31.690 --> 01:10:35.170 aufspalten, wenn ich etwas eingefügt habe, das kann ich reduzieren. 01:10:35.910 --> 01:10:40.310 Ich habe also beim Top-Down-Teilen jeweils zwei neue Zweiknoten 01:10:40.310 --> 01:10:44.170 erzeugt und höchstens einen neuen Vierknoten. 01:10:46.250 --> 01:10:52.170 Das heißt, die Suche endet in einem neuen Zweiknoten oder einem alten 01:10:52.170 --> 01:10:54.390 Zwei - oder Dreiknoten. 01:10:55.570 --> 01:10:59.710 Und wenn das ein Zwei- oder Dreiknoten ist, kann ich direkt einfügen 01:10:59.710 --> 01:11:00.990 ohne neues Aufteilen. 01:11:01.530 --> 01:11:05.110 Das heißt, diesen ganzen Aufwand, um etwas umzuordnen in dem Baum, 01:11:05.470 --> 01:11:09.830 habe ich bei dem Suchen bereits gemacht und ich muss nicht nach dem 01:11:09.830 --> 01:11:12.450 Einfügen dann wieder nach oben laufen. 01:11:13.290 --> 01:11:20.830 Das heißt, hier in dem Baum, auf dem Weg hier durch, jedes Mal, wenn 01:11:20.830 --> 01:11:24.830 da ein großer Knoten war, dann werden die halt aufgeteilt und ich habe 01:11:24.830 --> 01:11:28.150 dann den ganzen Aufwand, nur beim Runterlaufen zu machen und muss 01:11:28.150 --> 01:11:29.810 anschließend nur noch einfach einfügen. 01:11:31.270 --> 01:11:35.890 Hier ist ein Beispiel nochmal für so einen Suchbaum, für einen 2-3-4 01:11:35.890 --> 01:11:36.270 -Baum. 01:11:37.050 --> 01:11:42.810 Sie sehen, hier habe ich jetzt also nicht alles verschiedene Elemente, 01:11:42.930 --> 01:11:47.010 sondern ich habe hier, das E taucht natürlich hier mehrfach auf, Sie 01:11:47.010 --> 01:11:50.250 sehen hier diese Aufteilung. 01:11:51.310 --> 01:11:58.630 Ich habe einen 2-3-4-Baum mit in diesem Fall Höhe gerade 3, je 01:11:58.630 --> 01:11:59.590 nachdem, wie ich hier zähle. 01:11:59.770 --> 01:12:06.170 Also ich habe die Pfadlänge hier bis zu den Blättern ist jeweils 3 und 01:12:06.170 --> 01:12:08.110 die Knoten sind dann unterschiedlich dick. 01:12:09.810 --> 01:12:13.730 Wenn ich das Ganze mit einem binären Suchbaum machen würde, dann würde 01:12:13.730 --> 01:12:14.510 der so aussehen. 01:12:16.730 --> 01:12:22.150 Und der wäre halt nicht so effizient in dem Fall. 01:12:23.090 --> 01:12:25.710 Also 2-3-4-Baum sieht ganz ordentlich aus. 01:12:25.830 --> 01:12:29.070 Der Aufwand pro Knoten ist ein bisschen unterschiedlich, aber 01:12:29.070 --> 01:12:31.790 insgesamt komme ich hier mit Log N immer noch aus. 01:12:33.270 --> 01:12:39.590 Also die wichtigen Eigenschaften sind, dass ich hier jeweils bei allen 01:12:39.590 --> 01:12:43.750 Bäumen gleiche Pfadlänge habe, kleiner gleich Log N. 01:12:45.210 --> 01:12:49.630 Wenn ich jetzt dieses Top-Down-Teilen mache, das Runterlaufen, dabei 01:12:49.630 --> 01:13:02.730 jeweils teilen, wenn ich beliebigen 2-3-4-Baum habe, dann werden pro 01:13:02.730 --> 01:13:07.370 Einfügeoperation maximal Log N 4 Knoten geteilt. 01:13:07.370 --> 01:13:13.090 Ich habe ja maximal Log N Knoten auf dem Weg von der Wurzel zu dem 01:13:13.090 --> 01:13:13.410 Blatt. 01:13:13.950 --> 01:13:18.210 Wenn ich aber vorher schon immer Top-Down-Teilen gemacht habe, dann 01:13:18.210 --> 01:13:25.770 habe ich auf jedem Weg von der Wurzel zu einem Blatt maximal einen 01:13:25.770 --> 01:13:27.370 vollen Knoten. 01:13:28.930 --> 01:13:32.550 Und dadurch habe ich also den Aufwand deutlich reduziert. 01:13:32.990 --> 01:13:35.450 Nur der Baum wird eventuell ein bisschen größer. 01:13:35.450 --> 01:13:39.690 Ich nutze diese Möglichkeit, die Höhe zu reduzieren, nicht ganz aus, 01:13:40.310 --> 01:13:42.670 weil ich dafür sorge, dass die Knoten nicht zu groß werden, dass auf 01:13:42.670 --> 01:13:46.130 jedem Pfad maximal ein voller Knoten ist. 01:13:47.350 --> 01:13:50.930 Und jetzt die Frage, was mache ich eigentlich, wenn ich löschen 01:13:50.930 --> 01:13:51.330 möchte? 01:13:52.310 --> 01:13:55.930 Und da kriegen wir dann ähnliche Probleme, das ist aber nicht ganz 01:13:55.930 --> 01:13:56.310 trivial. 01:13:58.130 --> 01:14:02.190 Deswegen schieben wir das normalerweise in die Übung, weil das hier 01:14:02.190 --> 01:14:03.670 etwas länger dauert, das darzustellen. 01:14:03.670 --> 01:14:05.830 Aber die Ideen stelle ich trotzdem vor. 01:14:09.050 --> 01:14:14.390 Wenn ich ein Element rauslöschen möchte, dann habe ich hier meinen 01:14:14.390 --> 01:14:19.830 Baum, ich habe hier irgendwo ein Element gefunden, das möchte ich 01:14:19.830 --> 01:14:20.450 rauslöschen. 01:14:21.070 --> 01:14:22.710 Und der Baum ist eventuell noch ein bisschen größer. 01:14:23.770 --> 01:14:26.230 Jetzt ist die Frage, wie verändert sich dadurch die Struktur meines 01:14:26.230 --> 01:14:26.650 Baumes? 01:14:27.730 --> 01:14:32.210 Ich möchte das erste A aus einem 2-3-4-Baum-S rauslöschen. 01:14:32.210 --> 01:14:35.610 Das Ergebnis muss wieder ein vollständiger 2-3-4-Baum sein. 01:14:36.570 --> 01:14:40.470 Wenn das A gar nicht drin ist, brauche ich nichts zu tun, dann muss 01:14:40.470 --> 01:14:43.030 ich nur einmal suchen, stelle fest, das Ding ist gar nicht drin, ich 01:14:43.030 --> 01:14:45.450 bin bei einem Blatt gelandet, ich muss nichts tun. 01:14:46.110 --> 01:14:48.830 Der andere Fall ist, ich muss was tun, dann habe ich die Situation, 01:14:48.950 --> 01:14:50.670 die ich gerade eben schon leicht skizziert habe. 01:14:51.930 --> 01:14:55.350 Ich habe irgendwo das A gefunden und das soll raus. 01:14:55.350 --> 01:15:04.370 Wenn ich das A rausnehme, dann muss ich dafür sorgen, das geht erst 01:15:04.370 --> 01:15:06.070 aus diesem Knoten hier oben raus. 01:15:06.870 --> 01:15:10.950 Ich habe aber hier unten einen Teilbaum, das sind Elemente, die sind 01:15:10.950 --> 01:15:16.550 größer, gleich diesem A, und kleiner als das darauf folgende Element, 01:15:16.670 --> 01:15:19.470 nennen wir das mal hier einfach x, da oben. 01:15:21.550 --> 01:15:25.770 Das heißt, ich brauche ein neues Vergleichselement, damit das hier 01:15:25.770 --> 01:15:26.690 richtig funktioniert. 01:15:27.770 --> 01:15:32.470 Und dafür nehme ich einfach das nächstgrößere Element in meinem Baum, 01:15:33.390 --> 01:15:38.770 und das ist das am linkesten stehende Element in diesem Teilbaum da 01:15:38.770 --> 01:15:39.350 unten drunter. 01:15:40.050 --> 01:15:41.090 Das ist dieses Element B. 01:15:41.810 --> 01:15:45.230 Das heißt, das nächstgrößere Element steht dort unten links in dem 01:15:45.230 --> 01:15:45.810 Teilbaum. 01:15:46.710 --> 01:15:48.190 Das muss ich nur da oben hinschieben. 01:15:50.290 --> 01:15:53.730 Damit habe ich jetzt hier oben das Problem gelöst. 01:15:54.250 --> 01:15:55.750 Da ist das B gelandet. 01:15:56.290 --> 01:15:59.230 Dann habe ich aber hier das Problem, dass ich da unten natürlich ein 01:15:59.230 --> 01:16:00.410 Element rausnehme. 01:16:01.130 --> 01:16:05.930 Es darf sich dadurch nicht die Höhe meines Baumes verringern, also die 01:16:05.930 --> 01:16:07.190 Fahrtlänge in dem Fall. 01:16:08.290 --> 01:16:14.150 Das heißt, wenn das B in einem Drei- oder Vierknoten drin war, das 01:16:14.150 --> 01:16:17.270 heißt, da waren zwei Schlüssel oder drei Schlüssel drin, ist es gar 01:16:17.270 --> 01:16:17.990 kein Problem. 01:16:18.670 --> 01:16:22.170 Dann kann ich ja das B einfach rausstreichen, es bleibt das nächste 01:16:22.170 --> 01:16:25.410 Element C übrig und vielleicht noch ein weiteres. 01:16:26.110 --> 01:16:30.890 Und ich habe hier entsprechend meine Blätter unten dran. 01:16:31.590 --> 01:16:36.390 Dadurch habe ich kein Problem mit meiner Fahrtlängenrestriktion. 01:16:37.630 --> 01:16:42.830 Wenn das Ganze ein kleinstmöglicher Knoten war, das B war alleine da 01:16:42.830 --> 01:16:44.310 drin, was mache ich denn dann? 01:16:44.310 --> 01:16:52.950 Dann, naja, ich weiß, dass da ist ein Element C oben drüber, rechts 01:16:52.950 --> 01:16:58.130 daneben ist noch irgendein Knoten. 01:16:58.590 --> 01:17:00.690 Ich habe ja auf jeden Fall Nachbarknoten. 01:17:02.190 --> 01:17:08.770 Und dann ziehe ich einfach das C runter und schiebe das D nach oben. 01:17:11.330 --> 01:17:13.070 Natürlich habe ich dann das gleiche Problem wieder. 01:17:13.150 --> 01:17:14.510 Das heißt, das zieht sich hier so ein bisschen durch. 01:17:16.630 --> 01:17:22.290 Und wenn das Ganze wieder ein, wenn das B in einem Zweiknoten ist und 01:17:22.290 --> 01:17:24.830 rechts daneben ein Drei- oder Vierknoten, bin ich dann auch fertig. 01:17:25.370 --> 01:17:29.270 Wenn das noch wieder ein kleiner Knoten ist, muss ich wieder 01:17:29.270 --> 01:17:30.110 weitermachen. 01:17:30.450 --> 01:17:33.790 Aber ich bin eben am unteren Rand und jetzt kann es sein, dass ich 01:17:33.790 --> 01:17:35.370 dann... 01:17:35.370 --> 01:17:37.970 Trotzdem, ich habe ja hier oben etwas rausgezogen. 01:17:38.150 --> 01:17:43.790 Wenn dann hier oben ein kleinerer, wenn ich da was rausnehme, wenn das 01:17:43.790 --> 01:17:48.350 nur ein kleinstmöglicher Knoten war, ich habe natürlich das D nach 01:17:48.350 --> 01:17:52.350 oben geschoben, aber es kann passieren, dass ich eben wirklich etwas 01:17:52.350 --> 01:17:53.570 ganz rausschiebe. 01:17:53.710 --> 01:17:57.610 Dann habe ich hier unten, also das B ist ein Zweiknoten, das ist der 01:17:57.610 --> 01:17:59.330 rechte Nachbar auch ein Zweiknoten. 01:17:59.330 --> 01:18:06.270 Dann habe ich hier das C, ich habe hier C und D jetzt einfach 01:18:06.270 --> 01:18:10.550 zusammengepackt und habe das Element C da oben rausgenommen. 01:18:13.490 --> 01:18:17.250 Wenn das jetzt ein kleiner Knoten war, dann kann das sein, dass ich 01:18:17.250 --> 01:18:20.050 noch wieder das gleiche Problem nach oben weiter fortführen muss. 01:18:20.550 --> 01:18:23.690 Und auf die Art und Weise habe ich also hier auf der nächsten Ebene 01:18:23.690 --> 01:18:25.030 eventuell wieder so etwas zu tun. 01:18:25.030 --> 01:18:32.610 Und wenn das hier oben die Wurzel war, was hier steht, dann würde ich 01:18:32.610 --> 01:18:41.430 im Prinzip die Wurzel wegnehmen und hätte anschließend in dem Fall, 01:18:41.770 --> 01:18:45.650 dass das die Wurzel ist, dann verringert sich die Höhe des Baumes um 01:18:45.650 --> 01:18:45.950 eins. 01:18:47.530 --> 01:18:49.870 Aber das wird schon ein aufwändiger Prozess und Sie können sich 01:18:49.870 --> 01:18:52.670 vorstellen, wenn wir eben gerade dieses Top-Down-Teilen gemacht haben 01:18:52.670 --> 01:18:56.610 und wir müssen dann wieder löschen, kann diese Situation durchaus 01:18:56.610 --> 01:18:59.930 auftauchen, dass wir ziemlich bis nach oben laufen müssen und dass wir 01:18:59.930 --> 01:19:03.350 nicht genügend dicke Knoten oben drüber haben, in denen ich einfach 01:19:03.350 --> 01:19:04.770 etwas löschen kann. 01:19:05.550 --> 01:19:06.990 Also das hat alles seine Vor- und Nachteile. 01:19:08.270 --> 01:19:11.730 Also diese Operation ist ein bisschen aufwendig, kann man aber 01:19:11.730 --> 01:19:12.950 algorithmisch alles hinbekommen. 01:19:14.150 --> 01:19:18.130 Und der Aufwand kann in Log N immer noch bleiben, das ist also alles 01:19:18.130 --> 01:19:22.150 machbar und jetzt haben wir also, wie gesagt, das habe ich jetzt nicht 01:19:22.150 --> 01:19:24.890 vollständig durchgeführt, bis zum Ende des Anderen haben wir 01:19:24.890 --> 01:19:25.630 eigentlich relativ durchdekliniert. 01:19:26.850 --> 01:19:31.130 Die Aufwände fürs Suchen, fürs Einfügen und fürs Löschen sind in 01:19:31.130 --> 01:19:37.050 solchen 2, 3, 4 Bäumen jeweils in logarithmischer Zeit durchzuführen. 01:19:38.910 --> 01:19:42.070 Oder die Aufwände sind logarithmisch in der Anzahl der Schlüsse. 01:19:42.590 --> 01:19:44.850 Jetzt ist die Frage, wie kann ich das Ganze implementieren. 01:19:44.910 --> 01:19:46.890 Stellen Sie sich vor, Sie müssen sich eine Datenstruktur überlegen, 01:19:46.930 --> 01:19:47.810 wie Sie das implementieren. 01:19:47.810 --> 01:19:53.070 Dann definieren Sie irgendeine Klasse und Sie haben dort Attribute 01:19:53.070 --> 01:19:57.490 drin, die Ihnen angeben, Sie brauchen also 3 unterschiedliche 01:19:57.490 --> 01:19:58.190 Knotentypen. 01:19:58.750 --> 01:20:02.110 Wenn Sie das Aufteilen machen von den 4 Knoten, dann müssen Sie 2 neue 01:20:02.110 --> 01:20:06.970 Knoten erzeugen, 2 neue Objekte, die jeweils von einem anderen Typ 01:20:06.970 --> 01:20:07.330 sind. 01:20:07.750 --> 01:20:10.090 Und Sie müssen sich immer merken, ob Sie jetzt den ersten, zweiten 01:20:10.090 --> 01:20:11.570 oder dritten Nachfolger wählen. 01:20:12.570 --> 01:20:15.030 Die Datenstruktur wird ein bisschen kompliziert. 01:20:15.030 --> 01:20:18.290 Können Sie sich gerne überlegen, wie Sie das in Java implementieren 01:20:18.290 --> 01:20:18.650 würden. 01:20:19.870 --> 01:20:22.370 Sie müssen halt Attribute drin haben, die Ihnen erlauben, diese 01:20:22.370 --> 01:20:25.030 Unterscheidung zu machen und entsprechend dann jeweils zu verzweigen. 01:20:27.470 --> 01:20:34.150 Und dieser Vorteil, dass ich eben dann nur so schön gleiche Längen auf 01:20:34.150 --> 01:20:37.590 dem Faden habe, der geht so ein bisschen verloren durch etwas 01:20:37.590 --> 01:20:41.510 aufwendige Datenstrukturen und auch die Einzeloperationen sind nicht 01:20:41.510 --> 01:20:42.250 wirklich einfach. 01:20:43.570 --> 01:20:49.170 Und jetzt ist die Idee, dass man die 2-3-4-Bäume einfacher darstellt. 01:20:49.790 --> 01:20:51.650 Und diese Idee ist ziemlich genial. 01:20:54.230 --> 01:20:57.890 Wir hatten das gerade eben schon mal gesehen, da hatte ich Ihnen 01:20:57.890 --> 01:21:04.450 aufgemalt, wenn ich so einen, ich male mal hier A, B, C, 1, 2, 3, 4, 01:21:04.530 --> 01:21:11.910 wenn Sie so etwas haben, solch einen Knoten oder ich male hier anders 01:21:11.910 --> 01:21:18.650 Bäume 1, 2, 3, 4 dahin, dann kann ich das auch bauen, gleich 01:21:18.650 --> 01:21:21.730 alternativ auf diese Art und Weise. 01:21:21.910 --> 01:21:24.750 Und ich habe hier 1, 2, 3, 4. 01:21:26.130 --> 01:21:31.630 Und dann ist im Prinzip diese Struktur und die Struktur hier, das sind 01:21:31.630 --> 01:21:33.870 eigentlich zwei äquivalente Darstellungen. 01:21:33.870 --> 01:21:37.550 Die Pfadlänge ist hier etwas größer, in dem rechten Baum. 01:21:39.470 --> 01:21:41.490 Und genau das will man jetzt anwenden. 01:21:43.070 --> 01:21:48.010 Und ich tue einfach so, als könnte ich einen solchen dicken Knoten auf 01:21:48.010 --> 01:21:54.590 diese Art und Weise darstellen und ich markiere diese Kanten hier 01:21:54.590 --> 01:21:57.650 einfach durch eine andere Farbe. 01:21:58.090 --> 01:22:01.430 Ich verwende zum Annotieren nur Rot, deswegen könnte ich das jetzt 01:22:01.430 --> 01:22:02.330 hier unterschiedlich machen. 01:22:02.330 --> 01:22:07.930 Ich sage einfach, dieses hier sind jetzt rote Kanten und das sind 01:22:07.930 --> 01:22:09.450 schwarze Kanten. 01:22:10.750 --> 01:22:12.450 Und das hier waren auch alles schwarze Kanten. 01:22:14.670 --> 01:22:17.490 Und die roten Kanten, sage ich, das sind interne Kanten, die 01:22:17.490 --> 01:22:20.310 interessieren mich nicht, die zähle ich nicht, ich zähle nur die 01:22:20.310 --> 01:22:21.070 schwarzen Kanten. 01:22:22.350 --> 01:22:26.010 Und wenn ich das auf die Art und Weise mache, dann könnte ich ja, weil 01:22:26.010 --> 01:22:30.890 ich ja logisch einen solchen dicken Knoten durch solche roten 01:22:30.890 --> 01:22:34.670 darstellen kann, ist die Anzahl der schwarzen Kanten auf dem Weg von 01:22:34.670 --> 01:22:38.870 der Wurzel zu den Blättern genauso die gleiche wie die Anzahl der 01:22:38.870 --> 01:22:40.590 Kanten in dem 2-3-4-Baum. 01:22:41.950 --> 01:22:46.090 Und dann sieht das zunächst mal noch nicht einfacher aus, ich habe 01:22:46.090 --> 01:22:49.250 jetzt auf einmal noch mehr Knoten hier drin, aber Sie werden gleich 01:22:49.250 --> 01:22:55.390 sehen, bei den Rot-Schwarz-Bäumen, da kann ich jetzt einen 2-3-4-Baum 01:22:55.390 --> 01:23:00.530 einfach darstellen, wenn ich einen einfachen Knoten habe, ist das der 01:23:00.530 --> 01:23:01.890 gleiche im Rot-Schwarz-Baum. 01:23:02.330 --> 01:23:06.310 Wenn ich hier zwei Schlüssel drin habe, dann baue ich daraus entweder 01:23:06.310 --> 01:23:13.310 so einen Knoten, bei dem diese hier so nebeneinander liegen oder so. 01:23:13.850 --> 01:23:17.010 Von außen ist das nicht sichtbar, eine rote Kante da drin. 01:23:18.970 --> 01:23:21.490 Entweder ist A die Wurzel oder B ist die Wurzel. 01:23:22.230 --> 01:23:26.450 Das ist eine Alternative, die man dann bei den Operationen 01:23:26.450 --> 01:23:30.810 entsprechend ausnutzen kann oder mit der man arbeiten muss. 01:23:31.610 --> 01:23:36.170 Jetzt habe ich den dicksten Knoten und dann habe ich halt hier, wie 01:23:36.170 --> 01:23:41.590 gesagt, meinen neuen Rot-Schwarz-Baum, der halt schwarze und rote 01:23:41.590 --> 01:23:45.030 Kanten hat und ich habe im Prinzip die gleiche Struktur. 01:23:46.770 --> 01:23:50.470 Was brauche ich jetzt, um solche Knoten darzustellen? 01:23:52.270 --> 01:23:57.610 Ich brauche ein Objekt, das ist ein Knoten, und diese Knoten kann ich 01:23:57.610 --> 01:24:05.870 danach charakterisieren, ob sie von einer roten Kante oder von einer 01:24:05.870 --> 01:24:07.410 schwarzen Kante erreicht werden. 01:24:09.150 --> 01:24:12.730 Das heißt, ich brauche nur bei den Knoten anzugehen, dieses B hier 01:24:12.730 --> 01:24:18.030 bekommt einfach ein Bit, das sagt, hier habe ich eine rote Kante, die 01:24:18.030 --> 01:24:21.970 reinläuft, und bei dem A, da hätte ich eine schwarze Kante, die 01:24:21.970 --> 01:24:22.570 reinläuft. 01:24:22.930 --> 01:24:27.290 Das heißt, ich markiere im Prinzip die Knoten mit der in sie 01:24:27.290 --> 01:24:31.670 reinlaufenden Kantenfarbe und habe dadurch nur ein Bit, um zu 01:24:31.670 --> 01:24:34.110 unterscheiden, ob ein Knoten bzw. 01:24:34.390 --> 01:24:37.190 die reinlaufende Kante rot oder schwarz ist. 01:24:38.850 --> 01:24:43.070 Und wenn ich also jetzt eine Veränderung mache, ich lösche oder ich 01:24:43.070 --> 01:24:49.530 füge ein neues Element ein, wir hatten vorher gesehen, da mussten wir, 01:24:49.770 --> 01:24:52.490 wenn wir in so einen dicken Knoten was einfügen, mussten wir daraus 01:24:52.490 --> 01:24:55.310 dann drei neue Knoten bauen. 01:24:56.930 --> 01:25:02.990 Ich habe Knoten im Prinzip alle die gleiche Struktur, nur das eine Bit 01:25:02.990 --> 01:25:07.410 muss ich entsprechend wählen, ob das eine rote oder schwarze Kante 01:25:07.410 --> 01:25:08.430 wird, die da reinläuft. 01:25:09.910 --> 01:25:14.650 Und das ist deutlich einfacher, als wenn ich umbauen muss von zwei 01:25:14.650 --> 01:25:17.810 Knoten auf drei Knoten, auf vier Knoten oder von vier Knoten wieder 01:25:17.810 --> 01:25:20.630 auf zwei und drei Knoten oder ähnliches. 01:25:21.330 --> 01:25:26.430 Also die Operationen sind einfacher, alle Blätter haben die gleiche 01:25:26.430 --> 01:25:29.710 schwarze Tiefe, kleiner gleich lockend, daran ändert sich gar nichts. 01:25:31.170 --> 01:25:34.730 Ein Bit pro Knoten reicht, um ihn als rot oder schwarz zu kennzeichnen 01:25:34.730 --> 01:25:37.790 und damit habe ich eine einfache Datenstruktur, eine einfache 01:25:37.790 --> 01:25:42.050 Operation, eine einfache Implementierung auf dieser Struktur. 01:25:44.390 --> 01:25:50.330 Und jetzt kann ich also hier die Operationen auf Rot-Schwarz-Bäumen 01:25:50.330 --> 01:25:51.190 mir angucken. 01:25:51.750 --> 01:25:57.910 Beim Suchen kleiner gleich zweimal lockend vergleiche. 01:25:58.470 --> 01:26:02.450 Könnte ja sein, dass ich genauso viele rote wie schwarze Kanten habe. 01:26:02.450 --> 01:26:04.150 Ich musste einmal durchlaufen. 01:26:05.290 --> 01:26:08.070 Das ist genau die Anzahl der Vergleiche, die ich vorher bei den zwei, 01:26:08.150 --> 01:26:09.250 drei, vier Bäumen auch hatte. 01:26:09.730 --> 01:26:12.510 Da hatte ich nicht rote und schwarze Kanten, sondern musste innerhalb 01:26:12.510 --> 01:26:15.810 eines Knotens mehrere Elemente vergleichen. 01:26:16.390 --> 01:26:20.330 Das ist jetzt hier praktisch aufgeteilt auf rote und schwarze Kanten. 01:26:21.550 --> 01:26:26.870 Das Einfügen geht hier ganz einfach. 01:26:27.070 --> 01:26:33.010 Wir haben hier zum Beispiel, wenn wir einfügen wollen, hier hätten wir 01:26:33.010 --> 01:26:35.590 dieses hier als einen Knoten. 01:26:36.630 --> 01:26:40.330 Das wäre ein voller Knoten, ein Vierknoten und oben drüber ein 01:26:40.330 --> 01:26:41.530 Zweiknoten. 01:26:42.470 --> 01:26:44.110 Jetzt wird der umgebaut. 01:26:46.730 --> 01:26:51.150 Ich schiebe also ein, mache hier einen Farbwechsel. 01:26:52.270 --> 01:26:57.110 Jetzt habe ich hier diese beiden, ist ein Element nach oben geschoben. 01:26:57.110 --> 01:27:08.170 Dann habe ich oben drüber, also vorher habe ich hier A, B, C, D. 01:27:09.110 --> 01:27:16.190 Jetzt habe ich hier A, C, B, D. 01:27:16.790 --> 01:27:18.790 Ich verändere die gar nicht, ich muss nur die Farben ändern. 01:27:20.590 --> 01:27:26.890 Und ich habe jetzt einfach die Farbe hier oben von C verändert in Rot 01:27:26.890 --> 01:27:29.770 und die Farbe von B und D in Schwarz verändert. 01:27:31.030 --> 01:27:33.510 Und damit habe ich die Umgruppierung gemacht. 01:27:34.350 --> 01:27:35.450 Eine ganz einfache Operation. 01:27:36.490 --> 01:27:38.050 Und das sah vorher so kompliziert aus. 01:27:38.630 --> 01:27:40.310 Ich schiebe das mittlere Element nach oben. 01:27:41.250 --> 01:27:43.590 Das mittlere Element nach oben schieben ist jetzt ganz einfach. 01:27:44.610 --> 01:27:47.650 Ich mache nur einen Farbwechsel bei den entsprechenden Knoten. 01:27:48.930 --> 01:27:52.010 Und damit habe ich also eine sehr effiziente Datenstruktur gefunden, 01:27:52.150 --> 01:27:56.310 mit einfachen Operationen, um einen Baum zu realisieren, bei dem ich 01:27:56.310 --> 01:28:01.610 garantiert meine Log N oder zwei Log N Vergleiche im schlechtesten 01:28:01.610 --> 01:28:02.310 Fall habe. 01:28:02.810 --> 01:28:06.510 Und ich habe die Höhenbalancierung drin, also alles recht schön. 01:28:07.830 --> 01:28:11.710 Es gibt Sonderfälle, die man sich anschauen muss, die ich hier jetzt 01:28:11.710 --> 01:28:12.410 nicht betrachte. 01:28:13.370 --> 01:28:17.550 Das Löschen wird entsprechend auch hier jeweils dann implementiert. 01:28:17.870 --> 01:28:20.930 Wieder ein bisschen komplizierter als das, was so ähnlich wie vorher. 01:28:21.550 --> 01:28:25.850 Der Aufwand insgesamt für Einfügen, Löschen und Suchen ist Log N. 01:28:26.770 --> 01:28:31.210 Und ich habe damit eine Suchstruktur, die sich alles sehr gut 01:28:31.210 --> 01:28:31.690 rausstellt. 01:28:31.770 --> 01:28:32.770 Sie haben da hinten eine Frage. 01:28:33.310 --> 01:28:34.390 Ihnen ist was nicht klar. 01:28:44.600 --> 01:28:50.900 Also ich kann dieses Top-Down teilen zum Beispiel, was wir gemacht 01:28:50.900 --> 01:28:51.040 haben. 01:28:51.100 --> 01:28:53.180 Das ist im Prinzip das Top-Down teilen, was ich hier mache. 01:28:55.140 --> 01:29:02.280 Wenn ich hier umbauen möchte, ich möchte diesen dicken Knoten zu zwei 01:29:02.280 --> 01:29:04.600 kleinen machen und einen nach oben schieben. 01:29:04.920 --> 01:29:06.680 Das habe ich durch diese Operation erreicht. 01:29:08.620 --> 01:29:12.960 Und ich hätte vorher eine Datenstruktur gehabt, wo ich einen 01:29:12.960 --> 01:29:17.080 Vierknoten umbauen muss in zwei Zweiknoten. 01:29:17.380 --> 01:29:20.620 Und oben drüber, der Zweiknoten wird zu einem Dreiknoten. 01:29:22.880 --> 01:29:27.000 Das heißt, ich habe eine Reihe etwas aufwendiger Operationen zu 01:29:27.000 --> 01:29:27.220 machen. 01:29:27.860 --> 01:29:31.160 Die Datenstruktur, auf der ich arbeite, ist hier einfacher. 01:29:31.680 --> 01:29:34.820 Ich habe nur das eine Bit, was mir die Farbe im Prinzip kennzeichnet, 01:29:34.860 --> 01:29:35.920 der reinlaufenden Kante. 01:29:35.920 --> 01:29:40.620 Und da muss ich nur etwas umordnen. 01:29:40.800 --> 01:29:43.640 Ich habe hier im Prinzip nur das Bit jeweils zu verändern. 01:29:44.080 --> 01:29:47.500 Vorher musste ich wirklich neue Objekte erzeugen. 01:29:48.620 --> 01:29:49.600 Und das fällt hier weg. 01:30:04.410 --> 01:30:06.390 Warum muss ich da irgendetwas prüfen? 01:30:10.780 --> 01:30:15.840 Wenn ich das so machen möchte, wenn ich dieses Top-Down-Teilen machen 01:30:15.840 --> 01:30:16.740 möchte, da haben Sie recht. 01:30:17.580 --> 01:30:20.920 Wenn ich hier feststellen möchte, ich muss jetzt nach oben laufen, das 01:30:20.920 --> 01:30:25.040 ist richtig, dann müsste ich hier entsprechend gucken, sind die beiden 01:30:25.040 --> 01:30:28.960 Nachfolger, das wäre ein extra Aufwand. 01:30:30.840 --> 01:30:33.000 Kann ich Ihnen jetzt nicht sagen, könnte man sich angucken. 01:30:33.840 --> 01:30:36.760 Aber insgesamt hat sich herausgestellt, die Rot-Schwarz-Bäume sind 01:30:36.760 --> 01:30:40.500 somit die effizienteste Datenstruktur für das Suchen. 01:30:41.520 --> 01:30:44.720 Aber haben Sie recht, das ist ein extra Aufwand bei dem Top-Down 01:30:44.720 --> 01:30:46.700 -Verfahren, bei den Top-Down-Teilen. 01:30:47.300 --> 01:30:49.700 Da muss ich natürlich erstmal wissen, ob die beiden Nachfolger 01:30:49.700 --> 01:30:51.280 tatsächlich rot sind, da haben Sie recht. 01:30:51.680 --> 01:30:54.960 Das habe ich bei der Art, wie ich hier das dargestellt habe, zunächst 01:30:54.960 --> 01:30:55.600 einmal nicht. 01:30:58.160 --> 01:31:00.800 Das kann ich erst in dem Knoten jeweils feststellen. 01:31:01.520 --> 01:31:05.720 Das wäre eben noch eine extra Abfrage, sind die beiden rot, wenn ja, 01:31:05.800 --> 01:31:07.380 dann muss ich entsprechend hier umprobieren. 01:31:08.520 --> 01:31:13.480 Okay, aber insgesamt ist das eine interessante Struktur. 01:31:14.060 --> 01:31:17.040 Wir sind schon über die Zeit, wir sind jetzt gerade durch dieses 01:31:17.040 --> 01:31:17.740 Kapitel durch. 01:31:17.960 --> 01:31:21.460 Nächstes Mal machen wir dann etwas über Graph-Algorithmen. 01:31:21.600 --> 01:31:23.540 Vielen Dank für die Aufmerksamkeit, ich wünsche Ihnen noch einen 01:31:23.540 --> 01:31:25.840 schönen Tag, der hoffentlich nicht zu heiß wird.