Re: Balanced Tree

Luc The Perverse wrote:
"Chris Smith" <cdsmith@xxxxxxx> wrote in message news:MPG.1e64dd86e531d551989dba@xxxxxxxxxxxxxxxxxxx
Luc The Perverse <sll_noSpamlicious_z_XXX_m@xxxxxxxxxx> wrote:
I have become quite used to supported functions being the google top hit -
like if you search for messagedigest, the top result is java.sun.com/ . . .
In this case, you probably didn't find them because this isn't an
external API... it's part of the core API. Furthermore, most people are
far more interested in their functionality (implementing SortedSet and
SortedMap) than in the detail of their being implemented as a balanced
binary tree.

It's like Jeopardy then - I must ask the right question.

Let me try again:

Can you point me in the direction of a simple example of SortedSet or SortedMap - and tell me what the difference is between the two? (I found this http://java.sun.com/j2se/1.3/docs/api/java/util/SortedSet.html but it's not really satisfying my need for an example) I would like one such that the complexity of an add and the complexity of a search never exceed log N and the items can be extracted in order. An extra bonus, though not completely necessary would be an optimized implementation of an "add if not found" function which would search for a matching entry, and insert the object if not found (if found, the object could be manipulated such as a counter being incremented, or the object's flag method invoked so it can be dealt with later) However this is not a must.

In C++ I would have used a Red Black tree for this sort of thing. I'm kind new to the whole idea of things already being put together for me in an easy to use manner. (And I never considered STL as easy to use)

You might want to take a look at the library called MultiTreeMap or others in the list:

http://www.manageability.org/blog/stuff/open-source-java-data-structures-and-algorithms/view

/tom
.