Spreizbaum

A Spreizbaum ist ein Binärer Suchbaum Mit der zusätzlichen Eigenschaft, auf die kürzlich auf Elemente zugegriffen werden, können Sie schnell wieder zugreifen. Wie selbstausgleichende binäre Suchbäume, ein Spreizbaum führt grundlegende Operationen wie Insertion, Suche und Entfernung durch. O(Protokoll n) amortisiert Zeit. Für Zufallszugriffsmuster aus einer ungleichmäßigen Zufallsverteilung kann ihre amortisierte Zeit schneller sein als logarithmisch, proportional zur Entropie des Zugangsmusters. Für viele Muster von nicht randomischen Operationen können Spreizbäume auch besser als logarithmische Zeit dauern, ohne dass das Muster vorangebracht wird. Gemäß der unbewiesenen dynamischen Optimalitäts Vermutung liegt ihre Leistung auf allen Zugriffsmustern innerhalb eines konstanten Faktors der bestmöglichen Leistung, die durch jeden anderen selbstanpassenden binären Suchbaum erreicht werden könnte, selbst eines, das für das Muster anpasst. Der Spreizbaum wurde von erfunden von Daniel Sleator und Robert Tarjan 1985.^[1]

Alle normalen Operationen an einem binären Suchbaum werden mit einer grundlegenden Operation kombiniert, die genannt wird Spreiz. Das Spreizen des Baumes für ein bestimmtes Element ordnet den Baum um, so dass das Element an der Wurzel des Baumes platziert ist. Eine Möglichkeit, dies mit der grundlegenden Suchoperation zu tun Baumrotationen in einer bestimmten Weise, um das Element an die Spitze zu bringen. Alternativ kann ein Top-Down-Algorithmus die Suche und die Baumreorganisation in eine einzelne Phase kombinieren.

Vorteile

Eine gute Leistung für einen Spreizbaum hängt von der Tatsache ab, dass er selbstoptimiert ist, da sich häufig zugängliche Knoten näher an die Wurzel bewegt, wo sie schneller zugreifen können. Die schlimmste Höhe-obwohl unwahrscheinlich-ist o (n), wobei der Durchschnitt O (log n). Die häufig verwendeten Knoten in der Nähe der Wurzel sind für viele praktische Anwendungen von Vorteil (auch siehe Referenzort) und ist besonders nützlich für die Implementierung Caches und Müllsammlung Algorithmen.

Zu den Vorteilen gehören:

• Vergleichbare Leistung: Die Durchschnittsfallleistung ist genauso effizient wie andere Bäume.^[3]
• Kleiner Speicherausdruck: Spreizbäume müssen keine Buchhaltungsdaten speichern.

Nachteile

Der bedeutendste Nachteil von Spreizbäumen ist, dass die Höhe eines Spreizbaums linear sein kann.^{[2]: 1} Dies ist beispielsweise nach dem Zugriff auf alle der Fall der Fall n Elemente in nicht abnehmender Reihenfolge. Da die Höhe eines Baumes der Worst-Case-Zugangszeit entspricht, bedeutet dies, dass die tatsächlichen Kosten eines einzelnen Betriebs hoch sein können. Jedoch das amortisiert Die Zugriffskosten dieses schlimmsten Falls sind logarithmisch, o (Protokoll n). Außerdem können die erwarteten Zugangskosten auf O reduziert werden (Protokoll n) Mit einer randomisierten Variante.^[4]

Die Darstellung von Spreizbäumen kann sich ändern, auch wenn sie auf "schreibgeschützte" Weise zugegriffen werden (d. H. Von finden Operationen). Dies erschwert die Verwendung solcher Spreizbäume in einer Umgebung mit mehreren Threaden. Insbesondere ist eine zusätzliche Verwaltung erforderlich, wenn mehrere Threads durchführen dürfen finden Operationen gleichzeitig. Dies macht sie auch für den allgemeinen Gebrauch in rein funktioneller Programmierung ungeeignet, obwohl sie auch dort in begrenzten Arten verwendet werden können, um vorrangige Warteschlangen zu implementieren.

