In der getrennten Mathematik ist Baumfolge eine Operation auf einem binären Baum, der die Struktur ändert, ohne die Ordnung der Elemente zu stören. Eine Baumfolge bringt einen Knoten im Baum und einen Knoten unten heran. Es wird verwendet, um die Gestalt des Baums zu ändern, und insbesondere seine Höhe durch das Herunterlassen kleinerer Subbäume und größerer Subbäume zu vermindern, auf verbesserte Leistung von vielen Baumoperationen hinauslaufend.

Dort besteht eine Widersprüchlichkeit in verschiedenen Beschreibungen betreffs der Definition der Richtung von Folgen. Einige sagen, dass die Richtung einer Folge von der Seite abhängt, die die Baumknoten darauf ausgewechselt werden, während andere sagen, dass es abhängt, welches Kind den Platz der Wurzel (Gegenteil vom ersteren) nimmt. Dieser Artikel nimmt die Annäherung der Seite, wohin die Knoten dazu ausgewechselt werden.

Illustration

Die richtige Folge-Operation, die so im Image oben gezeigt ist, wird mit Q durchgeführt wie die Wurzel und ist folglich eine richtige Folge auf, oder eingewurzelt an, Q. Diese Operation läuft auf eine Folge des Baums in im Uhrzeigersinn Richtung hinaus. Der inverse Betrieb ist die linke Folge, die auf eine Bewegung auf gegen den Uhrzeigersinn Richtung hinausläuft (die linke Folge, die oben gezeigt ist, wird an P eingewurzelt). Der Schlüssel zum Verstehen, wie eine Folge fungiert, soll seine Einschränkungen verstehen. Insbesondere kann sich die Ordnung der Blätter des Baums (wenn gelesen, link zum Recht zum Beispiel) nicht ändern (eine andere Weise, daran zu denken, besteht darin, dass die Ordnung, dass die Blätter in einer Tiefe die erste Suche besucht würden, dasselbe nach der Operation wie zuvor sein muss). Eine andere Einschränkung ist das Haupteigentum eines binären Suchbaums nämlich, dass das richtige Kind größer ist, als der Elternteil und das linke Kind kleiner sind als der Elternteil. Bemerken Sie, dass das richtige Kind eines linken Kindes der Wurzel eines Subbaums (zum Beispiel Knoten B im Diagramm für den Baum, der an Q eingewurzelt ist), das linke Kind der Wurzel werden kann, die selbst das richtige Kind der "neuen" Wurzel im rotieren gelassenen Subbaum wird, ohne jede jener Einschränkungen zu verletzen. Wie Sie im Diagramm sehen können, ändert sich die Ordnung der Blätter nicht. Die entgegengesetzte Operation bewahrt auch die Ordnung und ist die zweite Art der Folge.

Das Annehmen das ist ein binärer Suchbaum, wie oben angegeben, die Elemente, muss als Variablen interpretiert werden, die im Vergleich zu einander sein können. Die alphabetischen Charaktere werden oben als Platzhalter für diese Variablen verwendet.

Ausführliche Illustration

Wenn ein Subbaum rotieren gelassen wird, vermindert die Subbaumseite, auf die er rotieren gelassen wird, seine Höhe durch einen Knoten, während der andere Subbaum seine Höhe vergrößert. Das macht Baumfolgen nützlich, für einen Baum wiederzuerwägen.

Das Verwenden der Fachsprache dessen Wühlt nach dem Elternteilknoten der Subbäume, um zu rotieren, Sich für den Knoten Zu drehen, der der neue Elternteilknoten, RS für die Folge-Seite werden wird auf zu rotieren und OS für die Gegenseite der Folge. Im obengenannten Diagramm für die Wurzel Q ist der RS C, und der OS ist P. Der Pseudocode für die Folge ist:

Türangel = Wurzel. OS

Wurzel. OS = Türangel. RS

Türangel. RS = lassen einwurzeln

Wurzel = Türangel

Das ist eine unveränderliche Zeitoperation.

Der Programmierer muss auch sicherstellen, dass der Elternteil der Wurzel zur Türangel nach der Folge hinweist. Außerdem sollte der Programmierer bemerken, dass diese Operation auf eine neue Wurzel für den kompletten Baum hinauslaufen und darauf achten kann, Zeigestöcke entsprechend zu aktualisieren.

Inorder Invariance

