Rotationsabstand

Im Diskrete Mathematik und Theoretische Informatik, das Rotationsabstand zwischen zwei Binärbäume mit der gleichen Anzahl von Knoten ist die minimale Anzahl von Baumrotationen benötigt neu konfigurieren ein Baum in einen anderen. Aufgrund einer kombinatorischen Äquivalenz zwischen binären Bäumen und Triangulationen konvexer Polygone entspricht der Drehabstand dem Flip -Abstand für Triangulationen von konvexe Polygone.

Die Rotationsentfernung wurde zuerst von Karel čulík II und definiert Derick Holz 1982.^[1] Alle zwei n-Node binäre Bäume haben höchstens einen Rotationsabstand 2n - 6und einige Bäumepaare haben genau diese Entfernung. Das Rechenkomplexität Die Berechnung der Rotationsentfernung ist unbekannt.^[2]

Definition

Baumrotation

A Binärbaum ist eine Struktur, die aus einer Reihe von Knoten besteht Linke Kind oder Richtiges Kind eines anderen Knotens sein Elternteil, und in denen die übergeordneten Links von jedem Knoten schließlich zum Stammknoten führen. (In einigen Quellen werden die hier beschriebenen Knoten als "interne Knoten" bezeichnet, es gibt einen anderen Satz von Knoten, die als "externe Knoten" bezeichnet werden. Jeder interne Knoten muss genau zwei Kinder haben, und jeder externe Knoten muss keine Kinder haben.^[1] Die hier beschriebene Version kann erhalten werden, indem alle externen Knoten aus einem solchen Baum entfernt werden.)

Für jeden Knoten x Im Baum gibt es a Subtree der gleichen Form, verwurzelt bei x und bestehend aus allen Knoten, die erreichen können x durch folgende übergeordnete Links. Jeder binäre Baum hat eine Bestellung seiner Knoten von links nach rechts In -Order Traversal, erhalten durch rekursives Durchqueren des linken Teilbaums (der Unterbaum am linken Kind der Wurzel, falls ein solches Kind existiert), dann die Wurzel selbst auflisten und dann rekursiv den rechten Subtree durchqueren. In einem Binärer SuchbaumJeder Knoten ist einem Suchschlüssel zugeordnet, und die Bestellung von links nach rechts muss mit der Reihenfolge der Schlüssel übereinstimmen.^[2]

A Baumrotation ist eine Operation, die die Struktur eines Binärbaums ändert, ohne seine Reihenfolge von links nach rechts zu ändern. Mehrere selbstausgleichender binärer Suchbaum Datenstrukturen Verwenden Sie diese Rotationen als primitive Operation in ihren Rebalancing -Algorithmen. Eine Rotation arbeitet auf zwei Knoten x und y, wo x ist der Elternteil von yund umstrukturiert den Baum durch Herstellung y Eltern sein x und an die Stelle von x im Baum. Um eine der Kinderverbindungen von zu befreien y und Platz zum Verknüpfen machen x als Kind von yDiese Operation muss möglicherweise auch eines der Kinder von verschieben y ein Kind von werden x. Es gibt zwei Variationen dieser Operation, a Rechte Rotation in welchem y beginnt wie das linke Kind von x und x endet als das richtige Kind von y, und ein linke Rotation in welchem y beginnt als das richtige Kind von x und x endet wie das linke Kind von y.^[2]

Zwei Bäume, die die gleiche Links-rechts-Sequenz von Knoten haben, können durch eine Folge von Rotationen ineinander transformiert werden. Der Rotationsabstand zwischen den beiden Bäumen ist die Anzahl der Rotationen in der kürzestmöglichen Folge von Rotationen, die diese Transformation ausführen. Es kann auch als die beschrieben werden kürzester Wegentfernung in einem Rotationsdiagramm, ein Diagramm mit einem Scheitelpunkt für jeden binären Baum auf einer bestimmten links nach rechts und eine Kante für jede Rotation zwischen zwei Bäumen.^[2] Dieses Rotationsdiagramm ist genau das Diagramm von Scheitelpunkten und Kanten eines Associadron.^[3]

Äquivalenz zur Flip -Entfernung

Die Flip-Graphen eines Pentagon und eines Sechsecks, die den Rotationen von Drei-Knoten- und Binärbäumen mit vier Knoten entsprechen

