Wir brauchen ADT mit Such- und Rangfunktionen. Das heißt, zusätzlich zu der Schnittstelle der STL-Map ist eine Funktion 'int get_rank (key)' erforderlich.
Die Standardimplementierung einer solchen Funktion erfordert das Unterstützen und Aktualisieren eines extra ganzzahligen Felds in jedem Knoten des selbstausgeglichenen Suchbaums (z. B. in einem schwarz-roten Baum, der in der STL-Karte / dem AWL-Satz verwendet wird). Aber es scheint, STL map / set macht das nicht.
Wir suchen nach einer Lösung basierend auf Standardcontainern (STL, Boost) mit der bestmöglichen Zeitkomplexität: das Finden / Hinzufügen / Löschen eines Elements nehme O (log n) (wie in STL map / set), das Berechnen des Rangs durch einen Schlüssel erfordert auch O (log n).
Mit dem Rang eines Elements meinen wir die Position des Elements in der sortierten Reihenfolge aller Elemente der Karte / Menge.
Beispiel. set = {0, 4, 6, 7, 8} Rang (0) = 1, Rang (4) = 2, Rang (6) = 3, Rang (7) = 4, Rang (8) = 5.
Unserer Meinung nach kann das Problem unter den oben genannten Einschränkungen der Zeitkomplexität nicht durch eine Kombination von zwei Karten gelöst werden, wobei eine nach Schlüssel sortiert und die andere nach Rang sortiert wird.
Danke.
Der Rang des gegebenen Schlüssels K ist die Anzahl der Schlüssel, die kleiner oder gleich K sind.
Z. B. setze s = {1, 3, 4, 6, 9}. Dann Rang (1) = 1, Rang (4) = 3, Rang (9) = 5.
Die STL-Funktion distance () kann verwendet werden, um den Rang eines Elements x in der Menge s zu berechnen.
rank = Abstand (s.begin (), s.find (x));
Das Problem ist, dass seine Zeitkomplexität O (n) ist.
Beachten Sie, dass die vorgeschlagenen zwei Maps (oder Mengen), die nach Schlüssel und Rang indiziert sind, keine korrekte Lösung darstellen. Das Problem ist, dass eine Änderung eines Elements die Ränge vieler anderer beeinflusst. Z. B. das Hinzufügen von Element 0 zu der obigen Menge ändert die Ränge aller existierenden Elemente: s '= {0, 1, 3, 4, 6, 9}. Rang (1) = 2, Rang (4) = 4, Rang (9) = 6.
Danke.
Ich habe einen "rangierten Rot-Schwarz-Baum" implementiert, der einem Rot-Schwarz-Baum ähnelt, außer dass jeder Knoten die Entfernung von dem Knoten speichert, der ihm vorangeht, anstatt einen Schlüssel zu speichern / p>
Dies macht genau das, was Sie wollen, außer dass der "Rang" des ersten Knotens 0 und nicht 1 ist (Sie können 1 hinzufügen / subtrahieren, falls nötig).
Meine Lösung ist PUBLIC DOMAIN und basiert auf einem öffentlichen Lernprogramm für einen regulären rot-schwarzen Baum. Alle Operationen - einschließlich Einfügen, Entfernen, Suchen und Bestimmen des Rangs - haben eine logarithmische Zeit in Bezug auf die Anzahl der Elemente in der Datenstruktur.
Sie können es hier finden: Ссылка
Sie sollten die neueste Version von dem obigen Link, derzeit (zum jetzigen Zeitpunkt) rrb_v4_release.cpp.
Ich nehme an, dass Sie mit rank eigentlich die Entfernung von der Wurzel meinen, denn wenn sie zusammenhängend mit dem Wert gespeichert werden könnte, müssten Sie nicht auf eine solche Länge gehen.
Ich denke, Sie könnten es "extern" machen, da in diesem Fall der Rang aus der Anzahl der Male, die das Vergleichsprädikat verwendet wird, extrapoliert werden kann ...
%Vor% Es zählt die Anzahl der Tests, aber da std::map den Test beendet, sobald es den richtigen Schlüssel bekommt ... sollte es in Ordnung sein :) Obwohl es wahrscheinlich etwas Offset gibt, um daraus abzuleiten (1 oder 2) der Rang stattdessen.
Wenn Sie rank besser definieren, mag ich vielleicht etwas mehr arbeiten, aber ich möchte nicht zu viel Zeit in die falsche Richtung verbringen.
Tags und Links c++ stl boost tree multiway-tree