Schließlich beim Zugriffsmuster ist Zufälligerweise fügt der zusätzliche Spreizaufwand im Vergleich zu weniger dynamischen Alternativen einen signifikanten konstanten Faktor hinzu.

Operationen

Spreiz

Wenn ein Knoten x Es wird zugegriffen, ein Spreizvorgang wird durchgeführt x um es zur Wurzel zu bewegen. Um einen Spreizvorgang durchzuführen, führen wir eine Sequenz von durch Spreizstufen, jeder von denen bewegt sich x näher an der Wurzel. Durch die Durchführung eines Spreizvorgangs auf dem Knoten von Interesse nach jedem Zugang werden die kürzlich zugänglichen Knoten in der Nähe der Wurzel gehalten und der Baum bleibt grob ausgewogen, so dass wir die gewünschten amortisierten Zeitgrenzen erreichen.

Jeder bestimmte Schritt hängt von drei Faktoren ab:

• Ob x ist das linke oder rechte Kind seines übergeordneten Knotens, p,
• ob p ist die Wurzel oder nicht, und wenn nicht
• ob p ist das linke oder rechte Kind von es ist Elternteil, g (das Großelternteil von x).

Es ist wichtig, sich daran zu erinnern, sich zu setzen gg (das Urgroßeltern von x) nach einer Spreizoperation jetzt auf x zu zeigen. Wenn gg ist null, dann ist x offensichtlich die Wurzel und muss als solches aktualisiert werden.

Es gibt drei Arten von Spreizschritten, von denen jede zwei symmetrische Varianten hat: links und rechtshändig. Aus Gründen der Kürze wird nur einer dieser beiden für jeden Typ gezeigt. (In den folgenden Diagrammen zeigen Kreise Knoten von Interesse an und Dreiecke zeigen Unterbäume der willkürlichen Größe an.) Die drei Arten von Spreizschritten sind:

Zick Schritt: Dieser Schritt erfolgt, wenn p ist die Wurzel. Der Baum wird an der Kante zwischen gedreht x und p. Es gibt Zig -Schritte, die mit dem Problem der Parität behandelt werden, und werden nur als letzter Schritt in einem Spreizvorgang durchgeführt, und nur wann x hat zu Beginn der Operation eine seltsame Tiefe.

Zick-Zig-Schritt: Dieser Schritt erfolgt, wenn p ist nicht die Wurzel und x und p sind entweder beide rechte Kinder oder beide links Kinder. Das Bild unten zeigt den Fall, wo x und p sind beide gelassene Kinder. Der Baum wird an der Kanteverbindung gedreht p mit es ist Elternteil gund dann am Randverbindung gedreht x mit p. Beachten Sie, dass Zick-Zig-Schritte das einzige sind, das Spreizbäume von der unterscheidet zur Wurzel drehen Methode von Allen und Munro eingeführt^[5] Vor der Einführung von Spreizbäumen.

