In der Informatik sind der treap und der randomized binäre Suchbaum zwei nah zusammenhängende Formen von binären Suchbaumdatenstrukturen, die einen dynamischen Satz von bestellten Schlüsseln aufrechterhalten und binäre Suchen unter den Schlüsseln erlauben. Nach jeder Folge von Einfügungen und Auswischen von Schlüsseln ist die Gestalt des Baums eine zufällige Variable mit demselben Wahrscheinlichkeitsvertrieb wie ein zufälliger binärer Baum; insbesondere mit der hohen Wahrscheinlichkeit ist seine Höhe zum Logarithmus der Zahl von Schlüsseln proportional, so dass jede Suche, Einfügung oder Auswischen-Operation Zeit in Anspruch nehmen, um zu leisten.

Treap

Der treap wurde zuerst von Cecilia R. Aragon und Raimund Seidel 1989 beschrieben; sein Name ist ein Handkoffer des Baums und Haufens.

Es ist ein Kartesianischer Baum, in dem jeder Schlüssel (zufällig gewählt) numerischer Vorrang gegeben wird. Als mit jedem binären Suchbaum ist die inorder überquerende Ordnung der Knoten dasselbe als die sortierte Ordnung der Schlüssel. Die Struktur des Baums wird durch die Voraussetzung bestimmt, dass es Haufen-bestellt wird: D. h. die Prioritätsnummer für jeden Nichtblatt-Knoten muss größer oder gleich dem Vorrang seiner Kinder sein. So, als mit Kartesianischen Bäumen mehr allgemein, ist der Wurzelknoten der Knoten des maximalen Vorrangs, und seine linken und richtigen Subbäume werden auf dieselbe Weise von den Subfolgen der sortierten Ordnung nach links und des Rechts auf diesen Knoten gebildet.

Eine gleichwertige Weise, den treap zu beschreiben, besteht darin, dass er durch das Einfügen der Knoten "höchster Vorrang zuerst" in einen binären Suchbaum gebildet werden konnte, ohne jedes Wiederausgleichen zu tun. Deshalb, wenn die Prioritäten unabhängige Zufallszahlen sind (von einem Vertrieb über einen genug großen Raum von möglichen Prioritäten sicherzustellen, dass zwei Knoten kaum denselben Vorrang haben werden) dann, hat die Gestalt eines treap denselben Wahrscheinlichkeitsvertrieb wie die Gestalt eines zufälligen binären Suchbaums, eines gebildeten Suchbaums durch das Einfügen der Knoten, ohne in einer zufällig gewählten Einfügungsordnung wiederzubalancieren. Weil, wie man bekannt, zufällige binäre Suchbäume logarithmische Höhe mit der hohen Wahrscheinlichkeit haben, ist dasselbe für treaps wahr.

Spezifisch unterstützt der treap die folgenden Operationen:

