Referenz für den Hauptsatz über Baumrotationen

13

Von zwei binären Suchbäumen wird gesagt, dass sie linear äquivalent sind, wenn sie in ihren Durchquerungen in der richtigen Reihenfolge übereinstimmen. Der folgende Satz erklärt, warum Baumrotationen so grundlegend sind:

A und B seien binäre Suchbäume. Dann sind A und B genau dann linear äquivalent, wenn sie durch eine Folge von Baumrotationen verbunden sind.

Ich habe dieses Ergebnis bemerkt, als ich zum ersten Mal vor langer Zeit etwas über Datenstrukturen gelernt habe und den besonderen Status von Baumrotationen genauer verstehen wollte.

Der Beweis ist einfach und intuitiv: Drehen Sie das kleinste Element bis zur Wurzelposition entlang der linken Wirbelsäule. In der Reihenfolge Invariante kann dieser umgeordnete Baum keinen linken Teilbaum haben. Gehen Sie nun zum rechten Teilbaum. Das Ergebnis ist eine Normalform zum Testen der linearen Äquivalenz.

Obwohl es sich um einen grundlegenden Satz handelt, bin ich in der Literatur noch nie darauf gestoßen. Ich würde mich sehr über eine Referenz freuen, wenn ich dieses Ergebnis das nächste Mal verwenden kann.

(Bonus-Rätsel: Welcher Algorithmus ist der beste, um die kürzeste Folge von Baumrotationen zu finden, die zwei linear äquivalente binäre Suchbäume verbinden?)

reference-request ds.data-structures Per Vognsen
quelle
Ein anderer Ort, an dem nach einer Referenz gesucht werden muss, ist, dass das Äquivalenzmodul eines assoziativen Operators entscheidend ist, da dies auf dasselbe hinausläuft. Alle mir bekannten Referenzen halten dies jedoch für selbstverständlich.
Rob Simmons

Antworten:

10

Wie David Eppstein an dieser Stelle ausführt , ist es nicht bekannt, dass P selbst den kürzesten Pfad für binäre Bäume findet. In den Kommentaren zu dieser Antwort verweist er auf die besten aktuellen Grenzen

Suresh Venkat
quelle
Ich akzeptiere diese Antwort, da ich etwas daraus gelernt habe. Ich würde jedoch immer noch gerne eine Referenz für den Struktursatz finden, wenn jemand eine kennt.
Per Vognsen
11

Eine frühe Veröffentlichung, die diese Beobachtung explizit gemacht hat - Rotationen bewahren inorder Traversals -, ist (in Abbildung 2 von) Sleator und Tarjans 1983 selbstanpassende binäre Suchbäume . Die Move-to-Root-Heuristik wurde 1978 in Allen and Munros selbstorganisierendem Binary Search Trees- Artikel untersucht.

Lev Reyzin
quelle
Die interessante Richtung in Per's Äquivalenz ist nicht, dass Rotationen in der richtigen Reihenfolge beibehalten werden, sondern dass Sie mit Hilfe von Rotationen zwischen zwei beliebigen Bäumen reisen können, die die gleiche Reihenfolge haben.
Radu GRIGore
Ja - deshalb habe ich den Move-to-Root hinzugefügt. Es gibt auch eine andere Veröffentlichung von Sleator, Tarjan und Thurston (Rotationsabstand, Triangulationen und hyperbolische Geometrie), in der die Abstände zwischen zwei Bäumen berechnet werden, die ich in meiner Antwort nicht berücksichtigt habe. Ich glaube nicht, dass die Beobachtung von Per in irgendeiner Zeitung so erscheint, wie sie ist, aber ich würde es lieben, wenn ich mich als falsch erweisen würde.
Lev Reyzin
Richtig, die einfache Richtung ist ein notwendiger Bestandteil der Korrektheitsnachweise für AVL-Bäume, 2-3 Bäume usw. Die entgegengesetzte Richtung ist tiefer. Es heißt, dass Sie der Vollständigkeit halber keine strukturerhaltenden Transformationen außer Baumrotationen benötigen.
Per Vognsen
5

Ö(1)Ö(1) -Zeit ausgeführt werden soll.) Natürlich können Sie dies auch Interessieren Sie sich für die Referenzen innerhalb von.

Joan M. Lucas, Der Rotationsgraph binärer Bäume ist Hamiltonian, Journal of Algorithms, Band 8, Ausgabe 4, Dezember 1987, Seiten 503-535, ISSN 0196-6774, DOI: 10.1016 / 0196-6774 (87) 90048-4 .

Ein einfacherer, auch konstruktiver Beweis für die einfachere Tatsache, dass ein Hamiltonianer im Rotationsgraphen Pfad existiert, findet sich in diesem späteren Artikel, der von Lucas und ihren Mitarbeitern gemeinsam verfasst wurde.

Lucas JM, Vanbaronaigien DR, Ruskey F., Über Rotationen und die Erzeugung binärer Bäume, Journal of Algorithms, Band 15, Ausgabe 3, November 1993, Seiten 343-366, ISSN 0196-6774, DOI: 10.1006 / jagm.1993.1045 .

Maverick Woo
quelle
-2

Ein einfacherer, auch konstruktiver Beweis für die einfachere Tatsache, dass ein Hamilton-Pfad im Rotationsgraphen existiert, ist in diesem letzteren zu finden.

007singh
quelle
4
Ihre Antwort scheint unvollständig zu sein?
Jeremy