Zick-Zack-Schritt: Dieser Schritt erfolgt, wenn p ist nicht die Wurzel und x ist ein richtiges Kind und p ist ein linkes Kind oder umgekehrt (umgekehrt (x ist übrig, p ist richtig). Der Baum wird an der Kante zwischen gedreht p und xund dann an der resultierenden Kante zwischen gedreht x und g.

Verbinden

Bei zwei Bäumen s und t so, dass alle Elemente von S kleiner sind als die Elemente von T, können die folgenden Schritte verwendet werden, um sie mit einem einzelnen Baum zu verbinden:

• Spreizen Sie den größten Artikel in S. Jetzt befindet sich dieses Element in der Wurzel von S und hat ein null rechtes Kind.
• Stellen Sie das richtige Kind der neuen Wurzel auf T.

Teilt

Einen Baum und ein Element gegeben x, geben Sie zwei neue Bäume zurück: eine, die alle Elemente weniger als oder gleich enthält x und die anderen, die alle Elemente enthalten, die größer als x. Dies kann auf folgende Weise erfolgen:

• Spreizen x. Jetzt ist es in der Wurzel, so dass der Baum links alle Elemente enthält, die kleiner als x und der Baum rechts enthält alle Elemente größer als x.
• Teilen Sie den rechten Unterbaum vom Rest des Baumes auf.

Einfügen

Einen Wert einfügen x in einen Spreizbaum:

• Einfügung x Wie bei einem Normalen Binärer Suchbaum.
• Wenn ein Gegenstand eingefügt wird, wird eine Spreize durchgeführt.
• Infolgedessen der neu eingefügte Knoten x wird die Wurzel des Baumes.

Alternative:

• Verwenden Sie die Split -Operation, um den Baum zum Wert von zu teilen x zu zwei Unterbäumen: S und T.
• Erstellen Sie einen neuen Baum, in dem x ist die Wurzel, S ist sein linker Unterbaum und t sein rechter Unterbaum.

Streichung

Zum Löschen eines Knotens xVerwenden Sie dieselbe Methode wie bei einem binären Suchbaum:

• Wenn x hat zwei Kinder:
  • Tauschen Sie seinen Wert mit dem entweder dem rechts den linken Unterbaum (seinem Vorgänger in Ordnung) oder dem linken Knoten des rechten Teilbaums (sein in Ordnung).
  • Entfernen Sie stattdessen diesen Knoten.

Auf diese Weise wird die Löschung auf das Problem reduziert, einen Knoten mit 0 oder 1 Kindern zu entfernen. Im Gegensatz zu einem binären Suchbaum in einem Spreizbaum nach dem Löschen spreizen wir den Elternteil des entfernten Knotens auf die Oberseite des Baumes.

Alternative:

• Der zu gelöschte Knoten wird zuerst gespreizt, d. H. An die Wurzel des Baumes gebracht und dann gelöscht. hinterlässt den Baum mit zwei Unterbäumen.
• Die beiden Unterbäume werden dann mit einer "Join" -Operation verbunden.

Implementierung und Varianten

Wie oben erwähnt, wird während eines zweiten Bottom-up-Durchgangs über den Zugangspfad eines Knotens durchgeführt. Es ist möglich, den Zugriffspfad während des ersten Durchgangs für die Verwendung während des zweiten Zeits aufzuzeichnen. Dies erfordert jedoch zusätzlichen Platz während des Zugangsvorgangs. Eine andere Alternative besteht darin, einen übergeordneten Zeiger in jedem Knoten zu halten, was den Bedarf an zusätzlichen Platz während des Zugangsvorgängen vermeidet, aber aufgrund der Notwendigkeit, diese Zeiger zu aktualisieren^[1]

Eine andere Methode, die verwendet werden kann, basiert auf dem Argument, dass wir den Baum auf dem Weg den Zugangspfad hinunter umstrukturieren können, anstatt einen zweiten Pass zu erstellen. Diese Top-Down-Spreizroutine verwendet drei Sätze von Knoten-linker Baum, rechter Baum und mittlerer Baum. Die ersten beiden enthalten alle Elemente des Originalbaums, von denen bekannt ist, dass sie weniger oder größer als aktuelles Element sind. Der mittlere Baum besteht aus dem am aktuellen Knoten verwurzelten Unterbaum. Diese drei Sätze werden den Zugriffspfad auf dem Laufenden, während die Spreizvorgänge in Schach gehalten werden. Eine andere Methode, Halbspiele, ändert den Zick-Zig-Fall, um die Umstrukturierung in allen Operationen zu verringern.^[1][6]

Unten befindet sich eine Implementierung von Spreizbäumen in C ++, die Zeiger verwendet, um jeden Knoten auf dem Baum darzustellen. Diese Implementierung basiert auf der Bottom-up-Spreizversion und verwendet die zweite Löschmethode auf einem Spreizbaum. Im Gegensatz zur obigen Definition tut diese C ++ - Version auch nicht Spalten Sie den Baum auf Finds - er spreizt nur Einfügungen und Löschungen auf, und der Findoperation hat daher eine lineare Zeitkomplexität.

#enthalten  #ifndef splay_tree #define splay_tree Schablone<Modellname T, Modellname Comp = std::weniger<T>> Klasse splay_tree { Privatgelände:   Comp Comp;   ohne Vorzeichen lang P_SIZE;      Struktur Knoten {   Knoten *links, *Rechts;   Knoten *Elternteil;   T Schlüssel;   Knoten(Const T& drin = T()) : links(nullptr), Rechts(nullptr), Elternteil(nullptr), Schlüssel(drin) { }   ~Knoten() {   }   } *Wurzel;      Leere links_rotate(Knoten *x) {   Knoten *y = x->Rechts;   wenn (y) {   x->Rechts = y->links;   wenn (y->links) y->links->Elternteil = x;   y->Elternteil = x->Elternteil;   }      wenn (!x->Elternteil) Wurzel = y;   anders wenn (x == x->Elternteil->links) x->Elternteil->links = y;   anders x->Elternteil->Rechts = y;   wenn (y) y->links = x;   x->Elternteil = y;   }      Leere Right_rotate(Knoten *x) {   Knoten *y = x->links;   wenn (y) {   x->links = y->Rechts;   wenn (y->Rechts) y->Rechts->Elternteil = x;   y->Elternteil = x->Elternteil;   }   wenn (!x->Elternteil) Wurzel = y;   anders wenn (x == x->Elternteil->links) x->Elternteil->links = y;   anders x->Elternteil->Rechts = y;   wenn (y) y->Rechts = x;   x->Elternteil = y;   }      Leere spreizen(Knoten *x) {   während (x->Elternteil) {   wenn (!x->Elternteil->Elternteil) {   wenn (x->Elternteil->links == x) Right_rotate(x->Elternteil);   anders links_rotate(x->Elternteil);   } anders wenn (x->Elternteil->links == x && x->Elternteil->Elternteil->links == x->Elternteil) {   Right_rotate(x->Elternteil->Elternteil);   Right_rotate(x->Elternteil);   } anders wenn (x->Elternteil->Rechts == x && x->Elternteil->Elternteil->Rechts == x->Elternteil) {   links_rotate(x->Elternteil->Elternteil);   links_rotate(x->Elternteil);   } anders wenn (x->Elternteil->links == x && x->Elternteil->Elternteil->Rechts == x->Elternteil) {   Right_rotate(x->Elternteil);   links_rotate(x->Elternteil);   } anders {   links_rotate(x->Elternteil);   Right_rotate(x->Elternteil);   }   }   }      Leere ersetzen(Knoten *u, Knoten *v) {   wenn (!u->Elternteil) Wurzel = v;   anders wenn (u == u->Elternteil->links) u->Elternteil->links = v;   anders u->Elternteil->Rechts = v;   wenn (v) v->Elternteil = u->Elternteil;   }      Knoten* SUBTREE_MINIMUM(Knoten *u) {   während (u->links) u = u->links;   Rückkehr u;   }      Knoten* SUBTREE_MAXIMUM(Knoten *u) {   während (u->Rechts) u = u->Rechts;   Rückkehr u;   } Öffentlichkeit:   splay_tree() : Wurzel(nullptr), P_SIZE(0) { }      Leere Einfügung(Const T &Schlüssel) {   Knoten *z = Wurzel;   Knoten *p = nullptr;      während (z) {   p = z;   wenn (Comp(z->Schlüssel, Schlüssel)) z = z->Rechts;   anders z = z->links;   }      z = Neu Knoten(Schlüssel);   z->Elternteil = p;      wenn (!p) Wurzel = z;   anders wenn (Comp(p->Schlüssel, z->Schlüssel)) p->Rechts = z;   anders p->links = z;      spreizen(z);   P_SIZE++;   }      Knoten* finden(Const T &Schlüssel) {   Knoten *z = Wurzel;   während (z) {   wenn (Comp(z->Schlüssel, Schlüssel)) z = z->Rechts;   anders wenn (Comp(Schlüssel, z->Schlüssel)) z = z->links;   anders Rückkehr z;   }   Rückkehr nullptr;   }      Leere löschen(Const T &Schlüssel) {   Knoten *z = finden(Schlüssel);   wenn (!z) Rückkehr;      spreizen(z);      wenn (!z->links) ersetzen(z, z->Rechts);   anders wenn (!z->Rechts) ersetzen(z, z->links);   anders {   Knoten *y = SUBTREE_MINIMUM(z->Rechts);   wenn (y->Elternteil ! = z) {   ersetzen(y, y->Rechts);   y->Rechts = z->Rechts;   y->Rechts->Elternteil = y;   }   ersetzen(z, y);   y->links = z->links;   y->links->Elternteil = y;   }      löschen z;   P_SIZE--;   } /* // die alternative Implementierung     Hohlraumlöre (const t & key) {         Knoten *z = Find (Schlüssel);         if (! z) kehre zurück;            Splay (z);            Knoten *s = z-> links;         Knoten *t = z-> rechts;         z; z;            Knoten *SMAX = NULL;         if (s) {             S-> Eltern = null;             SMAX = SUBREE_MAXIMUM (s);             Splay (Smax);             root = Smax;         }         if (t) {             Wenn (s)                 Smax-> rechts = t;             anders                 root = t;             T-> Eltern = Smax;         }            P_SIZE--;     } */      Const T& Minimum() { Rückkehr SUBTREE_MINIMUM(Wurzel)->Schlüssel; }   Const T& maximal() { Rückkehr SUBTREE_MAXIMUM(Wurzel)->Schlüssel; }      bool leer() Const { Rückkehr Wurzel == nullptr; }   ohne Vorzeichen lang Größe() Const { Rückkehr P_SIZE; } }; #endif // splay_tree 

Analyse

Eine einfache Amortisierte Analyse von statischen Spreizbäumen können mit dem durchgeführt werden Potenzielle Methode. Definieren:

• Größe(r) = die Anzahl der Knoten im unter dem Knoten verwurzelten Unterbaum r (einschließlich r).
• Rang(r) = log₂(Größe(r)).
• Φ = die Summe der Ränge aller Knoten im Baum.

Φ ist tendenziell hoch für schlecht ausgewogene Bäume und niedrig für ausgewogene Bäume.

Um die anzuwenden Potenzielle MethodeWir berechnen zuerst Δφ: die Änderung des durch einen Spreizvorgangs verursachten Potentials. Wir überprüfen jeden Fall getrennt. Bezeichnen Sie durch Rang 'die Rangfunktion nach dem Operation. x, p und g sind die von der Rotationsoperation betroffenen Knoten (siehe Abbildungen oben).

Zickschritt

Δφ	= Rang '(p) - Rang (p) + Rang '(x) - Rang (x))	[Da nur P- und X -Änderung rangiert]
	= Rang '(p) - Rang (x))	[Seit Rang '(x) = Rang (p)]
	≤ Rang '(x) - Rang (x))	[Seit Rang '(p) <Rank '(x)]

