Baum verbinden/schneiden - Link/cut tree

Ein Link/Cut-Tree ist eine Datenstruktur zur Darstellung eines Waldes , einer Menge verwurzelter Bäume , und bietet die folgenden Operationen:

• Fügen Sie der Gesamtstruktur einen Baum hinzu, der aus einem einzelnen Knoten besteht.
• Wenn ein Knoten in einem der Bäume vorhanden ist, trennen Sie ihn (und seinen Unterbaum) von dem Baum, zu dem er gehört.
• Hängen Sie einen Knoten an einen anderen Knoten als seinen untergeordneten Knoten an.
• Suchen Sie bei einem gegebenen Knoten die Wurzel des Baums, zu dem er gehört. Indem man diese Operation an zwei verschiedenen Knoten durchführt, kann man überprüfen, ob sie zum selben Baum gehören.

Der dargestellte Wald kann aus sehr tiefen Bäumen bestehen. Wenn wir den Wald also als einfache Sammlung von übergeordneten Zeigerbäumen darstellen , kann es lange dauern, die Wurzel eines bestimmten Knotens zu finden. Wenn wir jedoch jeden Baum im Wald als Link/Cut-Baum darstellen, können wir in O (log( n )) amortisierter Zeit herausfinden, zu welchem ​​Baum ein Element gehört . Darüber hinaus können wir die Sammlung von Verknüpfungs-/Schnittbäumen schnell an Veränderungen im dargestellten Wald anpassen. Insbesondere können wir es so anpassen, dass es in O ( log (n)) amortisierter Zeit zusammengeführt (link) und aufgeteilt (cut) wird.

Verknüpfungs-/Schnittbäume unterteilen jeden Baum im dargestellten Wald in vertex-disjunkte Pfade, wobei jeder Pfad durch eine Hilfsdatenstruktur repräsentiert wird (oft Spreizbäume , obwohl das ursprüngliche Papier Spreizbäume älter ist und daher verzerrte binäre Suchbäume verwendet). Die Knoten in der Hilfsdatenstruktur sind nach ihrer Tiefe im entsprechenden dargestellten Baum geordnet. In einer Variante, Naive Partitioning , werden die Pfade durch die zuletzt aufgerufenen Pfade und Knoten bestimmt, ähnlich wie bei Tango Trees . Bei der Partitionierung nach Größe werden Pfade durch das schwerste Kind (Kind mit den meisten Kindern) des angegebenen Knotens bestimmt. Dies ergibt eine kompliziertere Struktur, reduziert jedoch die Kosten der Operationen von amortisiertem O(log n) auf den ungünstigsten Fall O(log n). Es hat Verwendungen bei der Lösung einer Vielzahl von Netzwerkflussproblemen und zum Jive von Datensätzen.

In der ursprünglichen Veröffentlichung bezeichneten Sleator und Tarjan Link/Cut-Bäume als „dynamische Bäume“ oder „dynamische Prüfstandsbäume“.

Struktur

Wir nehmen einen Baum, in dem jeder Knoten einen beliebigen Grad an ungeordneten Knoten hat, und teilen ihn in Pfade auf. Wir nennen dies den dargestellten Baum . Diese Pfade werden intern durch Hilfsbäume repräsentiert (hier werden wir Splay Trees verwenden), wobei die Knoten von links nach rechts den Pfad von der Wurzel zum letzten Knoten auf dem Pfad darstellen. Knoten, die im dargestellten Baum verbunden sind, die sich nicht auf demselben bevorzugten Pfad (und daher nicht im gleichen Hilfsbaum) befinden, werden über einen Pfad-Eltern-Zeiger verbunden . Dieser Zeiger wird in der Wurzel des Hilfsbaums gespeichert, der den Pfad darstellt.

Demonstrieren, wie Knoten nach Tiefe im Link-Cut-Baum gespeichert werden

Bevorzugte Wege

Beim Zugriff auf einen Knoten v im dargestellten Baum wird der gewählte Pfad zum bevorzugten Pfad . Das bevorzugte Kind eines Knotens ist das letzte Kind, das sich auf dem Zugriffspfad befand, oder null, wenn der letzte Zugriff auf v erfolgte oder keine Zugriffe auf diesen bestimmten Zweig des Baums erfolgten. Eine bevorzugte Kante ist die Kante, die das bevorzugte Kind mit v verbindet .

In einer alternativen Version werden die bevorzugten Pfade vom schwersten Kind bestimmt.

Es wird gezeigt, wie ein Link-Cut-Baum bevorzugte Pfade in einen Wald aus Bäumen verwandelt.

