Hello everyone ,
I need to use a balanced tree implementation which supports retrieve rank of a given entry in O ( log n ) time . Currently the way I see to do this would be to use TreeSet which is a red-black tree implementation . Then call headMap() method of the given entry which runs in O(1) and then call size() method on the headMap() received which takes O(size of head map) time ( hence linear ) . I need to be able to do this in log(N) . Obviously it is possible to implement a tree on my own which takes care of rank issue also . Such balanced trees which support rank queries in O ( log N ) are called order statistic trees . My question is doesn’t there exist something in the JAVA API itself which can help me do this .
2 Likes
@everyone : Figured out the answer . There is no default implementation in java library for this . I had to modify Java’s TreeSet or TreeMap class to contain an extra field and extra function for implementing an order-statistic tree . Got the AC in contest timings itself . Cool 
Hey , some people were asking me a link to the implementation .
Here is the solution which uses it .
CodeChef: Practical coding for everyone ( Solution Page )
CodeChef: Practical coding for everyone ( Related Problem Page , problem figured in Feb 2013 contest ) .
Here you can find the class MyTreeMap as an inner class which is an implementation of order-statistic tree in Java .
1 Like
I added a couple methods to vinnetpaliwal’s code to look up the element at rank i and output all the keys to an array.
public K getKeyForRank(int i) {
Entry<K, V> e = root;
for (;;) {
int leftSize = e.left == null ? 0 : e.left.size;
if (leftSize <= i) {
i -= leftSize;
if (i > 0) {
i--;
e = e.right;
} else
break;
} else
e = e.left;
}
return e.key;
}
public K[] keysToArray(K[] a) {
if (a.length < size)
a = (K[]) java.lang.reflect.Array.newInstance(a.getClass()
.getComponentType(), size);
addToArray(root, a, 0);
return a;
}
private void addToArray(Entry<K, V> e, K[] a, int i) {
if (e == null)
return;
addToArray(e.left, a, i);
int leftSize = e.left == null ? 0 : e.left.size;
a[i + leftSize] = e.key;
addToArray(e.right, a, i + leftSize + 1);
}I was also looking for order statistic tree implementation in java. In case someone wants to refer I found a neat implementation here
1 Like