Möchten Sie eine effiziente Reihenfolge beibehalten, bei der Sie Elemente „zwischen“ zwei anderen Elementen in der Reihenfolge einfügen können?

Question

Stellen Sie sich vor, ich hätte eine Reihenfolge für eine Reihe von Elementen wie folgt:

Wobei ein Pfeil $X \leftarrow Y$ $X < Y$ bedeutet.Es ist auch transitiv:$\left(X < Y ight) \wedge \left(Y < Z ight) \impliziert \left(X < Z ight)$.

Um Abfragen wie $A \stackrel {?}{<} D$ effizient beantworten zu können, ist eine Art Beschriftung oder Datenstruktur erforderlich.Sie könnten beispielsweise die Knoten von links nach rechts nummerieren und so einfach einen Ganzzahlvergleich durchführen, um die Abfrage zu beantworten:$A \stackrel {?}{<} D \impliziert 1 < 4 \impliziert T$.Es würde ungefähr so ​​aussehen:

Wobei die Zahl die Reihenfolge ist und der Buchstabe nur ein Name ist.

Aber was wäre, wenn Sie in der Reihenfolge Elemente „zwischen“ zwei anderen Elementen einfügen müssten, etwa so:

Wie kann man eine solche Reihenfolge aufrechterhalten?Bei der einfachen Nummerierung stößt man auf das Problem, dass es keine ganzen Zahlen „zwischen“ $2,3$ gibt, die verwendet werden könnten.

Answer 1

Dies ist als bekannt Problem „Auftragswartung“..Es gibt eine relativ einfache Lösung, die die amortisierte Zeit von $O(1)$ sowohl für Abfragen als auch für Einfügungen verwendet.Mit „relativ einfach“ meine ich, dass man einige Bausteine ​​verstehen muss, aber sobald man diese verstanden hat, der Rest nicht schwer zu erkennen ist.

http://courses.csail.mit.edu/6.851/spring12/lectures/L08.html

Die Grundidee ist eine zweistufige Datenstruktur.Die oberste Ebene ähnelt der AVL-Baumlösung von Realz Slaw, jedoch

• Die Knoten werden direkt mit Bitfolgen der Länge $O(\lg n)$ beschriftet, deren Reihenfolge mit ihrer Reihenfolge im Baum übereinstimmt.Der Vergleich benötigt daher eine konstante Zeit

• Es wird ein Baum mit weniger Rotationen als ein AVL-Baum verwendet, z. B. ein Sündenbockbaum oder ein Baum mit Gewichtsverteilung, sodass Umbenennungen seltener vorkommen.

Die unterste Ebene sind die Blätter des Baumes.Diese Ebene verwendet die gleiche Länge von Beschriftungen, $O(\lg n)$, enthält aber nur $O(\lg n)$ Elemente in jedem Blatt einer einfachen verknüpften Liste.Dadurch erhalten Sie genügend zusätzliche Bits, um sie aggressiv umzubenennen.

Bei jedem Einfügen von $O(\lg n)$ werden die Blätter zu groß oder zu klein, was zu einer Änderung der obersten Ebene führt, die $O(\lg n)$ amortisierte Zeit (im schlimmsten Fall $\Omega(n)$ Zeit) in Anspruch nimmt ).Amortisiert beträgt dies nur $O(1)$.

Es gibt viel komplexere Strukturen für die Durchführung von Aktualisierungen im ungünstigsten Fall von $O(1)$.

Answer 2

Anstelle einer einfachen Nummerierung könnten Sie die Zahlen auch über einen großen (konstanten) Bereich verteilen, z. B. Ganzzahlminimum und -maximum einer CPU-Ganzzahl.Dann können Sie weiterhin Zahlen „dazwischen“ setzen, indem Sie den Durchschnitt der beiden umgebenden Zahlen bilden.Wenn die Zahlen zu eng werden (wenn Sie beispielsweise zwei benachbarte Ganzzahlen haben und keine Zahl dazwischen steht), können Sie die gesamte Reihenfolge einmalig neu nummerieren und die Zahlen gleichmäßig über den Bereich verteilen.

Natürlich kann es zu der Einschränkung kommen, dass alle Zahlen im Bereich der großen Konstante verwendet werden.Erstens ist dies normalerweise kein Problem, da die Integer-Größe auf einem Computer groß genug ist, sodass mehr Elemente wahrscheinlich sowieso nicht in den Speicher passen würden.Wenn es jedoch ein Problem darstellt, können Sie sie einfach mit einem größeren Ganzzahlbereich neu nummerieren.

Wenn die Eingabereihenfolge nicht pathologisch ist, kann diese Methode die Umnummerierungen amortisieren.

Beantwortung von Fragen

Ein einfacher Ganzzahlvergleich kann die Abfrage $\left(X \stackrel{?}{<}Y ight)$ beantworten.