Die Baumfolge macht das inorder Traversal des binären Baums invariant. Das deutet an, dass die Ordnung der Elemente nicht betroffen wird, wenn eine Folge in jedem Teil des Baums durchgeführt wird. Hier sind die inorder Traversals der Bäume, die oben gezeigt sind:

Verlassener Baum: ((A, P, B), Q, C) Richtiger Baum: (A, P, (B, Q, C))

</pre>

Die Computerwissenschaft ein vom anderen ist sehr einfach. Der folgende ist Beispiel-Pythonschlange-Code, der diese Berechnung durchführt:

def right_rotation (treenode):

link, Q, C = treenode

A, P, B = hat verlassen

kehren Sie (A, P, (B, Q, C)) zurück

</pre>

Eine andere Weise, darauf zu schauen, ist:

Richtige Folge des Knotens Q:

Lassen Sie P das linke Kind von Q sein.

Satz P, um die neue Wurzel zu sein.

Veranlassen Sie das linke Kind von Q, das richtige Kind von P zu sein.

Veranlassen Sie das richtige Kind von P, Q zu sein.

</pre>

Verlassene Folge des Knotens P:

Lassen Sie Q das richtige Kind von P sein.

Satz Q, um die neue Wurzel zu sein.

Veranlassen Sie das richtige Kind von P, das linke Kind von Q zu sein.

Veranlassen Sie das linke Kind von Q, P zu sein.

</pre>

Alle anderen Verbindungen werden verlassen, wie - ist.

Es gibt auch doppelte Folgen, die Kombinationen von linken und richtigen Folgen sind. Eine doppelte linke Folge an X kann definiert werden, um eine richtige Folge am richtigen Kind X gefolgt von einer linken Folge an X zu sein; ähnlich kann eine doppelte richtige Folge an X definiert werden, um eine linke Folge am linken Kind X gefolgt von einer richtigen Folge an X zu sein.

Baumfolgen werden in mehreren Baumdatenstrukturen wie AVL-Bäume, rot-schwarze Bäume, gespreizte Bäume und treaps verwendet. Sie verlangen nur unveränderliche Zeit, weil sie lokale Transformationen sind: Sie funktionieren nur auf 5 Knoten, und brauchen den Rest des Baums nicht zu untersuchen.

Folgen für das Wiederausgleichen

Ein Baum kann mit Folgen wiedererwogen werden. Nach einer Folge vergrößert die Seite der Folge seine Höhe um 1, während die Seite gegenüber der Folge seine Höhe ähnlich vermindert. Deshalb kann man Folgen auf Knoten strategisch anwenden, deren sich linkes Kind und richtiges Kind in der Höhe durch mehr als 1 unterscheiden. Selbstbalancierende binäre Suchbäume wenden diese Operation automatisch an. Ein Typ des Baums, der diese wiederbalancierende Technik verwendet, ist der AVL Baum.

Folge-Entfernung

Die Folge-Entfernung zwischen irgendwelchen zwei binären Bäumen mit derselben Zahl von Knoten ist die minimale Zahl von Folgen musste sich ein zum anderen verwandeln. Mit dieser Entfernung wird der Satz des N-Knotens binäre Bäume ein metrischer Raum: Die Entfernung ist symmetrisch, wenn gegeben, zwei verschiedene Bäume positiv, und befriedigt die Dreieck-Ungleichheit.

Es ist ein offenes Problem, ob dort ein polynomischer Zeitalgorithmus besteht, um Folge-Entfernung zu berechnen.

Daniel Sleator, Robert Tarjan und William Thurston haben gezeigt, dass die Folge-Entfernung zwischen irgendwelchen zwei N-Knotenbäumen (für n  11) höchstens 2n &minus ist; 6, und dass ungeheuer viele Paare von Bäumen das weit einzeln sind.

Siehe auch

• AVL Baum, rot-schwarzer Baum, und gespreizter Baum, Arten von binären Suchbaumdatenstrukturen, die Folgen verwenden, um Gleichgewicht aufrechtzuerhalten.
• Associativity einer binären Operation meint, dass das Durchführen einer Baumfolge darauf das Endresultat nicht ändert.
• Gitter von Tamari, ein teilweise bestellter Satz, in dem die Elemente als binäre Bäume und die Einrichtung zwischen Elementen definiert werden können, werden durch die Baumfolge definiert.

Links

• Java applets demonstrierende Baumfolgen
• Der AVL Baumfolge-Tutorenkurs (Volltextformat) durch John Hargrove