Bei einer Familie von Triangulationen eines geometrischen Objekts a Flip ist eine Operation, die eine Triangulation in eine andere verwandelt, indem eine Kante zwischen zwei Dreiecken entfernt und dem resultierenden Viereck die gegenüberliegende Diagonale hinzugefügt wird. Der Flip -Abstand zwischen zwei Triangulationen ist die minimale Anzahl von Flips, die zur Umwandlung einer Triangulation in eine andere erforderlich sind. Es kann auch als der kürzeste Weg in a beschrieben werden Flip -Graph, ein Diagramm mit einem Scheitelpunkt für jede Triangulation und eine Kante für jeden Flip zwischen zwei Triangulationen. Auf diese Weise können Flips und Flip -Entfernungen für verschiedene Arten von Triangulationen definiert werden, einschließlich Triangulationen von Punkten in der Punkte in der Euklidische Ebene, Triangulationen von Polygoneund Triangulationen von Abstrakten Verteiler.

Es gibt eine Eins-zu-Eins-Korrespondenz zwischen Triangulationen eines gegebenen konvexes Polygon, mit einer ausgewiesenen Wurzelkante und binären Bäumen, die Triangulationen nehmen n-Seitig Polygone in binäre Bäume mit n - 2 Knoten. In dieser Korrespondenz entspricht jedes Dreieck einer Triangulation einem Knoten in einem binären Baum. Der Wurzelknoten ist das Dreieck mit der bestimmten Wurzelkante als einer seiner Seiten, und zwei Knoten sind als Eltern und Kind im Baum verknüpft, wenn die entsprechenden Dreiecke eine Diagonale in der Triangulation teilen. Unter dieser Korrespondenz entsprechen Rotationen in binären Bäumen genau Flips in den entsprechenden Triangulationen. Daher der Rotationsabstand auf (n - 2)-Node -Bäume entsprechen genau dem Flip -Abstand bei Triangulationen von n-Seitig konvexe Polygone.

Maximalwert

Čulík & Wood (1982) Definieren Sie die "rechte Wirbelsäule" eines binären Baums als der Weg, der durch Start von der Wurzel und nach dem rechten Kinderverbindungen befolgt wird, bis ein Knoten erreicht ist, der kein richtiges Kind hat. Wenn ein Baum die Eigenschaft hat, die nicht alle Knoten zur rechten Wirbelsäule gehören, gibt es immer eine richtige Rotation, die die Länge der rechten Wirbelsäule erhöht. Denn in diesem Fall gibt es mindestens einen Knoten x auf der rechten Wirbelsäule mit einem linken Kind y Das ist nicht auf der richtigen Wirbelsäule. Durchführen einer richtigen Rotation an x und y fügt hinzu y auf der rechten Wirbelsäule, ohne einen anderen Knoten davon zu entfernen. Durch wiederholtes Erhöhen der Länge der rechten Wirbelsäule, jeder n-Nodebaum kann in den einzigartigen Baum mit der gleichen Knotenreihenfolge umgewandelt werden, in der alle Knoten zur rechten Wirbelsäule gehören n - 1 Schritte. Bei zwei beliebigen Bäumen mit der gleichen Knotenreihenfolge kann man einen in den anderen verwandeln, indem der erste Baum mit allen Knoten auf der rechten Wirbelsäule in einen Baum umgewandelt wird und dann die gleiche Transformation des zweiten Baums in einem Summe von höchstens umgekehrt wird 2n - 2 Schritte. Deshalb als Čulík & Wood (1982) bewiesen, der Rotationsabstand zwischen zwei beliebigen Bäumen ist höchstens 2n - 2.^[1]

Indem Sie das Problem in Bezug auf Flips von konvexen Polygonen anstelle von Bäumen in Betracht ziehen, Sleator, Tarjan & Thurston (1988) konnten zeigen, dass die Rotationsentfernung höchstens ist 2n - 6. In Bezug auf Triangulationen konvexer Polygone ist die rechte Wirbelsäule die Abfolge der Dreiecke, die am rechten Endpunkt der Wurzelkante erfasst sind, und der Baum, in dem alle Scheitelpunkte auf der Wirbelsäule liegen Fan -Triangulation für diesen Scheitelpunkt. Die Hauptidee ihrer Verbesserung besteht darin, beide Triangulationen zu einer Fan -Triangulation für jeden Scheitelpunkt zu versuchen, und nicht nur den für den richtigen Endpunkt der Wurzelkante. Es ist nicht möglich, dass all diese Entscheidungen gleichzeitig den schlimmsten Fall geben n - 1 von jeder Starttriangulation, die die Verbesserung verleiht.^[2]

