Rank Tree in C++

Question

We need ADT having search and rank features. That is, in addition to the interface of STL map, a function 'int get_rank(key)' is required.

Standard implementation of such function requires supporting and updating an extra integer field in every node of self-balanced searching tree (e.g., in black-red tree, used in STL map/set). But it seems, STL map/set do not do this.

We're looking for a solution based on standard containers (STL, Boost) having the best possible Time Complexity: finding/adding/erasing an element take O(log n) (like in STL map/set), computing the rank by a key takes also O(log n).

By the rank of an element, we mean the position of the element in the sorted sequence of all the elements of the map/set.

Example. set = {0, 4, 6, 7, 8} rank(0)=1, rank(4)=2, rank(6)=3, rank(7)=4, rank(8)=5.

In our opinion, under Time Complexity constrains above, the problem cannot be solved by a combination of two maps one sorting by key and other sorting by rank.

Thanks.

Survey

The complexities of search, insert and delete are often inversely related to each other. We can't decide which trade-off is best for you. – Weariless

There is an implementation of rank tree satisfying all the time complexity constrains, see, e.g., the book of Cormen, T.H. "Introduction to Algorithms". – Survey

It can be done with GNU extension in the libstdc++, see here. – Betatron

Answer 1

The rank of the given key K is the number of keys which are less or equal to K.

E.g., let set s = {1, 3, 4, 6, 9}. Then rank(1) = 1, rank(4) = 3, rank(9) = 5.

The STL function distance() can be used for computing the rank of an element x appearing in the set s.

rank = distance(s.begin(), s.find(x));

The problem is that its time complexity is O(n).

Note that proposed two maps (or sets) indexed by key and by rank is not correct solution. The problem is that a change of one element affects ranks of many others. E.g., adding element 0 to the set s above change the ranks of all existing elements: s' = {0, 1, 3, 4, 6, 9}. rank(1) = 2, rank(4) = 4, rank(9) = 6.

Thanks.

Survey

Answer 2

I've implemented a "ranked red-black tree" which is similar to a red-black tree except each node stores the distance from the node that precedes it via an in-order traversal, rather than storing a key.

This does exactly what you want, except the "rank" of the first node is 0 and not 1 (you can add/subtract 1 if needed).

My solution is PUBLIC DOMAIN and is based on a public domain tutorial for a regular red-black tree. All operations -- including insert, remove, find, and determine rank have logarithmic time with respect to the number of elements in the data structure.

You can find it here: http://code.google.com/p/options/downloads/list

You should get the latest version from the above link, currently (as of this writing) rrb_v4_release.cpp.

Lockridge

Answer 3

you can use some other map like containers .
keep a size fields can make binary search tree easy to random access .
here is my implementation ...
std style , random access iterator ...
size balanced tree ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
and B+tree ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h

Carilla

Nice library. But why not provide some notes in English? – Subbasement

I have a question. You have 2 specializations for sbtree: multimap and multiset. What about a regular map and set? Overall, a very useful classes, Cheers) Was looking for a while something like that. Can't see a reason why standard libs do not have weigh-balanced containers in them. – Subbasement

one of my other project need a rank supported multimap ... i public it after that ... – Pilsner

Answer 4

I would suppose that by rank you actually mean the distance from the root, since if it could be stored contiguously with the value you would not have to go to such length.

I think you could do it "externally", since in this case the rank can be extrapolated from the number of times the comparison predicate is used...

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

It counts the number of tests, but since std::map stops testing as soon as it gets the right key... it should be alright :) Though there is probably some offset to deduce there (1 or 2) to get the rank instead.

If you gave a better definition of rank I may work a bit more but I don't want to spend too much time in the wrong direction.

Aorangi