• Um nach einem gegebenen Schlüsselwert zu suchen, wenden Sie einen binären Standardsuchalgorithmus in einem binären Suchbaum an, die Prioritäten ignorierend.
• Um einen neuen Schlüssel x in den treap einzufügen, erzeugen Sie einen zufälligen Vorrang y für x. Binäre Suche x im Baum, und schafft einen neuen Knoten an der Blatt-Position, wo die binäre Suche beschließt, dass ein Knoten für x bestehen sollte. Dann nicht weniger als ist x nicht die Wurzel des Baums und hat eine größere Prioritätsnummer als sein Elternteilz, führen Sie eine Baumfolge durch, die die Elternteilkind-Beziehung zwischen x und z umkehrt.
• Um einen Knoten x vom treap, zu löschen, wenn x ein Blatt des Baums einfach ist, entfernen Sie es. Wenn x ein einzelnes Kind z hat, entfernen Sie x vom Baum und lassen Sie z das Kind des Elternteils von x sein (oder machen Sie z die Wurzel des Baums, wenn x keinen Elternteil hatte). Schließlich, wenn x zwei Kinder hat, tauschen Sie seine Position im Baum mit der Position seines unmittelbaren Nachfolgers z in der sortierten Ordnung, auf einen der vorherigen Fälle hinauslaufend. In diesem Endfall kann der Tausch das Haufen bestellende Eigentum für z verletzen, so müssen zusätzliche Folgen eventuell durchgeführt werden, um dieses Eigentum wieder herzustellen.
• Um einen treap in zwei kleinere treaps zu spalten, fügen diejenigen, die kleiner sind als Schlüssel x und diejenigen, die größer sind als Schlüssel x, x in den treap mit dem maximalen Vorrang — größer ein als der Vorrang jedes Knotens im treap. Nach dieser Einfügung wird x der Wurzelknoten des treap, alle Werte weniger sein, als x im linken subtreap und allen größeren Werten gefunden wird, als x im Recht subtreap gefunden wird. Das kostet so viel wie eine einzelne Einfügung in den treap.
• Zwei treaps (angenommen verschmelzend, das Produkt eines ehemaligen Spalts zu sein), kann man sicher annehmen, dass der größte Wert im ersten treap weniger ist als der kleinste Wert im zweiten treap. Fügen Sie einen Wert x, solch ein, dass x größer als dieser Max-Wert im ersten treap und kleiner ist als der Minute-Wert im zweiten treap, und teilen Sie es der minimale Vorrang zu. Nach der Einfügung wird es ein Blatt-Knoten sein und kann leicht gelöscht werden. Das Ergebnis ist ein von den zwei ursprünglichen treaps verschmolzener treap. Das "macht" einen Spalt effektiv "auf", und kostet dasselbe.

Aragon und Seidel schlagen auch vor, höhere Prioritäten oft zugegriffenen Knoten zum Beispiel durch einen Prozess zuzuteilen, der, auf jedem Zugang, eine Zufallszahl wählt und den Vorrang des Knotens mit dieser Zahl ersetzt, wenn es höher ist als der vorherige Vorrang. Diese Modifizierung würde den Baum veranlassen, seine zufällige Gestalt zu verlieren; statt dessen oft würden zugegriffene Knoten mit größerer Wahrscheinlichkeit in der Nähe von der Wurzel des Baums sein, das Verursachen sucht nach ihnen, um schneller zu sein.

Blelloch und Reid-Miller beschreiben eine Anwendung von treaps zu einem Problem, Sätze von Sachen aufrechtzuerhalten und Satz-Vereinigung durchzuführen, setzen Kreuzung, und setzen Unterschied-Operationen mit einem treap, um jeden Satz zu vertreten. Naor und Nissim beschreiben eine andere Anwendung, um Genehmigungszertifikate im öffentlichen Schlüssel cryptosystems aufrechtzuerhalten.

Randomized binärer Suchbaum

Der randomized binäre Suchbaum, der von Martínez und Roura nachher zur Arbeit von Aragon und Seidel auf treaps eingeführt ist, versorgt dieselben Knoten mit demselben zufälligen Vertrieb der Baumgestalt, aber erhält verschiedene Information innerhalb der Knoten des Baums aufrecht, um seine randomized Struktur aufrechtzuerhalten.

Anstatt zufällige Prioritäten auf jedem Knoten zu versorgen, versorgt der randomized binäre Suchbaum an jedem Knoten eine kleine ganze Zahl, die Zahl seiner Nachkommen (sich als ein aufzählend); diese Zahlen können während Baumfolge-Operationen an nur einer unveränderlichen zusätzlichen Zeitdauer pro Folge aufrechterhalten werden. Wenn ein Schlüssel x in einen Baum eingefügt werden soll, der bereits n Knoten hat, wählt der Einfügungsalgorithmus mit der Wahrscheinlichkeit 1 / (n + 1), um x als die neue Wurzel des Baums zu legen, und sonst nennt es das Einfügungsverfahren rekursiv, um x innerhalb des verlassenen oder richtigen Subbaums einzufügen (je nachdem, ob sein Schlüssel weniger ist als oder größer als die Wurzel). Die Zahlen von Nachkommen werden durch den Algorithmus verwendet, um die notwendigen Wahrscheinlichkeiten für die zufälligen Wahlen an jedem Schritt zu berechnen. Das Stellen x an der Wurzel eines Subbaums kann entweder als im treap durch das Einfügen davon an einem Blatt und dann das Drehen davon aufwärts, oder durch einen alternativen Algorithmus durchgeführt werden, der von Martínez und Roura beschrieben ist, der den Subbaum in zwei Stücke spaltet, die als der verlassene und die richtigen Kinder des neuen Knotens zu verwenden sind.