Betrieb

Die Operationen, die uns interessieren, sind FindRoot(Node v), Cut(Node v), Link(Node v, Node w) und Path(Node v). Jede Operation wird unter Verwendung des Unterprogramms Access(Node v) implementiert. Wenn wir auf einen Scheitelpunkt v zugreifen , wird der bevorzugte Pfad des repräsentierten Baums in einen Pfad von der Wurzel R des repräsentierten Baums zum Knoten v geändert . Wenn ein Knoten auf dem Zugriffspfad zuvor ein bevorzugtes Kind u hatte und der Pfad jetzt zu Kind w geht , wird die alte bevorzugte Kante gelöscht (geändert in einen Pfad-Elternzeiger ), und der neue Pfad geht nun durch w .

Zugang

Nach dem Durchführen eines Zugriffs auf den Knoten v hat dieser keine bevorzugten Kinder mehr und befindet sich am Ende des Pfads. Da Knoten im Hilfsbaum nach Tiefe kodiert sind, bedeutet dies, dass alle Knoten rechts von v im Hilfsbaum getrennt werden müssen. In einem Spreizbaum ist dies ein relativ einfaches Verfahren; wir spreizen bei v , was v zur Wurzel des Hilfsbaums bringt . Wir trennen dann den rechten Teilbaum von v , das ist jeder Knoten, der auf dem vorherigen bevorzugten Pfad darunter lag. Die Wurzel des getrennten Baums hat einen Pfad-Eltern-Zeiger, auf den wir auf v zeigen .

Wir gehen nun den repräsentierten Baum zur Wurzel R hinauf , unterbrechen und setzen den bevorzugten Pfad, wo nötig, zurück. Dazu folgen wir dem Pfad-Eltern-Zeiger von v (da v jetzt die Wurzel ist, haben wir direkten Zugriff auf den Pfad-Eltern-Zeiger). Wenn der Pfad, auf dem sich v befindet, bereits die Wurzel R enthält (da die Knoten nach der Tiefe kodiert sind, wäre dies der am weitesten links liegende Knoten im Hilfsbaum), ist der Pfad-Eltern-Zeiger null, und der Zugriff ist abgeschlossen. Andernfalls folgen wir dem Zeiger auf einen Knoten auf einem anderen Pfad w . Wir wollen den alten bevorzugten Pfad von w durchbrechen und ihn wieder mit dem Pfad verbinden, auf dem v ist. Um dies zu tun, spreizen wir bei w und trennen seinen rechten Teilbaum, indem wir seinen Pfad-Eltern-Zeiger auf w setzen . Da alle Knoten nach der Tiefe verschlüsselt sind und jeder Knoten im Pfad von v tiefer ist als jeder Knoten im Pfad von w (da sie Kinder von w im dargestellten Baum sind), verbinden wir einfach den Baum von v als das richtige Kind von w . Wir spreizen wieder bei v , was, da v ein Kind der Wurzel w ist , v einfach zur Wurzel dreht . Wir wiederholen diesen gesamten Vorgang, bis der Pfad-Eltern-Zeiger von v null ist, an welchem ​​Punkt er sich auf demselben bevorzugten Pfad wie die Wurzel des repräsentierten Baums R befindet .

Während eines Zugriffs werden alte bevorzugte Pfade unterbrochen und durch Pfad-Eltern-Zeiger ersetzt, während der Knoten, auf den zugegriffen wird, zur Wurzel des Baums gespreizt wird

FindRoot

FindRoot bezieht sich auf das Finden der Wurzel des repräsentierten Baums, der den Knoten v enthält . Da die Zugriffs- Subroutine v auf den bevorzugten Pfad setzt, führen wir zuerst einen Zugriff aus. Nun liegt der Knoten v auf dem gleichen bevorzugten Pfad und somit dem gleichen Hilfsbaum wie die Wurzel R . Da die Hilfsbäume nach der Tiefe kodiert sind, ist die Wurzel R der am weitesten links liegende Knoten des Hilfsbaums. Wir wählen also einfach rekursiv das linke Kind von v aus, bis wir nicht mehr weiterkommen und dieser Knoten die Wurzel R ist . Die Wurzel kann linear tief sein (was für einen Spreizbaum der schlimmste Fall ist), wir spreizen sie daher, damit der nächste Zugriff schnell ist.

Schneiden