Zick-Zig-Schritt

Δφ	= Rang '(g) - Rang (g) + Rang '(p) - Rang (p) + Rang '(x) - Rang (x))
	= Rang '(g) + Rang '(p) - Rang (p) - Rang (x))	[seit Rang '(x) = Rang (g)]]
	≤ Rang '(g) + Rang '(x) - 2 Rang (Rang (x))	[Seit Rang (x) <Rang (Rang (p) und Rang '(x)> Rang '(p)]
	≤ 3 (Rang '(x) −rank (x)) - 2	[Aufgrund der Konkavität der Protokollfunktion]

Zick-Zack-Schritt

Δφ	= Rang '(g) - Rang (g) + Rang '(p) - Rang (p) + Rang '(x) - Rang (x))
	≤ Rang '(g) + Rang '(p) - 2 Rang (Rang (x))	[Seit Rang '(x) = Rang (g) und Rang (x) <Rang (Rang (p)]
	≤ 3 (Rang '(x) −rank (x)) - 2	[Aufgrund der Konkavität der Protokollfunktion]

Die amortisierten Kosten einer Operation beträgt Δφ plus die tatsächlichen Kosten. Die tatsächlichen Kosten eines Zick-Zig- oder Zick-Zack-Betriebs betragen 2, da zwei Rotationen vorgenommen werden müssen. Somit:

amortisiert	= Kosten + Δφ
	≤ 3 (Rang '(x) −rank (x))

Wenn dies über den gesamten Spreizvorgang zusammengefasst ist, ist dies Teleskope bis 3 (Rang (root) –Rank (x)) Was ist o (log n). Der Zig -Betrieb fügt amortisierte Kosten von 1 hinzu, aber es gibt höchstens einen solchen Betrieb.

Jetzt wissen wir also, dass die Gesamtsumme amortisiert Zeit für eine Sequenz von m Operationen ist:

${\ displayStyle t _ {\ mathhrm {amortisiert}} (m) = o (m \ log n)}$

Um von der amortisierten Zeit bis zur tatsächlichen Zeit zu übergehen, müssen wir die Abnahme des Potenzials aus dem Anfangszustand hinzufügen, bevor eine Operation abgeschlossen ist (φ_i) in den endgültigen Zustand nach Abschluss aller Operationen (φ_f).

$oder = O (n \ log n)}$

Wo die letzte Ungleichheit aus der Tatsache kommt, dass für jeden Knoten x, der minimale Rang beträgt 0 und der maximale Rang ist log (log) (n).

Jetzt können wir endlich die tatsächliche Zeit gebunden:

$oder$

Gewichtete Analyse

Die obige Analyse kann auf folgende Weise verallgemeinert werden.

• Jedem Knoten zuweisen r ein Gewicht w(r).
• Größe definieren (r) = die Summe der Gewichte von Knoten im untergeberten Unterbaum r (einschließlich r).
• Rang definieren (r) und φ genau wie oben.

Die gleiche Analyse gilt und die amortisierten Kosten eines Spreizvorgangs sind erneut:

$oder } {w (x)}} \ rechts)}$

wo W ist die Summe aller Gewichte.

Die Abnahme von der Anfangs- zum endgültigen Potential ist begrenzt:

$oder$

Da die maximale Größe eines einzelnen Knotens ist W und das Minimum ist w (x).

Daher wird die tatsächliche Zeit durch:

$oder W} {w (x)}}} \ rechts)}$

