2

I"ve coded a Red Black binary statistic tree to get the rank of an arbitrary object that is comparable to the other objects in the Red Black tree. I wonder if there is an API class that provides the same functionality.

It would also be nice if given a rank, the class has a function to return an object of that rank within the tree.

Note that the Red-black BST allows these two operations in log(n) time where n is the number of objects in the tree.

fodon
  • 4,565
  • 12
  • 44
  • 58
  • 2
    You mean you implemented an order statistic tree? I don't think those are in the Java stdlib. – Fred Foo Jul 15 '13 at 15:13
  • java.util.TreeSet uses a red-black tree implemented by a java.util.TreeMap. http://en.wikipedia.org/wiki/Java_collections_framework – sara Jul 15 '13 at 15:13
  • How do people normally rank objects in a dynamically formed data structure such as a tree? – fodon Jul 15 '13 at 16:14

3 Answers3

4

The standard API doesn't have an order statistic tree. TreeMap in particular doesn't have methods for finding the rank of a key, or finding a key by rank in O(log n) time.

It doesn't look like usual add-on libraries (Apache Commons Collections, Google Guava) have an order statistic tree, either.

Joni
  • 108,737
  • 14
  • 143
  • 193
4

Check out http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html.

Prof. Sedgewick named the trees as RedBlack, so, most probably, it's a correct implementation of RedBlack BSTs. It has rank too (running in O(lgN)). (I would not risk writing my own version if it supports deletion). That's at least a good reference. (Not in java.util alas)

Maria Sakharova
  • 1,389
  • 15
  • 15
-1

Yes there is a TreeMap:

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

It would also be nice if given a rank, the class has a function to return an object of that rank within the tree.

The NavigableMap interface (implemented by TreeMap) offers methods such as floorKey and ceilingKey.

Community
  • 1
  • 1
assylias
  • 321,522
  • 82
  • 660
  • 783
  • 2
    Which of the problems I posed does this solve in log(n) time? – fodon Jul 15 '13 at 15:53
  • 1
    @fodon I had misunderstood your need. You could put the objects as keys and a dummy value. You can then call `map.headMap().size()` to get the rank (not sure if it is O(log(n))). But I'm not sure how you will get access to the n-th item with that methodology. – assylias Jul 15 '13 at 16:02
  • Yes, that is a good idea. It would be interesting to know if it is log(n) process to find size() of the headmap() – fodon Jul 15 '13 at 16:15
  • 6
    Just checked and it looks like size() is a O(n) process. It iterates through all elements in the subtree. Look at the AscendingSubMap class in TreeMap and see how it gets to size(). – fodon Jul 15 '13 at 16:36