Sleator, Tarjan & Thurston (1988) verwendete auch ein geometrisches Argument, um zu zeigen, dass für unendlich viele Werte von nDer maximale Drehabstand ist genau 2n - 6. Sie verwenden erneut die Interpretation des Problems in Bezug auf Triangulationen konvexer Polygone und interpretieren die Start- und Beendigungstriangulation als obere und untere Gesichter von a Konvexes Polyeder mit dem konvexen Polygon selbst interpretiert als Hamiltonian Circuit In diesem Polyeder. Unter dieser Interpretation kann eine Abfolge von Flips von einer Triangulation zur anderen in eine Sammlung von übersetzt werden Tetraeder Das trianguliert das gegebene dreidimensionale Polyeder. Sie finden eine Familie von Polyeder mit dem Grundstück, das (in dreidimensionalem Hyperbolische Geometrie) Das Polyeder hat ein großes Volumen, aber alle Tetraeder in ihnen haben viel kleineres Volumen, was bedeutet, dass viele Tetraeder in jeder Triangulation benötigt werden. Die binären Bäume, die die Übersetzung der oberen und unteren Gesichter dieser Polyeder in Bäume erhalten, haben zumindest einen hohen Rotationsabstand 2n - 6.^[2]

Anschließend, Pournin (2014) lieferte einen Beweis dafür für alle n ≥ 11Der maximale Drehabstand ist genau 2n - 6. Der Beweis von Pournins ist kombinatorisch und vermeidet die Verwendung hyperbolischer Geometrie.^[3]

Rechenkomplexität

Sowie die Definition der Rotationsentfernung, Čulík & Wood (1982) gefragt nach dem Rechenkomplexität Berechnung des Rotationsabstands zwischen zwei gegebenen Bäumen. Die Existenz von kurzen Rotationssequenzen zwischen zwei beliebigen Bäumen impliziert, dass das Testen der Rotationsabstand höchstens ist k gehört zum Komplexitätsklasse Np, aber es ist nicht bekannt, dass es ist NP-CompleteEs ist auch nicht bekannt, dass es lösbar ist in Polynomzeit. Der Algorithmus von Fordham berechnet jedoch den Drehabstand in der linearen Zeit, ermöglicht jedoch nur Rotationen am Wurzelknoten und seinem rechten Kind. Der Algorithmus von Fordham basiert auf einer Klassifizierung von Knoten in 7 Typen, und eine Nachschlagetabelle wird verwendet, um die Anzahl der Rotationen zu ermitteln, die erforderlich sind, um einen Knoten von einem Typ in einen anderen zu verwandeln.

Der Rotationsabstand zwischen zwei beliebigen Bäumen kann unter der äquivalenten Sicht der Polygon -Triangulationen durch die Anzahl der Diagonalen, die aus einer Triangulation entfernt werden müssen, unteren begrenzt werden und durch andere Diagonale ersetzt werden müssen, um die andere Triangulation zu erzeugen. Es kann auch durch die doppelte Zahl über die Obergrenze begrenzt werden, indem das Problem in Unterprobleme entlang jeder Diagonale aufgeteilt wird, die zwischen beiden Triangulationen geteilt werden und dann die Methode von anwenden Čulík & Wood (1982) zu jedem Teilproblem. Diese Methode liefert eine Näherungsalgorithmus für das Problem mit einem Annäherungsverhältnis von zwei.^[4] Ein ähnlicher Ansatz der Aufteilung in Teilprobleme entlang gemeinsamer Diagonalen führt zu a Fix-Parameter-Traktable Algorithmus zur Berechnung des Rotationsabstands genau.^[5][6]

Die Bestimmung der Komplexität der Berechnung des Rotationsabstands genau ohne Parametrisierung bleibt ungelöst und die besten Algorithmen Exponentialzeit.^[7] Die Existenz von Fordhams Algorithmus deutet jedoch nachdrücklich darauf hin, dass ein linearer Zeitalgorithmus für die Berechnung der Rotationsentfernung vorhanden ist.

Verweise