Leistungsmenge

Es gibt mehrere Theoreme und Vermutungen in Bezug auf die Worst-Case-Laufzeit für die Durchführung einer Sequenz S von m Zugriff in einem Spreizbaum, der enthält n Elemente.

Dynamische Optimalitäts Vermutung

Zusätzlich zu den nachgewiesenen Leistungsgarantien für Spreizbäume gibt es eine unbewiesene Vermutung von großem Interesse aus dem ursprünglichen Sleator- und Tarjan -Papier. Diese Vermutung ist als die bekannt Dynamische Optimalitäts Vermutung Und es wird im Grunde genommen behauptet, dass Spreizbäume ebenso wie jeder andere binäre Suchbaumalgorithmus bis zu einem konstanten Faktor.

Dynamische Optimalitäts Vermutung:^[1] Lassen ${\ displayStyle a}$ Seien Sie jeder binäre Suchbaumalgorithmus, der auf ein Element zugreift ${\ displayStyle x}$ durch Überqueren des Pfades von der Wurzel nach ${\ displayStyle x}$ zum Preis von ${\ displayStyle d (x) +1}$und das zwischen Zugang kann zu Rotationen im Baum zu einem Preis von 1 pro Rotation führen. Lassen ${\ displayStyle a (s)}}$ die Kosten für sein ${\ displayStyle a}$ Um die Sequenz auszuführen ${\ displayStyle S}$ von Zugang. Dann sind die Kosten für einen Spreizbaum, der den gleichen Zugriff durchführen kann ${\ displayStyle o [n+a (s)]}$.

