At what level is a given element in a Java TreeSet?

Question

Does anybody know a fast way to detect at what level a given element is in a TreeSet? By level, I mean the depth of this element in the tree, i.e. the number of its ancestors.

Background. I use Java's TreeSet class to store my elements. To compare two elements I need to compute some auxiliary information about them. I cannot store this auxiliary information for each element as it would take too much memory. On the other hand, if I regenerate the auxiliary information for each comparison, my program is too slow. When an element is inserted in the TreeSet, my current implementation computes the auxiliary information for the element it inserts and does not recompute it until the element has found its place in the TreeSet. Afterwards, the auxiliary information is discarded. To speed up my program, I would like to store the auxiliary information also for the top levels of the TreeSet, as they are involved in many comparisons. So, after comparing two nodes, I would like to decide whether to keep or discard their auxiliary information based on their depth in the TreeSet.

Update. I would also be grateful if somebody could suggest an alternate class implementing some kind of balanced trees (AVL trees, red/black trees, Splay trees, ...), and where one has access to the height of an element.

Answer 1

The exact depth of each node is simply not exposed by a TreeSet. You'd have to write your own if this is how you want to do it.

You might be able to do something like have each key in the set refer to a shared object that manages the auxiliary information. Each time compareTo() is invoked on a key, it would notify the manager to update its counter for that key. The manager would use these stats to decide which should maintain their auxiliary information.