Balanced Tree

java-programmer, Balanced Tree I was wondering if there were a built in (or freely available) library for
handling balanced trees.

I find many projects use them or could benefit from them.

:)

java-programmer >> Balanced Tree Luc The Perverse wrote:

> I was wondering if there were a built in (or freely available) library for
> handling balanced trees.

Might help if you could say in what way(s) java.util.TreeMap doesn't meet your
requirements.

-- chris

java-programmer >> Balanced Tree Well, if you want to use the tree for something other then just being a
tree, java.util.TreeMap and TreeSet provides Red-Black Trees. They are
not very tuneable, but work just fine for many applications.

java-programmer >> Balanced Tree "Chris Uppal" <email***@***.com> wrote in message
news:43fa1fb1$0$1175$email***@***.com...
> Luc The Perverse wrote:
>
>> I was wondering if there were a built in (or freely available) library
>> for
>> handling balanced trees.
>
> Might help if you could say in what way(s) java.util.TreeMap doesn't meet
> your
> requirements.

Hmm nothing in my requirements - just that they don't appear in the top 5
results in the google search "balanced tree java" - I will have to look
into them!

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/ . . .

:)

java-programmer >> Balanced Tree Luc The Perverse <email***@***.com> 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.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

java-programmer >> Balanced Tree "Chris Smith" <email***@***.com> wrote in message
news:email***@***.com...
> Luc The Perverse <email***@***.com> 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)

:)

java-programmer >> Balanced Tree Luc The Perverse wrote:
> "Chris Smith" <email***@***.com> wrote in message
> news:email***@***.com...
>
>>Luc The Perverse <email***@***.com> 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)
>
> --
> LTP
>
> :)
>
>
Java TreeMap is a RedBlack tree.

A Set is just keys, a Map is key value pairs.

java-programmer >> Balanced Tree Luc The Perverse wrote:
> "Chris Smith" <email***@***.com> wrote in message
> news:email***@***.com...
>> Luc The Perverse <email***@***.com> 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

java-programmer >> Balanced Tree Luc The Perverse wrote:

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

SortedSet and SortedMap are just interfaces that define behaviour that is the
same as that of any other object that implements Set or Map, with the single
additional constraint that iterating over the elements or keys will take them
in sorted order (plus a couple of other methods to take advantage of the
additional structure the ordering provides).

> 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.

java.util.TreeMap is a concrete implementation of the SortedMap interface which
provides those guarantees.

> An extra bonus [...snipped...] However this is not a must.

java.util.TreeMap doesn't provide that.

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

Maybe it would help to review the overview and tutorial at:
http://java.sun.com/j2se/1.5.0/docs/guide/collections/index.html

-- chris