Es gibt mehrere Folgen der dynamischen Optimalitäts Vermutung, die unbewiesen bleiben:

Durchquerte Vermutung:^[1] Lassen ${\ displayStyle t_ {1}}$ und ${\ displayStyle t_ {2}}$ Seien Sie zwei Spreizbäume mit den gleichen Elementen. Lassen ${\ displayStyle S}$ Seien Sie die Sequenz, die durch Besuch der Elemente in erhalten wird ${\ displayStyle t_ {2}}$ in der Vorbestellung (d. H. Tiefe erste Suchreihenfolge). Die Gesamtkosten für die Ausführung der Sequenz ${\ displayStyle S}$ von Zugangses auf ${\ displayStyle t_ {1}}$ ist ${\ displayStyle o (n)}$.

Deque -Vermutung:^[11][13][14] Lassen ${\ displayStyle S}$ eine Sequenz von sein ${\ displayStyle m}$ Doppelte-Warteschlange Operationen (Push, Pop, Inject, Aus jüngen). Dann die Kosten für die Leistung ${\ displayStyle S}$ auf einem Spreizbaum ist ${\ displayStyle o (m+n)}$.

Split -Vermutung:^[6] Lassen ${\ displayStyle S}$ Seien Sie jede Permutation der Elemente des Spreizbaums. Dann die Kosten für das Löschen der Elemente in der Bestellung ${\ displayStyle S}$ ist ${\ displayStyle o (n)}$.

