How to find the index of an element in a TreeSet?

java algorithm data-structures treeset sortedset
jtbandes picture jtbandes · Oct 27, 2011 · Viewed 43.1k times · Source

I'm using a TreeSet<Integer> and I'd quite simply like to find the index of a number in the set. Is there a nice way to do this that actually makes use of the O(log(n)) complexity of binary trees?

(If not, what should I do, and does anyone know why not? I'm curious why such a class would be included in Java without something like a search function.)

Answer

jtbandes picture jtbandes · Oct 27, 2011

I poked around TreeSet and its interfaces for a while, and the best way I found to get the index of an element is:

set.headSet(element).size()

headSet(element) returns the sub-TreeSet of elements less than its argument, so the size of this set will be the index of the element in question. A strange solution indeed.

Related questions

How to return the k-th element in TreeSet in Java?

Maybe I am not using the right data structure. I need to use a set, but also want to efficiently return the k-th smallest element. Can TreeSet in Java do this? There seems no built-in method of TreeSet to do …

Read More
Computational Complexity of TreeSet methods in Java

Is the computational complexity of TreeSet methods in Java, same as that of an AVLTree? Specifically, I want to know the computational complexity of the following methods: 1.add 2.remove 3.first 4.last 5. floor 6. higher Java Doc for method description: http://docs.…

Read More
How to detect a loop in a linked list?

Say you have a linked list structure in Java. It's made up of Nodes: class Node { Node next; // some user data } and each Node points to the next node, except for the last Node, which has null for next. Say …

Read More