[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/27\/treap-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/27\/treap-wikipedia\/","headline":"Treap – Wikipedia","name":"Treap – Wikipedia","description":"before-content-x4 In der Informatik ist die treap und das randomisierter bin\u00e4rer Suchbaum sind zwei eng verwandte Formen von bin\u00e4ren Suchbaumdatenstrukturen,","datePublished":"2020-11-27","dateModified":"2020-11-27","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki15\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki15\/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\/4\/4b\/TreapAlphaKey.svg\/220px-TreapAlphaKey.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/4\/4b\/TreapAlphaKey.svg\/220px-TreapAlphaKey.svg.png","height":"270","width":"220"},"url":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/27\/treap-wikipedia\/","wordCount":4188,"articleBody":" (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4In der Informatik ist die treap und das randomisierter bin\u00e4rer Suchbaum sind zwei eng verwandte Formen von bin\u00e4ren Suchbaumdatenstrukturen, die einen dynamischen Satz geordneter Schl\u00fcssel beibehalten und bin\u00e4re Suchen zwischen den Schl\u00fcsseln erm\u00f6glichen. Nach jeder Folge von Einf\u00fcgungen und L\u00f6schungen von Schl\u00fcsseln ist die Form des Baums eine Zufallsvariable mit der gleichen Wahrscheinlichkeitsverteilung wie ein zuf\u00e4lliger Bin\u00e4rbaum. Insbesondere ist seine H\u00f6he mit hoher Wahrscheinlichkeit proportional zum Logarithmus der Anzahl der Schl\u00fcssel, so dass jede Such-, Einf\u00fcge- oder L\u00f6schoperation logarithmische Zeit ben\u00f6tigt, um ausgef\u00fchrt zu werden. (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of ContentsBeschreibung[edit]Operationen[edit]Massenoperationen[edit]Randomisierter bin\u00e4rer Suchbaum[edit]Vergleich[edit]Siehe auch[edit]Verweise[edit]Externe Links[edit]Beschreibung[edit] Ein Treap mit alphabetischem Schl\u00fcssel und numerischer maximaler Heap-ReihenfolgeDer Treap wurde erstmals 1989 von Raimund Seidel und Cecilia R. Aragon beschrieben;[1][2] Sein Name ist ein Portmanteau aus Baum und Haufen. Es ist ein kartesischer Baum, in dem jeder Schl\u00fcssel eine (zuf\u00e4llig ausgew\u00e4hlte) numerische Priorit\u00e4t erh\u00e4lt. Wie bei jedem bin\u00e4ren Suchbaum entspricht die Inorder-Traversal-Reihenfolge der Knoten der sortierten Reihenfolge der Schl\u00fcssel. Die Struktur des Baums wird durch die Anforderung bestimmt, dass er Heap-geordnet sein muss: Das hei\u00dft, die Priorit\u00e4tsnummer f\u00fcr jeden Nicht-Blatt-Knoten muss gr\u00f6\u00dfer oder gleich der Priorit\u00e4t seiner untergeordneten Knoten sein. Wie bei kartesischen B\u00e4umen im Allgemeinen ist der Wurzelknoten der Knoten mit der maximalen Priorit\u00e4t, und seine linken und rechten Teilb\u00e4ume werden auf die gleiche Weise aus den Teilsequenzen der sortierten Reihenfolge links und rechts von diesem Knoten gebildet. (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Eine \u00e4quivalente Art der Beschreibung des Treaps besteht darin, dass er gebildet werden kann, indem die Knoten mit der h\u00f6chsten Priorit\u00e4t zuerst in einen bin\u00e4ren Suchbaum eingef\u00fcgt werden, ohne dass ein Neuausgleich durchgef\u00fchrt wird. Wenn die Priorit\u00e4ten unabh\u00e4ngige Zufallszahlen sind (aus einer Verteilung \u00fcber einen ausreichend gro\u00dfen Raum m\u00f6glicher Priorit\u00e4ten, um sicherzustellen, dass zwei Knoten wahrscheinlich nicht dieselbe Priorit\u00e4t haben), hat die Form eines Treaps dieselbe Wahrscheinlichkeitsverteilung wie die Form von ein zuf\u00e4lliger bin\u00e4rer Suchbaum, ein Suchbaum, der durch Einf\u00fcgen der Knoten ohne Neuausgleich in einer zuf\u00e4llig ausgew\u00e4hlten Einf\u00fcgereihenfolge gebildet wird. Da zuf\u00e4llige bin\u00e4re Suchb\u00e4ume mit hoher Wahrscheinlichkeit eine logarithmische H\u00f6he aufweisen, gilt dies auch f\u00fcr Treaps.Aragon und Seidel schlagen au\u00dferdem vor, Knoten mit h\u00e4ufigem Zugriff h\u00f6here Priorit\u00e4ten zuzuweisen, beispielsweise durch einen Prozess, der bei jedem Zugriff eine Zufallszahl ausw\u00e4hlt und die Priorit\u00e4t des Knotens durch diese Nummer ersetzt, wenn sie h\u00f6her als die vorherige Priorit\u00e4t ist. Diese \u00c4nderung w\u00fcrde dazu f\u00fchren, dass der Baum seine zuf\u00e4llige Form verliert. Stattdessen befinden sich Knoten, auf die h\u00e4ufig zugegriffen wird, eher in der N\u00e4he der Wurzel des Baums, wodurch die Suche nach ihnen schneller wird.Naor und Nissim[3] Beschreiben einer Anwendung zum Verwalten von Autorisierungszertifikaten in Kryptosystemen mit \u00f6ffentlichem Schl\u00fcssel.Operationen[edit]Treaps unterst\u00fctzen die folgenden grundlegenden Operationen: (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Wenden Sie zum Suchen nach einem bestimmten Schl\u00fcsselwert einen standardm\u00e4\u00dfigen bin\u00e4ren Suchalgorithmus in einem bin\u00e4ren Suchbaum an, wobei Sie die Priorit\u00e4ten ignorieren.So f\u00fcgen Sie einen neuen Schl\u00fcssel ein x Generieren Sie in den Treap eine zuf\u00e4llige Priorit\u00e4t y zum x. Bin\u00e4re Suche nach x Erstellen Sie im Baum einen neuen Knoten an der Blattposition, an der die bin\u00e4re Suche einen Knoten f\u00fcr bestimmt x sollte existieren. Dann, solange x ist nicht die Wurzel des Baums und hat eine gr\u00f6\u00dfere Priorit\u00e4tsnummer als das \u00fcbergeordnete Element zF\u00fchren Sie eine Baumrotation durch, die die Eltern-Kind-Beziehung zwischen umkehrt x und z.So l\u00f6schen Sie einen Knoten x aus dem Treap, wenn x ist ein Blatt des Baumes, entfernen Sie es einfach. Wenn x hat ein einziges Kind z, entfernen x vom Baum und machen z sei das Kind des Elternteils von x (oder machen z die Wurzel des Baumes wenn x hatte keine Eltern). Zum Schluss, wenn x hat zwei Kinder, tauschen Sie ihre Position im Baum mit der Position seines unmittelbaren Nachfolgers z in der sortierten Reihenfolge, was zu einem der vorherigen F\u00e4lle f\u00fchrt. In diesem letzten Fall kann der Swap die Heap-Reihenfolgeseigenschaft f\u00fcr verletzen zDaher m\u00fcssen m\u00f6glicherweise zus\u00e4tzliche Rotationen durchgef\u00fchrt werden, um diese Eigenschaft wiederherzustellen.Massenoperationen[edit]Zus\u00e4tzlich zu den Einf\u00fcge-, L\u00f6sch- und Suchvorg\u00e4ngen mit einem Element wurden mehrere schnelle “Massen” -Operationen f\u00fcr Treaps definiert: Vereinigung, Schnittmenge und Mengenunterschied. Diese beruhen auf zwei Hilfseins\u00e4tzen: Teilt und beitreten.Um einen Treap in zwei kleinere Treaps aufzuteilen, die kleiner als der Schl\u00fcssel sind xund diejenigen, die gr\u00f6\u00dfer als der Schl\u00fcssel sind xeinf\u00fcgen x in den Treap mit maximaler Priorit\u00e4t – gr\u00f6\u00dfer als die Priorit\u00e4t eines Knotens im Treap. Nach dieser Einf\u00fcgung x wird der Wurzelknoten des Treaps sein, alle Werte kleiner als x wird im linken Teilbereich gefunden, und alle Werte sind gr\u00f6\u00dfer als x finden Sie im rechten Teilbereich. Dies kostet so viel wie ein einzelnes Einsetzen in den Treap.Wenn man zwei Treaps verbindet, die das Produkt eines fr\u00fcheren Split sind, kann man davon ausgehen, dass der gr\u00f6\u00dfte Wert im ersten Treap kleiner ist als der kleinste Wert im zweiten Treap. Erstellen Sie einen neuen Knoten mit Wert x, so dass x ist gr\u00f6\u00dfer als dieser Maximalwert im ersten Treap und kleiner als der Minimalwert im zweiten Treap. Weisen Sie ihm die minimale Priorit\u00e4t zu und setzen Sie dann sein linkes Kind auf den ersten Heap und sein rechtes Kind auf den zweiten Heap. Nach Bedarf drehen, um die Heap-Reihenfolge festzulegen. Danach ist es ein Blattknoten und kann leicht gel\u00f6scht werden. Das Ergebnis ist ein Treap, der aus den beiden urspr\u00fcnglichen Treaps zusammengef\u00fchrt wurde. Dies macht einen Split effektiv “r\u00fcckg\u00e4ngig” und kostet dasselbe. Im Allgemeinen kann die Verkn\u00fcpfungsoperation mit zwei Treaps und einem Schl\u00fcssel mit beliebiger Priorit\u00e4t arbeiten (dh nicht erforderlich, um die h\u00f6chste zu sein).Der Join-Algorithmus lautet wie folgt:function join(L, k, R) if prior(k, k(L)) and prior(k, k(R)) return Node(L, k, R) if prior(k(L), k(R)) return Node(left(L), k(L), join(right(L), k, R)) return Node(join(L, k, left(R), k(R), right(R))Der Split-Algorithmus lautet wie folgt:function split(T, k) if (T = nil) return (nil, false, nil) (L, (m, c), R) = expose(T) if (k = m) return (L, true, R) if (k < m) (L', b, R') = split(L, k) return (L', b, join(R', m, R)) if (k > m) (L', b, R') = split(R, k) return (join(L, m, L'), b, R))Die Vereinigung zweier Treaps t1 und t2, die Mengen darstellen EIN und B. ist ein Treap t das repr\u00e4sentiert EIN \u222a B.. Der folgende rekursive Algorithmus berechnet die Vereinigung:function union(t1, t2): if t1 = nil: return t2if t2 = nil: return t1if priority(t1) < priority(t2): swap t1 and t2 t \u2190 split t2 on key(t1) return join(union(left(t1), t))Hier, Teilt Es wird angenommen, dass zwei B\u00e4ume zur\u00fcckgegeben werden: einer h\u00e4lt die Tasten weniger als die Eingabetaste, einer h\u00e4lt die gr\u00f6\u00dferen Tasten. (Der Algorithmus ist zerst\u00f6rungsfrei, es gibt jedoch auch eine destruktive Version an Ort und Stelle.)Der Algorithmus f\u00fcr die Schnittmenge ist \u00e4hnlich, erfordert jedoch die beitreten Hilfsroutine. Die Komplexit\u00e4t jeder Vereinigung, Schnittmenge und Differenz ist \u00d6((m Log n\/.m) f\u00fcr Treaps von Gr\u00f6\u00dfen m und nmit m \u2264 n. Da die rekursiven Aufrufe zur Vereinigung unabh\u00e4ngig voneinander sind, k\u00f6nnen sie au\u00dferdem parallel ausgef\u00fchrt werden.[4]Split und Union rufen Join auf, befassen sich jedoch nicht direkt mit den Ausgleichskriterien von Treaps. Eine solche Implementierung wird normalerweise als “Join-basierte” Implementierung bezeichnet.Beachten Sie, dass, wenn Hash-Werte von Schl\u00fcsseln als Priorit\u00e4ten verwendet werden und strukturell gleiche Knoten bereits bei der Erstellung zusammengef\u00fchrt werden, jeder zusammengef\u00fchrte Knoten eine eindeutige Darstellung eines Satzes von Schl\u00fcsseln ist. Vorausgesetzt, es kann nur einen simultanen Wurzelknoten geben, der einen bestimmten Satz von Schl\u00fcsseln darstellt, k\u00f6nnen zwei S\u00e4tze durch Zeigervergleich, der zeitlich konstant ist, auf Gleichheit getestet werden.Diese Technik kann verwendet werden, um die Zusammenf\u00fchrungsalgorithmen so zu verbessern, dass sie auch dann schnell arbeiten, wenn der Unterschied zwischen zwei S\u00e4tzen gering ist. Wenn die Eingabes\u00e4tze gleich sind, k\u00f6nnen die Vereinigungs- und Schnittfunktionen sofort unterbrochen werden, wenn einer der Eingabes\u00e4tze als Ergebnis zur\u00fcckgegeben wird, w\u00e4hrend die Differenzfunktion den leeren Satz zur\u00fcckgeben sollte.Lassen d sei die Gr\u00f6\u00dfe der symmetrischen Differenz. Die modifizierten Zusammenf\u00fchrungsalgorithmen werden dann auch durch begrenzt \u00d6((d Log n\/.d).[5][6]Randomisierter bin\u00e4rer Suchbaum[edit]Der randomisierte bin\u00e4re Suchbaum, der von Mart\u00ednez und Roura im Anschluss an die Arbeit von Aragon und Seidel an Treaps eingef\u00fchrt wurde,[7] speichert dieselben Knoten mit derselben zuf\u00e4lligen Verteilung der Baumform, beh\u00e4lt jedoch unterschiedliche Informationen innerhalb der Knoten des Baums bei, um seine zuf\u00e4llige Struktur beizubehalten.Anstatt zuf\u00e4llige Priorit\u00e4ten auf jedem Knoten zu speichern, speichert der randomisierte bin\u00e4re Suchbaum an jedem Knoten eine kleine Ganzzahl, die Anzahl seiner Nachkommen (z\u00e4hlt sich selbst als eins); Diese Zahlen k\u00f6nnen w\u00e4hrend Baumrotationsvorg\u00e4ngen nur mit einer konstanten zus\u00e4tzlichen Zeitdauer pro Rotation beibehalten werden. Wenn ein Schl\u00fcssel x soll in einen Baum eingef\u00fcgt werden, der bereits hat n Knoten w\u00e4hlt der Einf\u00fcgealgorithmus mit der Wahrscheinlichkeit 1 \/ (n + 1) zu platzieren x als neue Wurzel des Baums, und ansonsten ruft es die Einf\u00fcgeprozedur rekursiv zum Einf\u00fcgen auf x innerhalb des linken oder rechten Teilbaums (abh\u00e4ngig davon, ob sein Schl\u00fcssel kleiner oder gr\u00f6\u00dfer als die Wurzel ist). Die Anzahl der Nachkommen wird vom Algorithmus verwendet, um die erforderlichen Wahrscheinlichkeiten f\u00fcr die Zufallsauswahl bei jedem Schritt zu berechnen. Platzieren x an der Wurzel eines Teilbaums kann entweder wie im Treap ausgef\u00fchrt werden, indem es an einem Blatt eingef\u00fcgt und dann nach oben gedreht wird, oder durch einen von Mart\u00ednez und Roura beschriebenen alternativen Algorithmus, der den Teilbaum in zwei Teile aufteilt, um als linker und zu verwenden rechte Kinder des neuen Knotens.Die L\u00f6schprozedur f\u00fcr einen randomisierten bin\u00e4ren Suchbaum verwendet die gleichen Informationen pro Knoten wie die Einf\u00fcgeprozedur, ben\u00f6tigt jedoch im Gegensatz zur Einf\u00fcgeprozedur nur durchschnittlich O (1) zuf\u00e4llige Entscheidungen, um die beiden Teilb\u00e4ume zu verbinden, die vom linken und rechten Kind des gel\u00f6schter Knoten in einem einzelnen Baum. Dies liegt daran, dass sich die zu verbindenden Teilb\u00e4ume im Durchschnitt in der Tiefe \u0398 (log n) befinden. Das Verbinden von zwei B\u00e4umen der Gr\u00f6\u00dfe n und m erfordert im Durchschnitt \u0398 (log (n + m)) zuf\u00e4llige Auswahlm\u00f6glichkeiten. Wenn der linke oder rechte Teilbaum des zu l\u00f6schenden Knotens leer ist, ist die Verkn\u00fcpfungsoperation trivial. Andernfalls wird das linke oder rechte untergeordnete Element des gel\u00f6schten Knotens mit einer Wahrscheinlichkeit proportional zur Anzahl der Nachkommen als neue Teilbaumwurzel ausgew\u00e4hlt, und der Join wird rekursiv fortgesetzt.Vergleich[edit]Die pro Knoten im randomisierten Bin\u00e4rbaum gespeicherten Informationen sind einfacher als in einem Treap (eine kleine Ganzzahl anstelle einer hochpr\u00e4zisen Zufallszahl), f\u00fchren jedoch eine gr\u00f6\u00dfere Anzahl von Aufrufen an den Zufallszahlengenerator (O (log) durch n) Aufrufe pro Einf\u00fcgung oder L\u00f6schung statt eines Aufrufs pro Einf\u00fcgung) und das Einf\u00fcgeverfahren ist etwas komplizierter, da die Anzahl der Nachkommen pro Knoten aktualisiert werden muss. Ein kleiner technischer Unterschied besteht darin, dass bei einem Treap eine geringe Wahrscheinlichkeit einer Kollision besteht (zwei Schl\u00fcssel erhalten dieselbe Priorit\u00e4t), und in beiden F\u00e4llen gibt es statistische Unterschiede zwischen einem echten Zufallszahlengenerator und dem Pseudozufallszahlengenerator Wird normalerweise auf digitalen Computern verwendet. In jedem Fall sind die Unterschiede zwischen dem theoretischen Modell der perfekten Zufallsauswahl, die zum Entwerfen des Algorithmus verwendet wird, und den F\u00e4higkeiten der tats\u00e4chlichen Zufallszahlengeneratoren verschwindend gering.Obwohl sowohl der Treap- als auch der randomisierte bin\u00e4re Suchbaum nach jeder Aktualisierung dieselbe zuf\u00e4llige Verteilung der Baumformen aufweisen, kann der Verlauf der \u00c4nderungen an den B\u00e4umen, die von diesen beiden Datenstrukturen \u00fcber eine Folge von Einf\u00fcge- und L\u00f6schvorg\u00e4ngen ausgef\u00fchrt werden, unterschiedlich sein. Wenn beispielsweise in einem Treap die drei Zahlen 1, 2 und 3 in der Reihenfolge 1, 3, 2 eingef\u00fcgt werden und dann die Zahl 2 gel\u00f6scht wird, haben die verbleibenden zwei Knoten dieselbe Eltern-Kind-Beziehung wie sie tat vor dem Einf\u00fcgen der mittleren Zahl. In einem zuf\u00e4lligen bin\u00e4ren Suchbaum ist der Baum nach dem L\u00f6schen wahrscheinlich einer der beiden m\u00f6glichen B\u00e4ume auf seinen beiden Knoten, unabh\u00e4ngig davon, wie der Baum vor dem Einf\u00fcgen der mittleren Zahl aussah.Siehe auch[edit]Verweise[edit]^ Aragon, Cecilia R.; Seidel, Raimund (1989), “Randomisierte Suchb\u00e4ume” (PDF), Proc. 30. Symp. Grundlagen der Informatik (FOCS 1989), Washington, DC: IEEE Computer Society Press, S. 540\u2013545, doi:10.1109 \/ SFCS.1989.63531, ISBN 0-8186-1982-1^ Seidel, Raimund; Aragon, Cecilia R. (1996), “Randomisierte Suchb\u00e4ume”, Algorithmica, 16 (4\/5): 464\u2013497, doi:10.1007 \/ s004539900061^ Naor, M.; Nissim, K. (April 2000), “Zertifikatsperrung und Zertifikatsaktualisierung” (PDF), IEEE Journal zu ausgew\u00e4hlten Bereichen der Kommunikation, 18 (4): 561\u2013570, doi:10.1109 \/ 49.839932[permanent dead link].^ Blelloch, Guy E.; Reid-Miller, Margaret (1998), “Fast-Set-Operationen mit Treaps”, Proc. 10. ACM Symp. Parallele Algorithmen und Architekturen (SPAA 1998), New York, NY, USA: ACM, S. 16\u201326, doi:10.1145 \/ 277651.277660, ISBN 0-89791-989-0.^ Liljenzin, Olle (2013). “Konfluent persistente Sets und Maps”. arXiv:1301.3388. Bibcode:2013arXiv1301.3388L. ^ Konfluente Sets und Maps auf GitHub^ Mart\u00ednez, Conrado; Roura, Salvador (1997), “Randomisierte bin\u00e4re Suchb\u00e4ume”, Zeitschrift der ACM, 45 (2): 288\u2013323, doi:10.1145 \/ 274787.274812Externe Links[edit]Wikimedia Commons hat Medien im Zusammenhang mit Treap. (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki15\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/27\/treap-wikipedia\/#breadcrumbitem","name":"Treap – Wikipedia"}}]}]