Hier möchten wir den dargestellten Baum am Knoten v ausschneiden . Zuerst greifen wir auf v zu . Dadurch werden alle Elemente, die niedriger als v im repräsentierten Baum sind, als das rechte Kind von v im Hilfsbaum platziert. Alle Elemente, die sich jetzt im linken Teilbaum von v befinden, sind die Knoten, die höher als v im dargestellten Baum sind. Wir trennen daher das linke Kind von v (das durch seinen Pfad-Eltern-Zeiger immer noch eine Bindung an den ursprünglich repräsentierten Baum aufrechterhält). Nun ist v die Wurzel eines repräsentierten Baumes. Der Zugriff auf v unterbricht auch den bevorzugten Pfad unterhalb von v , aber dieser Unterbaum behält seine Verbindung zu v durch seinen Pfad-Eltern-Zeiger bei.

Verknüpfung

Wenn v eine Baumwurzel und w ein Knoten in einem anderen Baum ist, verknüpfen Sie die Bäume, die v und w enthalten, indem Sie die Kante (v, w) hinzufügen, wodurch w zum Elternteil von v wird . Dazu greifen wir sowohl auf v als auch auf w in ihren jeweiligen Bäumen zu und machen w zum linken Kind von v . Da v die Wurzel ist und Knoten im Hilfsbaum nach Tiefe kodiert sind, bedeutet der Zugriff auf v , dass v kein linkes Kind im Hilfsbaum hat (da es als Wurzel die minimale Tiefe ist). Das Hinzufügen von w als linkes Kind macht es effektiv zum Elternteil von v im repräsentierten Baum.

Weg

Für diese Operation möchten wir eine Aggregatfunktion über alle Knoten (oder Kanten) auf dem Pfad von Wurzel R zu Knoten v ausführen (wie "Summe" oder "Min" oder "Max" oder "Increase" usw.). Dazu greifen wir auf v zu , wodurch wir einen Hilfsbaum mit allen Knoten auf dem Pfad von Wurzel R zu Knoten v erhalten . Die Datenstruktur kann um Daten erweitert werden, die wir abrufen möchten, z. B. Min- oder Max-Werte oder die Summe der Kosten im Teilbaum, die dann von einem gegebenen Pfad in konstanter Zeit zurückgegeben werden können.

Pseudocode von Operationen

Switch-Preferred-Child(x, y):
    path-parent(right(x)) = x
    right(x, y)

Access(v):
    Switch-Path-Parent(v, null)
    while (v is not root)
        w = path-parent(v)
        splay(w)
        Switch-Path-Parent(w, v)
        path-parent(v) = null
        v = w
    splay(v)

Link(v, w):
    Access(v)
    Access(w)
    left(v) = w

Cut(v):
    Access(v)
    left(v) = null

Analyse

Schneiden und Verknüpfen haben O (1) Kosten, plus die des Zugriffs. FindRoot hat eine amortisierte Obergrenze von O (log n ) zuzüglich der Kosten des Zugriffs. Die Datenstruktur kann je nach Implementierung mit zusätzlichen Informationen (wie dem min- oder max-wertigen Knoten in seinen Unterbäumen oder der Summe) angereichert werden. Somit kann Path diese Informationen in konstanter Zeit zuzüglich der Zugriffsgrenze zurückgeben.

Es bleibt also den Zugang zu binden , um unsere Laufzeit zu finden.

Access verwendet das Spreizen, von dem wir wissen, dass es eine amortisierte obere Grenze von O (log n ) hat. Die verbleibende Analyse befasst sich also damit, wie oft wir spreizen müssen. Dies ist gleich der Anzahl der bevorzugten untergeordneten Änderungen (der Anzahl der Kanten, die im bevorzugten Pfad geändert wurden), während wir den Baum durchqueren.

Wir haben den Zugriff mit einer Technik namens Heavy-Light Decomposition gebunden .

Schwer-Leicht-Zersetzung

Diese Technik bezeichnet eine Kante als schwer oder leicht, abhängig von der Anzahl der Knoten im Unterbaum. repräsentiert die Anzahl der Knoten im Unterbaum von v im repräsentierten Baum. Eine Kante heißt schwer, wenn size(v) > 1 ⁄ 2 size(parent(v)). Somit können wir sehen, dass jeder Knoten höchstens 1 schwere Kante haben kann. Eine Kante, die keine schwere Kante ist, wird als leichte Kante bezeichnet. ${\displaystyle Größe (v)}$

