Wie ist der Speicher des Arrays aus Segmentbaum 2 * 2 ^ (ceil (log (n))) - 1?
Der Link: Ссылка . Dies ist der zitierte Text:
Wir beginnen mit einem Segment arr [0. . . n-1]. und jedes Mal teilen wir das aktuelle Segment in zwei Hälften (wenn es noch kein Segment der Länge 1 geworden ist), und rufen dann die gleiche Prozedur auf beiden Hälften auf, und für jedes solche Segment speichern wir die Summe in dem entsprechenden Knoten. Alle Ebenen des konstruierten Segmentbaums sind bis auf die letzte Ebene vollständig gefüllt. Außerdem wird der Baum ein Full Binary Tree sein, da wir Segmente auf jeder Ebene in zwei Hälften teilen. Da der konstruierte Baum immer ein voller Binärbaum mit n Blättern ist, wird es n-1 interne Knoten geben. Die Gesamtzahl der Knoten beträgt also 2n - 1. Die Höhe des Segmentbaums ist ceil [log (n)]. Da der Baum mit einem Array dargestellt wird und die Beziehung zwischen Eltern- und Kindindizes beibehalten werden muss, beträgt die Größe des für den Segmentbaum reservierten Speichers 2 * 2 ^ (ceil (log (n))) - 1.
Wie ist der Speicher (letzte Zeile des obigen Para) so viel? Wie werden die übergeordneten und untergeordneten Indizes im Code gespeichert, wenn sie korrekt sind? Bitte begründen Sie dies. Wenn das falsch ist, was ist dann der richtige Wert?
4 Antworten
Was hier passiert ist, wenn Sie ein Array von n Elementen haben, dann wird der Segmentbaum einen Blattknoten für jeden dieser n Einträge haben. Somit haben wir (n) Blattknoten und auch (n-1) interne Knoten.
Gesamtanzahl der Knoten = n + (n-1) = 2n-1 Jetzt wissen wir, dass es sich um einen vollständigen Binärbaum handelt, und daher ist die Höhe: ceil (Log2 (n)) +1
Gesamtanzahl von Knoten = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ ceil (Log2 (n)) // was eine geometrische Progression ist, wo 2 ^ i die Anzahl der Knoten auf der Ebene i bezeichnet.
Formel der Summation G.P. = a * (r ^ Größe - 1) / (r-1) wo a = 2 ^ 0
Gesamtanzahl von Knoten = 1 * (2 ^ (ceil (Log2 (n)) + 1) -1) / (2-1)
= 2 * [2 ^ ceil (Log2 (n))] -1 (Sie brauchen Platz im Array für jeden der internen Knoten und Blattknoten, die diese Anzahl in der Anzahl sind), daher ist es das Array von Größe.
= O (4 * n) ca. ..
Sie können auch so denken, ist der Segmentbaum das:
%Vor%Wenn das oben genannte Segmentbaum ist, dann ist das Array des Segmentbaums: 10, 3, 7, 1, 2, 3, dh das 0. Element speichert die Summe der ersten und zweiten Einträge, der erste Eintrag wird gespeichert die Summe von 3 und 4. und 2. speichert die Summe von 5. und 6. Eintrag !!
Die bessere Erklärung ist auch: Wenn die Array-Größe n eine Potenz von 2 ist, dann haben wir genau n-1 interne Knoten, die sich zu 2n-1 Gesamtknoten. Aber nicht immer haben wir n als Potenz von 2, also brauchen wir im Grunde die kleinste Potenz von n , die größer ist als n . Das bedeutet dies,
%Vor%Sie können meine gleiche Antwort sehen hier
Seltsamerweise las ich aus derselben Quelle wie die Frage, als ich darauf stieß. Ich werde versuchen, mein Bestes zu geben.
Beginnen wir mit einem grundlegenden Unterschied in den Baumdarstellungen (nur im context ):
-
Das fast "Worst Case" -Szenario. Dieser ist nicht ganz ausgewogen und macht nicht wirklich Spaß. Warum? Da bei verschiedenen Eingaben unterschiedliche Bäume erzeugt werden können, ist die Zeit zum Durchqueren nicht sehr vorhersehbar.
-
Unser "Best Case" -Szenario. Dieser ist vollständig ausgewogen oder vollständig und wird immer eine vorhersehbare Zeit benötigen. Außerdem ist dieser Baum auch besser "gehackt" .
Kommen wir nun zu unserer Frage zurück. [Siehe das erste Bild] Wir wissen, dass für jedes n-input Array (die Zahlen in grün ) n-1 interne Knoten (Die Zahlen in blau ). Daher muss ein maximaler 2n-1 Knotenraum zugewiesen werden.
Aber der Code hier macht etwas Gegenteiliges. Warum und wie?
-
Was Sie erwarten: Sie erwarten, dass der für 2n-1 Knoten zugewiesene Speicher ausreichend ist. Mit anderen Worten, dies sollte getan werden:
%Vor%Wenn der Rest des Codes gut funktioniert, ist das keine gute Idee. Das liegt daran, dass es unseren unausgewogenen Baum erzeugt, ähnlich wie in unserem ersten Fall. Solch ein Baum ist nicht einfach zu durchqueren oder einfach auf Problemlösungen anzuwenden.
-
Was wirklich passiert: Wir fügen zusätzlichen Speicher mit
%Vor%nulloder0hinzu. Wir machen das:Das ist genug Raum, um einen ausgewogenen vollständigen Baum zu erzeugen. Ein solcher Baum ist leicht zu durchqueren (mit einigen speziellen Modifikationen) und kann direkt auf Probleme angewendet werden.
Wie haben wir genügend Speicher für Fall 2 zugewiesen? Hier ist wie:
-
Wir wissen, dass es in unserem ausgewogenen Segmentbaum mindestens drei Komponenten gibt:
- n Zahlen aus unserem Eingabe-Array.
- n-1 interne Knoten, die zwingend erforderlich sind.
- Der zusätzliche Speicherplatz, den wir für padding reservieren müssen.
-
Wir wissen auch, dass ein ausgewogener Baum mit k Blättern Folgendes haben wird:
-
Durch Kombination der beiden erhalten wir das gewünschte Ergebnis:
%Vor%
Trivia! Wenn Sie 2 auf die Stärke von x oben setzen, stellen Sie sicher, dass wir die nächste Dekaden-Ganzzahl erhalten, nämlich:
- Größer als oder gleich
n(Anzahl der Elemente in unserem Eingabe-Array). - Ist perfekt und wiederholt durch 2 teilbar, um einen vollständig ausgewogenen 2-stufigen (binären) Baum zu erhalten.
Die Größe des Eingabearrays ist n.
Alle Eingabe-Array-Elemente werden Blattknoten im Segmentbaum sein, also die Anzahl der Blattknoten = n
Da der Segmentbaum ein vollständiger Baum ist, ist die Höhe des Segmentbaums h = ⌈ Log 2
So Anzahl der Knoten in einem Segmentbaum = <2>
Der Segmentbaum ist ein vollständig binärer Baum, in dem alle Blätter das Element in Ihrem Eingabe-Array bezeichnen. Und wie erwähnt hier
Die Anzahl der Knoten n in einem vollständigen Binärbaum ist bei mindestens n = 2h + 1 und höchstens n = 2 ^ {h + 1} - 1 , wobei h ist die Höhe des Baumes. Und h = log_2n .% Co_de%
Hier ist der Python-Code zum Ermitteln der maximalen Anzahl von Knoten in der Segmentstruktur -
%Vor%Tags und Links arrays memory data-structures tree segment-tree