Joco Kedves

Greenhorn

Posts: 7

posted 15 years ago

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?

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

Joco Kedves

Greenhorn

Posts: 7

posted 15 years ago

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)?

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

author

Ranch Hand

Ranch Hand

Posts: 3252

posted 15 years ago

There are two steps to the algorithm given.

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

Wanderer

Sheriff

Sheriff

Posts: 18671

Roseanne Zhang

Ranch Hand

Posts: 1953

posted 15 years ago

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.

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

Greenhorn

Posts: 7

posted 15 years ago

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.

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

Greenhorn

Posts: 7

posted 15 years ago

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

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

Ranch Hand

Posts: 1953

posted 15 years ago

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

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

Roseanne

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

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

Roseanne

Peter den Haan

author

Ranch Hand

Ranch Hand

Posts: 3252

Joco Kedves

Greenhorn

Posts: 7

Joco Kedves

Greenhorn

Posts: 7

posted 15 years ago

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.

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.