Das Auswischen-Verfahren für einen randomized binären Suchbaum verwendet dieselbe Information pro Knoten wie das Einfügungsverfahren, und wie das Einfügungsverfahren macht es eine Folge von O (loggen Sie n), zufällige Entscheidungen, um sich den zwei Subbäumen anzuschließen, die vom verlassenen und den richtigen Kindern des gelöschten Knotens in einen einzelnen Baum hinuntersteigen. Wenn der verlassene oder richtige Subbaum des zu löschenden Knotens leer sind, ist die Verbindungslinie-Operation trivial; sonst werden der verlassene oder das richtige Kind des gelöschten Knotens als die neue Subbaumwurzel mit der Wahrscheinlichkeit ausgewählt, die zu seiner Zahl von Nachkommen proportional ist, und die Verbindungslinie geht rekursiv weiter.

Vergleich

Die Information, die pro Knoten im randomized binären Baum versorgt ist, ist einfacher als in einem treap (eine kleine ganze Zahl aber nicht eine Zufallszahl der hohen Präzision), aber es macht eine größere Zahl von Anrufen zum Zufallszahlengenerator (O (loggen Sie n) Anrufe pro Einfügung oder Auswischen aber nicht ein Anruf pro Einfügung), und das Einfügungsverfahren ist wegen des Bedürfnisses ein bisschen mehr kompliziert, die Zahlen von Nachkommen pro Knoten zu aktualisieren. Ein geringer technischer Unterschied ist, dass, in einem treap, es eine kleine Wahrscheinlichkeit einer Kollision (zwei Schlüssel gibt, die denselben Vorrang bekommen), und in beiden Fällen es statistische Unterschiede zwischen einem wahren Zufallszahlengenerator und dem pseudozufälligen auf Digitalcomputern normalerweise verwendeten Zahlengenerator geben wird. Jedoch jedenfalls haben die Unterschiede zwischen dem theoretischen Modell von vollkommenen zufälligen Wahlen gepflegt, den Algorithmus zu entwerfen, und die Fähigkeiten zu wirklichen Zufallszahlengeneratoren sind klein vanishingly.

Obwohl der treap und der randomized binäre Suchbaum beide denselben zufälligen Vertrieb von Baumgestalten nach jeder Aktualisierung haben, kann die Geschichte von Modifizierungen zu den Bäumen, die durch diese zwei Datenstrukturen über eine Folge der Einfügung und Auswischen-Operationen durchgeführt sind, verschieden sein. Zum Beispiel, in einem treap, wenn die drei Nummern 1, 2, und 3 in den Auftrag 1, 3, 2, und dann eingefügt werden, wird die Nummer 2 gelöscht, die restlichen zwei Knoten werden dieselbe Elternteilkind-Beziehung haben, die sie vor der Einfügung der mittleren Zahl getan haben. In einem randomized binären Suchbaum, dem Baum nachdem wird das Auswischen ebenso wahrscheinlich irgendein der zwei möglichen Bäume auf seinen zwei Knoten, unabhängig davon sein, wie was der Baum vor der Einfügung der mittleren Zahl ausgesehen hat.

Links

• Sammlung von treap Verweisungen und Info durch Cecilia Aragon
• Treap Applet durch Kubo Kovac
• Belebter treap
• Randomized binäre Suchbäume. Vortrag bemerkt von einem Kurs durch Jeff Erickson an UIUC. Trotz des Titels ist das in erster Linie über treaps und Hopser-Listen; randomized binäre Suchbäume werden nur kurz erwähnt.
• Ein hoher Leistungsschlüsselwert-Laden, der auf treap durch die Junyi Sonne gestützt ist
• VB6 Durchführung von treaps. 6 grundlegende Sehdurchführung von treaps als ein COM-Gegenstand.
• ActionScript3 Durchführung eines treap
• Reiner Python und Cython treap im Gedächtnis und duptreap
• Treaps in C#. Durch Roy Clemmons