Getting closest element from a TreeSet

[Joco Kedves]

I need to have a data structure storing integers which can be added or removed in n*log n time. A TreeSet would be just fine for this purpose, but most of the time I do not know the exact element I wan to find. I just know that I need either the number 5, or if 5 is not present, then I need the closest number which is greater then 5 (6,7, whatever, depending on the contents of the data structure). This is not a major difference if I would write the tree structure myself, but can I somehow avoid doing that? Is there a possiblity to use TreeSet in this way, or maybe some other class?

[Joco Kedves]

Instead of "n*log n" I meant "log n". Sorry.

[Jim Yingst]

<pre>
public Object getBestMatch(SortedSet set, Object item)
{
if (set.contains(item))
return item;
Set tail = set.tailSet();
if (tail.isEmpty())
return null;
return tail.first();
}
</pre>

[Joco Kedves]

Dear Jim!
First of all, thanks for your reply. But assuming that you meant to type this code:
public Object getBestMatch(SortedSet set, Object item){
if (set.contains(item))
return item;
SortedSet tail = set.tailSet(item);
if (tail.isEmpty())
return null;
return tail.first();
}
How do we know the cost of getting the "tailset" of our set. Can you explain why do you think that it is log n (where n means the number of elements stored in the sorted set)?

[Peter den Haan]

Originally posted by Joco Kedves:
How do we know the cost of getting the "tailset" of our set. Can you explain why do you think that it is log n (where n means the number of elements stored in the sorted set)?

There are two steps to the algorithm given.

• Create the tailSet. This is an O(1) operation, as the tailSet is no more than a view on the underlying Set (simply examine the source code of TreeMap, which backs the set, if you want to confirm this).
• Find the first entry in the tailSet. This is done using tree traversal which takes O(log(n)) (examine TreeMap.getCeilEntry()).

- Peter

[Jim Yingst]

> assuming that you meant to type this code...
Oops. Yes, I meant SortedSet rather than Set. Thanks Peter for the followup.

[Roseanne Zhang]

This is a smart student to ask his homework assignment question with his/her own thinking, and got his answer back.
In contrast of some students just throwing his/her teacher's assignment here, I actually have no objections on this one.

---

JavaChina has been moved to http://javachina.developergroup.org/

[Joco Kedves]

Thanks everybody for the answers.
To Peter:
I certainly will need to look at the source code of TreeMap, because I need to confirm this thing.
To Rosanne:
No, Rosanne, this is not a student assignment. I am a mathematician, who is trying to write a little program as a demonstration of an algorithm which he invented with some collegues. He decided to write the code in JAVA and got a JAVA 1.1 book from the library, although he never wrote anything in that language before. To tell the truth, since he left the university (which was quite a few years ago) he never wrote anything in any language. So he did his little program, but then did not want to write a search tree "by hand", but did not know how to figure out what this TreeSet class does. So he posed a question here. (Maybe it should have been put in the "beginner" section?)
Thanks again anyway.

[Joco Kedves]

One more thing to Rosanne:
My question was not about finding the colsest match in a TreeSet, but more like "is it possible to find the closest match using TreeSet and its methods in log n time, and if so, how." Since still I do not understand what "no more than a view on the underlying set" (as Peter put it) means, I am still not convinced, but I see that people here believe that tailSet() is an O(1) operation, which is very promising. I am very happy with it as an answer, now all I have to do is look at the souce to make suru. All the best.

[Roseanne Zhang]

Sorry for misconception.
It did look like a student hw assignment to me since I was/still is a teacher to certain extent.
As to big O, Peter's answer is correct if you look into the source code. For TreeSet

1) set.contains(item)       O(lg(n))
2) tail = set.tailSet(item) O(1)
3) tail.first()             O(lg(n))
4) Over all                 O(lg(n))

A little surprising on 2) and 3) if you do not look at the code.
Roseanne

[Peter den Haan]

Small clarification: tailSet(), headSet() and subSet() return very small objects that delegate all the hard work to methods of the underlying set. No new set is constructed. Hence O(1) and pretty insignificant.
- Peter

[Joco Kedves]

Originally posted by Roseanne Zhang:

1) set.contains(item)       O(lg(n))
2) tail = set.tailSet(item) O(1)
3) tail.first()             O(lg(n))
4) Over all                 O(lg(n))

A little surprising on 2) and 3) if you do not look at the code.
Roseanne
[/B]

Yes, 2) seems surprising.

[Joco Kedves]

I have come back here just to tell you what I have learned from the source of TreeMap and TreeSet (which is probably wasting our resources, but I want you to know that your answers really helped).
I found out that a "tailset" is basically only a value where the tailset is "started", so creating a tailset is really an O(1) operation. Then getting the first element of the tailset is just looking for the element which is equal to this starting value of the tailset, or if no such element exists, then looking for the least element which is greater than the starting value. And exactly this is done (of course in log n time) by a method of TreeMap called getCeilEntry(...).
Thanks again for your answers.