[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki25\/2021\/11\/30\/disjunkte-datenstruktur-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki25\/2021\/11\/30\/disjunkte-datenstruktur-wikipedia\/","headline":"Disjunkte Datenstruktur \u2013 Wikipedia","name":"Disjunkte Datenstruktur \u2013 Wikipedia","description":"before-content-x4 MakeSet erzeugt 8 Singletons. Nach einigen Operationen von Union, einige S\u00e4tze werden zusammen gruppiert. In der Informatik, u disjunkte","datePublished":"2021-11-30","dateModified":"2021-11-30","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki25\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki25\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/6\/67\/Dsu_disjoint_sets_init.svg\/360px-Dsu_disjoint_sets_init.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/6\/67\/Dsu_disjoint_sets_init.svg\/360px-Dsu_disjoint_sets_init.svg.png","height":"33","width":"360"},"url":"https:\/\/wiki.edu.vn\/wiki25\/2021\/11\/30\/disjunkte-datenstruktur-wikipedia\/","wordCount":12558,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4  MakeSet  erzeugt 8 Singletons.  Nach einigen Operationen von Union, einige S\u00e4tze werden zusammen gruppiert.In der Informatik, u disjunkte Datenstruktur, auch a . genannt union\u2013Datenstruktur finden oder Zusammenf\u00fchren\u2013Suchen-Set, ist eine Datenstruktur, die eine Sammlung von disjunkten (nicht \u00fcberlappenden) Mengen speichert.  \u00c4quivalent speichert es eine Partition einer Menge in disjunkte Teilmengen.  Es bietet Operationen zum Hinzuf\u00fcgen neuer Mengen, zum Zusammenf\u00fchren von Mengen (ersetzen durch ihre Vereinigung) und zum Finden eines repr\u00e4sentativen Mitglieds einer Menge.  Die letzte Operation erm\u00f6glicht es, effizient herauszufinden, ob sich zwei Elemente in denselben oder unterschiedlichen Mengen befinden.  Obwohl es mehrere M\u00f6glichkeiten gibt, disjunkte Datenstrukturen zu implementieren, werden sie in der Praxis oft mit einer bestimmten Implementierung namens a . identifiziert disjunkter Wald.  Dies ist ein spezialisierter Waldtyp, der Vereinigungen und Funde in nahezu konstanter amortisierter Zeit durchf\u00fchrt.  Um eine Sequenz von . auszuf\u00fchren m Additions-, Vereinigungs- oder Suchoperationen in einer disjunkten Gesamtstruktur mit n Knoten ben\u00f6tigt Gesamtzeit \u00d6(m\u03b1(n)), wo \u03b1(n) ist die extrem langsam wachsende inverse Ackermann-Funktion.  Disjunkte Gesamtstrukturen garantieren diese Leistung nicht pro Vorgang.  Einzelne Vereinigungs- und Suchvorg\u00e4nge k\u00f6nnen l\u00e4nger als eine konstante Zeit dauern \u03b1(n) Zeit, aber jede Operation bewirkt, dass sich die Gesamtstruktur der disjunkten Menge selbst anpasst, sodass aufeinanderfolgende Operationen schneller sind.  Disjunkte W\u00e4lder sind sowohl asymptotisch optimal als auch praktisch effizient.  Datenstrukturen mit disjunkten Mengen spielen eine Schl\u00fcsselrolle in Kruskals Algorithmus zum Auffinden des minimalen Spannbaums eines Graphen.  Die Bedeutung von minimalen Spannb\u00e4umen bedeutet, dass disjunkte Datenstrukturen einer Vielzahl von Algorithmen zugrunde liegen.  Dar\u00fcber hinaus haben disjunkte Datenstrukturen auch Anwendungen f\u00fcr symbolische Berechnungen sowie in Compilern, insbesondere f\u00fcr Registerzuordnungsprobleme.Table of ContentsGeschichte[edit]Darstellung[edit]Betrieb[edit]Neue Sets erstellen[edit]Setvertreter finden[edit]Zusammenf\u00fchren von zwei S\u00e4tzen[edit]Zeitkomplexit\u00e4t[edit]Beweis der O(log*(n)) Zeitkomplexit\u00e4t von Union-Find[edit]Anwendungen[edit]Siehe auch[edit]Verweise[edit]Externe Links[edit]Geschichte[edit]Disjunkte W\u00e4lder wurden erstmals 1964 von Bernard A. Galler und Michael J. Fischer beschrieben.[2]  1973 war ihre zeitliche Komplexit\u00e4t begrenzt auf \u00d6(Protokoll*\u2061(n)){displaystyle O(log^{*}(n))}, der iterierte Logarithmus von   n{displaystyle n}, von Hopcroft und Ullman.[3]  1975 bewies Robert Tarjan als erster die \u00d6(m\u03b1(n)){displaystyle O(malpha(n))}  (inverse Ackermann-Funktion) obere Schranke der Zeitkomplexit\u00e4t des Algorithmus,[4]  und zeigte 1979, dass dies die untere Grenze f\u00fcr einen eingeschr\u00e4nkten Fall war.[5]  Das haben Fredman und Saks 1989 gezeigt \u03a9(\u03b1(n)){displaystyle Omega (alpha (n))}  (amortisierte) W\u00f6rter m\u00fcssen abgerufen werden durch irgendein disjunkte Datenstruktur pro Operation,[6]  Damit wird die Optimalit\u00e4t der Datenstruktur bewiesen.1991 ver\u00f6ffentlichten Galil und Italiano eine \u00dcbersicht \u00fcber Datenstrukturen f\u00fcr disjunkte Mengen.[7]1994 beschrieben Richard J. Anderson und Heather Woll eine parallelisierte Version von Union-Find, die niemals blockiert werden muss.[8]2007 entwickelten Sylvain Conchon und Jean-Christophe Filli\u00e2tre eine persistente Version der disjunkten Walddatenstruktur, die eine effiziente Beibehaltung fr\u00fcherer Versionen der Struktur erm\u00f6glichte, und formalisierten ihre Korrektheit mit dem Beweisassistenten Coq.[9]  Die Implementierung ist jedoch nur asymptotisch, wenn sie ephemer verwendet wird oder wenn dieselbe Version der Struktur wiederholt mit begrenztem Backtracking verwendet wird.Darstellung[edit]Jeder Knoten in einem Wald mit disjunkter Menge besteht aus einem Zeiger und einigen Hilfsinformationen, entweder einer Gr\u00f6\u00dfe oder einem Rang (aber nicht beides).  Die Zeiger werden verwendet, um \u00fcbergeordnete Zeigerb\u00e4ume zu erstellen, wobei jeder Knoten, der nicht die Wurzel eines Baums ist, auf seinen \u00fcbergeordneten Knoten zeigt.  Um Root-Knoten von anderen zu unterscheiden, haben ihre Elternzeiger ung\u00fcltige Werte, wie z. B. einen zirkul\u00e4ren Verweis auf den Knoten oder einen Sentinel-Wert.  Jeder Baum stellt eine im Wald gespeicherte Menge dar, wobei die Mitglieder der Menge die Knoten im Baum sind.  Wurzelknoten stellen Mengenrepr\u00e4sentanten bereit: Zwei Knoten befinden sich genau dann in derselben Menge, wenn die Wurzeln der B\u00e4ume, die die Knoten enthalten, gleich sind.Knoten in der Gesamtstruktur k\u00f6nnen auf beliebige Weise gespeichert werden, die f\u00fcr die Anwendung geeignet ist, aber eine g\u00e4ngige Technik besteht darin, sie in einem Array zu speichern.  In diesem Fall k\u00f6nnen Eltern durch ihren Array-Index angegeben werden.  Jeder Array-Eintrag erfordert \u0398(log n) Speicherbits f\u00fcr den Elternzeiger.  F\u00fcr den Rest des Eintrags ist eine vergleichbare oder geringere Speichermenge erforderlich, daher ist die Anzahl der zum Speichern des Waldes erforderlichen Bits (n Protokoll n).  Wenn eine Implementierung Knoten fester Gr\u00f6\u00dfe verwendet (wodurch die maximale Gr\u00f6\u00dfe des Waldes begrenzt wird, der gespeichert werden kann), ist der erforderliche Speicher linear in n.Betrieb[edit]Datenstrukturen mit disjunkten Mengen unterst\u00fctzen drei Operationen: Erstellen einer neuen Menge, die ein neues Element enth\u00e4lt;  Finden des Repr\u00e4sentanten der Menge, die ein gegebenes Element enth\u00e4lt;  und Zusammenf\u00fchren von zwei S\u00e4tzen.Neue Sets erstellen[edit]Die MakeSet Operation f\u00fcgt ein neues Element hinzu.  Dieses Element wird in einen neuen Satz platziert, der nur das neue Element enth\u00e4lt, und der neue Satz wird der Datenstruktur hinzugef\u00fcgt.  Wenn die Datenstruktur stattdessen als Teilung einer Menge betrachtet wird, dann ist die MakeSet Die Operation vergr\u00f6\u00dfert die Menge durch Hinzuf\u00fcgen des neuen Elements und erweitert die vorhandene Partition, indem das neue Element in eine neue Untermenge eingef\u00fcgt wird, die nur das neue Element enth\u00e4lt.In einem zusammenhanglosen Wald, MakeSet initialisiert den Elternzeiger des Knotens und die Gr\u00f6\u00dfe oder den Rang des Knotens.  Wenn eine Wurzel durch einen Knoten repr\u00e4sentiert wird, der auf sich selbst zeigt, kann das Hinzuf\u00fcgen eines Elements mit dem folgenden Pseudocode beschrieben werden:function MakeSet(x) is    if x is not already in the forest then        x.parent\u00a0:= x        x.size\u00a0:= 1     \/\/ if nodes store size        x.rank\u00a0:= 0     \/\/ if nodes store rank    end ifend functionDiese Operation hat eine konstante Zeitkomplexit\u00e4t.  Insbesondere das Initialisieren eines disjunkten Waldes mit n Knoten erfordert \u00d6(n)Zeit.In der Praxis, MakeSet muss eine Operation vorausgehen, die Speicher zuweist, um zu halten x.  Solange die Speicherzuweisung ein amortisierter Vorgang mit konstanter Zeit ist, wie es f\u00fcr eine gute dynamische Array-Implementierung der Fall ist, \u00e4ndert dies nicht die asymptotische Leistung der Zufallsstruktur.Setvertreter finden[edit]Die Find Operation folgt der Kette von Elternzeigern von einem angegebenen Abfrageknoten x bis es ein Wurzelelement erreicht.  Dieses Wurzelelement stellt die Menge dar, zu der x geh\u00f6rt und kann sein x selbst.  Find gibt das erreichte Wurzelelement zur\u00fcck.Ausf\u00fchren von a Find Der Betrieb stellt eine wichtige Chance zur Verbesserung des Waldes dar.  Die Zeit in a Find Die Operation wird damit verbracht, \u00fcbergeordnete Zeiger zu verfolgen, daher f\u00fchrt ein flacherer Baum zu schnelleren Find Operationen.  Wenn ein Find ausgef\u00fchrt wird, gibt es keinen schnelleren Weg, die Wurzel zu erreichen, als jedem Elternzeiger nacheinander zu folgen.  Die w\u00e4hrend dieser Suche besuchten Elternzeiger k\u00f6nnen jedoch aktualisiert werden, um n\u00e4her auf die Wurzel zu zeigen.  Da jedes Element, das auf dem Weg zu einer Wurzel besucht wird, Teil desselben Sets ist, \u00e4ndert dies nichts an den im Forest gespeicherten Sets.  Aber es macht Zukunft Find Operationen schneller, nicht nur f\u00fcr die Knoten zwischen dem Abfrageknoten und der Wurzel, sondern auch f\u00fcr deren Nachkommen.  Diese Aktualisierung ist ein wichtiger Bestandteil der amortisierten Leistungsgarantie der disjunkten Gesamtstruktur.Es gibt mehrere Algorithmen f\u00fcr Find die die asymptotisch optimale Zeitkomplexit\u00e4t erreichen.  Eine Familie von Algorithmen, bekannt als Pfadkomprimierung, l\u00e4sst jeden Knoten zwischen dem Abfrageknoten und dem Stamm auf den Stamm verweisen.  Die Pfadkomprimierung kann mit einer einfachen Rekursion wie folgt implementiert werden:function Find(x) is    if x.parent \u2260 x then        x.parent\u00a0:= Find(x.parent)        return x.parent    else        return x    end ifend functionDiese Implementierung macht zwei Durchg\u00e4nge, einen den Baum hinauf und einen zur\u00fcck nach unten.  Es erfordert gen\u00fcgend Arbeitsspeicher, um den Pfad vom Abfrageknoten zum Stamm zu speichern (im obigen Pseudocode wird der Pfad implizit unter Verwendung des Aufrufstapels dargestellt).  Dies kann auf eine konstante Speichermenge verringert werden, indem beide Durchg\u00e4nge in die gleiche Richtung ausgef\u00fchrt werden.  Die Konstantenspeicherimplementierung geht zweimal vom Abfrageknoten zum Stamm, einmal, um den Stamm zu finden und einmal, um Zeiger zu aktualisieren:function Find(x) is    root\u00a0:= x    while root.parent \u2260 root do        root\u00a0:= root.parent    end while    while x.parent \u2260 root do        parent\u00a0:= x.parent        x.parent\u00a0:= root        x\u00a0:= parent    end while    return rootend functionTarjan und Van Leeuwen entwickelten auch One-Pass Find Algorithmen, die die gleiche Worst-Case-Komplexit\u00e4t beibehalten, aber in der Praxis effizienter sind.[4]    Diese werden Pfadaufspaltung und Pfadhalbierung genannt.  Beide aktualisieren die Elternzeiger von Knoten auf dem Pfad zwischen dem Abfrageknoten und der Wurzel.  Pfadaufteilung ersetzt jeden Elternzeiger auf diesem Pfad durch einen Zeiger auf den Gro\u00dfelternknoten des Knotens:function Find(x) is    while x.parent \u2260 x do        (x, x.parent)\u00a0:= (x.parent, x.parent.parent)    end while    return xend functionWeghalbierung funktioniert \u00e4hnlich, ersetzt aber nur jeden anderen Elternzeiger:function Find(x) is    while x.parent \u2260 x do        x.parent\u00a0:= x.parent.parent        x\u00a0:= x.parent    end while    return xend functionZusammenf\u00fchren von zwei S\u00e4tzen[edit]Die Operation Union(x, y) ersetzt das Set mit x und das Set enth\u00e4lt ja mit ihrer Vereinigung.  Union erste Verwendungen Find um die Wurzeln der B\u00e4ume zu bestimmen, die enthalten x und ja.  Wenn die Wurzeln gleich sind, gibt es nichts mehr zu tun.  Andernfalls m\u00fcssen die beiden B\u00e4ume zusammengef\u00fchrt werden.  Dies geschieht durch Setzen des Elternzeigers von x&#8216;s Wurzel zu ja&#8216;s oder das Setzen des Elternzeigers von ja&#8216;s Wurzel zu x&#8216;S.Die Wahl, welcher Knoten zum Elternknoten wird, hat Konsequenzen f\u00fcr die Komplexit\u00e4t zuk\u00fcnftiger Operationen auf dem Baum.  Wenn es unvorsichtig gemacht wird, k\u00f6nnen B\u00e4ume \u00fcberm\u00e4\u00dfig hoch werden.  Nehmen wir zum Beispiel an, dass Union habe immer den Baum gemacht, der enth\u00e4lt x ein Unterbaum des Baums, der . enth\u00e4lt ja.  Beginnen Sie mit einem Wald, der gerade mit Elementen initialisiert wurde 1,2,3,\u2026,n,{displaystyle 1,2,3,ldots,n,}  und ausf\u00fchren Union(1, 2), Union(2, 3), &#8230;, Union(n - 1, n).  Der resultierende Wald enth\u00e4lt einen einzelnen Baum, dessen Wurzel ist n, und der Pfad von 1 nach n geht durch jeden Knoten im Baum.  F\u00fcr diesen Wald ist die Zeit zu laufen Find(1) ist \u00d6(n).In einer effizienten Implementierung wird die Baumh\u00f6he mit Vereinigung nach Gr\u00f6\u00dfe oder Vereinigung nach Rang.  Beide erfordern, dass ein Knoten neben seinem Elternzeiger auch Informationen speichert.  Diese Informationen werden verwendet, um zu entscheiden, welcher Stamm der neue Elternteil wird.  Beide Strategien sorgen daf\u00fcr, dass B\u00e4ume nicht zu tief werden.Bei der Vereinigung nach Gr\u00f6\u00dfe speichert ein Knoten seine Gr\u00f6\u00dfe, die einfach die Anzahl der Nachkommen ist (einschlie\u00dflich des Knotens selbst).  Wenn die B\u00e4ume mit Wurzeln x und ja zusammengef\u00fchrt werden, wird der Knoten mit mehr Nachkommen zum \u00fcbergeordneten Knoten.  Wenn die beiden Knoten die gleiche Anzahl von Nachkommen haben, kann jeder zum Elternteil werden.  In beiden F\u00e4llen wird die Gr\u00f6\u00dfe des neuen Elternknotens auf seine neue Gesamtzahl der Nachkommen eingestellt.function Union(x, y) is    \/\/ Replace nodes by roots    x\u00a0:= Find(x)    y\u00a0:= Find(y)    if x = y then        return  \/\/ x and y are already in the same set    end if    \/\/ If necessary, rename variables to ensure that    \/\/ x has at least as many descendants as y    if x.size < y.size then        (x, y)\u00a0:= (y, x)    end if    \/\/ Make x the new root    y.parent\u00a0:= x    \/\/ Update the size of x    x.size\u00a0:= x.size + y.sizeend functionDie Anzahl der Bits, die zum Speichern der Gr\u00f6\u00dfe erforderlich sind, ist eindeutig die Anzahl der Bits, die zum Speichern erforderlich sind n.  Dies erh\u00f6ht den Speicherbedarf des Waldes um einen konstanten Faktor.F\u00fcr die Vereinigung nach Rang speichert ein Knoten seine Rang, was eine obere Schranke f\u00fcr seine H\u00f6he ist.  Wenn ein Knoten initialisiert wird, wird sein Rang auf Null gesetzt.  B\u00e4ume mit Wurzeln verschmelzen x und ja, vergleichen Sie zuerst ihre Reihen.  Wenn die R\u00e4nge unterschiedlich sind, wird der gr\u00f6\u00dfere Rangbaum zum \u00fcbergeordneten Element, und die R\u00e4nge von x und ja \u00c4ndere dich nicht.  Wenn die R\u00e4nge gleich sind, kann jeder zum Elternteil werden, aber der Rang des neuen Elternteils wird um eins erh\u00f6ht.  W\u00e4hrend der Rang eines Knotens eindeutig mit seiner H\u00f6he zusammenh\u00e4ngt, ist das Speichern von R\u00e4ngen effizienter als das Speichern von H\u00f6hen.  Die H\u00f6he eines Knotens kann sich w\u00e4hrend a . \u00e4ndern Find Das Speichern von Reihen vermeidet den zus\u00e4tzlichen Aufwand, die H\u00f6he korrekt zu halten.  Im Pseudocode ist Vereinigung nach Rang:function Union(x, y) is    \/\/ Replace nodes by roots    x\u00a0:= Find(x)    y\u00a0:= Find(y)    if x = y then        return  \/\/ x and y are already in the same set    end if    \/\/ If necessary, rename variables to ensure that    \/\/ x has rank at least as large as that of y    if x.rank < y.rank then        (x, y)\u00a0:= (y, x)    end if    \/\/ Make x the new root    y.parent\u00a0:= x    \/\/ If necessary, increment the rank of x    if x.rank = y.rank then        x.rank\u00a0:= x.rank + 1    end ifend functionEs kann gezeigt werden, dass jeder Knoten einen Rang . hat IchProtokoll\u2061nIch{displaystyle lfloor log nrfloor }  oder weniger.[10]    Folglich kann der Rang gespeichert werden in \u00d6(Log-Log n) Bits, was ihn zu einem asymptotisch vernachl\u00e4ssigbaren Teil der Waldgr\u00f6\u00dfe macht.Aus den obigen Implementierungen ist klar, dass die Gr\u00f6\u00dfe und der Rang eines Knotens keine Rolle spielen, es sei denn, ein Knoten ist die Wurzel eines Baums.  Sobald ein Knoten ein Kind wird, wird nie wieder auf seine Gr\u00f6\u00dfe und seinen Rang zugegriffen.Zeitkomplexit\u00e4t[edit]Eine disjunkte Waldimplementierung, in der Find Elternzeiger nicht aktualisiert und in denen Union versucht nicht, Baumh\u00f6hen zu kontrollieren, kann B\u00e4ume mit H\u00f6he haben \u00d6(n).  In einer solchen Situation ist die Find und Union Operationen erfordern \u00d6(n) Zeit.Wenn eine Implementierung nur die Pfadkomprimierung verwendet, wird eine Sequenz von n MakeSet  Operationen, gefolgt von bis zu n &#8211; 1 Union  Betrieb und F Find  Betrieb, hat eine Worst-Case-Laufzeit von \u0398(n+F\u22c5(1+Protokoll2+F\/n\u2061n)){displaystyle Theta (n+fcdotleft(1+log_{2+f\/n}nright))}.[10]Union nach Rang verwenden, aber ohne Elternzeiger w\u00e4hrend zu aktualisieren Find, ergibt eine Laufzeit von \u0398(mProtokoll\u2061n){displaystyle Theta (mlog n)}  zum m Operationen jeglicher Art, bis zu n davon sind MakeSet Operationen.[10]Die Kombination von Pfadkomprimierung, Teilung oder Halbierung mit Vereinigung nach Gr\u00f6\u00dfe oder Rang reduziert die Laufzeit f\u00fcr m Operationen jeglicher Art, bis zu n davon sind MakeSet Operationen, zu \u0398(m\u03b1(n)){displaystyle Theta (malpha (n))}.[4][5]    Dadurch wird die amortisierte Laufzeit jedes Vorgangs \u0398(\u03b1(n)){displaystyle Theta (alpha (n))}.  Dies ist asymptotisch optimal, was bedeutet, dass jede disjunkte Mengendatenstruktur verwenden muss \u03a9(\u03b1(n)){displaystyle Omega (alpha (n))}  amortisierte Zeit pro Vorgang.[6]    Hier ist die Funktion \u03b1(n){displaystylealpha(n)}  ist die inverse Ackermann-Funktion.  Die inverse Ackermann-Funktion w\u00e4chst au\u00dferordentlich langsam, daher ist dieser Faktor 4 oder weniger f\u00fcr jeden n das kann tats\u00e4chlich im physikalischen Universum geschrieben werden.  Dies macht disjunkte Mengenoperationen praktisch amortisiert konstante Zeit.Beweis der O(log*(n)) Zeitkomplexit\u00e4t von Union-Find[edit]Die genaue Analyse der Leistung eines disjunkten Waldes ist etwas kompliziert.  Es gibt jedoch eine viel einfachere Analyse, die beweist, dass die amortisierte Zeit f\u00fcr alle m Find  oder Union Operationen auf einem disjunkten Wald mit n Objekte ist \u00d6(mlog*n), wo Protokoll*  bezeichnet den iterierten Logarithmus.[11][12][13][14]Lemma 1: Wenn die find-Funktion dem Pfad zur Wurzel folgt, steigt der Rang des Knotens, auf den sie trifft.Beweis: Behaupten Sie, dass diese Tatsache auch im Laufe der Zeit wahr bleibt, wenn die Operationen Find und Union auf den Datensatz angewendet werden.  Wenn jeder Knoten zun\u00e4chst die Wurzel seines eigenen Baums ist, ist dies trivialerweise wahr.  Der einzige Fall, in dem der Rang eines Knotens ge\u00e4ndert werden kann, ist, wenn die Operation Union by Rank angewendet wird.  In diesem Fall wird ein Baum mit einem kleineren Rang an einen Baum mit einem h\u00f6heren Rang angeh\u00e4ngt und nicht umgekehrt.  Und w\u00e4hrend der Find-Operation werden alle Knoten, die entlang des Pfads besucht werden, an die Wurzel angeh\u00e4ngt, die einen h\u00f6heren Rang als ihre Kinder hat, sodass auch diese Operation nichts an dieser Tatsache \u00e4ndert.Lemma 2: Ein Knoten du das ist die Wurzel eines Teilbaums mit Rang R hat mindestens 2R{displaystyle 2^{r}}  Knoten.Beweis: Wenn zun\u00e4chst jeder Knoten die Wurzel seines eigenen Baums ist, ist dies trivialerweise wahr.  Angenommen, ein Knoten du mit Rang R hat mindestens 2R  Knoten.  Dann, wenn zwei B\u00e4ume mit Rang R werden mit der Operation Union by Rank zusammengef\u00fchrt, einem Baum mit Rang R + 1 Ergebnisse, deren Wurzel mindestens 2R+2R=2R+1{displaystyle 2^{r}+2^{r}=2^{r+1}}  Knoten.Lemma 3: Die maximale Anzahl von Knoten des Rangs R ist h\u00f6chstens n2R.{displaystyle {frac {n}{2^{r}}}.}Beweis: Aus Lemma 2 wissen wir, dass ein Knoten du das ist die Wurzel eines Teilbaums mit Rang R hat mindestens 2R{displaystyle 2^{r}}  Knoten.  Wir erhalten die maximale Anzahl von Knoten des Rangs R wenn jeder Knoten mit Rang R ist die Wurzel eines Baumes, der genau . hat 2R{displaystyle 2^{r}}  Knoten.  In diesem Fall ist die Anzahl der Knoten vom Rang R ist n2R.{displaystyle {frac {n}{2^{r}}}.}Der Einfachheit halber definieren wir hier &#8220;Bucket&#8221;: Ein Bucket ist eine Menge, die Scheitelpunkte mit bestimmten R\u00e4ngen enth\u00e4lt.Wir erstellen einige Buckets und legen induktiv Vertices entsprechend ihrer R\u00e4nge in die Buckets.  Das hei\u00dft, Knoten mit Rang 0 gehen in den nullten Bucket, Knoten mit Rang 1 gehen in den ersten Bucket, Knoten mit Rang 2 und 3 gehen in den zweiten Bucket.  Wenn die BNS Bucket enth\u00e4lt Knoten mit R\u00e4ngen aus dem Intervall [r,2r\u22121]=[r,R\u22121]{displaystyle left[r,2^{r}-1right]=[r,R-1]}  dann enth\u00e4lt der (B+1)-te Bucket Knoten mit R\u00e4ngen aus dem Intervall [R,2R\u22121].{displaystyle left[R,2^{R}-1right].}  Beweis f\u00fcr \u00d6(Protokoll*\u2061n){displaystyle O(log^{*}n)}  Union findenWir k\u00f6nnen zwei Beobachtungen \u00fcber die Eimer machen.Die Gesamtzahl der Eimer ist h\u00f6chstens Protokoll*nBeweis: Wenn wir von einem Eimer zum n\u00e4chsten gehen, addieren wir noch zwei zur Potenz, d. h. den n\u00e4chsten Eimer zu [B,2B\u22121]{displaystyle left[B,2^{B}-1right]}  wird sein [2B,22B\u22121]{displaystyle left[2^{B},2^{2^{B}}-1right]}Die maximale Anzahl von Elementen im Bucket [B,2B\u22121]{displaystyle left[B,2^{B}-1right]}  ist h\u00f6chstens 2n2B{displaystyle {frac {2n}{2^{B}}}}Beweis: Die maximale Anzahl von Elementen im Eimer [B,2B\u22121]{displaystyle left[B,2^{B}-1right]}  ist h\u00f6chstens n2B+n2B+1+n2B+2+\u22ef+n22B\u22121\u22642n2B.{displaystyle {frac {n}{2^{B}}}+{frac {n}{2^{B+1}}}+{frac {n}{2^{B+2}} }+cdots +{frac {n}{2^{2^{B}-1}}}leq {frac {2n}{2^{B}}}.}Lassen F stellen die Liste der durchgef\u00fchrten &#8220;Suchen&#8221;-Operationen dar, und lassen SieT1=\u03a3F(Link zur Wurzel){displaystyle T_{1}=sum _{F}{text{(Link zur Wurzel)}}}T2=\u03a3F(Anzahl der \u00fcberquerten Glieder, bei denen die Eimer unterschiedlich sind){displaystyle T_{2}=sum _{F}{text{(Anzahl der durchlaufenen Links bei unterschiedlichen Buckets)}}}T3=\u03a3F(Anzahl der \u00fcberquerten Glieder, bei denen die Eimer gleich sind).{displaystyle T_{3}=sum _{F}{text{(Anzahl der durchquerten Links, bei denen die Buckets gleich sind).}}}Dann sind die Gesamtkosten von m findet ist T=T1+T2+T3.{displaystyle T=T_{1}+T_{2}+T_{3}.}Da jede Find-Operation genau eine Traversierung durchf\u00fchrt, die zu einer Wurzel f\u00fchrt, gilt T1 = \u00d6(m).Auch aus der oben angef\u00fchrten Anzahl der Eimer haben wir T2 = \u00d6(mProtokoll*n).Zum T3, nehmen wir an, wir durchlaufen eine Kante von du zu v, wo du und v haben Rang im Eimer [B, 2B \u2212 1]  und v ist nicht die Wurzel (zum Zeitpunkt dieser Durchquerung, sonst w\u00fcrde die Durchquerung ber\u00fccksichtigt werden) T1).  Fix du und betrachte die Folge v1,v2,\u2026,vk{displaystyle v_{1},v_{2},ldots,v_{k}}  die die Rolle \u00fcbernehmen v in verschiedenen Suchoperationen.  Wegen der Pfadkompression und der Nichtber\u00fccksichtigung der Kante zu einer Wurzel enth\u00e4lt diese Folge nur verschiedene Knoten und wegen Lemma 1 wissen wir, dass die R\u00e4nge der Knoten in dieser Folge streng ansteigen.  Da sich beide Knoten im Eimer befinden, k\u00f6nnen wir schlie\u00dfen, dass die L\u00e4nge k der Sequenz (die Anzahl der Male, die node du an eine andere Wurzel im selben Bucket angeh\u00e4ngt ist) ist h\u00f6chstens die Anzahl der R\u00e4nge in den Buckets B, das hei\u00dft h\u00f6chstens 2B\u22121\u2212B[B,2B\u22121]\u03a3du2B.{displaystyle T_{3}leq sum _{[B,2^{B}-1]}sum _{u}2^{B}.}Aus den Beobachtungen 1 und 2 k\u00f6nnen wir schlie\u00dfen, dass T3\u2264\u03a3B2B2n2B\u22642nProtokoll*\u2061n.{displaystyle T_{3}leq sum_{B}2^{B}{frac {2n}{2^{B}}}leq 2nlog^{*}n.}Deswegen, T=T1+T2+T3=\u00d6(mProtokoll*\u2061n).{displaystyle T=T_{1}+T_{2}+T_{3}=O(mlog^{*}n).}Anwendungen[edit]  Eine Demo f\u00fcr Union-Find, wenn der Algorithmus von Kruskal verwendet wird, um den minimalen Spannbaum zu finden.Datenstrukturen mit disjunkten Mengen modellieren die Partitionierung einer Menge, um beispielsweise die zusammenh\u00e4ngenden Komponenten eines ungerichteten Graphen zu verfolgen.  Dieses Modell kann dann verwendet werden, um zu bestimmen, ob zwei Scheitelpunkte zu derselben Komponente geh\u00f6ren oder ob das Hinzuf\u00fcgen einer Kante zwischen ihnen zu einem Zyklus f\u00fchren w\u00fcrde.  Der Union-Find-Algorithmus wird in Hochleistungsimplementierungen der Vereinheitlichung verwendet.[15]Diese Datenstruktur wird von der Boost Graph Library verwendet, um ihre Inkrementell verbundene Komponenten Funktionalit\u00e4t.  Es ist auch eine Schl\u00fcsselkomponente bei der Implementierung des Kruskal-Algorithmus, um den minimalen Spannbaum eines Graphen zu finden.Beachten Sie, dass die Implementierung als W\u00e4lder mit disjunkter Menge das L\u00f6schen von Kanten nicht zul\u00e4sst, auch nicht ohne Pfadkomprimierung oder Rangheuristik.Sharir und Agarwal berichten \u00fcber Zusammenh\u00e4nge zwischen dem Worst-Case-Verhalten disjunkter Mengen und der L\u00e4nge von Davenport-Schinzel-Sequenzen, einer kombinatorischen Struktur aus der Computergeometrie.[16]Siehe auch[edit]Verweise[edit]^ ein B C D e F Tarjan, Robert Endre (1975).  \u201eEffizienz eines guten, aber nicht linearen Set Union Algorithmus\u201c. Zeitschrift der ACM. 22 (2): 215\u2013225.  mach:10.1145\/321879.321884.  hdl:1813\/5942.  S2CID 11105749.^ Galler, Bernard A.;  Fischer, Michael J. (Mai 1964).  \u201eEin verbesserter \u00c4quivalenzalgorithmus\u201c. Mitteilungen des ACM. 7 (5): 301\u2013303.  mach:10.1145\/364099.364331.  S2CID 9034016..  Das Papier stammt aus disjunkten W\u00e4ldern.^ Hopcroft, JE;  Ullmann, JD (1973).  &#8220;Zusammenf\u00fchrungsalgorithmen einstellen&#8221;. SIAM Journal on Computing. 2 (4): 294\u2013303.  mach:10.1137\/0202024.^ ein B C Tarjan, Robert E.;  van Leeuwen, Jan (1984).  \u201eWorst-Case-Analyse von Set Union Algorithmen\u201c. Zeitschrift der ACM. 31 (2): 245\u2013281.  mach:10.1145\/62.2160.  S2CID 5363073.^ ein B Tarjan, Robert Endre (1979). &#8220;Eine Klasse von Algorithmen, die nichtlineare Zeit ben\u00f6tigen, um disjunkte Mengen aufrechtzuerhalten&#8221;. Zeitschrift f\u00fcr Informatik und Systemwissenschaften. 18 (2): 110\u2013127.  mach:10.1016\/0022-0000(79)90042-4.^ ein B Fredman, M.;  Saks, M. (Mai 1989).  \u201eDie Zellsondierungskomplexit\u00e4t dynamischer Datenstrukturen\u201c. Tagungsband des einundzwanzigsten j\u00e4hrlichen ACM Symposiums f\u00fcr Theory of Computing: 345\u2013354.  mach:10.1145\/73007.73040.  ISBN 0897913078.  S2CID 13470414. Satz 5: Beliebige CPROBE(log n) Die Implementierung des Mengenvereinigungsproblems erfordert \u03a9(m \u03b1(m, n)) Zeit zum Ausf\u00fchren m Find&#8217;s und n\u22121 Unions, beginnend mit n Singleton-Sets.^ Galil, Z.;  Italiano, G. (1991).  \u201eDatenstrukturen und Algorithmen f\u00fcr disjunkte Satzvereinigungsprobleme\u201c. ACM-Computing-Umfragen. 23 (3): 319\u2013344.  mach:10.1145\/116873.116878.  S2CID 207160759.^ Anderson, Richard J.;  Woll, Heather (1994). Wartefreie parallele Algorithmen f\u00fcr das Union-Find-Problem.  23. ACM-Symposium zur Computertheorie.  S. 370\u2013380.^ Conchon, Sylvain;  Filli\u00e2tre, Jean-Christophe (Oktober 2007).  \u201eEine persistente Union-Find-Datenstruktur\u201c. ACM SIGPLAN Workshop zu ML.  Freiburg, Deutschland.^ ein B C Cormen, Thomas H.;  Leiserson, Charles E.;  Rivest, Ronald L.;  Stein, Clifford (2009).  \u201eKapitel 21: Datenstrukturen f\u00fcr disjunkte Mengen\u201c. Einf\u00fchrung in Algorithmen (Dritte Aufl.).  MIT-Presse.  S. 571\u2013572.  ISBN 978-0-262-03384-8.^ Raimund Seidel, Micha Sharir.  &#8220;Top-down-Analyse der Pfadkompression&#8221;, SIAM J. Comput.  34(3):515\u2013525, 2005^ Tarjan, Robert Endre (1975). &#8220;Effizienz eines guten, aber nicht linearen Set-Union-Algorithmus&#8221;. Zeitschrift der ACM. 22 (2): 215\u2013225.  mach:10.1145\/321879.321884.  hdl:1813\/5942.  S2CID 11105749.^ Hopcroft, JE;  Ullmann, JD (1973).  &#8220;Zusammenf\u00fchrungsalgorithmen einstellen&#8221;. SIAM Journal on Computing. 2 (4): 294\u2013303.  mach:10.1137\/0202024.^ Robert E. Tarjan und Jan van Leeuwen.  Worst-Case-Analyse von Set-Union-Algorithmen.  Zeitschrift der ACM, 31(2):245\u2013281, 1984.^ Ritter, Kevin (1989). &#8220;Vereinigung: Eine multidisziplin\u00e4re Umfrage&#8221; (PDF). ACM-Computing-Umfragen. 21: 93\u2013124.  mach:10.1145\/62029.62030.  S2CID 14619034.^ Sharir, M.;  Agarwal, P. (1995). Davenport-Schinzel-Sequenzen und ihre geometrischen Anwendungen.  Cambridge University Press.Externe Links[edit]     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki25\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki25\/2021\/11\/30\/disjunkte-datenstruktur-wikipedia\/#breadcrumbitem","name":"Disjunkte Datenstruktur \u2013 Wikipedia"}}]}]