Treap – Wikipedia

Posted on by
before-content-x4

In der Informatik ist die treap und das randomisierter binärer Suchbaum sind zwei eng verwandte Formen von binären Suchbaumdatenstrukturen, die einen dynamischen Satz geordneter Schlüssel beibehalten und binäre Suchen zwischen den Schlüsseln ermöglichen. Nach jeder Folge von Einfügungen und Löschungen von Schlüsseln ist die Form des Baums eine Zufallsvariable mit der gleichen Wahrscheinlichkeitsverteilung wie ein zufälliger Binärbaum. Insbesondere ist seine Höhe mit hoher Wahrscheinlichkeit proportional zum Logarithmus der Anzahl der Schlüssel, so dass jede Such-, Einfüge- oder Löschoperation logarithmische Zeit benötigt, um ausgeführt zu werden.

Beschreibung[edit]

Ein Treap mit alphabetischem Schlüssel und numerischer maximaler Heap-Reihenfolge

Der 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üssel eine (zufällig ausgewählte) numerische Priorität erhält. Wie bei jedem binären Suchbaum entspricht die Inorder-Traversal-Reihenfolge der Knoten der sortierten Reihenfolge der Schlüssel. Die Struktur des Baums wird durch die Anforderung bestimmt, dass er Heap-geordnet sein muss: Das heißt, die Prioritätsnummer für jeden Nicht-Blatt-Knoten muss größer oder gleich der Priorität seiner untergeordneten Knoten sein. Wie bei kartesischen Bäumen im Allgemeinen ist der Wurzelknoten der Knoten mit der maximalen Priorität, und seine linken und rechten Teilbäume werden auf die gleiche Weise aus den Teilsequenzen der sortierten Reihenfolge links und rechts von diesem Knoten gebildet.

Eine äquivalente Art der Beschreibung des Treaps besteht darin, dass er gebildet werden kann, indem die Knoten mit der höchsten Priorität zuerst in einen binären Suchbaum eingefügt werden, ohne dass ein Neuausgleich durchgeführt wird. Wenn die Prioritäten unabhängige Zufallszahlen sind (aus einer Verteilung über einen ausreichend großen Raum möglicher Prioritäten, um sicherzustellen, dass zwei Knoten wahrscheinlich nicht dieselbe Priorität haben), hat die Form eines Treaps dieselbe Wahrscheinlichkeitsverteilung wie die Form von ein zufälliger binärer Suchbaum, ein Suchbaum, der durch Einfügen der Knoten ohne Neuausgleich in einer zufällig ausgewählten Einfügereihenfolge gebildet wird. Da zufällige binäre Suchbäume mit hoher Wahrscheinlichkeit eine logarithmische Höhe aufweisen, gilt dies auch für Treaps.

Aragon und Seidel schlagen außerdem vor, Knoten mit häufigem Zugriff höhere Prioritäten zuzuweisen, beispielsweise durch einen Prozess, der bei jedem Zugriff eine Zufallszahl auswählt und die Priorität des Knotens durch diese Nummer ersetzt, wenn sie höher als die vorherige Priorität ist. Diese Änderung würde dazu führen, dass der Baum seine zufällige Form verliert. Stattdessen befinden sich Knoten, auf die häufig zugegriffen wird, eher in der Nähe 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 öffentlichem Schlüssel.

Operationen[edit]

Treaps unterstützen die folgenden grundlegenden Operationen:

after-content-x4
  • Wenden Sie zum Suchen nach einem bestimmten Schlüsselwert einen standardmäßigen binären Suchalgorithmus in einem binären Suchbaum an, wobei Sie die Prioritäten ignorieren.
  • So fügen Sie einen neuen Schlüssel ein x Generieren Sie in den Treap eine zufällige Priorität y zum x. Binäre Suche nach x Erstellen Sie im Baum einen neuen Knoten an der Blattposition, an der die binäre Suche einen Knoten für bestimmt x sollte existieren. Dann, solange x ist nicht die Wurzel des Baums und hat eine größere Prioritätsnummer als das übergeordnete Element zFühren Sie eine Baumrotation durch, die die Eltern-Kind-Beziehung zwischen umkehrt x und z.
  • So löschen 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älle führt. In diesem letzten Fall kann der Swap die Heap-Reihenfolgeseigenschaft für verletzen zDaher müssen möglicherweise zusätzliche Rotationen durchgeführt werden, um diese Eigenschaft wiederherzustellen.

Massenoperationen[edit]