Varianten

Um die Anzahl der Umstrukturierungsvorgänge zu verringern Halbspiel, in dem ein Element nur zur Hälfte zur Wurzel gespreizt wird.^[1][2]

Eine andere Möglichkeit, die Umstrukturierung zu verringern m Zugriffsvorgänge.^[1]

Siehe auch

• Avl Baum
• B-Baum
• Fingerbaum
• Geometrie binärer Suchbäume
• Iaconos Arbeitssatzstruktur
• Link/Schnittbaum
• Liste der Datenstrukturen
• Sündenbaum
• Splaysort, ein Sortieralgorithmus mit Spreizbäumen
• T-tree
• Treap
• Baumrotation
• Bäume
• Reißverschluss (Datenstruktur)

Anmerkungen

Verweise

• Albers, Susanne; Karpinski, Marek (28. Februar 2002). "Randomisierte Spreizbäume: theoretische und experimentelle Ergebnisse" (PDF). Informationsverarbeitungsbriefe. 81 (4): 213–221. doi:10.1016/s0020-0190 (01) 00230-7.
• Allen, Brian; Munro, Ian (Oktober 1978). "Selbst organisierende binäre Suchbäume". Journal of the ACM. 25 (4): 526–535. doi:10.1145/322092.322094. S2CID 15967344.
• Brinkmann, Gunnar; Degraer, Jan; De loof, Karel (Januar 2009). "Rehabilitation eines ungeliebten Kindes: Halbspiel" (PDF). Software: Übung und Erfahrung. 39 (1): 33–45. Citeseerx 10.1.1.84.790. doi:10.1002/spe.v39: 1. HDL:11382/102133. Die Ergebnisse zeigen, dass das Semi-Spaying, das in derselben Arbeit wie Splaying eingeführt wurde, besser abschneidet als unter fast allen möglichen Bedingungen. Dies macht das Semi-Spiel zu einer guten Alternative für alle Anwendungen, bei denen normalerweise Spreiber angewendet werden würde. Der Grund, warum Splaying so prominent wurde, während das Semi-Spaying relativ unbekannt ist und viel weniger untersucht ist, ist schwer zu verstehen.
• Cole, Richard; Mishra, Knospe; Schmidt, Jeanette; Siegel, Alan (Januar 2000). "Auf der dynamischen Finger-Vermutung für Spreizbäume. Teil I: Spreiz-Sortierprotokoll N-Block-Sequenzen". Siam Journal über Computing. 30 (1): 1–43. Citeseerx 10.1.1.36.4558. doi:10.1137/s0097539797326988.
• Cole, Richard (Januar 2000). "Auf der dynamischen Finger -Vermutung für Spreizbäume. Teil II: Der Beweis". Siam Journal über Computing. 30 (1): 44–85. Citeseerx 10.1.1.36.2713. doi:10.1137/s009753979732699x.
• Elmasry, AMR (April 2004). "Auf dem sequentiellen Zugangstheorem und der Deque -Vermutung für Spreizbäume". Theoretische Informatik. 314 (3): 459–466. doi:10.1016/j.tcs.2004.01.019.
• Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael (2014). Datenstrukturen und Algorithmen in Java (6 ed.). Wiley. p. 506. ISBN 978-1-118-77133-4.
• Grinberg, Dennis; Rajagopalan, Sivaramakrishnan; Venkatesan, Ramarathnam; Wei, Victor K. (1995). "Spreizbäume für die Datenkomprimierung". In Clarkson, Kenneth L. (Hrsg.). Proceedings des sechsten jährlichen ACM-SIAM-Symposiums für diskrete Algorithmen, 22. bis 24. Januar 1995. San Francisco, Kalifornien, USA. ACM/Siam. S. 522–530. Die durchschnittliche Zugangstiefe in einem Spreizbaum ist proportional zur Entropie.
• Knuth, Donald (1997). Die Kunst der Computerprogrammierung. Vol. 3: Sortieren und Suchen (3. Aufl.). Addison-Wesley. p. 478. ISBN 0-201-89685-0. Die Zeit, die für den Zugriff auf Daten in einem Spreizbaum benötigt wird, ist als höchstens ein kleines Vielfalt der Zugriffszeit eines staatlich optimalen Baumes, wenn es über jede Reihe von Operationen abgeschrieben wird.
• Lucas, Joan M. (1991). "Über die Wettbewerbsfähigkeit von Spreizbäumen: Beziehungen zum Union-Find-Problem". Online-Algorithmen: Verfahren eines DIMACS-Workshops, 11. bis 13. Februar 1991. Serie in diskreter Mathematik und theoretischer Informatik. Vol. 7. Zentrum für diskrete Mathematik und theoretische Informatik. S. 95–124. ISBN 0-8218-7111-0.
• Pettie, Seth (2008). Spreizbäume, Davenport-Schinzel-Sequenzen und die Deque-Vermutung (PDF). Proc. 19. ACM-SIAM-Symposium über diskrete Algorithmen. Vol. 0707. S. 1115–1124. Arxiv:0707.2160. Bibcode:2007ArXIV0707.2160p.
• Sleator, Daniel D.; Tarjan, Robert E. (1985). "Selbstanpassende binäre Suchbäume" (PDF). Journal of the ACM. 32 (3): 652–686. doi:10.1145/3828.3835. S2CID 1165848.
• Sundar, Rajamani (1992). "Auf der Deque -Vermutung für den Spreizalgorithmus". Combinatorica. 12 (1): 95–124. doi:10.1007/bf01191208. S2CID 27422556.
• Tarjan, Robert E. (1985). "Sequentieller Zugriff in Spreizbäumen braucht linear". Combinatorica. 5 (4): 367–378. doi:10.1007/bf02579253. S2CID 34757821.

Externe Links

• Nists Wörterbuch über Algorithmen und Datenstrukturen: Spreizbaum
• Implementierungen in C und Java (von Daniel Sleator)
• Zeiger auf Spreizbaumvisualisierungen
• Schnelle und effiziente Implementierung von Spreizbäumen
• Top-Down-Spreizbaum-Java-Implementierung
• Reißverschlussbäume