Bei Verwendung maschineller Ganzzahlen wäre die Abfragezeit sehr kurz ( $\mathcal{O}\left(1 ight)$ ), da es sich um einen einfachen Ganzzahlvergleich handelt.Die Verwendung eines größeren Bereichs würde größere ganze Zahlen erfordern, und der Vergleich würde $\mathcal{O}\left(\log{|integer|} ight)$ erfordern.

Einfügen

Zunächst würden Sie die verknüpfte Liste der Reihenfolge pflegen, die in der Frage gezeigt wird.Die Einfügung hier würde angesichts der Knoten, zwischen denen das neue Element platziert werden soll, $\mathcal{O}\left(1 ight)$ betragen.

Das Beschriften des neuen Elements geht normalerweise schnell mit $\mathcal{O}\left(1 ight)$, da Sie die neue Zahl einfach durch Mittelung der umgebenden Zahlen berechnen würden.Gelegentlich kann es vorkommen, dass Ihnen „zwischendurch“ die Zahlen ausgehen, was den Zeitumnummerierungsvorgang $\mathcal{O}\left(n ight)$ auslöst.

Umnummerierung vermeiden

Sie können Gleitkommazahlen anstelle von Ganzzahlen verwenden. Wenn Sie also zwei „benachbarte“ Ganzzahlen erhalten, werden diese verwendet dürfen gemittelt werden.So können Sie eine Neunummerierung vermeiden, wenn Sie mit zwei ganzzahligen Gleitkommazahlen konfrontiert werden:Teilen Sie sie einfach in zwei Hälften.Irgendwann verliert der Gleitkommatyp jedoch seine Genauigkeit und zwei „adacent“ Gleitkommazahlen können nicht gemittelt werden (der Durchschnitt der umgebenden Zahlen wird wahrscheinlich einer der umgebenden Zahlen entsprechen).

Sie können auf ähnliche Weise eine Ganzzahl mit „Dezimalstelle“ verwenden, wobei Sie zwei Ganzzahlen für ein Element verwalten.eine für die Zahl und eine für die Dezimalzahl.Auf diese Weise können Sie eine Neunummerierung vermeiden.Die dezimale Ganzzahl wird jedoch irgendwann überlaufen.

Durch die Verwendung einer Liste von Ganzzahlen oder Bits für jede Beschriftung kann die Neunummerierung vollständig vermieden werden.Dies entspricht grundsätzlich der Verwendung von Dezimalzahlen mit unbegrenzter Länge.Der Vergleich würde lexikographisch erfolgen und die Vergleichszeiten würden sich mit der Länge der beteiligten Listen erhöhen.Allerdings kann dies die Kennzeichnung aus dem Gleichgewicht bringen;Einige Beschriftungen erfordern möglicherweise nur eine Ganzzahl (keine Dezimalzahl), andere verfügen möglicherweise über eine Liste mit langer Länge (lange Dezimalstellen).Dies ist ein Problem, und auch hier kann eine Neunummerierung Abhilfe schaffen, indem die Nummerierung (hier Nummernlisten) gleichmäßig über einen gewählten Bereich (Bereich bedeutet hier möglicherweise Länge der Listen) neu verteilt wird, sodass nach einer solchen Neunummerierung alle Listen die gleiche Länge haben .

---

Diese Methode wird tatsächlich in verwendet dieser Algorithmus (Implementierung,relevante Datenstruktur);Im Verlauf des Algorithmus muss eine willkürliche Reihenfolge eingehalten werden, und der Autor verwendet dazu Ganzzahlen und Umnummerierungen.

---

Wenn Sie versuchen, sich an Zahlen zu halten, wird Ihr Schlüsselraum etwas eingeschränkt.Man könnte stattdessen Zeichenfolgen variabler Länge verwenden, indem man die Vergleichslogik „a“ < „ab“ < „b“ verwendet.Es bleibt noch zwei Probleme zu lösen. A.Schlüssel könnten willkürlich lang sein B.Der Vergleich langer Schlüssel könnte kostspielig werden

Answer 3

Sie können einen schlüssellosen AVL-Baum oder ähnliches pflegen.

Es würde wie folgt funktionieren:Der Baum behält eine Reihenfolge der Knoten bei, genau wie ein AVL-Baum es normalerweise tut, aber anstelle des Schlüssels, der bestimmt, wo der Knoten liegen „sollte“, gibt es keine Schlüssel, und Sie müssen die Knoten explizit „nach“ einem anderen Knoten (oder in) einfügen mit anderen Worten „zwischen“ zwei Knoten), wobei „nachher“ bedeutet, dass es beim Durchlaufen des Baums in der richtigen Reihenfolge danach kommt.Der Baum behält somit auf natürliche Weise die Reihenfolge für Sie bei und gleicht sie aufgrund der integrierten Rotationen der AVL auch aus.Dadurch wird alles automatisch gleichmäßig verteilt.

