Java: balanced binary search tree

Question

Given my recent (somewhat successful) question:

Algorithmic issue: determining "user sessions"

I'm pretty sure that the way to solve it cleanly is to use a balanced binary tree (which would give an n log m solution to the problem, where thankfully the m is going to be quite small, even tiny, compared to the n), like hinted by one of the answer (answer which comes with some pseudo-code).

My question is simple: does the default Java API have a self-balancing tree?

If not, do you know of any implementation of such a tree (Apache, Google collections, anything)?

If nothing looks suitable, what would be the best tree to start with to implement such a balanced binary tree?

Nikita Rybak · Accepted Answer · 2010-08-02 19:03:58Z

4

java.util.TreeSet is a balanced tree implementation. It guarantees O(logn) access time by modifying tree structure when necessary, so it won't degenerate into a list.

The main question is: what operations you need from that tree and if TreeSet supports them.

answered Aug 2, 2010 at 19:03

Nikita Rybak

68.2k22 gold badges163 silver badges183 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java: balanced binary search tree

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related