Rangbaum in C++

Question

Wir brauchen ADT mit Such- und Rankingfunktionen. Das heißt, zusätzlich zur Schnittstelle der STL-Map ist eine Funktion "int get_rank(key)" erforderlich.

Die Standardimplementierung einer solchen Funktion erfordert die Unterstützung und Aktualisierung eines zusätzlichen Integer-Feldes in jedem Knoten des selbstbalancierten Suchbaums (z. B. im schwarz-roten Baum, der in STL map/set verwendet wird). Aber es scheint, dass STL map/set dies nicht tut.

Wir suchen eine Lösung, die auf Standard-Containern (STL, Boost) basiert und die bestmögliche Zeitkomplexität aufweist: Finden/Hinzufügen/Löschen eines Elements dauert O(log n) (wie in STL map/set), die Berechnung des Rangs durch einen Schlüssel dauert ebenfalls O(log n).

Unter dem Rang eines Elements versteht man die Position des Elements in der sortierten Folge aller Elemente der Karte/Menge.

Beispiel. Menge = {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 Zeitkomplexitätsbedingungen nicht durch eine Kombination von zwei Karten gelöst werden, von denen eine nach dem Schlüssel und die andere nach dem Rang sortiert ist.

Merci.

Answer 1

Der Rang des gegebenen Schlüssels K ist die Anzahl der Schlüssel, die kleiner oder gleich K sind.

Zum Beispiel sei die Menge s = {1, 3, 4, 6, 9}. Dann ist 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 = distance(s.begin(), s.find(x));

Das Problem ist, dass die Zeitkomplexität O(n) beträgt.

Beachten Sie, dass die vorgeschlagenen zwei Karten (oder Mengen), die nach Schlüssel und nach Rang indiziert sind, keine korrekte Lösung darstellen. Das Problem besteht darin, dass die Änderung eines Elements die Ränge vieler anderer Elemente beeinflusst. Wenn z. B. das Element 0 zur obigen Menge s hinzugefügt wird, ändern sich die Ränge aller vorhandenen Elemente: s' = {0, 1, 3, 4, 6, 9}. Rang(1) = 2, Rang(4) = 4, Rang(9) = 6.

Merci.

Answer 2

Ich habe einen "Rang-Rot-Schwarz-Baum" implementiert, der einem Rot-Schwarz-Baum ähnelt, mit dem Unterschied, dass jeder Knoten den Abstand zu dem Knoten speichert, der ihm durch ein in-order traversal vorausgeht, anstatt einen Schlüssel zu speichern.

Dies entspricht genau dem, was Sie wollen, außer dass der "Rang" des ersten Knotens 0 und nicht 1 ist (Sie können bei Bedarf 1 addieren/subtrahieren).

Meine Lösung ist PUBLIC DOMAIN und basiert auf einem Public-Domain-Tutorial für einen regulären Rot-Schwarz-Baum. Alle Operationen - einschließlich Einfügen, Entfernen, Suchen und Ermitteln des Rangs - haben logarithmische Zeit in Bezug auf die Anzahl der Elemente in der Datenstruktur.

Sie können es hier finden: http://code.google.com/p/options/downloads/list

Sie sollten die neueste Version über den obigen Link beziehen, derzeit (zum Zeitpunkt der Erstellung dieses Artikels) rrb_v4_release.cpp.

Answer 3

Sie können eine andere Karte wie Container verwenden.
halten eine Größe Felder können binäre Suchbaum leicht zu zufälligen Zugriff zu machen.
hier ist meine Umsetzung ...
std style , random access iterator ...
Größe ausgeglichener Baum ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
und B+tree ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h

Answer 4

Ich würde annehmen, dass durch rank Sie meinen eigentlich den Abstand zur Wurzel, denn wenn er zusammenhängend mit dem Wert gespeichert werden könnte, müssten Sie nicht so lange suchen.

Ich denke, man könnte es "extern" machen, da in diesem Fall der Rang aus der Anzahl der Verwendung des Vergleichsprädikats extrapoliert werden kann...

namespace detail
{
  template <class Comparator>
  class CounterComparator: Comparator
  {
  public:
    CounterComparator(size_t& counter):
        Comparator(), mCounter(&counter) {}
    CounterComparator(Comparator comp, size_t& counter):
        Comparator(comp), mCounter(&counter) {}

    template <class T, class U>
    bool operator()(T& lhs, U& rhs) const
    { 
      ++(*mCounter);
      return this->Comparator::operator()(lhs,rhs);
    }
  private:
    size_t* mCounter;
  };
} // namespace detail

template <
  class Key, 
  class Value, 
  class Cmp = std::less<Key>, 
  class Allocator = std::allocator< std::pair<const Key,Value> >
>
class SuperMap
{
  typedef detail::CounterComparator<Cmp> Comparator;
public:
  SuperMap(): mCounter(0), mData(Comparator(mCounter)) {}

  Value& operator[](const Key& key) { return mData[key]; }

  size_t rank(const Key& key) const
  { 
    mCounter = 0; mData.find(key); return mCounter;
  }

private:
  typedef std::map<Key,Value, Comparator, Allocator> data_type;

  mutable size_t mCounter;
  data_type mData;
}; // class SuperMap

int main(int argc, char* argv[])
{
  SuperMap<int,int> superMap;
  superMap[1] = 42;
  std::cout << superMap.rank(1) << std::endl;
}

// outputs
// 2

Sie zählt die Anzahl der Tests, aber da std::map hört auf zu testen, sobald es den richtigen Schlüssel hat... es sollte alles in Ordnung sein :) Obwohl es wahrscheinlich einige Offset abzuleiten gibt (1 oder 2), um den Rang stattdessen zu erhalten.

Wenn Sie eine bessere Definition von rank Vielleicht arbeite ich noch ein bisschen mehr, aber ich möchte nicht zu viel Zeit in die falsche Richtung investieren.