Einfügen

Zusätzlich zum regulären Einfügen in die Liste, wie in der Frage gezeigt, würden Sie einen separaten AVL-Baum verwalten.Das Einfügen in die Liste selbst ist $\mathcal{O}\left(1 ight)$, da Sie die Knoten „vorher“ und „nachher“ haben.

Die Einfügungszeit in den Baum beträgt $\mathcal{O}\left(\log {n} ight)$, genau wie die Einfügung in einen AVL-Baum.Das Einfügen erfordert einen Verweis auf den Knoten, nach dem Sie einfügen möchten, und Sie fügen den neuen Knoten einfach links vom Knoten ganz links des rechten untergeordneten Knotens ein.Dieser Ort ist in der Reihenfolge des Baums „nächster“ (er ist der nächste in der Durchquerung in der Reihenfolge).Führen Sie dann die typischen AVL-Rotationen durch, um den Baum wieder ins Gleichgewicht zu bringen.Sie können einen ähnlichen Vorgang für „Vorher einfügen“ ausführen.Dies ist hilfreich, wenn Sie etwas am Anfang der Liste einfügen müssen und es keinen Knoten „vor“ Knoten gibt.

Beantwortung von Fragen

Um Abfragen von $\left(X \stackrel{?}{<}Y ight)$ zu beantworten, suchen Sie einfach alle Vorfahren von $X$ und $Y$ im Baum und analysieren die Position von where im Baum, die Vorfahren gehen auseinander;derjenige, der nach „links“ divergiert, ist der kleinere von beiden.

Dieses Verfahren benötigt $\mathcal{O}\left(\log{n} ight)$ Zeit, um den Baum bis zur Wurzel zu erklimmen und die Vorfahrenlisten zu erhalten.Es stimmt zwar, dass dies langsamer zu sein scheint als der Ganzzahlvergleich, aber in Wahrheit ist es dasselbe;nur dieser ganzzahlige Vergleich auf einer CPU wird durch eine große Konstante begrenzt, um ihn zu $\mathcal{O}\left(1 ight)$ zu machen;Wenn Sie diese Konstante überlaufen lassen, müssen Sie mehrere Ganzzahlen beibehalten (tatsächlich $\mathcal{O}\left(\log{n} ight)$ Ganzzahlen) und das Gleiche tun $\mathcal{O}\left(\log{ n} ight)$ Vergleiche.Alternativ können Sie die Baumhöhe durch einen konstanten Betrag „begrenzen“ und auf die gleiche Weise „schummeln“, wie es die Maschine mit ganzen Zahlen macht:Jetzt sehen Abfragen wie $\mathcal{O}\left(1 ight)$ aus.

Demonstration des Einfügevorgangs

Zur Veranschaulichung können Sie einige Elemente mit ihrer Reihenfolge aus der Liste in die Frage einfügen:

Schritt 1

Beginnen Sie mit $D$

Aufführen:

Baum:

Schritt 2

Fügen Sie $C$ ein, $\emptyset < C < D$.

Aufführen:

Baum:

Beachten Sie, dass Sie $C$ explizit „vor“ $D$ setzen, nicht weil der Buchstabe C vor D steht, sondern weil $C < D$ in der Liste steht.

Schritt 3

Fügen Sie $A$, $\emptyset < A < C$ ein.

Aufführen:

Baum:

AVL-Rotation:

Schritt 4

Fügen Sie $B$, $A < B < C$ ein.

Aufführen:

Baum:

Keine Drehungen notwendig.

Schritt 5

Fügen Sie $E$, $D < E < \emptyset$ ein

Aufführen:

Baum:

Schritt 6

Fügen Sie $F$, $B < F < C$ ein

Wir platzieren es einfach direkt „nach“ $B$ im Baum, in diesem Fall indem wir es einfach rechts von $B$ anhängen;somit liegt $F$ jetzt direkt nach $B$ in der Reihenfolge-Durchquerung des Baums.

Aufführen:

Baum:

AVL-Rotation:

Demonstration der Vergleichsoperation

$A \stackrel{?}{<} F$

ancestors(A) = [C,B]
ancestors(F) = [C,B]
last_common_ancestor = B
B.left = A
B.right = F
... A < F #left is less than right

$D \stackrel{?}{<} F$

ancestors(D) = [C]
ancestors(F) = [C,B]
last_common_ancestor = C
C.left = D
C.right = B #next ancestor for F is to the right
... D < F #left is less than right

$B \stackrel{?}{<} A$

ancestors(B) = [C]
ancestors(A) = [B,C]
last_common_ancestor = B
B.left = A
... A < B #left is always less than parent

---

Diagrammquellen

• gist.github.com/realazthat/9299877a83cba4720aec