Zusätzlich zu den Einfüge-, Lösch- und Suchvorgängen mit einem Element wurden mehrere schnelle “Massen” -Operationen für Treaps definiert: Vereinigung, Schnittmenge und Mengenunterschied. Diese beruhen auf zwei Hilfseinsätzen: Teilt und beitreten.

  • Um einen Treap in zwei kleinere Treaps aufzuteilen, die kleiner als der Schlüssel sind xund diejenigen, die größer als der Schlüssel sind xeinfügen x in den Treap mit maximaler Priorität – größer als die Priorität eines Knotens im Treap. Nach dieser Einfügung x wird der Wurzelknoten des Treaps sein, alle Werte kleiner als x wird im linken Teilbereich gefunden, und alle Werte sind größer 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üheren Split sind, kann man davon ausgehen, dass der größte 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ößer als dieser Maximalwert im ersten Treap und kleiner als der Minimalwert im zweiten Treap. Weisen Sie ihm die minimale Priorität 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öscht werden. Das Ergebnis ist ein Treap, der aus den beiden ursprünglichen Treaps zusammengeführt wurde. Dies macht einen Split effektiv “rückgängig” und kostet dasselbe. Im Allgemeinen kann die Verknüpfungsoperation mit zwei Treaps und einem Schlüssel mit beliebiger Priorität arbeiten (dh nicht erforderlich, um die höchste 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äsentiert EIN ∪ 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<, t> ← split t2 on key(t1)
    return join(union(left(t1), t<), key(t1),
                    union(right(t1), t>))

Hier, Teilt Es wird angenommen, dass zwei Bäume zurückgegeben werden: einer hält die Tasten weniger als die Eingabetaste, einer hält die größeren Tasten. (Der Algorithmus ist zerstörungsfrei, es gibt jedoch auch eine destruktive Version an Ort und Stelle.)

Der Algorithmus für die Schnittmenge ist ähnlich, erfordert jedoch die beitreten Hilfsroutine. Die Komplexität jeder Vereinigung, Schnittmenge und Differenz ist Ö((m Log n/.m) für Treaps von Größen m und nmit m ≤ n. Da die rekursiven Aufrufe zur Vereinigung unabhängig voneinander sind, können sie außerdem parallel ausgeführt 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üsseln als Prioritäten verwendet werden und strukturell gleiche Knoten bereits bei der Erstellung zusammengeführt werden, jeder zusammengeführte Knoten eine eindeutige Darstellung eines Satzes von Schlüsseln ist. Vorausgesetzt, es kann nur einen simultanen Wurzelknoten geben, der einen bestimmten Satz von Schlüsseln darstellt, können zwei Sätze durch Zeigervergleich, der zeitlich konstant ist, auf Gleichheit getestet werden.

Diese Technik kann verwendet werden, um die Zusammenführungsalgorithmen so zu verbessern, dass sie auch dann schnell arbeiten, wenn der Unterschied zwischen zwei Sätzen gering ist. Wenn die Eingabesätze gleich sind, können die Vereinigungs- und Schnittfunktionen sofort unterbrochen werden, wenn einer der Eingabesätze als Ergebnis zurückgegeben wird, während die Differenzfunktion den leeren Satz zurückgeben sollte.

Lassen d sei die Größe der symmetrischen Differenz. Die modifizierten Zusammenführungsalgorithmen werden dann auch durch begrenzt Ö((d Log n/.d).[5][6]

Randomisierter binärer Suchbaum[edit]

Der randomisierte binäre Suchbaum, der von Martínez und Roura im Anschluss an die Arbeit von Aragon und Seidel an Treaps eingeführt wurde,[7] speichert dieselben Knoten mit derselben zufälligen Verteilung der Baumform, behält jedoch unterschiedliche Informationen innerhalb der Knoten des Baums bei, um seine zufällige Struktur beizubehalten.

Anstatt zufällige Prioritäten auf jedem Knoten zu speichern, speichert der randomisierte binäre Suchbaum an jedem Knoten eine kleine Ganzzahl, die Anzahl seiner Nachkommen (zählt sich selbst als eins); Diese Zahlen können während Baumrotationsvorgängen nur mit einer konstanten zusätzlichen Zeitdauer pro Rotation beibehalten werden. Wenn ein Schlüssel x soll in einen Baum eingefügt werden, der bereits hat n Knoten wählt der Einfügealgorithmus mit der Wahrscheinlichkeit 1 / (n + 1) zu platzieren x als neue Wurzel des Baums, und ansonsten ruft es die Einfügeprozedur rekursiv zum Einfügen auf x innerhalb des linken oder rechten Teilbaums (abhängig davon, ob sein Schlüssel kleiner oder größer als die Wurzel ist). Die Anzahl der Nachkommen wird vom Algorithmus verwendet, um die erforderlichen Wahrscheinlichkeiten für die Zufallsauswahl bei jedem Schritt zu berechnen. Platzieren x an der Wurzel eines Teilbaums kann entweder wie im Treap ausgeführt werden, indem es an einem Blatt eingefügt und dann nach oben gedreht wird, oder durch einen von Martínez 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öschprozedur für einen randomisierten binären Suchbaum verwendet die gleichen Informationen pro Knoten wie die Einfügeprozedur, benötigt jedoch im Gegensatz zur Einfügeprozedur nur durchschnittlich O (1) zufällige Entscheidungen, um die beiden Teilbäume zu verbinden, die vom linken und rechten Kind des gelöschter Knoten in einem einzelnen Baum. Dies liegt daran, dass sich die zu verbindenden Teilbäume im Durchschnitt in der Tiefe Θ (log n) befinden. Das Verbinden von zwei Bäumen der Größe n und m erfordert im Durchschnitt Θ (log (n + m)) zufällige Auswahlmöglichkeiten. Wenn der linke oder rechte Teilbaum des zu löschenden Knotens leer ist, ist die Verknüpfungsoperation trivial. Andernfalls wird das linke oder rechte untergeordnete Element des gelöschten Knotens mit einer Wahrscheinlichkeit proportional zur Anzahl der Nachkommen als neue Teilbaumwurzel ausgewählt, und der Join wird rekursiv fortgesetzt.

Vergleich[edit]

Die pro Knoten im randomisierten Binärbaum gespeicherten Informationen sind einfacher als in einem Treap (eine kleine Ganzzahl anstelle einer hochpräzisen Zufallszahl), führen jedoch eine größere Anzahl von Aufrufen an den Zufallszahlengenerator (O (log) durch n) Aufrufe pro Einfügung oder Löschung statt eines Aufrufs pro Einfügung) und das Einfügeverfahren 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üssel erhalten dieselbe Priorität), und in beiden Fällen 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ähigkeiten der tatsächlichen Zufallszahlengeneratoren verschwindend gering.

Obwohl sowohl der Treap- als auch der randomisierte binäre Suchbaum nach jeder Aktualisierung dieselbe zufällige Verteilung der Baumformen aufweisen, kann der Verlauf der Änderungen an den Bäumen, die von diesen beiden Datenstrukturen über eine Folge von Einfüge- und Löschvorgängen ausgeführt werden, unterschiedlich sein. Wenn beispielsweise in einem Treap die drei Zahlen 1, 2 und 3 in der Reihenfolge 1, 3, 2 eingefügt werden und dann die Zahl 2 gelöscht wird, haben die verbleibenden zwei Knoten dieselbe Eltern-Kind-Beziehung wie sie tat vor dem Einfügen der mittleren Zahl. In einem zufälligen binären Suchbaum ist der Baum nach dem Löschen wahrscheinlich einer der beiden möglichen Bäume auf seinen beiden Knoten, unabhängig davon, wie der Baum vor dem Einfügen der mittleren Zahl aussah.

Siehe auch[edit]

Verweise[edit]

  1. ^ Aragon, Cecilia R.; Seidel, Raimund (1989), “Randomisierte Suchbäume” (PDF), Proc. 30. Symp. Grundlagen der Informatik (FOCS 1989), Washington, DC: IEEE Computer Society Press, S. 540–545, doi:10.1109 / SFCS.1989.63531, ISBN 0-8186-1982-1
  2. ^
    Seidel, Raimund; Aragon, Cecilia R. (1996), “Randomisierte Suchbäume”, Algorithmica, 16 (4/5): 464–497, doi:10.1007 / s004539900061
  3. ^ Naor, M.; Nissim, K. (April 2000), “Zertifikatsperrung und Zertifikatsaktualisierung” (PDF), IEEE Journal zu ausgewählten Bereichen der Kommunikation, 18 (4): 561–570, doi:10.1109 / 49.839932[permanent dead link].
  4. ^ 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–26, doi:10.1145 / 277651.277660, ISBN 0-89791-989-0.
  5. ^ Liljenzin, Olle (2013). “Konfluent persistente Sets und Maps”. arXiv:1301.3388. Bibcode:2013arXiv1301.3388L.
  6. ^ Konfluente Sets und Maps auf GitHub
  7. ^ Martínez, Conrado; Roura, Salvador (1997), “Randomisierte binäre Suchbäume”, Zeitschrift der ACM, 45 (2): 288–323, doi:10.1145 / 274787.274812

Externe Links[edit]


after-content-x4