Treap mit impliziten Schlüsseln

Question

Es gibt eine Datenstruktur namens Treap: das ist ein zufälliger binärer Suchbaum, der auch ein Haufen zufällig erzeugter sogenannter "Prioritäten" ist.

Es gibt eine Variation dieser Struktur, bei der Schlüssel implizit sind, sie werden nicht im Baum gespeichert, aber wir betrachten den geordneten Index des Knotens im Baum als Schlüssel dieses Knotens. Wir müssen die Größe des Unterbaums in jedem Knoten anstelle des Schlüssels speichern. Diese Technik ermöglicht es uns, über Treap wie eine Art Array zu denken, das viele Operationen in O (log N) -Zeit unterstützt: Einfügen, Löschen, Reversion von Subarrays, Ändern des Intervalls und so weiter.

Ich weiß ein bisschen über diese Struktur, aber nicht so viel. Ich habe versucht, es zu googeln, aber ich habe nur viele Artikel über Treap selbst gefunden, aber nichts über diese "implizite Treap"/"indexierte Liste". Ich kenne seinen Namen gar nicht, weil meine Muttersprache nicht Englisch ist und Vorlesungen, die ich gehört habe, den ursprünglichen Begriff der Struktur verwendet haben, nicht den englischen Originalbegriff. Dieser native Begriff kann direkt in Englisch als "Treap auf den impliziten Schlüsseln" oder "Cartesian Tree auf den impliziten Schlüsseln" übersetzt werden.

Kann jemand mich auf den Artikel über diese Struktur zeigen oder mir seinen ursprünglichen Namen sagen? Vielen Dank.

P.S. Entschuldigung, wenn mein Englisch nicht verständlich genug war.

UPD: Einige zusätzliche Erklärung über Struktur, die ich suche.

Betrachten Sie einen üblichen Treap mit zufällig ausgewählten Prioritäten und Schlüssel, die tatsächliche Benutzerdaten im Baum gespeichert sind. Dann stellen wir uns vor, wir haben einige andere Benutzerinformationen in jedem Knoten gespeichert, und Schlüssel sind nichts als die Suchschlüssel. Der nächste Schritt ist das Berechnen und Pflegen der Teilbaumgröße in jedem Knoten: wir müssen diesen Parameter nach jedem Zusammenführen/Teilen/Hinzufügen/Entfernen aktualisieren, aber es ermöglicht uns zum Beispiel, Kth Element des Baumes in O zu finden (log N) Zeit.

Wenn wir Teilbaumgrößen in jedem Knoten haben, können wir Schlüssel wegwerfen und uns vorstellen, dass Treap ein Array von Benutzerdaten in Inorder-Traversierung darstellt. Der Array-Index jedes Elements kann leicht aus Teilbaumgrößen berechnet werden. Jetzt können wir ein Element in der Mitte des Arrays hinzufügen/entfernen oder dieses Array aufteilen - alles in O (log N) Zeit.

Wir können auch "mehrere" Operationen ausführen - zum Beispiel einen konstanten Wert für alle Elemente unseres "Arrays" hinzufügen. Um dies zu implementieren, müssen wir diese Operation verzögern, fügen einen Parameter in jedem Knoten hinzu, der eine verzögerte Konstante darstellt, die "später" zu allen Elementen des Unterarrays dieses Knotens hinzugefügt werden muss, und die Änderungen "nach unten" als "schieben" notwendig. Das Hinzufügen einer Konstante zum Subarray oder zum Zeichnen (Markieren) des Subarrays kann auf diese Weise verzögert werden, indem das Subarray umgekehrt wird (hier müssen die verzögerten Informationen im Knoten im Bit "Subarray umgekehrt" werden) und so weiter.

UPD2: Hier code snippet - Stück der geringen Menge an Informationen, die ich gefunden habe. Bemerke nicht kyrillisch :) Wörter "с неявным ключом" bedeuten in der direkten Übersetzung "mit dem impliziten Schlüssel".

Answer 1

Sie finden diese Datenstruktur in dem Papier von Kaplan und Verbin zum Sortieren vorzeichenbehafteter Permutationen durch Umkehrungen (Seite 7, Abschnitt 3.1): http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf.

Answer 2

Die Schlüsselidee (kein Wortspiel beabsichtigt!) In Treaps ist die Verwendung von Schlüsseln, die randomisiert sind. Wenn Sie die Schlüssel entfernen, sehe ich nicht, wie Sie einen Treap haben können: vielleicht habe ich Ihre Frage missverstanden. Oder Sie beziehen sich auf die Alternative zu Treaps, die randomisierten binären Suchbaum. Beide Datenstrukturen verwenden die gleiche Idee, mit der Sie die Komplexität im Durchschnitt erreichen können, indem Sie sicherstellen, dass Ihr Baum wie ein durchschnittlicher Baum aussieht (anstelle eines pathologischen Falls).

Mit den Treaps tun Sie dies mit zufälligen Prioritäten und Balancing.

Bei zufälligen Binärbäumen wird die Zufälligkeit nur während der Konstruktion berücksichtigt: Wenn Sie also einen Knoten in Baum T einfügen, hat er die Wahrscheinlichkeit 1/(Größe (T) + 1) an der Wurzel Größe (T) ist die Anzahl der Knoten von T; Wenn der Knoten nicht im Stammverzeichnis eingefügt wird, wird der Vorgang rekursiv fortgesetzt, bis er hinzugefügt wird. (Siehe Artikel mein C. Martinez für eine detaillierte Studie dieser Bäume.)

Diese Datenstruktur verhält sich genau wie ein Treap, aber verwendet einen anderen Mechanismus, der keine Schlüssel erfordert.

Wenn dies nicht das war, wonach Sie suchen, könnten Sie vielleicht einige zusätzliche Informationen teilen: Hat Ihr Dozent jemanden erwähnt, der an dieser Struktur gearbeitet haben könnte, wo haben Sie diesen Dozenten und welche/Ihre Nationalität? Es mag nicht so aussehen, aber das Wissen über Ihre Muttersprache könnte ein wichtiger Hinweis sein, da Sie Algorithmen/Datenstrukturen in der Regel in ein bestimmtes Land eingliedern können, das sie hervorgebracht hat.

Answer 3

Ich glaube nicht, dass es einen Namen für diese Datenstruktur gibt, da es einfach eine Kombination von zwei orthogonalen Konzepten ist. Sie könnten implizite Schlüssel wie diese mit fast jeder selbstbalancierenden Baumdatenstruktur verwenden.

Sie können sich einen Blick auf die Sündenbockbäume werfen, da sie die Teilbaumgröße bereits für das Rebalancing verwenden und keinen Overhead pro Knoten benötigen.

Answer 4

Vielleicht suchen Sie nach einer Rope (komplexe Form der Zeichenkette), die auf Ihre Bedürfnisse für verzögerte Operationen modifiziert wurde. Interessant ist, dass es eine offene Frage bezüglich der Seile right here right now gibt.