Die Lichttiefe bezieht sich auf die Anzahl der Lichtkanten auf einem gegebenen Pfad von der Wurzel zum Scheitelpunkt v . Lichttiefe ≤ lg n, weil wir jedes Mal, wenn wir eine Lichtkante durchlaufen, die Anzahl der Knoten um mindestens den Faktor 2 verringern (da sie höchstens die Hälfte der Knoten der Eltern haben kann).

Eine gegebene Kante im dargestellten Baum kann also eine von vier Möglichkeiten sein: stark bevorzugt , stark nicht bevorzugt , leicht bevorzugt oder leicht nicht bevorzugt .

Zuerst beweisen wir eine obere Schranke. ${\displaystyle O(\log^{2}n)}$

O (log ² n ) obere Grenze

Die Spreizoperation des Zugriffs gibt uns log n , also müssen wir die Anzahl der Zugriffe auf log n begrenzen, um die Obergrenze von O (log ² n ) zu beweisen .

Jeder Wechsel der Vorzugskante führt zur Bildung einer neuen Vorzugskante. Wir zählen also die Anzahl der gebildeten bevorzugten Kanten. Da es höchstens log n Kanten gibt, die auf einem gegebenen Pfad hell sind, gibt es höchstens log n helle Kanten, die sich zu bevorzugt ändern.

Die Anzahl der bevorzugten Kanten kann für jede gegebene Operation gelten, aber sie wird amortisiert. Über eine Reihe von Ausführungen können n -1 schwere Kanten bevorzugt werden (da es im dargestellten Baum insgesamt höchstens n -1 schwere Kanten gibt), aber von da an ist die Anzahl der bevorzugten starken Kanten gleich der Zahl von schweren Kanten, die in einem vorherigen Schritt nicht bevorzugt wurden. Für jede schwere Kante, die unbeliebt wird, muss eine leichte Kante bevorzugt werden. Wir haben bereits gesehen, dass die Zahl der Lichtkanten, die bevorzugt werden können, höchstens log n beträgt . Die Anzahl der schweren Kanten, die für m Operationen bevorzugt werden, ist also . Bei genügend Operationen ( ) ergibt sich der Durchschnitt zu . ${\displaystyle O(n)}$${\displaystyle O(\log n)}$${\displaystyle m(\log n)+(n-1)}$${\displaystyle m>n-1}$${\displaystyle O(\log n)}$

Verbesserung auf O (log n ) obere Schranke

Wir haben die Anzahl der bevorzugten Child-Änderungen an gebunden. Wenn wir also zeigen können, dass sich die Kosten für jede bevorzugte Child-Änderung amortisiert haben, können wir die Zugriffsoperation an binden . Dies geschieht nach der Potentialmethode . ${\displaystyle O(\log n)}$${\displaystyle O(\log n)}$

Sei s(v) die Anzahl der Knoten unter v im Baum der Hilfsbäume. Dann die Potentialfunktion . Wir wissen, dass die fortgeführten Kosten der Aufteilung begrenzt sind durch: ${\displaystyle \Phi =\sum_{v}\log {s(v)}}$

${\displaystyle cost(splay(v))\leq 3\left(\log {s(root(v))}-\log {s(v)}\right)+1}$

Wir wissen, dass v nach dem Spreizen das Kind seines Pfad-Elternknotens w ist . Wir wissen also:

${\displaystyle s(v)\leq s(w)}$

Wir verwenden diese Ungleichheit und die amortisierten Zugangskosten, um eine Teleskopsumme zu erreichen, die begrenzt ist durch:

${\displaystyle 3\left(\log {s(R)}-\log {s(v)}\right)+O({\text{Anzahl der bevorzugten untergeordneten Änderungen}})}$

wobei R die Wurzel des repräsentierten Baums ist und wir wissen, dass die Anzahl der bevorzugten untergeordneten Änderungen beträgt . s ( R ) = n , also haben wir uns amortisiert. ${\displaystyle O(\log n)}$${\displaystyle O(\log n)}$

Anwendung

Link/Cut-Bäume können verwendet werden, um das dynamische Konnektivitätsproblem für azyklische Graphen zu lösen . Gegeben zwei Knoten x und y sind sie genau dann verbunden, wenn FindRoot(x) = FindRoot(y). Eine andere Datenstruktur, die für den gleichen Zweck verwendet werden kann, ist Euler Tour Tree .

Bei der Lösung des Maximum-Flow-Problems können Link/Cut-Bäume verwendet werden, um die Laufzeit des Dinic-Algorithmus von bis zu verbessern . ${\displaystyle O(V^{2}E)}$${\displaystyle O(VE\log V)}$

Siehe auch

• Spreizbaum
• Potentielle Methode

Weiterlesen