Balanced Tree

[Luc The Perverse]

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.

 

[Chris Uppal]

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

 

[Stefan Schulz]

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.

 

[Luc The Perverse]

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

 

[Chris Smith]

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

 

[Luc The Perverse]

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)

 

[Wibble]

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 TreeMap is a RedBlack tree.

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

 

[tom fredriksen]

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

 

[Chris Uppal]

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