Was ist die Initialisierungszeit eines Link-Cut-Baums?

Link-Cut-Baum ist eine von Sleator und Tarjan erfundene Datenstruktur, die verschiedene Operationen und Abfragen in einer Knoten-Gesamtstruktur in Zeit O ( log n ) unterstützt . (Zum BeispielkombiniertOperation Link zwei Bäume im Wald zu einem, während Operation Cut einen Baum im Wald in zwei Bäume unterteilt.)$n$$O(\log n)$

Unter Verwendung von Link-Cut-Bäumen sind mehrere Anwendungen bekannt, und hier interessiert mich insbesondere Goodrichs Separatorzerlegung , bei der bei einem Knoten-Ebenengraphen G ein entsprechender Binärbaum erhalten werden kann, in dem Knoten Teilgraphen von G und die Kinder von sind ein Knoten H sind die Subgraphen von H durch den Separator auf geteilt H . Eine solche Zerlegung kann leicht in O ( n log n ) -Zeit konstruiert werden (da ein Separator in O ( n ) -Zeit gefunden werden kann und der Separator den so ausgeglichenen Graphen danach teilt$n$$G$$G$$H$$H$$H$$O(n \log n)$$O(n)$ Ebene von Trennungen die Blätter des Baumes sind der Größe O ( 1 ) ). Der Hauptbeitrag von Goodrich besteht darin, dass er eine solche Zerlegung in der Zeit O ( n ) konstruieren kann, indem er die Datenstrukturen beibehält und wiederverwendet, die zum Auffinden von Trennzeichen in jeder Ebene verwendet werden.$O(\log n)$$O(1)$$O(n)$

Eine der Datenstrukturen, die bei der Konstruktion verwendet werden, ist in der Tat der Link-Cut-Baum. Auf Seite 7 des Papiers von Goodrich behauptete er, dass die Initialisierung des Link-Cut-Baums in der Zeit . Während ich alle dort zitierten Artikel durcharbeite, scheint es mir, dass es insgesamt Zeit O ( n log n ) braucht , wenn wir einen Link-Cut-Baum über Operation Link erstellen .$O(n)$$O(n \log n)$

Verstehe ich etwas falsch? Kann die Initialisierung eines Link-Cut-Baums in der Zeit ?$O(n)$

Vielen Dank an Hsueh-I Lu , meinen Lehrer an der National Taiwan University, der die folgende Lösung anbietet.

Es stellt sich heraus, dass die Antwort ziemlich einfach ist; Bei der Initialisierung einer Datenstruktur müssen wir die Struktur nicht anhand der von ihr unterstützten Abfragen und Operationen erstellen . Natürlich können wir während der Erstellung keine Abfragen durchführen, wie wir es normalerweise tun, wenn wir den Baum durch Verknüpfungsoperation erstellen . In dieser Separator-Zerlegungsanwendung benötigen wir sie jedoch nicht.

Das heißt, in der Anwendung auf die Separatorzerlegung müssen wir die Link-Cut-Bäume L (T) für den Spanning Tree T im Eingabegraphen G konstruieren, anstatt die Strukturen und Werte der Bäume L (T zu berechnen ) Durch Verknüpfungsoperation berechnen wir direkt die Schwer-Leicht-Pfadzerlegung des Baums T und konstruieren die entsprechende binäre Baumstruktur für jeden Pfad und kleben die binären Bäume gemäß der Pfadzerlegung. Alle Schritte können in linearer Zeit ausgeführt werden.

Für jeden erforderlichen Wert auf den Knoten von L (T) weisen wir die vorberechneten Werte zu, da jeder Wert in linearer Zeit (in dieser Anwendung) aus T berechnet werden kann, anstatt Werte für binäre Baumstrukturen zuzuweisen und beim Verkleben der Bäume zu aktualisieren direkt auf die Knoten der endgültigen Link-Cut-Bäume L (T). Es muss nur ein konstanter Wertetyp zugewiesen werden, und dies kann wiederum in linearer Zeit erfolgen.

Kapitel 5.1 in "Datenstrukturen und Netzwerkalgorithmen", das ist ref. 43 in dem von Ihnen zitierten Artikel scheint die Antwort zu sein:

http://books.google.com/books?id=JiC7mIqg-X4C&lpg=PP1&ots=8frbjj8vL0&dq=data%20structures%20and%20network%20algorithms&pg=PA59#v=onepage&q&f=false

... Bei der Erörterung dieses Problems werden wir 'm' verwenden, um die Anzahl der Operationen zu bezeichnen, und 'n', um die Anzahl der Eckpunkte zu bezeichnen (Maketree-Operationen). Eine Möglichkeit, dieses Problem zu lösen, besteht darin, mit jedem Scheitelpunkt sein übergeordnetes Element und seine Kosten zu speichern. Bei dieser Darstellung benötigt jede Maketree-, Link- oder Cut-Operation O (1) Zeit, und jede Findroot-, Findcost- oder Addcost-Operation benötigt Zeit proportional zur Tiefe des Eingabescheitelpunkts, der O (n) ist ...

In der Vorschau stehen mehrere aufeinanderfolgende Seiten zur Verfügung.