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.

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.

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.

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