„Hallo, Amigo!“
„Hallo, Rishi!“
„Ich habe dort drüben meine alten Notizen gefunden und interessantes Material für Sie vorbereitet. Ich denke, es wird Sie interessieren, es zu hören.“
„Lass es uns hören. Du findest immer etwas Interessantes, das sich später als sehr nützlich erweist.“
„OK. Heute möchte ich Ihnen etwas über Bäume erzählen , also beginne ich mit Grafiken .“
„ Ein Graph ist ein System aus Punkten und Linien, die diese verbinden. Die Punkte werden als Eckpunkte des Graphen bezeichnet, und die Linien werden als Kanten des Graphen bezeichnet. Zum Beispiel:“
„Ein Diagramm lässt sich sehr gut als mathematisches Modell für verschiedene reale Prozesse und Aufgaben verwenden. Für Diagramme wurden viele verschiedene Aufgaben und Algorithmen erfunden, daher werden sie ziemlich häufig verwendet.“
„Angenommen, Scheitelpunkte sind Städte und Kanten sind Straßen. Dann wird die Suche nach der kürzesten Straße zwischen Städten zu: „Finde bei einem gegebenen Diagramm den kürzesten Weg zwischen zwei Scheitelpunkten. “
„Aber der Weg von A nach B ist nicht immer derselbe wie der Weg von B nach A. Daher werden manchmal zwei verschiedene Linien bevorzugt. Dazu werden die Linien (Kanten des Diagramms) durch Pfeile ersetzt. In Mit anderen Worten, der Graph kann zwei Pfeile haben: einen von A nach B und einen anderen von B nach A.
„Wenn der Graph Pfeile verwendet, nennt man ihn einen gerichteten Graphen ; wenn er nur Linien hat, dann nennt man ihn einen ungerichteten Graphen .“
„Jeder Scheitelpunkt kann eine eigene Anzahl von Kanten haben. Ein Scheitelpunkt kann auch überhaupt keine Kanten haben. Umgekehrt kann ein Scheitelpunkt durch Kanten mit jedem anderen Scheitelpunkt verbunden sein. Wenn jedes Scheitelpunktpaar in einem Diagramm durch eine Kante verbunden ist, dann man nennt es einen vollständigen Graphen. “
„Wenn Sie Kanten verwenden können, um jeden Scheitelpunkt in einem Diagramm zu erreichen, dann spricht man von einem verbundenen Graphen. Ein Graph, der drei separate Scheitelpunkte und keine Kanten hat, ist immer noch ein Graph, aber wir nennen ihn einen nicht zusammenhängenden Graphen.“
„Um einen verbundenen Graphen aus N Eckpunkten zu bilden, benötigt man mindestens N-1 Kanten. Diese Art von Graph wird Baum genannt.“
„Darüber hinaus wird normalerweise ein Scheitelpunkt als Wurzel des Baums ausgewählt und der Rest als Zweige deklariert. Baumzweige, die keine eigenen Zweige haben, werden Blätter genannt . Zum Beispiel:“
„Wenn jedes Element des Baums zwei Kinder hat, dann spricht man von einem Binärbaum . Mit anderen Worten, es kann entweder 0 oder 2 Zweige geben. Oben rechts sehen Sie einen Binärbaum .“
„ Ein Baum wird als vollständiger Binärbaum bezeichnet, wenn jeder Zweig zwei Kinder hat und alle Blätter (Eckpunkte ohne Kinder) in derselben Zeile liegen.“
"Zum Beispiel:"
„Warum werden diese Bäume benötigt?“
„Oh, Bäume werden an vielen Stellen verwendet. Im Allgemeinen sind Binärbäume sortierte strukturierte Daten.“
"Was ist das?"
„Ja, es ist ganz einfach. Wir speichern einen bestimmten Wert in jedem Scheitelpunkt. Und jedes Element folgt einer Regel: Der im rechten Kind gespeicherte Wert muss größer sein als der im Scheitelpunkt gespeicherte Wert, und der im linken Kind gespeicherte Wert muss größer sein kleiner sein als der im Scheitelpunkt gespeicherte Wert. Diese Reihenfolge ermöglicht es, die benötigten Elemente des Baums schnell zu finden.
„Können Sie erklären, was das bedeutet?“
„Baumelemente werden normalerweise durch Hinzufügen sortiert. Angenommen, wir haben 7 Elemente: 13, 5, 4, 16, 8, 11, 10.“
„So werden die Elemente zum Baum hinzugefügt.“
„Wenn wir in diesem Baum nach der Zahl 7 suchen, dann läuft die Suche so ab“
„0) Beginnen Sie an der Wurzel.“
„1a) Ist 7 gleich 13? Nein“
„1b) Ist 7 größer als 13? Nein, also gehen wir zum linken Teilbaum.“
„2a) Ist 7 gleich 5? Nein.“
„2b) Ist 7 größer als 5? Ja, also gehen wir zum rechten Teilbaum.“
„3a) Ist 7 gleich 8? Nein“
„3b) Ist 7 größer als 8? Nein, also gehen wir zum linken Teilbaum.“
„4a) Es gibt keinen linken Teilbaum, was bedeutet, dass die Zahl 7 nicht im Baum ist.“
„Ah. Mit anderen Worten, wir müssen nur die Eckpunkte auf dem Pfad von der Wurzel zum potenziellen Ort der gewünschten Zahl überprüfen. Ja, das geht wirklich schnell.“
„Darüber hinaus müssen Sie, wenn der Baum ausgeglichen ist, nur etwa 20 Eckpunkte durchlaufen, um eine Million Elemente zu durchsuchen.“
„Ich stimme zu – das sind nicht sehr viele.“
„Was meinst du mit ausgeglichenem Baum?“
„Ein Baum, der nicht verzerrt ist, also keine langen Äste hat. Wenn die Elemente beispielsweise bereits sortiert wären, als wir den Baum gebaut haben, hätten wir einen sehr langen Baum gemacht, der aus einem Ast besteht. “
„Hmm. Du hast recht. Was machen wir also?“
„Wie Sie wahrscheinlich schon vermutet haben, hat der effizienteste Baum Zweige, die ungefähr gleich lang sind. Dann verwirft jeder Vergleich den größten Teil des verbleibenden Teilbaums.“
„Also müssen wir den Baum wieder aufbauen?“
„Ja. Es muss „ausgewogen“ sein – um einem vollständigen Binärbaum so nahe wie möglich zu kommen.“
„Um dieses Problem zu lösen, wurden selbstausgleichende Bäume erfunden. Wenn der Baum nach dem Hinzufügen eines Elements verzerrt wird, werden die Elemente leicht neu angeordnet, damit alles in Ordnung ist. Hier ist ein Beispiel für den Ausgleich:“
„Einige dieser Bäume sind als rotschwarze Bäume bekannt .“
„Warum heißen sie Rot-Schwarz?“
„Ihr Erfinder hat alle Eckpunkte mit zwei Farben gezeichnet. Eine Farbe war Rot und die andere war Schwarz. Die verschiedenen Eckpunkte gehorchen unterschiedlichen Regeln. Dies bildet die gesamte Grundlage für das Ausgleichsverfahren.“
"Zum Beispiel:"
„Also, was sind diese Regeln?“
„1) Ein roter Scheitelpunkt kann nicht das untergeordnete Element eines roten Scheitelpunkts sein.“
„2) Die Schwarztiefe jedes Blattes ist gleich (die Schwarztiefe bezieht sich auf die Anzahl der schwarzen Scheitelpunkte auf dem Weg von der Wurzel).“
„3) Die Wurzel des Baumes ist schwarz.“
„Ich werde nicht erklären, wie das funktioniert – Ihr Kopf explodiert wahrscheinlich bereits.“
„Ja. Mein Prozessor gibt ein wenig Rauch ab.“
„Hier ist ein Link für Sie. Wenn Sie möchten, können Sie hier mehr darüber lesen.“
„Und jetzt geh und mach eine Pause.“
GO TO FULL VERSION