Treap mit impliziten Schlüssel

Question

Es gibt eine Datenstruktur namens Treap. Das ist eine randomisierte binärer Suchbaum, der auf zufällig erzeugte so genannte „Prioritäten“ auch ein Haufen ist

Es gibt eine Variation dieser Struktur, bei denen Schlüssel implizit sind, werden sie in dem Baum nicht gespeichert, sondern wir den geordneten Index des Knotens in dem Baum als dieses Knotens Schlüssel betrachten. Wir brauchen statt Schlüssel in jeder Knotengröße von Unterstruktur zu speichern. Diese Technik ermöglicht es uns, über Treap wie eine Art von Array zu denken, die viel Betrieb in O (log N) Zeit unterstützt. Einfügen, Löschen, Reversion von Subarray, Ändern auf Intervall und so weiter

weiß, dass ich ein wenig über diese Struktur, aber nicht so viel. Ich habe versucht, es zu googeln, aber ich habe nur viele Artikel über Treap selbst, aber nichts über diese „implizite Treap“ / „indizierte Liste“ gefunden. Ich selbst weiß nicht, seinen Namen, weil meine Muttersprache nicht Englisch ist und Vortrags Ich habe die native Begriff der Struktur verwendet Mithören nicht englischen Original Begriff. Dieser native Begriff kann direkt auf Englisch als „Treap auf den impliziten Tasten“ oder „cartesianischen Baum auf den impliziten Tasten“ übersetzt werden.

Kann jemand Punkt mich auf den Artikel über diese Struktur oder sagen Sie mir ihren ursprünglichen Namen? Danke.

P. S. Sorry, wenn mein Englisch ist nicht verständlich genug.

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

Betrachten wir eine übliche Treap mit zufällig gewählten Prioritäten und Schlüssel, die im Baum gespeichert eigentlichen Nutzdaten sind. Dann lassen Sie sich vorstellen, dass wir eine andere Benutzerinformation in jedem Knoten gespeichert sind, und Tasten sind nichts anderes als die Suchschlüssel. Der nächste Schritt ist die Berechnung und in jedem Knoten die Unterstruktur Größe beibehalten: wir diesen Parameter nach jedem Merge / Split / Hinzufügen / Entfernen aktualisieren, aber es erlaubt uns zu finden, beispielsweise K-ten Element des Baumes in O (log N) Zeit.

Wenn wir Teilbaum Größen in jedem Knoten haben, können wir Schlüssel wegwerfen und dass Treap vorstellen, stellt eine Reihe von Benutzerdaten in Inorder Traversal. Array-Index jedes Elements kann leicht von Teilbaum Größen berechnet werden. alle in O (log N) Zeit

- Jetzt können wir ein Element in der Mitte der Array oder teilen dieses Array hinzufügen / entfernen.

Wir können auch „multiple“ Betrieb machen - zum Beispiel einen konstanten Wert für alle Elemente unserer „Array“ hinzufügen. Um dies umzusetzen, müssen wir diese Operation machen verzögert, fügen Sie einen Parameter in jedem Knoten, der eine verzögerte Konstante darstellt, die „später“ hinzugefügt, um alle Elemente der dieses Knotens Subarray zu sein hat, und „Push“ die Änderungen von oben nach unten als notwendig. Hinzufügen einer Konstante Subarray oder Malerei (Markierung) der Sub-Array kann auf diese Weise verzögert vorgenommen werden, da die Umkehrung der Sub-Array (hier die verzögerten Informationen in dem Knoten in der Bit „Sub-Array umgekehrt werden muss“), und so weiter.

UPD2: Hier Code-Schnipsel - Stück der geringen Menge an Informationen habe ich gefunden. Merke nicht kyrillisch :) Words "? ??????? ??????" bedeutet in direkter Übersetzung "mit impliziten Schlüsseln".

Answer 1

Sie können diese Datenstruktur in dem Papier von Kaplan und Verbin finden auf unterzeichnet Permutationen von Umkehrungen Sortierung (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 Schlüssel zu verwenden, die randomisiert werden. Wenn Sie die Tasten entfernen, sehe ich nicht, wie man eine Treap hat: so vielleicht falsch verstehe ich Ihre Frage. Oder vielleicht sind Sie auf die Alternative zu treaps Bezug genommen wird, die randomisierten binären Suchbaum . Beide Datenstrukturen verwenden, um die gleiche Idee, dass Sie sicherstellen, dass Ihr Baum sieht aus wie ein durchschnittlicher Baum (anstelle eines pathologischen Fall) durchschnittlichen Fall Komplexität erreichen kann.

Mit dem treaps, Sie tun dies zufällige Prioritäten mit und ausgleichend.

Mit randomisierten Binärbäumen wird die Zufälligkeit allein beim Bau einbezogen: Das heißt, wenn Sie Einsatz einen Knoten im Baum T, hat es Wahrscheinlichkeit 1 / (Größe (T) + 1) an der Wurzel zu sein, bei denen der Größe (T) die Anzahl der Knoten von T; und natürlich, wenn der Knoten nicht an der Wurzel eingefügt wird, fahren Sie rekursiv, bis er hinzugefügt wird. (Siehe Artikel meiner C. Martinez für eine detaillierte Untersuchung dieser Bäume.)

Diese Datenstruktur verhält sich genau wie ein Treap, sondern verwendet einen anderen Mechanismus, den Schlüssel nicht erforderlich.

Wenn dies nicht das, was Sie suchen, könnten Sie vielleicht einige zusätzliche Informationen teilen: hat Ihren Dozenten Erwähnung jeder, der auf dieser Struktur gearbeitet haben könnte, wo man hier tat diesen Dozenten und was seine / Ihre Nationalität. Es ist vielleicht nicht, wie es scheint, aber Ihre Muttersprache zu wissen, könnte einen wichtigen Hinweis, wie Sie in der Regel Algorithmen festflocken können / Datenstrukturen zu einem bestimmten Land, das sie ihren Ursprung.

Answer 3

Vielleicht suchen Sie einen Rope (komplexe Form von string) für verzögerte Betrieb auf Ihre Bedürfnisse angepasst. Interessant ist, dass es eine offene Frage ist, in Bezug auf Seile .

Answer 4

Ich glaube nicht, dass es ein Name für diese Datenstruktur ist, da es einfach eine Kombination von zwei orthogonalen Konzepten ist. Sie könnten mit fast jedem selbst ausgleichBaumDatenStruktur wie diese impliziten Schlüssel verwenden.

Sie vielleicht einen Blick auf Sündenbock Bäume nehmen wollen, da sie den Teilbaum Größe bereits für Rebalancing verwenden und benötigen keine pro-Knoten-Overhead.